This article discusses the pitfall I encountered while preparing for the coding competition. Before you continue to read this post, I recommend you to take a look at the rules of this game here (Wikipedia) and here for the hosting information.
I wanted to implement a tree based approach for the problem of playing this game successful. I also wanted to make use of the spare time while waiting on the opponents move. So at first I settled for a strategy where the program calculates all the time and only picks the best move when a request from the server comes in. So ideally the program should populate a tree with all possible combinations of turns by width (see picture below).
I quickly realized though that this would use a lot – and I mean a LOT – of ram. Just take a look at the following thoughts:
For the competition we decided to stick with the standard Go Board which is 19×19. Each position could either be blank, black or white. This means each position requires at least two bits to store the information. The permitted RAM of 1GB would therefor be able to hold ~11 million states not including any overhead. This number sounds very promising at first. At second glance you will see its far to little.
With an empty board there are 361 possible places where you can put your stone. It gets further complicated by the fact that each turn consists of two stones. This theoretically increases the possible turns to ~130 thousand possibilities. There is room for optimization though. It’s the same outcome of your turn no matter which stone gets placed first. Therefor the more accurate number would be ~65 thousand possibilities per turn. Now consider a tree which represents all possible turns with a depth/height of two. This tree would consist of roughly 4 billion states (65k * 65k) which already exceeds to 11 million states we can store in memory. This of course is only an estimate for an totally empty board. This number however will be as high until the very last moments of the game. Also this is only a tree with a depth of two which is not sufficient for a KI based on a algorithm which tests every combination.
Therefor I was forced to ditch the idea of saving every state inside a tree. It would still be an option to clean the tree since the worst turns will never be played. However this would complicate the program significantly. A more straight forward approach would be to visit each node by depth first.
This way we can delete each node as soon was every child was visited (which is quite easily done). The only thing we have to do is save the best performing turn we found. In a algorithm which stops at depth n we would at max store n states. On the other hand we loose the ability to calculate while waiting for the opponent because the tree may not be completed before a turn gets requested by the server. By this time we can’t be sure we found the best turn for a certain depth.
Don’t worry if you didn’t understand every word I wrote about this approach. Since I will continue this Dev-Log series there will be a lot more information available soon.
There are other algorithms we can use to program a tree based KI such as Monte-Carlo-tree-search. Those however rely on probability rather than testing each possibility. This algorithm also produces a valid answer at any time. This sounds very promising. However the first iteration of this KI will use the second approach because I already implemented it before for another game. But I’m very certain I will try the Monte-Carlo-tree-search on a later episode because it sounds very promising.
Signing off.
