Kasparov vs. DEEP BLUE: Computer Bites Human

J.  Popyack, Math/Comp Sci.

Mark this one down.  At 6:14 PM, Feb. 10, 1996, World Chess Champion Garry Kasparov, regarded by many as the greatest chess player in history, conceded defeat to DEEP BLUE, a chess-playing computer developed by a team of IBM scientists.  You’ll have to forgive your laptop computer if it steadfastly assigns this date and time to every document it creates from now on.  Better that than take a holiday the way we Americans do every July 4.  Truly, this was a landmark event in the history of computing.

I was fortunate enough to attend this opening round of the 6-game match as a technical advisor to William Macklin, who is covering the story for the Philadelphia Inquirer.  My press credentials afforded me entry to the room where the game itself was being played, somewhat removed from the ballroom where 700 paying customers gathered to witness the event.  There they were treated to televised feed from 3 cameras, plus live commentary from International Grandmaster Yasser Seirawan and Maurice Ashley, whose analyses were assisted by chess software FRITZ 4.0.  The match, sponsored by the Association for Computing Machinery, is being held under the auspices of the International Computer Chess Association.  The winner will take home $400,000 to the loser’s $100,000.

In the game room, Kasparov was faced by Feng-Hsuing Hsu, architect and principal designer of DEEP BLUE.  Dr. Hsu was seated next to a terminal connected to the machine.  The rate of play was 40 moves/player for the first two hours of each player’s time, during which this game was concluded.  Strict silence was mandated in the game room at all times, and so most of the press disappeared after the first 5 minutes.  I decided to stick around for a while.

Computer Chess Background:

Computer chess generally proceeds in three phases:  the opening moves can be played from a book of ‘best moves’ as the number of board configurations are relatively small; mid-game proceeds with the computer determining each move as though it is the first move of a brand-new game with a new board configuration to start with.  It does this by looking ahead as far as can be done reasonably within the time constraints, with a heuristic used to evaluate the board configurations that result.  Design of this heuristic and means of deciding when to quit looking in one direction and begin another are two of the difficult decisions that require the programmers to impart both intelligence and to some degree, their own personalities into the machine.  When the game has progressed to a point where few pieces remain, the endgame phase is reached, and predetermined sequences of moves may be employed to guide the machine.

DEEP BLUE Specifics:

DEEP BLUE maintains an opening game database of grandmaster games played in the last 100 years.  According to Hsu and team member Murray Campbell, with whom I spoke afterwards, mid-game is guided by a fairly straightforward Minimax procedure, with alpha-beta pruning and several enhancements.  Their evaluation function is quite complex, as is their means of terminating branches.  DEEP BLUE derives most of its power from its specialized hardware, designed specifically for playing chess: According to IBM online archives, there are 256 VLSI chess processors operating in parallel, which together can analyze roughly 50 billion chess positions in three minutes.  Random access memory has been designed precisely for representation of chessboards, determination of moves, evaluation of heuristics, etc.  When five chess pieces remain on the board, endgame scenarios are recalled from read-only memory.

Hsu also said that if two moves are scored equally, DEEP BLUE will choose the first one it finds.  In theory, this means that should DEEP BLUE lose a game, you should be able to beat it again by playing the same sequence of moves, because it will play the same moves in response.  In practice, however, this may not be the case.  First of all, since DEEP BLUE consists of many processors operating in parallel, its answers are not always determined in the same sequence.  Secondly, DEEP BLUE’s games against Kasparov are recorded into its opening game database.  At some point, it knows to stop repeating the same moves it made in a losing game.

The game:

Kasparov entered the room at 3 PM and the players began exchanging moves very quickly.  Kasparov’s tenth move took DEEP BLUE out of its book and the game began to slow down.  Two moves later, Kasparov left the room for 5 minutes, turned and viewed the board for another minute, then left again.  Seven minutes later he returned and moved his queen back one square.  DEEP BLUE’s next move, threatening Kasparov’s queen with a knight, caused the longest delay of the game.  Kasparov deliberated for 27 minutes before moving his queen again.  I decided to go into the public area and hear what was being said.

The commentary was excellent and informative.  Seirawan was frequently able to predict the next move for each player, while explaining the pros and cons.  Questions from the audience were entertained, answered, and debated.  A few other chess and computer chess experts were also brought to the stage.  I found I couldn’t concentrate on the game with all this talking, however, and went back to the game room at 4:30.

I was surprised to find the room practically deserted.  Besides Kasparov and Hsu, there were 3 cameramen, 1 official, 3 persons I decided were from Kasparov’s entourage, and me.  The tension and drama so pervasive in this room were hardly apparent to those watching the game in the ballroom.  Each player had made 24 moves, yet DEEP BLUE had 75 minutes remaining for its remaining 16 moves to Kasparov’s 41.  Kasparov was very animated – grimacing, fidgeting, and shaking his head from side to side.  He frequently left the table.  He showed unmistakable anguish after a quick exchange of rooks.

A few moves later, Kasparov deliberated for 12 minutes, then decided to advance a pawn that was already exposed.  His clock showed 25 minutes with 13 moves to go.  Apparently this move was quite unexpected by the experts.  Kasparov later said he was bluffing, which is not a good tactic when playing against a computer.  DEEP BLUE was left with an opening on which to base its attack.  On his 33rd move (with 7:24 remaining), Kasparov moved his remaining rook completely across the board to check DEEP BLUE’s king.  This move was mostly a desperate attempt to forestall DEEP BLUE’s own attack.  After moving its king to safety, DEEP BLUE checked Kasparov three times in succession.  At 6:14 PM, Kasparov reached across the table and shook Hsu’s hand, conceding the game.  After a short discussion, he left the room.

How to Beat DEEP BLUE:

To beat a computer at chess, you need to be able to see further ahead than it does.  Computers suffer from the ‘horizon effect’: due to time and space limitations, they can only look ahead a certain number of moves.  In effect, they can’t see beyond a limited horizon.  Most of the millions of moves they are able to generate and evaluate are truly worthless – to be complete however, they must be evaluated anyway.  This prevents the computer from focusing on ‘good moves’ only.  Through various enhancements, a good percentage of the ill-advised moves can be detected and ignored, but the horizon is only extended somewhat.  DEEP BLUE’s horizon is sufficiently distant to be able to beat highly rated players.  It shouldn’t make a mistake with short-term consequences, and it should be able to pounce on its opponent’s mistakes.  Kasparov needs to figure out how far it can see, then set a trap beyond the horizon.  DEEP BLUE will realize it is in danger long before reaching that point, however by then it maybe at a significant enough disadvantage that it won’t matter.

Kasparov did indeed beat DEEP BLUE in the second game after a restless night.  He blamed himself for not taking his opponent seriously enough in the first game.  From watching him closely, I would have to agree.  Most likely, he was surprised not to see any weaknesses displayed in DEEP BLUE’s moves.  Once he was better able to measure the horizon, he was able to construct a winning strategy.  Nevertheless, it was no cakewalk.  And there’s a lot more chess to be played.

NOTE: Tuesday’s and Wednesday’s games, the third and fourth in the series, ended in draws.  Kasparov won games five and six, and the match.