- Behind Deep Blue: Building the Computer that Defeated the World Chess Champion by Feng-hsiung Hsu
Princeton, 300 pp, £19.95, November 2002, ISBN 0 691 09065 3
Two bishops side by side put pressure at long range on the pawns defending the castled Black king. My queen, ready to advance to the middle of the board, completes the threat. Black will have to weaken his defence by advancing a pawn. There are further forces I can bring into play. I find it slightly frustrating that my mechanical opponent either knows what I mean to do or has taken standard precautions: there’s a knight in the way, and I can’t get at it. My plan – single-minded, bloody-minded, suicidal – revolves around a single square, h7, and he has it covered. Evidently, an all-out attack in the middle game isn’t the answer: there will be refutations, counter-attacks, sacrifices and exchanges; the balance of power will change. A dramatic early mate following an unstoppable combination would be a good way to win a game of chess, but I’ve never won like this. In fact, I’ve rarely won. I know the moves (though I have to remind myself how the en passant rule works), I can follow the basic openings, and I know the principles of development – advance bishops and knights, line up the rooks. But I can’t seem to beat anyone other than myself. I’m not patient enough. I don’t play well enough.
I didn’t play chess when I was younger. I used to say I wasn’t interested in war games, but I lied: I was too competitive to compete. When I was 13 everyone I knew was playing obsessively, all the time: too fast to follow, too fast for talk. Chess clocks were banged, pieces were exchanged, flags fell. Some people couldn’t lose, and never losing seemed to me a better, more convincing kind of statement than anything I could achieve at school with words. There were no excuses, no justifications, no self-deprecations: it was less equivocal, more final. I took for a while to reading about chess, along with stories about musketeers. I killed giants vicariously; I liked the legends. In 1858, Paul Morphy, a boy from New Orleans, played a count and a duke in a box at the Paris Opera during a performance of The Barber of Seville, and chose to throw away his major pieces one by one, finishing with the most elegant mate imaginable. In 1918, Capablanca, the famously instinctive Cuban prodigy, played the Ruy Lopez opening against Frank Marshall and was presented with a new, ingenious, aggressive defence. Marshall, it turned out, had kept his innovation unrevealed for ten years, waiting to unleash it on the player he most wanted to beat. Capablanca saw the prepared series of attacks and knew that Marshall must have analysed all conceivable responses; but he trusted that his position was defensible and played on to win, discovering in the onslaught undreamed-of solutions to apparently insoluble problems. The attractions of chess are perfection, impossibility, flair. And the attractions of chess legends are impossible arrogance and pathological decline. Bobby Fischer is supposed to have said that he’d challenge God, giving him the advantage of a pawn. The same statement, I now discover, is attributed to Steinitz during the days he spent shuffling barefoot through the New York snow: either the legends last better than the players, or the players find the legends too attractive not to steal them from one another. The heroism is bluster.
But chess is more than war. I regret only half-appreciating the beauty of some abstract moves, of sacrifices and gambits, of gambits declined. Watching a game unfold between two grandmasters is baffling (why has he moved his king when it’s not under threat?) but absorbing. One player makes a move; there’s a response. The players know the steps. There is negotiation: the advantage passes from side to side in subtle shifts. Science is involved. Karpov and Kasparov, the untouchables of the 1980s, fed off one another unforgivingly but creatively. Karpov is nicely dismissed in a textbook ascribed to Kasparov: ‘The lacklustre reign of Anatoly Karpov did little to fire the imagination of a new chess generation.’ But after their World Championship games they would look at a board together and examine possible continuations to find out how they could have played better. To beat each other they needed to hate each other, but they had a stronger need to improve their game, and spiralled upwards towards a wordless, inexplicable chess perfection. (Or so we suppose: no one else could understand what they were talking about.)
Chess, I once believed, was inhuman. You think your opponent’s thoughts as well as your own, you have refutations for all his possible moves: if he does this, then I do that; then he does this, and I do that; and I’ve got him. It’s a test of memory and logic I’m not capable of passing: something slips; I forget where I was. It’s hard enough to think for myself. In Stefan Zweig’s The Royal Game, favoured reading for chess obsessives, Dr B survives interrogation and confinement by teaching himself chess from a book of famous games, playing both Black and White; he exhausts the games in the book and plays himself in his head, his Black self improving to solve the ever harder problems his White self sets; eventually, divided, he goes mad. Reassuringly, this isn’t how chess is played: logic and calculation are only part of the game. At 14, a friend of mine looked at a board and said: ‘this square will be important later on.’ Experience tells: a pattern is recognisable, and instinct, in chess at least, is the product of recognition. Psychologists interested in discovering how a chess mind works have tended to find that expert players don’t think any further ahead than amateurs; in any given position, the experts consider fewer alternative moves. When asked to memorise a board with pieces randomly placed, experts are as bad at reconstructing it as amateurs; when asked to memorise a position taken from a game, however, they make far fewer mistakes: the relative positions of the pieces are more significant than their locations, and a nonsensical relationship is unmemorisable. Grandmaster etiquette – or bravado – dictates that the answer to the question ‘how many alternative moves do you consider?’ is ‘one: the best one’; the proper answer to the question ‘how many moves ahead do you think?’ is ‘one move further than my opponent.’ The alternative to the kind of tactical calculation that produces surprising and devastating combinations is slow positional play, which depends on recognition and feel, and gradually securing an advantage. Steinitz began his career with angry flair, and then discovered a quieter way to win. Kasparov, aggressive, is as much a calculating tactician as a strategist; Karpov plays positionally.
Chess has always demanded exaggerated opposition: black and white, good and evil. When Fischer played Spassky in Reykjavik in 1972 – Fischer inspired, demanding, American; Spassky calm, professional, Soviet – was it the lone white knight against the shadowy representative of the evil empire, or was it the good man against the unreliable, the grubby? There were no disinterested commentators. After Spassky retired from serious competition (unusually for a chess player, he wasn’t interested only in chess), the Soviet chess world – and therefore the entire chess world (Fischer having disappeared for less personable reasons) – was dominated by the unpredictable Viktor Korchnoi: unpredictable, his detractors would say, in everything but his game. In his account, he was crippled by the authorities. His commitment was called into question when he complained about his KGB minders during overseas tournaments; his salary was cut and his name kept out of official reports of his victories – he was always ‘the opponent’. When Karpov – the untainted, blue-eyed boy – arrived on the scene and started winning, Korchnoi was redundant. He defected and had to leave his wife and children behind. Or that’s Korchnoi’s story, as told in his autobiography, Chess Is My Life. Karpov’s ghost-written autobiography, also called Chess Is My Life, holds that Korchnoi was an attention-seeking monomaniac who refused offers to help secure his rehabilitation; moreover, he wasn’t naturally talented. Korchnoi wasn’t the only player to defect: Spassky, Tigran Petrosian, Igor Ivanov all went West. It was a winner’s world, and the winnings and the glory were to be had elsewhere. The defectors were traitors and heroes; they were brilliant and wrong-headed.
Individual v. empire: the paradigm was cemented in the Cold War, but its roots are longer lasting. There’s always a new kid on the block, a loner figure up for a bit of giant-killing. There are shades of The Magnificent Seven. There’s a man with a gun and a man with a knife; the man with the knife will win, until he’s unfairly outnumbered. The board of 64 squares and 32 pieces has never been sufficient to explain the full nightmare of chess: the abstraction is relentless, and a degree of tale-telling is required to survive it. When things start going wrong, you’re facing more than just your opponent. In a match against Korchnoi, Spassky wore a green eyeshade and sat at a distance from the table in order to thwart Korchnoi’s mind-bending rays. During the Reykjavik match, the Russians dismantled Spassky’s chair to find out if it had been tampered with by the Americans. In chess mythology, the counterpart to the loner with the knife is the wired sub-genius, acting on instructions from some larger agency: his orders come via his spectacles, or a microscopic implant in his ear.
Recently, the idea of the dominant superpower attempting to crush the rebellious spirit has been superseded: man is pitted against machine, monstrous calculation against human intuition and understanding. The 1997 match between Kasparov and Deep Blue had everything. The empire was IBM; the representative of the free-thinking world was, according to the ratings, the strongest player ever. In one corner of the 35th floor of the Equitable Center in New York, Big Blue set up their big baby: an $X million RS/6000 SP supercomputer comprising two six-foot boxes each housing 15 workstations running in parallel, each workstation containing 16 dedicated chess chips. Its combined maximum search speed was 200 million positions per second. Down the corridor, in a book-lined study, Garry Kasparov was installed, with all the consideration due a World Champion: supplies of bananas, mineral water, a leather armchair of the right firmness (though the organisers refused him a portable loo). The arrangements were fraught. Was the air-conditioning right? Would Deep Blue overheat? Would Kasparov freeze? Was the light too bright? They would play six games. The prize fund was $1.1 million: $700,000 for the winner, $400,000 for the loser.
Computers have been better at draughts than any human player for a while. Some even simpler games – Mancala, Nine Men’s Morris – have been ‘solved’ by computers. The computer can’t lose: it can calculate every possible response to each of its possible moves, then every response to each response until the game is over. But a computer can’t play perfect chess. There are 10128 possible chess games of 40 moves (the average), a very much larger number than 1080, which is the probable number of atoms in the Universe. Since 1958, computers have given themselves an advantage by abandoning searches if the result of a move leads to a worse position than one already examined; this means that the machine has to look at only about the square root of the total number of possible positions. This helps, but not enough. It doesn’t seem likely that a computer will ever be able to announce mate in 19 before its opponent has touched a piece. But they can achieve moments of perfection. Deep Blue included a database of all possible five-piece endgames. There is now a database of all pawnless six-piece endings, each combination involving up to 20 billion positions; a computer using it will be able to announce mate in 150 and never make a mistake. But pure calculation isn’t an adequate solution: even Deep Blue, which searched at least fifty times faster than the latest programs, had to know something about chess.
Feng-hsiung Hsu, who was Deep Blue’s chief architect, has written a book telling the story of his success, from his arrival as a graduate student at Carnegie Mellon, where he was tempted away from building printer engines for Chinese characters, through all the ups and downs (colleagues being poached by Wall Street firms, interdepartmental rivalries, power failures in Beijing), to the Kasparov/IBM showdown. A particular low point was a Spectator article claiming that the computer chess project was a front sponsored by the Defense Advanced Research Projects Agency. DARPA’s Lieutenant Colonel Robert Simpson was interviewed by Dominic Lawson (‘Dominic’ to Hsu – such is the democracy of computer geekery that he is filed under D in the index); not wanting to appear out of the loop, Simpson explained that an advanced chess program was ideally suited to hyperintelligent guidance systems for cruise missiles.
Hsu was the man who built the chips – the hardware man, the engineer. He says he finds programming boring, but I can’t imagine it’s more boring than working out how many little legs you can fit on a chip before it stops working. He explains that his chess chip has two main parts: a move generator (the easy bit), which comes up with possible moves; and an evaluation function (the hard bit), which decides whether the move suggested is any good. If making a certain move means that the computer will be a pawn up ten moves down the line, the decision will be easy. It’s not difficult to count who has more pieces, and very basic chess computers are good at that but not at much else: they will look for gradual material advantage, attacking a few pawns or going all out to trap a vulnerable knight. But this doesn’t get you very far against a player with plans which might require only one knight. Somehow the computer has to approximate a human ability to determine the value of a position: a good pawn structure, a safe king, well-developed pieces, a fianchettoed bishop.
At this point, Hsu’s story becomes alarming: his machine’s intelligence turns out to have been very unartfully induced. The early versions of his chip, before he and his team were snapped up by IBM for their dramatic demonstration, had to be taught some elementary things about chess. Deep Blue’s immediate predecessor, Deep Thought II, had been undone by Bent Larsen in Copenhagen. It had traded off a knight for a bishop, leaving it with a bishop pair, but it didn’t know that to turn the discrepancy into an advantage it would have to exchange a few pawns to open up the position and allow its bishops room to act. Larsen kept the position closed and his knights wreaked havoc. It was an easy problem to fix: an open position had to be assigned a higher value when both bishops were in play. As the computer improved it became harder to guess why it wasn’t making the best moves. Before the 1997 match, Deep Blue’s chief grandmaster trainer, Joel Benjamin, announced that his pupil was making some odd, time-wasting pawn moves. Hsu’s team wrote him a program to allow him to inspect the workings of the evaluation function. It seemed that Deep Blue could recognise the value of having a pair of rooks on the same file only when the file wasn’t blocked by pawns, and was duly (and pointlessly) clearing itself a way to arrive at the position it liked. After this, the little fixes became more speculative. They were twiddling knobs in the dark. In the second game against Kasparov, having lost the first, Deep Blue made what its designers thought was another mistake: Be4 to block an advancing Black pawn. There were impressed murmurings in the commentary room; the chess columns approved. On subsequent examination, it turned out that there had been a bug in the King Safety Evaluation Function. When it was fixed, the computer stopped playing Be4. So they kept their hands off it for the rest of the match, hoping for a few more remarkable moves.
But the third game was the most revealing, and disturbing for my understanding of science. Kasparov opened with the entirely unorthodox d3, presenting the computer with an opening it couldn’t possibly have a prepared response to. Like all chess players, Deep Blue knew its openings; Kasparov and his advisers had decided to make it struggle. But Hsu had taken the precaution of inventing what he called the ‘extended opening book’: when a position didn’t conform to a known opening, the computer would refer to a database of grandmaster games to determine what move a very strong player might have made, awarding known grandmaster moves a hefty bias. After Kasparov’s fifth move the position was recognisable; Deep Blue played Be7, moving its bishop in front of its king. The commentators disapproved: it was too cagey. Apparently, Michael Adams had once made the move in a similar position. Deep Blue scraped a draw. The IBM programmers were chastened, and for the next game took the drastic step of reducing the bias given to grandmaster moves that hadn’t been proved to be good. They drew the fourth game, and the fifth. In the final encounter Kasparov appeared to collapse. He made a series of questionable moves and resigned, thereby losing the match. This wasn’t the end of the fighting, however. Commentators accused Kasparov of playing badly. The Kasparov camp accused IBM of having cheated. Some doubt remains on both counts.
Until Kasparov lost to Deep Blue, grandmasters had a clear idea of how to beat computers. A computer can do no more than mimic a grandmaster’s positional sense, through a combination of trial and error and looking it up; its real advantage is that it can outcalculate anyone. If you allow it to bring a range of pieces into play it will find combinations far down the line that are very difficult to anticipate. Until 1997, the best defence had proved to be keeping the position closed, the centre blocked, to prevent any hope of immediately effective tactics for either side. Against Deep Blue, Kasparov played deliberately substandard moves: where the textbook would have recommended development, he would be cautious. Avoiding the textbook meant forcing the computer to play what it didn’t know, but it also meant tying it up in complex positions until superior human understanding tipped the balance. The strategy failed.
Part of the problem was that Kasparov is an attacking player: subtle positional give and take isn’t his style. The problematic consequence was that the chess wasn’t very interesting; the anti-computer approach worked to the extent that no one saw much evidence of Deep Blue’s calculating ability. Observers were dismissive. Anand, the world number three, was impressed by only two moves, both in the second game: they were, he said, the only good moves that differed significantly from what intuition would have suggested. One was Be4, basically the result of the king safety bug. Everyone had been expecting the computer to advance its queen and win an exposed pawn. Hsu claims that one reason Deep Blue avoided the capture was that it had seen a potential three-pawn sacrifice for Kasparov that would have given him a winning edge; he also claims that Kasparov hadn’t seen it.
Kasparov resigned in game two, his strategy of self-restraint having left him hemmed in and Deep Blue with plenty of room for manoeuvre. It was later established that in the final few moves Deep Blue had made some bad mistakes and that the game should have been drawn. Kasparov was understandably frustrated. He announced that no computer could have rejected the pawn capture, and that Deep Blue had spent an unnatural length of time on the move. Accusations were exchanged. Hsu had his moment on stage: ‘Well, shall we open up this box and see whether Bobby is inside?’ Kasparov, more practically but no less neurotically, seemed to think that human grandmasters had intervened, possibly from a suite in the Michelangelo Hotel across the road, where members of both entourages had been put up. At this point, the Kasparov camp demanded access to Deep Blue’s game log: they wanted to see inside the box. IBM dithered, then finally released a few hundred pages of printouts showing Deep Blue’s calculations for the moves Kasparov had been most suspicious about. Kasparov wasn’t satisfied. Hsu contends that Kasparov had asked for access to the wrong moves; Deep Blue had rejected the obvious pawn capture because it had seen the potential pawn sacrifice a few moves earlier.
The match was seen as inconclusive. I’m not fit to judge, but the chess world needed a rematch. Deep Blue was dismantled and Hsu left IBM; the new chess machines were powered by PCs rather than supercomputers, but they were learning. Last year in Bahrain, Deep Fritz (no relation) drew with Vladimir Kramnik, the latest (fairly) new arrival. In deference to the sensibilities and paranoia of world champions, the full game log was published on the Internet, and the programmers were forbidden from tweaking the evaluation function during the match. Kasparov’s comeback, against Deep Junior, was originally to have taken place last summer in Jerusalem, in a gesture of solidarity with the Israeli people during a time of crisis. It was postponed until October, then December. In the meantime, Kasparov lost to the clearly not superannuated Karpov in a speed match in New York.
The publicised reasons for the delays included the deteriorating situation in Israel; the need to secure full international media involvement; the Jewish high holidays; and the required presence on Putin’s trip to China of Kirsan Ilyumzhinov, President of the autonomous republic of Kalmykia and of the original official chess body, FIDE. Plus the fact that Kasparov was being sued by the First International Bank of Israel for defaulting on a $1.6 million loan for the development of a venture called Kasparov Chess Online. In January, Kasparov’s attorney, Richard Conn of Latham and Watkins, contested the suit in a Delaware court. Conn is an excellent lawyer. He was one of the counsels acting on behalf of the Montrose Chemical Corporation in a Supreme Court action in 1993 brought by Montrose against their insurers, who had refused to cover them for costs arising from the environmental damage caused by their production (for export use only) of DDT. In his spare time, Conn is Chairman of the Legal Committee of the US-Russia Business Council. He gives speeches to foreign investors suffering from bad behaviour by Russian companies, and advocates co-operation and deal-making rather than legal redress. His principle is that everyone can be a winner. He won Kasparov’s case, and the Deep Junior match finally began at the end of January. Kasparov had learned his lesson and was dynamically himself, winning the first game after an aggressive opening innovation designed to mislead the machine, developed after extensive pre-match analysis of the program’s habits. Deep Junior fought back with impressively unmachinelike play and a few spectacular sacrifices. The match was drawn.