Shall We Play A Game: The Story of Deep Blue

Sam Aisen is a student at the University of Southern California studying Computer Science (Games). He has been fascinated with games all his life and hopes to one day have a successful career in game development.

Abstract.

Deep Blue was a chess computer built by IBM in the late 20th century. Its development and victory against world chess champion Garry Kasparov was a landmark achievement in the field of computer science. The creation of a machine that had surpassed humanity’s ability to play chess well could only be possible through many years of rigorous research and development. Although Deep Blue’s inception began in 1987, people had already been working on developing chess computers for decades prior, with the idea of a chess-playing machine dating back to the 1700’s. Studying Deep Blue’s creation and its impact on the world can help us better understand How AI will affect our society.

Introduction.

AI has exploded as a topic of fascination throughout our society. While there are numerous benefits to the emerging applications of this technology, concerns are also widespread: what will AI mean to our lives? Fear of smart machines surpassing the human brain and conquering the human race, a staple of science fiction for centuries, is now more prominent than ever. As computers not only manage much of our society and most of our machines, AI can even create intriguing new works of art (DALL-E) and write excellent prose (Chat-GPT)! At this point, we can hardly avoid worrying about the impact of computers infringing on our work lives.

Figure 1: A starting chess board.

Chess, a game that has been popular for many centuries, has represented to its fans the most challenging and beautiful contest between human brains. The arrival of Bobby Fischer on the scene brought chess to the center of the global struggle between the USSR and the US. As the computer age arrived in the second half of the twentieth century, it seemed natural to consider the possibility that computers could master this ultimate test of human brain power. The story of the contest between a computer, IBM’s Deep Blue, and perhaps the greatest chess player in history, Garry Kasparov, captivated the world. It also brought many lessons on the capabilities and limitations of computers encroaching on and potentially surpassing human capabilities.

Creating a chess playing machine.

The idea of creating a machine that is capable of playing chess arose centuries before computers arrived on the scene. In the eighteenth century, “The Turk” was a famous demonstration of a machine that could beat humans at chess in the eighteenth century. Of course, this was only an elaborate trick, with a human hidden inside the “machine” making its moves.[1]

Figure 2: Cross section of the Turk. Public domain visual.

By the 1950s, computer scientists began to seriously consider the capabilities of computers in the game of chess. The fairly complex rules can be translated into computer code. The game has a strong quantitative element, with each piece having a numerical strength that facilitates the evaluation of chess positions. With sixteen pieces per side on a board of sixty-four squares, straightforward computation seems to be a substantial element to the game. Computers can calculate much faster and more accurately than people. Why couldn’t a computer be programmed to master this game and defeat even the strongest players?

But this was not as easy as it may have seemed. Even if a computer could be taught how to evaluate the relative advantage of chess position in order to select moves, a “brute-force” method, rating every possible position, overwhelms even today’s supercomputers. The number of possible positions in a chess game surpasses the number of atoms in the universe by many, many orders of magnitude. It is unlikely that any computer will ever be up to this task.[2]

How do humans manage this task? They take countless shortcuts. There are many strategies readily taught to chess students to narrow down (i.e., prune) the possible moves to those that merit consideration. Chess students know to “develop” pieces in the opening moves to increase their scope of action, to “control” the center of the chess board with pawns and pieces and to protect the king behind a wall of pawns. Effective early moves are taught as “openings” that can guide a player through the first ten or fifteen moves of a game. Certain strategies, such as creating open files and positioning rooks on the seventh row, are known to be powerful. Endgames, in which few pieces are left on the board, can be reduced to common configurations to guide move selection. Chess students need to learn all these methods to compete successfully.

Can computers be taught in a similar manner? Claude Shannon, a mathematician and computer scientist at Bell Labs, was an early pioneer in developing chess-playing computers. Shannon did not believe that a chess-playing computer would have any practical applications but was nonetheless convinced that the process of developing such a machine would yield theoretical advances in computer science. Shannon was the first to determine the number of possible moves in a chess game: 10120! He emphasized that processing power alone would be insufficient to master chess; pruning strategies to guide move selection would be essential.[2]

Feng-Hsiung Hsu, an undergraduate engineering student at Carnegie Mellon University, would eventually lead the Deep Blue development team. Hsu was drawn to the computer chess challenge. If he could succeed at this famous task, his career would likely be assured. Hsu’s ideas were different from conventional approaches. In contrast to the prevailing idea that a computer should assign an individual chip to evaluate each of the 64 squares on a chess board, Hsu felt that the evaluation of chess positions could be more efficiently accomplished by a single chip evaluating an entire board. Hsu’s approach proved advantageous in early tests of chess prowess.[3][4]

Figure 3: Chess chip used in Deep Blue. Adapted from [3].

However, raw computing power was still a key element in the computer chess effort. A chess game is so complex that a successful computer strategy must require many chips and processors working in parallel to assess positions and evaluate candidate moves. One student, or even a large academic team, would be limited in the hardware that could be afforded and assembled. Fortunately for Hsu, IBM, the leading computer manufacturer, recognized the potential commercial value of winning the race to build a computer to beat Kasparov. IBM was eventually proven correct; the company’s stock price soared after victory in Deep Blue’s second match– Hsu was then recruited to IBM.

IBM provided the computational power to achieve success. Each chess chip included hardware- and software-based routines achieving an evaluation function with over 8000 routines. The system used massively parallel processing, with a total of 480 chess chips on 30 processors. chips per processor. Pruning rules, for example, eliminating move choices that could have been reached earlier in a move tree, increased efficiency. Many strategies were derived from a large database of grandmaster games and grandmaster consultation.

Hsu was not himself a strong chess player. He knew the rules and played the game but did not understand chess at the grandmaster level. If a computer cannot win via brute force because there are too many potential positions to evaluate, the most successful human approaches to the game must be understood and incorporated into the design of a computer strategy. It was essential to recruit better players to the IBM effort. Joel Benjamin, a grandmaster, was recruited, and many other top players were consulted.[3]

Match 1, 1996. The match conditions were interesting. The time controls were standard for high-level tournament games: each player had 2 hours to make the first 40 moves. This amount of time to think might benefit a human since computers are so much faster at calculation. But the match was limited to 6 games, much shorter than a typical championship match. A brief match would seem to heavily favor the human by limiting fatigue, a major issue in chess but of no concern to the machine. Standard opening book play was fully programmed into Deep Blue, along with many other strategic guidance algorithms around positional and end-game play. But the programming teams did not have sufficient time to cover the huge number of strategic considerations familiar to grand masters.

In game 1, Deep Blue, with the advantage of playing white, triumphed. Interestingly, as is typical in human contests, immediately after the end of the game Kasparov asked Hsu (who made Deep Blue’s moves at the board) where he had made mistakes. Hsu, with his limited chess expertise, had no idea. Kasparov regained his confidence and did not lose another game. With the white pieces in game 2, Kasparov won. The next two games were drawn. Kasparov won games 5 and 6 to win the match.[1][3]

Match 2, 1997. Having protected the supremacy of humans in chess, why would Kasparov agree to a rematch? One might assume that additional grandmaster consultation and programming time would favor Deep Blue. But Kasparov had gained confidence after that first game and was paid generously for his participation. The Deep Blue team completed the strategic programming that was missing at the time of Match 1. They also studied, with their grandmaster consultants, all of Kasparov’s games between matches, allowing deeper programming focused on setting up positions that might draw Kasparov into misjudgments. In contrast, Deep Blue’s preparatory grandmaster games remained secret, limiting Kasparov’s ability to anticipate the computers evolving strategies.

Figure 4:Kasparov playing against Deep Blue in 1997. Image copyright Associated Press.

As in the first match, the first two games were won by the side playing the white pieces. Some have suggested that the first game, won by Kasparov, was determined by a bug in Deep Blue’s programming resulting in an unfortunate move selection prompted by the failure of the program to find a desirable option. In the second game, Deep Blue made some sophisticated moves involving positional gains at the cost of material advantage. Kasparov was disconcerted and eventually resigned though he had opportunities to force a draw. Kasparov could not believe that all moves in Game 2 could be made by a computer and he accused the Deep Blue team of cheating by making moves chosen by a grandmaster. No evidence of cheating was ever uncovered. After a draw in Game 3, Kasparov gained a strong position in Game 4 but was forced by time trouble (advantage, computer!) to rush his moves leading to another draw. After another draw in Game 5 the match was even going into the finale.

The final, deciding game was remarkable. Kasparov played some unusual moves to take Deep Blue out of its opening progression. Kasparov was aware that his moves could be refuted by a knight’s sacrifice that could ultimately leave his opponent in a winning position. He was confident that a computer would never sacrifice that much material in an opening outside its pre-programmed repertoire. But, with its fantastic speed and computational sophistication, Deep Blue found the knight sacrifice. Kasparov resigned, ending the shortest game in either match and leaving Deep Blue victorious.[1][3]

Chess Today. Throughout most of the twentieth century, strong chess players were confident they would never be challenged by a computer. Huge gains in computing power, allowing machines to evaluate 100,000 positions per second, suggested that this confidence might be misplaced. The first Kasparov-Deep Blue match raised the possibility of a computer win, and the second proved it. Today, commercial chess programs are substantially stronger than any human grandmaster. But just as with Deep Blue, these programs rely on extensive human experience in determining opening book and endgame moves, as well as positional guidelines for middle game move selection. In this sense, computer play might be considered to be somewhat hybrid. Conversely, all human players train extensively with computers, which is the main reason that today’s grandmasters are considered to be superior to historical champions. The best outcome arises from collaboration.

Some had predicted that computer superiority would dampen human enthusiasm for the game. But the opposite has occurred; the popularity of chess, supported by excellent online platforms and educational materials, has exploded. The website chess.com has over 100 million members, and hosts tens of millions of games per day. As in many other areas, computer chess and human chess are highly complementary.

Figure 5: Website Chess.com uses AI to evaluate plays.

The Future of AI. In recent years, there have been many discussions on the advancement of AI technology and its impact on society. As newly developed programs such as DALL-E and ChatGPT are able to accurately mimic human-made creative works with increasing quality, there is a growing sense of unease. Opponents of these programs argue that AI software poses a direct threat to the careers and livelihoods of artists, and that if left to continue to develop unmitigated, AI technology will inevitably lead to the end of art as whole.[5]

These fears of AI posing a threat to jobs draw many parallels to the public’s reactions to the games played between Deep Blue and Kasparov. Many were concerned about the implications of a machine surpassing humanity’s ability to play chess. These fears led to the majority of the public rooting for Kasparov in the “battle against the machine.”[3]

However, these fears have ultimately proven to be misplaced. While Deep Blue was ultimately victorious, and there have since been vast improvements in computer chess, the game still remains heavily popular among humans. Modern chess players see AI as an asset, not a threat.

It should also be noted that Kasparov himself is a vocal advocate for AI and new technology in spite of his defeat. He has stated that he believes that new technological developments such as AI benefit society and should be embraced, rather than feared. This directly contradicts the “man vs machine” narrative which dominated the media during his matches against Deep Blue.[6]

This history suggests that many concerns about AI in society are largely unnecessary. Similar to how modern chess engines are used to train players, it can be concluded that AI programs such as DALL-E and ChatGPT will become useful tools for creators, rather than replace them. This is not to say that there shouldn’t be regulations to prevent these technologies from being misused, only that such technologies should not be viewed with such fear that they are completely rejected. AI can enhance human achievement in every realm, including pure scientific research, recreation, the arts, healthcare and promoting quality of life for all. AI is yet another tool for humankind.

Keywords.

AI, ChatGPT, Chess, Computer Chess, Computer Science, DALL-E, Deep Blue, Games, Hsu, Kasparov, IBM, Shannon

References.

[1] J. Sharples, A cultural history of chess-players minds, machines, and Monsters. Manchester: Manchester University Press, 2017.

[2] C. E. Shannon, “Programming a computer for playing chess,” Computer Chess Compendium, pp. 2–13, 1988.

[3] F.-hsiung Hsu and J. Kleinberg, Behind deep blue: Building the computer that defeated the World Chess Champion. Princeton: Princeton University Press, 2022.

[4] M. Campbell, A. J. Hoane, and F.-hsiung Hsu, “Deep Blue,” Artificial Intelligence, vol. 134, no. 1-2, pp. 57–83, 2002.

[5] A. Gilead, “AI – opportunity or threat?,” Knight-Ridder/Tribune Business News, Tribune Content Agency LLC, Chicago, 2023.

[6] G. Kasparov, “Intelligent Machines Will Teach Us–Not Replace Us; Former world chess champion Garry Kasparov on the overblown fears about AI,” The Wall Street journal. Eastern edition, Dow Jones & Company Inc, New York, N.Y, 2018.

Abstract.

Introduction.

Creating a chess playing machine.

Further Reading.

Keywords.

References.

Similar Posts

Leave a Reply Cancel reply