Deep Blue and What Beating Kasparov Proved

On 11 May 1997 Deep Blue beat Garry Kasparov 3½-2½ in a six-game match in New York. The machine had no learning component, no general reasoning and no capability outside chess, and IBM dismantled it shortly afterwards. What the match demonstrated was a fact about chess and about search, and it took nineteen more years to find out how narrow that fact was. Two matches, and which one people mean There were two, and conflating them is the commonest error. | Match | Description | |---|---| | Philadelphia, February 1996 | Kasparov won 4-2. Deep Blue won game 1 - the first time a computer beat a reigning world champion in a game at classical time controls - and then lost the match. This is the game people are thinking of when they misremember 1996 as the year. | | New York, May 1997 | Deep Blue won 3½-2½. Kasparov won game 1; Deep Blue won games 2 and 6; games 3, 4 and 5 were drawn. The final game lasted nineteen moves. | Game 6 is worth knowing because it is not the epic the result implies. Kasparov played the Caro-Kann Defence and, on move seven, allowed a knight sacrifice on e6 that is a known motif in that line - a published trap rather than a discovery. His position was strategically lost within a dozen moves and he resigned on move 19. By his own later account he was not in a fit state to play, and the deciding game of the most famous match in computer chess history was decided by opening preparation and human exhaustion rather than by deep calculation. What the machine was Deep Blue’s lineage runs from ChipTest, built by Feng-hsiung Hsu at Carnegie Mellon from the mid-1980s, through Deep Thought, which in 1988 became the first program to beat a grandmaster in a tournament game and which lost 2-0 to Kasparov in 1989. Hsu, Murray Campbell and Thomas Anantharaman moved to IBM, and the project became Deep Blue. The 1997 machine, as reported by its builders: - An IBM RS/6000 SP with 30 processor nodes, each carrying custom chess accelerator chips - 480 of them in total - that performed move generation and position evaluation in hardware. - Roughly 200 million positions evaluated per second, searching typically to a depth of a dozen or so plies, and much deeper along forcing lines. - An evaluation function with thousands of tunable terms, whose weights were set by hand and by fitting to grandmaster games - not learned in any sense a modern reader would recognise. - An opening book prepared by grandmasters. Joel Benjamin, Miguel Illescas, John Fedorowicz and Nick de Firmian worked on the machine’s preparation, including tuning it against Kasparov specifically between games. This is the part IBM was least forthcoming about at the time and it is central to the controversy that followed. - Endgame tablebases giving perfect play for all positions with five or fewer pieces on the board. Kasparov, for comparison, calculated on the order of a few positions per second. The machine was doing something roughly a hundred million times more numerous and enormously less selective, and the two approaches came out within a game of each other over six games. That ratio is the actual scientific content of the match. Shannon’s 1950 taxonomy, and which type won Claude Shannon’s 1950 paper Programming a Computer for Playing Chess set the framework the whole field then worked within, and it contains the prediction that turned out backwards. Shannon distinguished two strategies: | Shannon's strategies | Description | |---|---| | Type A | Examine every legal continuation to a fixed depth, evaluate the leaves, take the minimax. Shannon judged this hopeless on the hardware of 1950 and on any hardware he anticipated, because the tree grows by a factor of roughly 30 per ply. | | Type B | Examine only plausible moves, as a human does, pruning the tree with chess knowledge before searching it. Shannon considered this the promising direction and the one that would be needed for strong play. | Deep Blue is a Type A program. It has selective extensions and it has alpha-beta pruning, which is provably safe rather than knowledge-based, but its fundamental strategy is to look at nearly everything and look at it very fast. The approach that the founding paper of computer chess judged a dead end is the approach that beat the world champion, and the approach it recommended - encode human chess understanding to avoid brute force - is the one that stalled for forty years. Shannon also estimated the game-tree complexity of chess at around 10120, a figure now known as the Shannon number. That estimate has not moved and it is the reason chess remains unsolved in the game-theoretic sense. Deep Blue did not solve chess. It played it better than the best human, which is an entirely different achievement. The move in game one In the first game of the 1997 match, in a position Deep Blue was losing, the machine played a rook move on move 44 that made no apparent sense. Kasparov, by his own account, could not construct an explanation for it other than that the machine was seeing something very deep, and he has said this affected how he played the rest of the match. Murray Campbell has since said publicly - the account is reported at length in Nate Silver’s The Signal and the Noise (2012) - that the move was the result of a bug: the machine failed to select a move within its time allocation and fell back to a default, which selected essentially at random. On this account the most psychologically important move of the match was a defect. This is a claim by one participant, reported by a journalist fifteen years later, and it is not independently verifiable from the match record. It is included because it is well attested and widely discussed, and flagged because a page about historical accuracy should not present a single-source recollection with the same confidence as the score of the match. The related and better-documented controversy is about transparency. Kasparov asked for the machine’s logs during the match and did not receive them at the time; IBM published them afterwards. He asked for a rematch and IBM declined, dismantling the machine instead. His settled position, stated in Deep Thinking (2017), is that he lost fairly and that he handled the match badly - a more generous account than the one he gave in 1997. What it proved, precisely - Proved: that in a domain with perfect information, a compact set of legal moves and an evaluation function that a human can write down, sufficient search depth beats the best human pattern-recognition. This is a real and non-obvious result. - Proved: that special-purpose hardware buys search depth, and that search depth converts to playing strength at a fairly predictable rate - roughly a fixed rating gain per additional ply, which was measurable across the machine’s generations. - Did not prove: that chess-playing ability indicates general intelligence. It demonstrated the reverse, and this is the important result of the whole exercise. The field had chosen chess in the 1950s precisely because it was assumed that anything strong enough to play chess would have to be intelligent generally. Deep Blue falsified that assumption. It could not be adapted to play any other game. - Did not prove: that the approach generalises to other games. Go has a branching factor around ten times larger and no compact evaluation function anybody could write, and it resisted for another nineteen years until a completely different method arrived. - Did not prove: that brute force beats knowledge. Deep Blue was full of chess knowledge - thousands of hand-written evaluation terms, a grandmaster-prepared opening book, perfect endgame tables. It is a hybrid, and describing it as pure brute force flatters the search and erases the four grandmasters. The philosopher of AI Drew McDermott made the most-quoted argument on the other side at the time - I am paraphrasing rather than quoting - which was that saying Deep Blue does not really think about chess is like saying an aeroplane does not really fly because it does not flap its wings. That objection is a good one and it does not rescue the generality claim: an aeroplane really does fly, and Deep Blue really did play chess, and neither can do anything else. What happened to computer chess afterwards Chess engines kept improving without any of the fanfare. Within about a decade, programs running on ordinary personal computers were stronger than Deep Blue, because the search techniques improved faster than the hardware did. By the 2010s the strongest engines were far beyond any human and the question had stopped being interesting. Then in December 2017 DeepMind’s AlphaZero learned chess from the rules alone by self-play and reached a level competitive with the strongest hand-engineered engine of the day, searching a tiny fraction of the positions per second. Two years later the leading open-source engine had incorporated a neural evaluation function of its own. The final state of computer chess is therefore a hybrid: alpha-beta search in the Deep Blue tradition, with the hand-written evaluation replaced by a learned one. Neither of the two 1997 positions won outright. Top comments (0)