A decade ago IBM's chess program, Deep Blue, beat world champion Garry Kasparov in a six-game match. The event marked a milestone, forcing humans to yield dominance of yet another strategic diversion. Only the Asian board game Go seemed to be computer science's Achilles' heel: humans could soundly beat the machines. A new algorithm can now take on strong human players--and win.
Go has proved enormously difficult for computer programmers because of the game's deceptive complexity. The objective of Go is to stake out territory and surround an opponent by placing black or white stones on the intersections of a nine-by-nine or 19-by-19 line grid. Especially on the large board, the number of possible moves per turn is huge--200 on average for each midgame position compared with the several dozen possible in chess. There are also enormous branching factors. Given N positions on the board, the total number of possible game positions is 3N, because every position can be occupied by a black or white piece, or it can be empty. The total number of legal positions on the small board is about 1038; on the large board, about 10170. Additionally, more stones do not ensure victory, and players must be able to consider local positions and the board as a whole.