Å®ÉúСÊÓƵ

Chess master David Levy once watched a man preparing to play a match against a computer and shaking with nerves. In contrast, when Marion Tinsley, the world draughts champion, beat his cybernetic challenger Chinook at the end of August, he leapt up and shouted ‘Three cheers for human beings!’. Clearly, playing against a program can be an emotional experience.

‘Machines have so many advantages,’ says Levy, who has played and won some famous computer challenges. ‘They will never make a careless mistake. The mistakes they do make are at a deep and subtle level. But computers are predictable, especially for someone who has played a lot against them.’ The best humans still regularly outwit the best chess programs. Tinsley’s win, by a 4-2 margin after 39 games, means the same holds true in draughts, where Chinook is officially the world’s second-best player. And computers are still at club player level in bridge and the oriental game of go. Yet if they can now perform millions of calculations a second, why can’t they beat everyone?

Actually, they could – but not in a human opponent’s lifetime. One estimate says there are 10120 possible moves in the average game of chess (‘The challenge of Go’, New Å®ÉúСÊÓƵ, 1 February 1979). Today’s best supercomputers would need about 10101 years to consider all these moves and find the ideal response. Go, played with black and white stones on a 19 by 19 board and requiring just nine rules, offers an average of 150 to 200 possible moves each time – amounting to roughly 10700 moves altogether. Could you wait 10681 years?

Computers do well in tactical situations, where the position is complicated but short-term and a human player can easily get confused. A human tends to look at the overall development of a game and recognize ‘themes’ from previous games. At the moment, making a program unbeatable means solving the mathematical problem that a game represents, and turning that solution into a program.

Some have done that, for some games. Early in August an Olympic Games for computers (sponsored by AST, a computer manufacturer) was held in London, with machine challenging machine in nine games including bridge, backgammon, go, go-moku and Scrabble, all of which require strategy and tactics. Victor Allis from the University of Limburg in Maastricht won a gold medal for his program Victoria, which is a solution of the relatively simple game of go-moku (New Å®ÉúСÊÓƵ, This Week, 15 August 1992). He has also solved the children’s game Connect4 and three-dimensional noughts and crosses. A human might draw with, but never beat, his programs.

Similarly, Chinook is not far off a final answer. Its developers challenged Tinsley, the world champion since 1954, for his title and a $6000 prize. In the first of each pair of games, the initial three moves were chosen by ballot (otherwise the champion could always play for a draw); in the second game of each pair the same opening was used and the players swopped sides, giving each an equal chance. In 38 years Tinsley had been beaten just eight times. But he had only beaten Chinook once before, and drawn 17 times. This time, Tinsley was at one stage 1-2 down in wins. Still, the computer advantage was not what it seemed. Chinook lost one game, and failed to save another, because it only calculated 20 moves ahead, against Tinsley’s 25.

Computer chess first captured the public imagination in 1967, when a program from what was then the Soviet Union beat an American program twice and drew twice. A year later, Levy bet £1000 that a computer would not beat him by 1978. He won the bet by comfortably beating Chess 4.7, then the world’s best program, which examined up to three million positions – equivalent to looking about seven moves ahead. It was stronger than 99.5 per cent of all the world’s chess players (‘Computers are now chess masters’, New Å®ÉúСÊÓƵ, 27 July 1978). Levy’s strategy was to make moves that effectively did nothing. ‘Sooner or later,’ he said, ‘the program will dig its own grave.’

Levy took another $1000 bet against losing within another five years, won that, and shortly afterwards retired from professional chess because he had lost the zest for winning. A couple of years ago, he says, ‘I played the world’s strongest program and it killed me.’

The killer was Deep Thought II, a customised workstation made by IBM. It can consider 10 million positions per second and is the first computer to achieve grandmaster status. Although it beat the Russian ex-world champion Anatoly Karpov (he made a blunder), it proved no match for world champion Garry Kasparov, who beat it twice in October 1989. Kasparov later told the New York Times magazine he thinks computers will never be good enough to beat the world champion because they lack the whole range of human skills. Undaunted, Deep Thought’s three designers are now working on another version which will consider a billion positions per second.

Yet in some games there are just too many possibilities. So it is with go and bridge. Go was invented 4000 years ago in China, and its few, simple rules are what give it so many possible moves – the ‘game tree’. The board has a 19 by 19 grid. One player plays white stones and the other black stones and each tries to capture as much of the board as possible by enclosing empty areas or the opponent’s stones.

Stones cannot move once placed on the board, but their significance can change dramatically at any time as their spatial relationship to the friendly and enemy stones changes. This makes it extremely difficult to tot up the likely scores until the game is almost over. Human players develop a feel for how the game is progressing without calculation, but computers lack feeling or intuition – a big problem, says Michael Reiss, who is researching neural networks at King’s College London. His program, Oxford Softworks Go, works by trying each possible next move and calculating the resulting score. It won the European Computer Go Championships, held in Canterbury this July, and the silver medal for go at the AST Olympiad.

But go programs are decades behind their chess or draughts siblings: none approaches the level of the thousands of professionals in Japan. Reiss is rated as an average British amateur club player, but he can always beat his program. Like many others, Reiss says he could do much more with a faster computer.

But is the answer a faster machine, or a differently wired one? Because of the patterns formed in games like go, chess and draughts, some people have suggested using pattern recognition techniques: like a person, the computer would look out for arrangements of the board which it had encountered before and knew how to handle. Neural networks, a type of software in which simple calculating stages are interconnected and can adapt to ‘learn’ like neurons in a nervous system, are exceptionally good at pattern recognition. But Paul Lu, one of the Chinook programming team, says that any neural network able to recognise the patterns in draughts would have to be very big because there are so many possible patterns.

Bridge-playing programs are at an even earlier stage of development than go programs. Bridge has several unusual features. First, the two pairs of players have only 52 available moves, and draws are not possible – unlike chess, draughts and go. Secondly, the cards come from a shuffled pack, introducing luck. Thirdly, the players do not see all the cards at all times. Computers can overcome some of these challenges by deduction and probability theory, which they handle very effectively. Gero Scholz, whose program Bridge King carried off the gold medal for bridge at the Olympiad, says: ‘If all the cards could be seen, the tree of possibilities would be about the same as for other games. Because we can’t see them, our tree is several dimensions bigger. Some programs try to make random assumptions about the cards, but this is not the best way.’

His co-programmer Hans Leber says their program does not look ahead at all; in bridge, decisions must be made in seconds rather than minutes. Bridge King simply deduces as much as it can about where the cards are, then follows a set of rules. So far, it can beat a hobby player but not a tournament player. ‘Our program still makes silly mistakes,’ says Scholz. ‘But we feel happy, because others make bigger mistakes.’ He believes that to improve, it must be built to use heuristics – that is, rules of thumb – and also know when to ignore them. Tom Throop, whose Bridge Baron won the silver medal, says it needs to know when to take a chance, too. Of course, a computer misses hints that people exploit such as how quickly opponents reply to a move, and whether they are squirming – which Throop calls ‘table presence’.

To non-enthusiasts, all the effort and money devoted to programming computers to play games might seem frivolous. But there are close parallels between many of the games and real-life situations. Levy says that ‘computer games present excellent models of problems in long-range planning’. Mikhail Botvinnik, who was the world chess champion 12 times between 1948 and 1963, wrote an algorithm for a chess program, and adapted it slightly to run a power station in Russia. (It wasn’t Chernobyl.) Levy claims the algorithm was better at running the power station than at chess; the decision tree was simpler.

Yet once a program has solved a game, one might think all the fun would disappear from it. The solution gives the perfect moves as well as the result. ‘There wouldn’t be any interest in humans playing against the computer,’ says Lu, who expects Chinook to solve draughts in a year or two. But Levy counters: ‘You could use the same program, slightly modified, to play at different levels.’ It could give its opponent a head start, or be fed random errors. ‘I believe the stronger the programs are, the more fun you can have with them,’ says Levy. ‘After all, every chess player in the world wants to play against Kasparov. A perfect program can teach them.’