The Electronic Holy War (original) (raw)

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.”

The victory was not quite a Deep Blue moment; Crazy Stone was given a small handicap, and Ishida is no longer in his prime. But it was an impressive feat. As with computer chess in the nineteen-eighties, computer Go is dominated by individual programmers and small teams. Crazy Stone, for example, is programmed by one man, Rémi Coulom, a professor of computer science at Université Lille 3, in France.

No large company has invested yet in computer Go the way that I.B.M. did with chess. Peter Norvig, a director at Google Research and one of the founders of modern A.I., told me that, even if Google or I.B.M. hired a cadre of experts, invested “one hundred times more hardware than anyone else had ever applied to the problem,” and was “very clever about the system-design architecture, the exact machine learning algorithms, and the insights from neuroscience,” he doesn’t know if this would be enough to make the equivalent of Deep Blue for Go.

Go sounds simple. The board is a square with nineteen vertical and nineteen horizontal lines that cross, creating three hundred and sixty-one intersecting points. It starts empty, and two players take turns placing circular stone pieces on vacant intersections until the game is finished—either when both sides agree to end it or one player withdraws. Players score by surrounding intersections or by capturing the opponent’s pieces, each worth one point. Why is this so hard for computers? In chess, it takes fifteen moves for the number of possible game states to equal the number of stars in the universe. Go gets there in ten moves. At that point, the average chess game is nearly half over, but Go is only beginning: the average game still has a hundred and forty moves left, each adding a new universe of possibilities.

To say that Go is more complex than chess, though, is a little like saying that one infinity is larger than another. While technically true—and mathematically possible—it does not fully explain why computers, which can’t fully compute chess or Go, have become good at one and not the other. “A few hundred orders of magnitude don’t matter when you’re up in the ten to the one hundred and twenty,” Murray Campbell, a member of the I.B.M. Deep Blue team, told me. The key lies in Go’s structure. Deep Blue was able to exploit a weakness in chess’s armor: at the grandmaster level, to tell who is winning, you add up the pieces on the board and consider their positions. Campbell explained that, to win, you just stay ahead the whole time, vastly reducing the number of moves for computers to consider.

Wei qi translates to “encircling game,” and one of its few rules is that, when a piece is surrounded by an opponent’s, it is removed from the board. The rule is transitive, so large groups of pieces can surround other large groups, and may themselves be surrounded. Part of the difficulty for computers—and humans—is that it is often hard to determine at any given time whether a group of pieces is being surrounded or doing the surrounding, and thus who is ahead. Feng-Hsiung Hsu, another member of the Deep Blue team, writes that the distinction is particularly hard for computers to grasp because “the status of one group can affect that of its neighbors—like a cowboy who points a revolver at another cowboy, only to find himself covered by a rifleman on a roof.” Without a clear understanding of who is ahead, programs like Deep Blue stutter. “All the machinery that was built up for computer chess is pretty useless,” Campbell said.

The first computer Go attempts were based on what can only be described as computational exegesis: Go strategies through the millennia are collected in aphorisms and proverbs, and some of them—“Never cut a bamboo joint,” “Don’t go fishing when your house is on fire,” “Never chase a dragon”—can be easily translated into lines of code. For example, “Don’t go fishing when your house is on fire” is interpreted for the computer as “prioritize local responses versus global search,” according to David Fotland, who has been writing Go programs since 1981. Other early Go programs used the human brain as inspiration: neuroscientists in Japan, China, and Korea put Go professionals into brain scanners, but the very tasks at which the human brain excels—pattern recognition, learning, intuition—are some of the hardest unsolved problems in A.I. Two decades of early efforts amounted to programs that were effective on a small scale, for tactical fighting but little else.