Dinkelhuber, a browser based 9x9 OGS Go Opening explorer with Katago support

https://raw.githubusercontent.com/yannikkellerde/dinkelhuber/master/images/site_preview.png

Check it out now

Dinkelhuber is a purely browser based 9x9 Go client and opening explorer that you can visit at go.yannikkeller.de.

Features

Opening explorer

In the tab on the right, you can explore over 400k OGS games, exploring the number of games, winrates for black and white and the average rating of the players of each move. By clicking on the cogwheel in the top-right, you can also filter the games for rules, komi or player strength. Below the moves on the right, you will find a list of top OGS games played in the line, which you can easily reach by clicking on them. Note that the ratings might not always perfectly match with the ones shown at OGS, but that's caused by the way OGS handles ratings and rating change.

Exploring OGS games

You can directly import OGS games to dinkelhuber. Just visit your game on OGS, copy the Game ID from the end of the URL, enter it into dinkelhuber's Game ID input field, hit enter, and the use the arrow keys to navigate through the game.

Running Katago

The browser go client can show engine lines in lizzie style. Of course, as I am not rich, I can't provide free katago analysis from my server, so you will have to run katago on your own machine. To get going, first make sure, that you have a working katago on a Linux machine (No Windows support yet). Then clone this repository. Navigate to python_server/gtp_socket_wrapper and create a folder katago where you put your katago executable as well as your default_gtp.cfg and default_model.bin.gz in. You will need Python 3 with the websock package installed pip3 install websock. Now start a terminal in python_server/gtp_socket_wrapper and run python3 websocket_server.py. In a browser navigate to go.yannikkeller.de and enter localhost:8030 into the GTP engine field and hit enter. If everything worked correctly, you should see engine evaluations plopping up on the board after a few seconds.

The neat thing about running katago via a websocket is that you can also access your katago instance remotely via your local network or even via the internet (If you have a good understanding of networking and sockets). To do this, you will need to edit the ip in server = WebSocketServer(ip="localhost", port=8030, in websocket_server.py to your machines network ip and then you can access it via this ip from your phone for example.

Acknowledgements

Thanks OGS for providing such a nice and easy game downloading api, without which dinkelhuber would not be possible.
Thanks to lichess the forever free and awesome chess platform, I got my opening explorer design from.
Thanks to kocsten for some awesome button designs.

Introduction

I was interested in solving the game Qango. Qango is a two player, zero sum, perfect knowlege game, which is equivalent to a bigger version of tic tac toe with different winning conditions. To solve the game I decided to use a proof-number search as the game includes a lot of forced variations. If you just wan't to check out the results, go to yannikkeller.de and get beaten down by the perfect ai. You can also just explore the winning moves here.

Rules of Qango

There are two different versions of Qango, the 6x6 version and the 7x7 version. My software focusses on solving the 6x6 version. Just like in tic tac toe, the players take alternating turns occupying squares until one of them achieves a winning pattern. Instead of marking them with X and O's, the players use white and black stones to mark theire squares. In Qango, there are the following winning patterns:

1. A 5 stone row, horizontally, vertically or diagonally
2. A 2x2 square
3. 3 contiguous squares of the same color (The Qango board is colored, click here to check out the color patterns)

As for advanced players, it becomes very obvious, that the game is winning for the first player in it's normal state, there is an additional Rule for advanced players called Burgregel. With this Rule, the first player isn't allowed to occupy the 4 squares in the center or the 4 squares in the 2-2 position in the first move (check out the black X-es in the beginning of the game when playing on yannikkeller.de).
A long time ago, I had already suspected, that the game would still be a first player win, even when using the Burgregel. In fact, I was able to finally proove it using this software.

Implementation

I implemented the Software in Python3, because Python is just such an easy to use high level language I love to use for just about any problem. Looking at it afterwards, I have to admit, that this was probably not the best decision to make. As Python is such a high level language, efficient working memory handeling is very hard in Python. As this is most limiting factor to the Proof-Number search, this is a real problem. In hindsight, it would probably have been a better choice to choose a lower level Language like C++.
To be real fast while going through the variations of the game, I implemented Qango in terms of bitwise operations. The position can be represented using two 64 bit integers, one for the first players Stone, the other for the second players Stones. The set bits in the integer then represent which squares have been occupied by that player. Finding out what moves are allowed in a position is then just a matter of or-ing two integers and then forming the complement.
When I then implemented the basic version of the Proof-Number search algorithm, I had to find out, that this was not even enough to solve the basic version of Qango. So I had to make the following improvements:

1. Make use of symetries and transpositions: As each Qango position can be represented in 8 symetrical ways and positions can be reached through multiple paths, it would be stupid not to make use of that. So I read this Paper and transformed my game tree into a directed acyclic graph.
2. Move ordering: In Qango, the squares in the center, are much more likely to be usefull to occupy, than the squares in the corner. So it was important to make sure, that when there is a tie in the Proof-Number of two nodes, the algorithm first checks out the move closer to the center.
3. **Deleting