Cracking GO

Can Monte Carlo Work on Go?

Some of the best Go programs today employ Monte Carlo ­methods, which play out move possibilities internally, in random games, then select the move with the best win/loss index. It can be considered a brute-force technique.

Monte Carlo has long been known to work reasonably for games of ”imperfect information” such as backgammon, in which the rolling of dice introduces an element of chance. The method is also a good option for games of perfect information that are too complex to crack by more straightforward means. Had it been applied to computer chess back in the 1950s, before today’s search algorithms were perfected, it might well have raised the standard of play.

Monte Carlo techniques have recently had success in Go played on a restricted 9-by-9 board. My hunch, however, is that they won’t play a significant role in creating a machine that can top the best human players in the 19-by-19 game. Even so, Monte Carlo is worth keeping in mind for games and gamelike computing challenges of truly daunting complexity.