Heuristics in Monte Carlo Go.
Peter D. Drake, Steve Uurtamo · 2007
Writing programs to play the classical Asian game of Go is considered one of the grand challenges of artificial intelligence. Traditional game tree search methods have failed to conquer Go because the search space is so vast and because static evaluation of board positions is extremely difficult. There has been considerable progress recently in using Monte Carlo sampling to select moves. This paper presents four heuristics used to bias the selection of moves during Monte Carlo sampling: the proximity heuristic (play near the last move), the avoid-the-first-two-lines heuristic (don't play at the edge of the board), the first-order history heuristic (play the move that has fared best elsewhere in the tree), and the second-order history heuristic (play the move that has fared best elsewhere in the tree in response to a particular move from the opponent). Experimental results show that the use of these heuristics significantly improves the ability of our program to defeat GNU Go, a widely-used Go program based on traditional, knowledge-intensive techniques.