Monte Carlo Artificial Intelligence for Go

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:

  1. Enumerate all the liberties (legal moves)
  2. 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.
  3. 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.

Advertisements


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s