Proof Number Qango

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