Brute-force computation has eclipsed humans in chess, and it could soon do the same in the ancient Asian game of Go.

Feng-hsiung Hsu, a key designer of Deep Blue--the IBM computer that in 1997 defeated chess grandmaster Garry Kasparov, then the world champion--now proposes to apply the same approach to the vastly more complex Chinese game of Weiqi, known in the West by its Japanese name, Go.

That approach, known as brute-force analysis, exploits the peculiar ability of computers to calculate vast numbers of possible game outcomes while sidestepping their weakness in judgment and planning. Brute force was long derided in the artificial-intelligence community as a copout from the grand challenge of mimicking not merely the results but also the modes of human thought, but, as Hsu points out, the method has proved itself time and again, not only on the chessboard but also in such practical spheres as market analysis and weather forecasting.

In his current position as a manager in Microsoft Research Asia, in Beijing, Hsu is looking for Chinese graduate students to design, with his support and encouragement, a preliminary version of a grandmaster Go machine. If the concept proves itself valid, the next step would be to pursue the ultimate goal of beating the best human players.

Go is played on a 19-by-19 board on which each player places a "stone" at the intersections of the lines with the aim of capturing enemy formations and territory. The game is devilishly difficult for computers because of its truly astronomical level of complexity. A typical Go position offers a player a choice of about 200 move possibilities, about six times more than in chess. That means each additional move ahead that a player attempts to calculate increases the complexity gap by a factor of six. After nine moves, a Go machine will have generated 10 million more possibilities than its chess-playing counterpart.

Adding still more to the relative challenge is the problem of assigning a numerical value to the positions that lie at the branch-ends in the analysis tree. In chess, such values can be assigned by simple arithmetic; in Go, additional moves must often be calculated. Only after grading millions or even billions of end positions can the program work its way backward along the tree of analysis to discover the best move.

Hsu insists that those problems can be overcome. First, he appeals to Moore's Law, the semiconductor industry's tendency to double the number of transistors on a chip every two years. Within a decade, Hsu argues, we will be able to make a special-purpose computer a million times more powerful than Deep Blue.

Second, he proposes algorithms to cut the analysis tree down to size. One such algorithm would in certain cases allow the program to rule out vast numbers of moves without having to look at each one. Another algorithm would reuse conclusions reached in one branch of the tree by "grafting" them onto another branch. The grafting idea was found wanting in chess programming, but Hsu explains why it ought to work better in Go.

- IEEE Spectrum Magazine