Ivars Peterson's MathTrek

## Greetings

Welcome to the first column in a weekly series devoted to "cool stuff" that I encounter while browsing the world of mathematics. I'll peek at new developments in mathematics and its applications, and I'll revisit old puzzles, famous problems, and historic events -- anything mathematical that happens to catch my eye. I hope you'll find something of value in these brief, informal forays into Mathland.

### Calculation and the Chess Master

As a spectator sport, championship chess lacks the bruising action of a professional basketball game and the spectacle of a football superbowl. It unfolds on a miniature, geometric battlefield at a leisurely, ordered pace, with each player moving a piece about every 3 minutes on average.

But there was no lack of drama in early February at the Pennsylvania Convention Center in Philadelphia when world chess champion Garry Kasparov took on the chess computer Deep Blue in a match of six games.

In a darkened hall, more than 400 spectators watched three giant screens showing the players (hidden away in a nearby room), the chessboard, and the analysis provided by a PC-based chess computer. They listened to a continuous stream of lively commentary from top chess players.

In this contest between man and machine, the four or more hours of a typical bout could pass remarkably quickly.

After a stunning loss in his first game, Kasparov adjusted his playing style to exploit weaknesses he had detected in the computer's play. He went on to win the second, fifth, and sixth games, while drawing the other two.

As one of the spectators at the last two games, I was left with a number of striking images of the confrontation: Kasparov hunched over the board, intently pondering his strategy. Kasparov crisply -- defiantly -- moving a piece, punching the clock, and briskly stepping out of the room to await the computer's response. Kasparov lounging in his chair, periodically checking his watch, and looking like a cat about to pounce on an unsuspecting mouse.

On the other side of the board sat a member of Deep Blue's team, watching the monitor connected via the Internet to the machine at IBM's Watson Research Center in Yorktown Heights, N.Y. The human's function was simply that of a messenger. Impassive, nearly expressionless, he noted the computer's choice, moved the piece, relayed Kasparov's response, and patiently awaited the next decision.

Even here, the human element played its part. The IBM team, advised by chess grandmaster Joel Benjamin, selected Deep Blue's suite of opening moves. The computer evaluated positions and potential moves according to recipes created by the team. And the group, not the computer, decided when to resign, accept a draw, or go for a win.

Inevitably, human error also intruded. In the second game, the computer failed to play the chosen opening because someone had stored the information in the wrong place. Several times, an operator pressed the incorrect key, and the whole program had to be restarted.

There were also minor, nagging irritations. On occasion, one of Deep Blue's messengers would fail to place a chess piece in the middle of its square, leaving it hanging to one side. Such sloppiness bothers top chess players. It creates an irresistible urge to right the piece or to get rid of it in some way.

So, this epic event was not so much a contest of man versus machine but of man versus men with machine -- a machine that calculates.

Indeed, there was a lot of talk about calculation on both sides of the chessboard.

Asked how many moves ahead he can think, Kasparov replied that it depended on the positions of the pieces. "Normally, I would calculate three to five moves," he said. "You don't need more.... But I can go much deeper if it is required." For example, in a position involving forced moves, it's possible to look ahead as many as 12 or 14 moves, he noted.

Combined with an extensive knowledge of chess and the sharp mind of a quick learner, this ability to calculate has allowed Kasparov to win or draw nearly every game that he has played during the last decade, whether against a human or a computer.

Deep Blue also looks ahead. For any arrangment of pieces, it considers all the possible moves it might make. For each of these moves, in turn, it puts itself in the place of its opponent and repeats the evaluation process. Step by repeated step, it searches deeper and deeper into the game, calculating from 50 to 100 billion chess positions within three minutes in a typical turn.

That's not nearly enough, however, to play a perfect game with a guaranteed outcome. In 1949, information theorist Claude Shannon estimated that there are about 10^120 possible 40-move games. To give you a sense of how enormous this number is: It dwarfs even the most generous estimates of the number of atoms in the universe. If each atom were replaced by a supercomputer, it would still be impossible to complete all the evaluations in preparation for a perfect game's first move.

The most unexpected things happen in the middle of a game, after a largely predictable sequence of opening moves and before the endgame when only a few pieces rule the chessboard and paths are relatively clear. It is in this muddled middle ground, with its explosion of possibilities, that humans excel and computers can lose their way.

Despite its record of three losses, two draws, and one win, Deep Blue performed remarkably well, impressing Kasparov and many other chess players with its proficiency in difficult situations.

"When I play chess, what I do is always try to reduce the number of mistakes," Kasparov remarked after his fifth game against Deep Blue. "I know I shouldn't go here or there. My intuition, my general knowledge [tells me]."

Simply by using what is essentially a brute force approach -- by searching deeply -- the machine also reduces its chances of making a mistake, of going the wrong way, Kasparov added.

He came back to this theme after his final victory. "What I do by just feeling that it's right or wrong ... [the] machine finds by just making these billions and billions of calculations," Kasparov said. In Deep Blue's great capacity to reduce the number of mistakes and, to a certain level, match human intuition, "I believe that ... I saw something similar to artificial intellect."

But it's the human element that gives meaning to this experiment. And human beings were the ones who lived the drama of the week-long chess match.

Most strikingly, Deep Blue served as a vehicle that allowed a team of engineers and computer scientists, with relatively modest chess knowledge and experience, to amplify their skills and play at the highest levels of the game.

Chung-Jen Tan, who managed the Deep Blue effort at IBM, commented to the audience (which included a large contingent of computer scientists attending an Association for Computing Machinery meeting) after the final game: "How many of you scientists here like us have a chance to play against Mr. Kasparov and actually beat him in a game?"

In 1912, J. B. Shaw wrote in the Bulletin of the American Mathematical Society: "The game of chess has always fascinated mathematicians, and there is reason to suppose that the possession of great powers of playing that game is in many features very much like the possession of great mathematical ability.... One has only to increase the number of pieces, to enlarge the field of the board, and to produce new rules which are to govern the pieces or the player, to have a pretty good idea of what mathematics consists."

Like a chess game, though infinitely more varied, mathematical research offers myriad choices and innumerable paths. Despite whatever help computers can provide in enumerating possibilities and in calculating prodigiously, it is human intuition, inspiration, experience, and knowledge that bring meaning to those endeavors.

### References:

Antonoff, Michael. "Curtains for Kasparov?" Popular Science, (March 1996): 42-46.
Goldsmith, Jeffrey. "The Last Human Chess Master." Wired, (February 1995).
Levy, David, and Monty Newborn. How Computers Play Chess. New York: W.H. Freeman, 1991.
Levy, David. Computer Gamesmanship: Elements of Intelligent Game Design. New York: Simon & Schuster, 1983.
Peterson, I. "Chess champion sinks Deep Blue's figuring." Science News, 149 (Feb. 24, 1996): 119.
Shaw, J. B. "What is Mathematics?" Bulletin of the American Mathematical Society, 18 (1912): 386-387.