Games: Backgammon and Go

This chapter discusses a seemingly radical way to replace knowledge with search. Evaluate a move by playing random sequences of moves to the end of the game. When you reach the end, you know the game result (win, loss, draw). Repeat playing random sequences as often as resources allow. This will give you an indication of how often you win. If the initial move is good, you will win more often than if the initial move is bad. In other words, you are using statistics to assess how good a move is. This technique is called Monte Carlo search. It was initially used in backgammon and Go programs and led to immediate performance improvements. By the early 2000s, computer Go programs were playing at the level of an average club player. Adding Monte Carlo search allowed Go programs to reach beyond the Master level in a few years.