The Monte Carlo Method for Game AI
The Monte Carlo method was first coined by Von Neumann in the 1940's.
Essentially, the computer tries randomly different simulations of the game in full from the current state. Each time, make a note of what the next move is and if we eventually win or not. Draw a statistical conclusion from this information and play the best move.
This works brilliantly for a game such as chess, but requires a lot more processing power for something such as go. Current computers (at the end of 2010 at the time of writing) simply cannot get through enough simulations to draw any meaningful conclusions. For instance there are billions of variations in just 3 moves of Go.
Essentially, the computer tries randomly different simulations of the game in full from the current state. Each time, make a note of what the next move is and if we eventually win or not. Draw a statistical conclusion from this information and play the best move.
This works brilliantly for a game such as chess, but requires a lot more processing power for something such as go. Current computers (at the end of 2010 at the time of writing) simply cannot get through enough simulations to draw any meaningful conclusions. For instance there are billions of variations in just 3 moves of Go.