Training AI to master Go

The number of possibilities in chess, though vast, is not so vast that with a powerful computer, you can't defeat the world's greatest human player. Go, an ancient Chinese game whose origin goes back to more than 5,500 years, is far more complex. In Go, a piece can be placed anywhere on the 19 x 19 board. To begin with, there are 361 possible moves. So to search forward k moves, you must consider 361k possibilities. To make things even more difficult, in chess, you can evaluate how good a position is fairly accurately by counting the number of pieces on each side, but in Go, no such simple evaluation function has been found. To know the value of a position, you must calculate through to the end of the game, some 200+ moves later. This makes the game impossible to play to a good standard using min-max.

Figure 5

To get a good feel of the complexity of Go, it is worth thinking about how humans learn to play Go versus Chess. When beginners starts learning Chess, they make...