[The following article is taken from the Jan. 2007 Issue of The Economist.]
Computers have started to outperform humans in games they used to lose
RESEARCHERS in the field of artificial intelligence have long been intrigued by games, and not just as a way of avoiding work. Games provide an ideal setting to explore important elements of the design of cleverer machines, such as pattern recognition, learning and planning. They also hold out the tantalising possibility of fame and fortune should the program ever clobber a human champion.
Ever since the stunning victory of Deep Blue, a program running on an IBM supercomputer, over Gary Kasparov, then world chess champion, in 1997, it has been clear that computers would dominate that particular game. Today, though, they are pressing the attack on every front. They are the undisputed champions in draughts and Othello. They are generally stronger in backgammon. They are steadily gaining ground in Scrabble, poker and bridge. And they are even doing pretty well at crossword puzzles. There is one game, however, where humans still reign supreme: Go. Yet here too their grip is beginning to loosen.
Go was invented more than 2,500 years ago in China (Confucius considered it a waste of time). It is a strategic contest in which two players take turns to place stones on the intersections of a grid with 19 lines on each side. Each player tries to stake out territory and surround his opponent. The rules are simple but the play is extraordinarily complex. During a game, some stones will “die”, and some will appear to be dead but spring back to life at an inopportune moment. It is often difficult to say who is winning right until the end.
Deep Blue and its successors beat Mr Kasparov using the “brute force” technique. Rather than search for the best move in a given position, as humans do, the computer considers all white’s moves—even bad ones—and all black’s possible replies, and all white’s replies to those replies, and so on for, say, a dozen turns. The resulting map of possible moves has millions of branches. The computer combs through the possible outcomes and plays the one move that would give its opponent the fewest chances of winning.
Unfortunately, brute force will not work in Go. First, the game has many more possible positions than chess does. Second, the number of possible moves from a typical position in Go is about 200, compared with about a dozen in chess. Finally, evaluating a Go position is fiendishly difficult. The fastest programs can assess just 50 positions a second, compared with 500,000 in chess. Clearly, some sort of finesse is required.
In the past two decades researchers have explored several alternative strategies, from neural networks to general rules based on advice from expert players, with indifferent results. Now, however, programmers are making impressive gains with a technique known as the Monte Carlo method. This form of statistical sampling is hardly new: it was originally developed in the Manhattan project to build the first nuclear bombs in the 1940s. But it is proving effective. Given a position, a program using a Monte Carlo algorithm contemplates every move and plays a large number of random games to see what happens. If it wins in 80% of those games, the move is probably good. Otherwise, it keeps looking.
This may sound like a lot of effort but generating random games is the sort of thing computers excel at. In fact, Monte Carlo techniques are much faster than brute force. Moreover, two Hungarian computer scientists have recently added an elegant twist that allows the algorithm to focus on the most promising moves without sacrificing speed.
The result is a new generation of fast programs that play particularly well on small versions of the Go board. In the past few months Monte Carlo-based programs have dominated computer tournaments on nine- and 13-line grids. MoGo, a program developed by researchers from the University of Paris, has even beaten a couple of strong human players on the smaller of these boards—unthinkable a year ago. It is ranked 2,323rd in the world and in Europe’s top 300. Although MoGo is still some way from competing on the full-size Go grid, humanity may ultimately have to accept defeat on yet another front.
JC Notes 