IMAGE: Bryan Christie Design

Click here for a comparison between Chess and Go

There is, however, a course midway between selectivity and exhaustiveness. Instead of analyzing to the end, the program can merely look a few moves further ahead than a human could manage. Deep Blue typically looked 12 plies ahead in all variations (and 40 or more plies in selective lines), generating around 170 million leaf nodes per second. Next, the program would evaluate each of these positions by counting “material,” that is, the standard values of the chess pieces. For example, a pawn is worth one point, a knight or bishop three, and so on. Then it added points for a range of positional factors, chosen with the help of human grandmasters.

The resulting evaluation function probably was no better than a middling amateur's ability to grade a single position. But by grading 200 million of them, it was able to do very well indeed. Just ask Kasparov.

This substitution of search for judgment is the essence of the brute-force method, and it turned out to have two critical advantages over selective search. To begin with, the program became easier to write, had far fewer bugs, and did not have so many blind spots. And crucially, the program played significantly and measurably better as the processing power increased, once the switch to brute force had been made.

Slate and Atkins believed their program was playing at only Class C level—that is, about the level of the typical avid tournament player, who is rated between 1400 and 1600 on the U.S. Chess Federation's rating scale. However, when they moved their program to a supercomputer, it shocked everyone by winning a tournament among Class A players, with ratings between 1800 and 2000. A Class A player is good enough to beat a Class C player 9 times out of 10, on average.

Moving to a supercomputer made this enormous difference because it allowed the program to look just a little further ahead. Detailed measurements later showed that when a brute-force program searched just one ply deeper, its strength improved by between 200 and 300 rating points. When two players are separated by that big a gap, the higher-rated player will win, on average, 4 out of 5 games.

It was this almost linear relationship between search depth and playing strength that first made me believe chess could be solved. I wondered whether the relationship would continue all the way up to the World Champion level—about 2900 on the Chess Federation's scale. In the end, this conjecture proved to be partly true. That is, the program did continue to play better as search depth increased, but additional gains in rating could also be achieved by improving the evaluation function and the selectivity of its search.

Go is played on a board crisscrossed by 19 vertical and 19 horizontal lines whose 361 points of intersection constitute the playing field. The object is to conquer those intersection points.

A player makes a move by placing a ­lozenge-shaped “stone” on an intersection, then the other player counters, and the two alternate moves. Players capture enemy stones by surrounding them, that is, by removing their “liberties,” which consist of either the vacant points adjacent to a stone itself or to friendly stones to which it is itself connected (see illustration, “The Goal of Go”). When no more moves are possible, the players count up the intersection points they control, and the player with the most points wins.

All the leading Go programmers today belittle brute force. In this they resemble the computer chess experts of 40 years ago. Selective search dominated thinking on computer chess from the late 1940s to the late 1970s, and that mind-set prevented any program from advancing beyond the level of a Class C player.

Go does, however, present two real problems, both having to do with the amount of searching the program must perform.

The first problem is the tree of analysis. Because Go offers more possibilities at every turn, the tree is far bigger for Go than for chess. At the start of the game, the first player can place a stone on any one of 361 positions, the second player has 360 choices, and so on. A typical game lasts about 200 moves, so it averages at least 200 move choices per turn—nearly 10 times as many as in the average chess position.

The second problem is the evaluation of the end positions. In Go you can't just count up stones, because you have to know which stones are worth counting. Conquered territory is defined as board space occupied or surrounded by “living” stones—stones the opponent cannot capture by removing their liberties. Before you can count a stone as live, you have to calculate several moves ahead just to satisfy yourself that it is really there in the first place.

Put these two problems together and you get a computational problem that at first glance seems intractable. But there are ways to engineer around it.