Do not pass Go

Computers can beat the world's best chess players but have yet to master other classic games like Go, writes David Levy

Ever since Garry Kasparov's sensational 1997 loss to the IBM chess monster Deep Blue, the chess world has thirsted for revenge. But the first opportunity ended in failure in Bahrain on Saturday, when Kasparov's former pupil and successor as World Champion, Vladimir Kramnik, could only draw an 8-game match against one of the world's leading chess engines, Fritz. But this was just the latest in a long series of human versus computer encounters that illustrate the inexorable march of artificial intelligence (AI).

It's a story that began at a Dartmouth University conference in 1956, when several of the founding fathers of AI defined the goals of that infant science. One of them was to create a computer program that could defeat the world chess champion. Success would, those scientists believed, reach to the very core of human intellectual endeavour.

By the early 1990s, due in no small part to the successes achieved in computer chess, the interest of the AI community had spread to many other games of skill, including backgammon, bridge, Go and Scrabble. Where exactly are we now in this fascinating struggle?

Some "thinking" games lend themselves to exhaustive analysis. Programmers are able to create a huge database containing every conceivable position in the game together with the correct result (win, lose or draw) assuming perfect play on both sides, and the number of moves required to achieve that result. Playing the game perfectly is easy for a program - it just looks up the current game position in its database and chooses a move that maximise its prospects. Games that have been "solved" in this way include Connect-4, Go-Moku (also known as 5-in-a-row) and 3-dimensional noughts and crosses (played on a mind-boggling 4x4x4 matrix), all of which are won by the first player with correct play.

The most interesting challenge to game programmers comes from those games for which perfect play throughout the contest cannot be expected for at least several years to come. But in some notable cases the strength of play of the leading programs, although not perfect, comes very close to or even exceeds that of the world's leading human players.

In Othello, for example, the strongest programs can now analyse 25 or more moves ahead. This means that, when the game is not quite two-thirds over, a program can see to the very end and thus play perfectly. Little surprise then that the American program Logistello thrashed world champion Takeshi Murakami of Japan by 6 games to 0 in 1997.

In draughts too, the world's strongest humans are no longer a match for the leading program, Chinook, which owes its strength to a very deep look-ahead and an enormous database of endgame positions. Chinook has such a huge score against the reigning (human) world champion, Ron King of Barbados, that he will not risk his title against the program in a match.

Backgammon presents problems of a different nature because of the randomness of the dice, creating so many possibilities at each move that only a shallow look-ahead is possible. But by applying probability theory together with sophisticated self-learning "neural network" techniques, programs such as Snowy (from Switzerland) and Jellyfish (Finland) have been developed that are capable of playing at or very close to world championship level.

Another game with a chance element is Scrabble. Before all of the tiles have been taken from the bag, a program cannot know what tiles are in its opponent's rack and therefore it cannot analyse perfect play until the last few moves of the game.

So before that stage of the game is reached, most Scrabble programs rely on the use of a massive dictionary, allowing them to consider every playable word in every position on the board. These techniques are sufficient to enable Maven, written by American Brian Sheppard, to challenge the world's best humans.

Shepherd believes that his program is now unbeatable over a series of games but, and probably as a gesture of self-preservation, the Scrabble community does not normally allow computer programs to compete in their tournaments.

And what of chess, the original target of the AI community? Ever since Kasparov's sensational loss to Deep Blue, the (human) chess world has been looking for revenge, hence the Kramnik versus Deep Fritz match.

But behind the public face of this encounter lies controversy over exactly how Kramnik's opponent was chosen and the way the match rules were stacked heavily in Kramnik's favour.

When negotiations for a Kramnik versus computer match commenced in October 2000, the obvious opponent was the German program Shredder, the reigning World Computer Chess Champion. But the match promoter Brain Games Network decided instead to hold a qualifying event to which many of the world's strongest programs were not invited, provoking outrage in computer chess forums on the internet. The qualifying event, held in Cadaques, Spain, was a 24-game match between Fritz and the Israeli program, Junior.

The qualifying match itself provoked surprise in the computer chess community, with doubts about how Junior's early 5-0 lead, which it sustained until after the 14th game completely eroded during the next 10 games, thereby causing a tied match and a play-off that was won by Fritz. Junior's surprising defeat, did, however, save Brain Games from the embarrassment of trying to arrange Bahraini visas for Junior's two Israeli programmers, Amir Ban and Shay Bushinsky.

Fast forward to Bahrain. The rules for Kramnik versus Deep Fritz (a multi-processor version of the program) could hardly have been more human-friendly. Fritz' programmer, Dutchman Frans Morsch, was required to freeze his code several months before the start and not to make any program changes thereafter.

Also, Kramnik was given a copy of the program with which he and his seconds could practice, allowing them to prepare with the utmost thoroughness, playing game after game at home in order to learn all about Fritz' style of play, the strategy it would use in certain opening variations, its strengths and its weaknesses. This was a far cry from 1997 when Kasparov did not see so much as a single game played by the current version of Deep Blue prior to his match in New York.

As if all this was not enough of a help, Kramnik was also allowed to train against Fritz using the very same 8-processor hardware that Deep Fritz would use in Bahrain. Added to which the rules stipulated that, if a game reached move 56, Kramnik would have the right to adjourn until the next day and to analyse the adjourned position using Fritz itself, in effect enabling Kramnik to "ask" what it intended to do against whatever variations he was considering playing after the resumption.

But despite having all these advantages Kramnik was unable to overcome Deep Fritz and thereby failed in his attempt to gain revenge on behalf of humankind for Kasparov's defeat by Deep Blue.

Kasparov's first opportunity of extracting his own revenge on the computer world opens on December 1 in Jerusalem where he takes on the Deep (parallel) version of Junior. The Israeli program is the reigning World Computer Chess Champion, a title won last July in Maastricht where Frans Morsch program, disguised by using the name Quest, finished fourth after losing to Junior in their individual encounter. Kasparov, whose current chess rating of 2,838 is 31 points ahead of Kramnik's, has been adamant that the rules for the Jerusalem match must be fair to both sides. He has asked for none of the advantages given to Kramnik in Bahrain.

What peaks will remain to be climbed in this field when Kasparov and his successors no longer have any chance against the best chess programs? Two games proving even tougher to crack than chess are bridge and Go. Although one or two programs can already handle the play of the cards in bridge rather well, much more research appears to be needed before programs can bid at anything approaching master level, let alone world champion. And while bidding remains a difficult hurdle for programs, so does making use of information obtained about the distribution of the opponent's cards from their own bidding.

Go always has been and still is the most difficult classic game to program. Knowledge engineering - the extraction of knowledge from human experts - is at best extremely difficult to achieve because human Go champions appear unable to explain exactly why a particular configuration or shape of Go stones on the board is good or bad. And without such knowledge programs will continue to flounder.

The game is so very deep and the number of legal moves so far exceeds that in chess, that a deep analysis of Go is impossible with today's technology. A Taiwanese businessman offered a prize of $1m for the first program to win a match against a Taiwanese junior champion aged 13 or thereabouts, but he died before the goal could be accomplished and it is probably still a decade or two away. Perhaps Go will be the final bastion in man's attempts to stave off his inevitable intellectual defeat at the hands of the machine.

Comments to