Go is an ancient board game, originating in China – where it is known as weiqi – before 600 B.C. It spread to Japan (where it is also known as Go), to Korea as baduk, and much more recently to Europe and America [American Go Association]. This game, in which players take turn placing stones on a 19×19 board in an attempt to capture territory, is polynomial-space hard [Reyzin]. Checkers is also polynomial-space hard, and is a solved problem [Schaeffer]. However, the sheer magnitude of options (and for intelligent algorithms, sheer number of possible strategies) makes it infeasible to create even passable novice AI with an exhaustive pure brute-force approach on modern hardware. The board is 19 x19, which, barring illegal moves, allows for about 10^171 possible ways to execute a game. This number is about 10^81 times greater than the believed number of elementary particles contained in the known universe [Keim].
Previously investigated approaches to creating AI for Go include human-like models such as pattern recognizers and machine learning [Burmeister and Wiles]. There are a number of challenges to these approaches, however, and they can be very sensitive to the designer’s perception of how one thinks during a game. Professional Go players seem to have a very intuitive sense of how to play, which is difficult to model. However, currently it seems the best algorithms are those from the Monte Carlo family, which attempt to develop order (in the form of a strategy) from the chaos of random game simulations. Programs such as Crazy Stone and MoGo have demonstrated the promise of these algorithms. It is expected that computer programs may outperform professional Go players within the next decade [Keim].
This project is an investigation into designing AI for the board game Go, using a Monte Carlo Search Tree algorithm. The general approach involves simulating games and creating a decision tree to represent the associated win rate for each possible move. Optimizations may be made by allocating more resources to investigating intelligent moves and more promising looking branches. The goal is to create a program that is playable with limited computational resources, allowing it to be capable of being presented in the form of a console game. The end product should be a game using XNA that has a two-human-player version and a human-versus-computer version.