Wired News: What makes programming go so much tougher than chess?Rémi Coulom: In Go, you don’t capture pieces, and so it’s very difficult to say that black is ahead or white is ahead just by looking at the board. In order to survive, a group of stones needs to surround two “eyes” — empty areas that can’t be invaded by the opponent.
On a 19-by-19(-line) board, you’ll have plenty of stones whose life or death status is undecided, and this is extremely difficult to analyze statically. This is different from the situation with chess or (checkers), where you can look at the board and say, “I have one more pawn than you.”
WN: What are “Monte Carlo” methods and how do they apply to Go?
Coulom: Monte Carlo methods are named after a quarter of Monaco that’s famous for its casinos. In the case of Go, the basic idea goes like this: To evaluate a potential move, you simulate thousands of random games. And if black tends to win more often than white, then you know that move is favorable to black.
WN: With 250 moves in a typical game, that must take a lot of computational power.
Coulom: The version of Crazy Stone in the Torino Olympiad ran on a four-CPU machine — two dual-core AMD Opterons at 2.2 GHz — and did about 50,000 random games per second. Unlike traditional algorithms, the Monte Carlo approach is extremely easy to parallelize, so it can take advantage of the multi-core architecture of the new generation of processors.
WN: Crazy Stone was not the first program to use Monte Carlo methods, but it was successful enough that it started a trend among Go programmers. What was your innovation?
Coulom: Because you can’t sample every possible random game, the Monte Carlo algorithm can easily fail to find the best moves. For instance, if most of the random games resulting from a certain move are losses, but one is a guaranteed win, the basic algorithm would take the average of those games and still evaluate it as a bad position.
Crazy Stone is clever enough to avoid this problem. When it notices that one sequence of moves looks better than the others, it tends to play it more often in the random games.