Computers conquer the final frontier in board games

Go_board_part-thumb-150x150 Ewen Callaway in New Scientist. (Note, Monte Carlo simulations are hardly new. I think Fermi used them in the 1930s or 1940s.):

“A lot of people have thought of Go as the last bastion of human superiority over computers, at least as far as board games go,” Hearn said. “Previous to this no one would have imagined that a computer would be able to beat a professional.”

Go is played widely in Asia and holds a far more important position there than chess does in the West, said Elwyn Berlekamp, another mathematician who studies the game, based at the University of California in Berkeley.

The game is played by two players who place black and white stones on a 19-by-19 square board. Players alternate turns placing a stone on the board, and the goal is to encircle another player's stones to the point where she has no moves left.

Because there are about 10^171 possible games of Go, computers applying the same approach that has lead to their superiority in chess and checkers — mapping out every possible move at each point in a game — fail miserably, Hearn said. A chess game has 10^50 possibilities, a checkers game just 10^20.

However, a new mathematical approach called a Monte Carlo simulation has changed everything. In a Monte Carlo simulation a computer plays numerous random games of Go, but applies knowledge from previous games to future games. This allows the computer to rule out huge swaths of real estate on the Go board and concentrate its computing power on the best moves, Hearn said.

Professional Go players know their reign will soon end.