May 22, 2007

10th Anniversary: Deep Blue beat Gary Kasparov


Deep Bluevs.Kasparov


It's the one of those great moments in history that will be more avidly recalled a century from now. We are too early in the beginnings of the digital society yet, to appreciate the milestone. Here's my little commemoration piece to mark the event.

On May 11, 1997 for the first time a computer effected a series defeat to the highest ranked chess prodigy ever. There have been a lot of controversies and arguments ever since, but the fact remains - the machine beat the best available human for the very first time. At the time I was very troubled, wondering what this means for humanity.

Chess

You can skip this section if you know chess.

Chess is a board game played by two players, involving strategy and said to originated in India as chaturanga. The starting position of the chess board looks like the image below:

Chess Board

Each kind of piece on the board has it's own defined movement. For example, bishops move along the diagonals, rooks move along the rows and columns, and so on. The Opening - both players start with a handful of possible moves to place their pieces out into the board using a choice of defence and offence to exert their influence over the board. The number of variations in the moves grows along with the game's complexity. Then, the players approach conflict situations and start taking out each other's pieces - the Middlegame. They eventually approach a stage called the Endgame, where the outcome of the game is to be decided. Examples of these endgames used to be printed next to the crossword puzzles in most news publications for readers to solve.

Grandmasters

Chess at the professional level perhaps is one of the most intense exercises of the human brain. The World Chess Federation (FIDE) currenlty uses the Elo system to rank chess players from both past and present. Generally one must have an Elo rating above 2500 to be ranked a Grandmaster. Russian Gary Kasparov's highest Elo rating of 2851 is yet to be surpassed. Kasparov officially retired two years ago, and the current best ranked player is India's Viswanathan Anand (best Elo rating of 2803).

Grandmasters have the strategies and positions of hundreds if not thousands of games available in their minds. Some are capable of playing multiple players simultaneously in exhibition matches. Others are experts at playing games blindfolded, or rather without looking at the board.

The (Re)Match

The 1997 Deep Blue-Kasparov match was actually a re-match. The previous year, Kasparov had comprehensively beaten Deep Blue 4-2. IBM had wanted another go, and Kasparov sportily consented.

Kasparov won the first match satisfactorily, and commentators noted that the computer played like a computer - that is, making valid moves but not performing any long-term strategic manouvers. Score 1-0 to Kasparov. In the second game, Kasparov played 'passively' and did not launch any major move. This time Deep Blue seemed to have out-played Kasparov and he resigned, complimenting his opponent. Later, other grandmaster showed Kasparov that he had given up a game that was heading for a draw. Score 1-1. Games 3, 4 and 5 all ended in draws. Observers felt that Kasparov wasn't displaying his usual flair and seemed a bit sullen. Deep Blue team recieved quiet complements from Kasparov. Score: 2.5-2.5

Kasparov v Deep Blue

Then came the historic Game 6, which lasted less than 30 minutes. Here to everyone's astonishment Kasparov made a common error during the opening, which eventually led to a shock decisive loss. The famous score 3.5-2.5 to Deep Blue.

After the Match - Notes, Debates and Controversies

So are machines now really better than people at chess? Many people still think that it's not true and that this match hasn't proven anything yet.

Kasparov, was particularly concerned with Game 2, he was convinced that there's something fishy with the way the computer had suddenly been able to change strategy mid-game, as this was not what 'a computer is supposed to play like'. He did say that if the computer fairly won that match then the Deep Blue team should win a Nobel prize. Kasparov's requests for printouts of the computer's thought processes were not responded to by the Deep Blue team. Kasparov also felt that the event was turning from an experiment to a publicity stunt for IBM.

The Deep Blue machine was not a machine that was just taught the basic rules of chess and that could calculate up to the grandmaster level on its own. It used Neural Network programming to incorporate previously played games of chess and evaluate moves. Kasparov once said, "Sometimes the computer plays very human moves." It was trained by at least two known Grandmasters. I think of Deep Blue as human-trained Artificial Intelligence (AI). But then again, is it really AI or some supercomputer-based advanced calculator, without any actual cognition?

Another not-that-well-known fact is that in 1980, Professor Edward Fredkin, Carnegie Mellon University Computer Science Department, had set up a prize offer of $100,000 to the first computer to beat a world chess champion. IBM's Deep Blue team went home with that one.

Conclusion: let there be a real test

Viswanathan Anand summed it up best - "He had two options: to play like Kasparov or to play like 'Mr. Anti Deep Blue.' The former runs the risk of playing to the strengths of the machines, the latter that the human ends up as disoriented as the machine. Humans, too, play weaker in unfamiliar situations and though they may find their way around better, machines can compensate for that with brute force.

Kasparov chose the latter. Unfortunately, as a result, we were never able to see the fabulous calculating abilities of Deep Blue. Not once did we see a spectacular example of brute force producing a solution that differed significantly from that suggested by intuition."


Considering that Deep Blue could analyse 200,000,000 moves per second and Kasparov could only analyse 3, I still think it's quite amazing what the human mind can match with its 'intuition'. It also validates Chess as admissible arena for the Mind versus Machine encounter.

After the match IBM stowed away the computer, disbanded the Deep Blue and refused Kasparov's requests for a rematch. Kasparov retired in 2005, and these days he is devising strategies to take the Kremlin.

The Deep Blue - Kasparov type face-off needs to be repeated. Perhaps a corporation other than IBM can enter their supercomputing machine in an offical chess tournament, to play with other reigning chess grandmasters. Then we would really get the real picture. We could also get a peek at the levels machines have reached 10 years on, and if all those engineering specficiations, statistics and figures mean anything in human terms.

Footnote: My interest in chess

My father is a passionate chess player and he taught me the game early on. Every now and then we have an intense game, with my father mostly prevailing. I had joined a Chess club during my early school years. Come to think about it, it was an interesting setting - studying in an American-run school in communist Romania. The Karpov vs. Kasparov rivalry, with all the ideologies and politics mixed up in it was very entertaining. We also learned about the strange case of the troubled chess prodigy - the American, Bobby Fischer. We played against machines (those early Apple machines I talked about) as well as other members. Being a computer geek, I was more comfortable playing machines instead of people. I usually let people have it easier, whereas I was hard on the machines.

Some interesting sites to explore chess are:

2 comments:

V said...

A wonderful read!!
It's amazing that the "Kasparov Phenomenon" has remained unparallelled and chess has never been more popular than it was in the late 90's.
A very interesting aspect though that inspite of every aspect of the match having been recorded, no archived information is available as stated on the IBM webpage-
http://www.research.ibm.com/deepblue/

Did the makers of Deep Blue suddenly find they were out of storage room for the most significant event in the history of chess or..in this era they do not have the capable minds to put the event online for everyone to see and analyse.

monty said...

stuff chess now if you can make a computer that can compute and challange me to a game of tiddly winks that would be an eye opener, i mean so much calculations are involved from the laws of motion, to physics of projectile, to psychology of when i am go go for its main boards as it tries to beat me :P