- Shopping Bag ( 0 items )
Ships from: Boonsboro, MD
Usually ships in 1-2 business days
Ships from: Montgomery, IL
Usually ships in 1-2 business days
Ivars Peterson's first article appeared on MAA On-line on February 26, 1996, on the chess match between world champion Garry Kasparov and chess computer Deep Blue. Since then he has written more than 250 articles on a wide range of topics in mathematics and its applications, along with a glance at old puzzles, famous problems, and historic events-anything mathematical that happens to catch his eye. There is something here for everyone, from the professional mathematician, to the student who enjoys doing mathematics, to the lay person who has interest in things mathematical.
Calculation and the Chess Master
As a spectator sport, championship chess lacks the unrelenting action of a basketball game and the bruising spectacle of a football superbowl. It unfolds at a seemingly sedate pace in an orderly manner on a miniature, geometric battlefield. In a typical tournament, a chess player moves a piece about once every 3 minute. Games can last as long as 7 hours.
Nonetheless, there was no lack of drama when world chess champion Garry Kasparov took on a chess computer deep Blue in a six-game match in early February 1996. More than 400 spectators jammed a darkened hall at the Pennsylvania Convention Center in Philadelphia to watch three giant screens that displayed the players and the chessboard. A continuous stream of lively commentary from top chess players added to the excitement. The combatants themselves were squirreled away in a nearby room, shielded from direct contact with the audience.
Deep Blue furnished the initial shock. In the first game of the match, the computer, playing with the advantage of white pieces, mounted a relentless attack on Kasparov's pieces, forcing the Russian grandmaster to resign on the 37th move. It was Kasparov's first loss ever to a computer under official tournament rules. Spurred by the unexpected defeat, Kasparov adjusted his playing style to exploit weaknesses he had detected in the computer's play. He recovered and went on to win the second, fifth, and sixth games, while drawing the other two.
As an observer at the final two games, I was lest with a number of striking images of the confrontation: Kasparov hunched over the chessboard, intently pondering his strategy. A weary Kasparov cradling his face in his cupped hands, Kasparov crisply-defiantly-moving a piece, punching the clock and briskly striding 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, who was watching the monitor connected via the Internet to the chess computer at IBM's Thomas J. Watson Research Center in Yorktown heights, N.Y. the person'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 a part. The IBM team, advised by chess grandmaster Joel Benjamin, selected Deep Blue's suite of opening moves for each game. 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 intruded. In the second game, the computer failed to play the chosen opening because someone had inadvertently stored the information in the wrong place. The computer had to improvise its own opening. Operators sometimes made typing errors when entering moves or failed to carry out the computer's instructions correctly. On one occasion, incorrect input data caused the computer to freeze at a crucial moment in the game, and the program had to be started up all over again.
Expert chess players viewing the games were bothered by another sort of sloppiness. They cringed whenever one of Deep blue's messengers failed to position a piece right in the middle of its square on the chessboard.
The epic event was not so much a contest of man versus machine as a contest of man versus man with a machine that calculates. Indeed, there was much talk about calculation on both sides of the chessboard. Chess is a game of simple rules and relatively few pieces. There are no undefined elements and there is no room for chance. The game owes its depth and complexity to its immense number of possible moves.
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." In a position involving forced moves, for example, 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, Kasparov's ability to calculate, or look ahead, allowed him to win or draw nearly every game that he ever played, whether against a human or a computer.
Deep Blue also looked ahead. For any arrangement of pieces, it considered all the possible moves it might make. For each of these moves in turn, it put itself in the place of its opponent and repeated the evaluation process. Step by step, it searched deeper and deeper into the game, calculating from 50 billion to 100 billion chess positions within 3 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 were about 10120 possible 40-move games. This number is so large that 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.
In chess, the most unexpected actions 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 n his muddled middle ground, with its explosion of possibilities, that human excel and computers 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]." Simple by using what is essentially a brute-force approach-by searching deeply- the machine also reduces its chances of making a mistake and of going the wrong way, Kasparov added.
He came back to this theme and of going the wrong way 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 minimize its mistakes and, to a certain level, match human intuition, "I believe that… I saw something similar to artificial intellect," he remarked.
However, the human element is what gives meaning to the Deep Blue experiment. Humans, not computers, experienced 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, who had relatively modest chess knowledge and experience, to amplify their skills and play at the highest level of the game.
After the final 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; "How may of you scientists here like us have a chance to play against Mr. Kasparov and actually beat him in a game?"
Chess has long appealed to mathematicians and computer scientists. "The problem is sharply defined, both in the allowed operations (the moves of chess) and in the ultimate goal (checkmate)," Shannon wrote in a 1950 essay. "It is neither so simple as to be trivial nor too difficult for satisfactory solutions." Investigating the chess-playing problem represents an attractive avenue for developing problem-solving techniques that can be used for more practical applications, Shannon noted.
Taking a broader perspective, mathematician J.B. Shaw wrote in 1912 in the Bulleting of the American Mathematical Society: "The game of chess has always fascinated mathematicians, and there is reason to suppose that he 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 calculating prodigiously, it is human intuition, inspiration, experience, creativity, and knowledge that bring meaning to those endeavors.
The 1997 rematch between world chess champion Garry Kasparov and the IBM chess computer Deep Blue had a different outcome. Indeed, the end came sooner than anyone expected. In the final game of a six-game match, Kasparov resigned abruptly after just 19 moves, giving Deep Blue the win. It was the first tournament Kasparov had ever lost to any opponent, human or computer, since he became champion.
In the 1996 bout with Deep Blue, Kasparov won by outmaneuvering the computer and exploiting weaknesses in its play. The Deep Blue team come better prepared for the 1997 rematch. The researchers had made the computer more powerful, added chess knowledge, and developed a program that allowed them, between games, to change crucial parameters governing play. The programmers also gave the computer sufficiently sensitive evaluation function so that it could distinguish between certain chess position subtleties that previously had been out of reach.
Nonetheless, the computer had limitations. In the pivotal second game, which Deep Blue won, Kasparov overlooked a sequence of moves that would have forced a draw. Interestingly Deep Blue also failed to detect the sequence. Chess experts later noted that the computer missed several moves earlier in the game that would have assured a quicker victory.
Kasparov's apparent loss of confidence- a decidedly human weakness- probably decided the match. Analysis of the games show that Kasparov was still arguably the better chess player. What shocked many observers was Kasparov's abrupt psychological collapse at the end.