Project Groups 2008-2009 - Kristen Ying

• Artificial Intelligence for Go (Kristen Ying)
  
       [Abstract] | [Project Blog]  | [Proposal] | [Final Report] | [Final Presentation]
  
  

Abstract

Computers have beaten pro human chess players through their superior computational ability. With the ancient board game Go, however, the sheer number of possibilities, as well as the subjective nature of what a more desirable board state is make it a more challenging problem. On February 7th, 2008, a computer finally beat a pro Go player , but with a 9-stone handicap on the human player, and with processing power over 1000 times that of Deep Blue.

Crazy Stone by Remi Coulom uses Monte-Carlo Tree Search and in 2006 began the current trend of using algorithms from this family. The Monte-Carlo method creates playouts, or played games with random (light playout) or heuristic-based (heavy playout) moves. Applied to game trees, each node keeps a win rate, remembering the number of playouts that were won from this position. As is often desirable in Go, such analysis favors the potential of winning, regardless of the potential margin by which the game may be won. Thus such algorithms may often result in winning by a small margin. Crazy Stone also utilizes pattern learning. The program MoGo, which received some early inspiration from Crazy Stone, made headlines when it defeated a pro player in a full-scale 19x19 game of Go on February 7th, 2008. The program uses the algorithm UTC (Upper Confidence bounds applied to Trees) for Monte-Carlo.

This project is an investigation into designing AI for the board game Go, Using a Monte Carlo Search Tree algorithm. The goal here is to create a program that is playable with limited computational resources, allowing it to be presented in the form of a console game. The end product should be a game on the XBox 360 which can be played by novice Go players.