Wednesday, 11 March 2009

Artificial Intelligence GO-es Monte Carlo


Korean Go game (circa 1910-1920): [Wikipedia]

Go is a strategic board game (zero-sum game) between 2 players. Go originated in China (where it is also known as wéiqí) approximately 2,500 years ago. It has been estimated that the total possible number of games of Go is approximately 10171, many more configurations than there are elementary particles in the known universe.

Brandon Keim has published a very interesting article in Wired - Humans No Match for Go Bot Overlords (10th March 2009) - where he descibes the impact on the game Go of new Go computer programs using the Monte Carlo method of analysis.

The Monte Carlo method was first described by the Manhattan Project nuclear weapons physicists at the Los Alamos National Laboratory in the 1940s. The origin of the name appears to come from the casinos where some of the scientists gambled. The method has wide application for modeling phenomena where there is significant uncertainty, i.e. calculating risk in business. Keen chess players will be familiar with this approach as a Monte Carlo analysis feature is available in the recently launched Rybka3 chess engine (see Chessbase article).

So how can the Monte Carlo method possibly help in playing Go?

The secret appears to be patterns and probabilities emerging from random simulations of Go games repeated again and again and again. The statistical analysis performed on these countless millions of games of Go highlights useful patterns which can then be described in a mathematical probabilistic fashion. The Go programs can then devote more time to the promising branches identified. In the future these Monte Carlo based Go programs will be able to incorporate the results of previous analysis into their playing algorithms, so producing incremental improvements in skill level. Eventually, the best Go programs will beat the elite professional Go players, just as the best chess programs have done in chess.

Related Posts:
ALCHEssMIST - Hans Berliner – Reviewing The Go Versus Chess Quote:

No comments: