Go is a classical strategic board game. It has very simple rules, with only two kinds of pieces, yet requires a depth of strategy similar to Chess. The computational problem of making optimal Go movies is computationally difficult. However, there is a simple randomized algorithm using Monte Carlo methods that seems to work well in practice:
- Enumerate all the liberties (legal moves)
- For each liberty, play out a random game where players take turns making completely random, but legal moves. Try k random trials, and keep track of the number of times w that the computer player wins.
- Choose the liberty with the highest win ratio w/k
This is a nice algorithm because it is simple, the player strength and running time can be tuned by adjusting the k parameter, it is embarrasingly parallel, and it seems to work well against human opponents. The basic algorithm has already been designed, implemented, and documented, but there is room for more work in this area.
Project: Implement a Monte-Carlo Go player. The project can be extended by parallelizing the algorithm, or by developing the player on a resource-constrained mobile device.