In May, 1997, I.B.M.’s Deep Blue supercomputer prevailed over Garry Kasparov in a series of six chess games, becoming the first computer to defeat a world-champion chess player. Two months later, the Times offered machines another challenge on behalf of a wounded humanity: the two-thousand-year-old Chinese board game wei qi, known in the West as Go. The article said that computers had little chance of success: “It may be a hundred years before a computer beats humans at Go—maybe even longer.”
Last March, sixteen years later, a computer program named Crazy Stone defeated Yoshio Ishida, a professional Go player and a five-time Japanese champion. The match took place during the first annual Densei-sen, or “electronic holy war,” tournament, in Tokyo, where the best Go programs in the world play against one of the best humans. Ishida, who earned the nickname “the Computer” in the nineteen-seventies because of his exact and calculated playing style, described Crazy Stone as “genius.”
Computers overtake humans in yet another field. After Deep Blue prevailed over Kasparov in chess, humans turned to the game of Go for solace. Here was a game, it was said, that humans would dominate in for quite some time. It turned out to not be much time at all.
Coulom’s Crazy Stone program was the first to successfully use what are known as “Monte Carlo” algorithms, initially developed seventy years ago as part of the Manhattan Project. Monte Carlo, like its casino namesake, the roulette wheel, depends on randomness to simulate possible worlds: when considering a move in Go, it starts with that move and then plays through hundreds of millions of random games that might follow. The program then selects the move that’s most likely to lead to one of its simulated victories. Google’s Norvig explained to me why the Monte Carlo algorithms were such an important innovation: “We can’t cut off a Go game after twenty moves and say who is winning with any certainty. So we use Monte Carlo and play the game all the way to the end. Then we know for sure who won. We repeat that process millions of times, and each time the choices we make along the way are better because they are informed by the successes or failures of the previous times.”
Crazy Stone won the first tournament it entered. Monte Carlo has since become the de facto algorithm for the best computer Go programs, quickly outpacing earlier, proverb-based software. The better the programs got, the less they resembled how humans play: during the game with Ishida, for example, Crazy Stone played through, from beginning to end, approximately three hundred and sixty million randomized games. At this pace, it takes Crazy Stone just a few days to play more Go games than humans collectively ever have.
Well, at least we still have Arimaa.