Deep Blue (chess computer)

Last updated

Deep Blue, at the Computer History Museum Deep Blue.jpg
Deep Blue, at the Computer History Museum

Deep Blue was a chess-playing computer developed by IBM. It is known for being the first computer chess-playing system to win both a chess game and a chess match against a reigning world champion under regular time controls.

Computer chess Computer hardware and software capable of playing chess

Computer chess includes both hardware and software capable of playing chess. Computer chess provides opportunities for players to practice even in the absence of human opponents, and also provides opportunities for analysis, entertainment and training. Since around 2005, chess engines have been able to defeat even the strongest human players. Nevertheless, it is considered unlikely that computers will ever solve chess due to its computational complexity.

IBM American multinational technology and consulting corporation

International Business Machines Corporation (IBM) is an American multinational information technology company headquartered in Armonk, New York, with operations in over 170 countries. The company began in 1911, founded in Endicott, New York, as the Computing-Tabulating-Recording Company (CTR) and was renamed "International Business Machines" in 1924.

Contents

Deep Blue won its first game against a world champion on 10 February 1996, when it defeated Garry Kasparov in game one of a six-game match. However, Kasparov won three and drew two of the following five games, defeating Deep Blue by a score of 4–2. Deep Blue was then heavily upgraded, and played Kasparov again in May 1997. [1] Deep Blue won game six, therefore winning the six-game rematch 3½–2½ and becoming the first computer system to defeat a reigning world champion in a match under standard chess tournament time controls. [2] Kasparov accused IBM of cheating [3] and demanded a rematch. IBM refused and dismantled Deep Blue.

Garry Kasparov 20th and 21st-century Russian chess player and activist

Garry Kimovich Kasparov is a Russian chess grandmaster, former world chess champion, writer, and political activist, whom many consider to be the greatest chess player of all time. From 1986 until his retirement in 2005, Kasparov was ranked world No. 1 for 225 out of 228 months. His peak rating of 2851, achieved in 1999, was the highest recorded until being surpassed by Magnus Carlsen in 2013. Kasparov also holds records for consecutive professional tournament victories (15) and Chess Oscars (11).

Deep Blue versus Kasparov, 1996, Game 1

Deep Blue–Kasparov, 1996, Game 1 is a famous chess game in which a computer played against a human being. It was the first game played in the 1996 Deep Blue versus Garry Kasparov match, and the first time that a chess-playing computer defeated a reigning world champion under normal chess tournament conditions.

Deep Blue versus Kasparov, 1997, Game 6 Chess match between human and computer

Game 6 of the Deep Blue–Kasparov rematch, played in New York City on May 11, 1997 and starting at 3:00 p.m. EDT, was the last chess game in the 1997 rematch of Deep Blue versus Garry Kasparov.

Development for Deep Blue began in 1985 with the ChipTest project at Carnegie Mellon University. This project eventually evolved into Deep Thought, at which point the development team was hired by IBM. [4] The project evolved once more with the new name Deep Blue in 1989. Grandmaster Joel Benjamin was also part of the development team.

ChipTest was a 1985 chess playing computer built by Feng-hsiung Hsu, Thomas Anantharaman and Murray Campbell at Carnegie Mellon University. It is the predecessor of Deep Thought which in turn evolved into Deep Blue.

Carnegie Mellon University private research university in Pittsburgh, Pennsylvania, United States

Carnegie Mellon University (CMU) is a private research university based in Pittsburgh, Pennsylvania. Founded in 1900 by Andrew Carnegie as the Carnegie Technical Schools, the university became the Carnegie Institute of Technology in 1912 and began granting four-year degrees. In 1967, the Carnegie Institute of Technology merged with the Mellon Institute of Industrial Research to form Carnegie Mellon University. With its main campus located 3 miles (5 km) from Downtown Pittsburgh, Carnegie Mellon has grown into an international university with over a dozen degree-granting locations in six continents, including campuses in Qatar and Silicon Valley, and more than 20 research partnerships.

Deep Thought was a computer designed to play chess. Deep Thought was initially developed at Carnegie Mellon University and later at IBM. It was second in the line of chess computers developed by Feng-hsiung Hsu, starting with ChipTest and culminating in Deep Blue. In addition to Hsu, the Deep Thought team included Thomas Anantharaman, Mike Browne, Murray Campbell and Andreas Nowatzyk. Deep Thought became the first computer to beat a grandmaster in a regular tournament game when it beat Bent Larsen in 1988, but was easily defeated in both games of a two-game match with Garry Kasparov in 1989 as well as in a correspondence match with Michael Valvo.

Origins

The project was started as ChipTest at Carnegie Mellon University by Feng-hsiung Hsu, followed by its successor, Deep Thought. After their graduation from Carnegie Mellon, Hsu, Thomas Anantharaman, and Murray Campbell from the Deep Thought team were hired by IBM Research to continue their quest to build a chess machine that could defeat the world champion. [5] Hsu and Campbell joined IBM in autumn 1989, with Anantharaman following later. [6] Anantharaman subsequently left IBM for Wall Street and Arthur Joseph Hoane joined the team to perform programming tasks. [7] Jerry Brody, a long-time employee of IBM Research, was recruited for the team in 1990. [8] The team was managed first by Randy Moulic, followed by Chung-Jen (C J) Tan. [9]

Feng-hsiung Hsu is a computer scientist and the author of the book Behind Deep Blue: Building the Computer that Defeated the World Chess Champion. His work led to the creation of the Deep Thought chess computer, which led to the first chess playing computer to defeat grandmasters in tournament play and the first to achieve a certified grandmaster-level rating.

Thomas S. Anantharaman is a computer statistician specializing in Bayesian inference approaches for NP-complete problems. He is best known for his work with Feng-hsiung Hsu from 1985-1990 on the Chess playing computers ChipTest and Deep Thought at Carnegie Mellon University which led to his 1990 PhD Dissertation: "A Statistical Study of Selective Min-Max Search in Computer Chess". This work was the foundation for the IBM chess-playing computer Deep Blue which beat world champion Garry Kasparov in 1997.

Murray Campbell is a Canadian computer scientist.

After Deep Thought's 1989 match against Kasparov, IBM held a contest to rename the chess machine and it became "Deep Blue", a play on IBM's nickname, "Big Blue". [10] After a scaled-down version of Deep Blue, Deep Blue Jr., played Grandmaster Joel Benjamin, Hsu and Campbell decided that Benjamin was the expert they were looking for to develop Deep Blue's opening book, and Benjamin was signed by IBM Research to assist with the preparations for Deep Blue's matches against Garry Kasparov. [11]

Joel Benjamin is an American chess grandmaster. In 1998, he was voted "Grandmaster of the Year" by the U.S. Chess Federation. As of October 2012, his Elo rating was 2530, making him the No. 37 player in the U.S. and the 620th-highest rated player in the world.

Opening book is often used to describe the database of chess openings given to computer chess programs. Such programs are quite significantly enhanced through the provision of an electronic version of an opening book. This eliminates the need for the program to calculate the best lines during approximately the first ten moves of the game, where the positions are extremely open-ended and thus computationally expensive to evaluate. As a result it places the computer in a stronger position using considerably less resources than if it had to calculate the moves itself.

In 1995 "Deep Blue prototype" (actually Deep Thought II, renamed for PR reasons) played in the 8th World Computer Chess Championship. Deep Blue prototype played the computer program Wchess to a draw while Wchess was running on a personal computer. In round 5 Deep Blue prototype had the white pieces and lost to the computer program Fritz 3 in 39 moves while Fritz was running on an Intel Pentium 90  MHz personal computer. In the end of the championship Deep Blue prototype was tied for second place with the computer program Junior while Junior was running on a personal computer. [12]

World Computer Chess Championship (WCCC) is an event held periodically since 1974 where computer chess engines compete against each other. The event is organized by the International Computer Games Association. It is often held in conjunction with the Computer Olympiad, a collection of computer tournaments for other board games.

<i>Power Chess</i> chess-playing video game

Power Chess is a chess-playing video game originally released in September 1996 by Sierra Entertainment for the Microsoft Windows 95 operating system. Later revisions of the software were released as "Power Chess '98" and "Power Chess 2.0".

Personal computer Computer intended for use by an individual person

A personal computer (PC) is a multi-purpose computer whose size, capabilities, and price make it feasible for individual use. Personal computers are intended to be operated directly by an end user, rather than by a computer expert or technician. Unlike large costly minicomputer and mainframes, time-sharing by many people at the same time is not used with personal computers.

Design

Deep Blue employed custom VLSI chips to execute the alpha-beta search algorithm in parallel, [13] an example of GOFAI (Good Old-Fashioned Artificial Intelligence) rather than of deep learning which would come a decade later. It was a brute force approach, and one of its developers even denied that it was artificial intelligence at all. [14]

Deep Blue versus Kasparov

Deep Blue and Kasparov played each other on two occasions. The first match began on 10 February 1996, in which Deep Blue became the first machine to win a chess game against a reigning world champion (Garry Kasparov) under regular time controls. However, Kasparov won three and drew two of the following five games, beating Deep Blue by a score of 4–2 (wins count 1 point, draws count ½ point). The match concluded on 17 February 1996.

Deep Blue was then heavily upgraded (unofficially nicknamed "Deeper Blue") [15] and played Kasparov again in May 1997, winning the six-game rematch 3½–2½, ending on 11 May. Deep Blue won the deciding game six after Kasparov made a mistake in the opening, becoming the first computer system to defeat a reigning world champion in a match under standard chess tournament time controls.

The system derived its playing strength mainly from brute force computing power. It was a massively parallel, RS/6000 SP Thin P2SC-based system with 30 nodes, with each node containing a 120 MHz P2SC microprocessor, enhanced with 480 special purpose VLSI chess chips. Its chess playing program was written in C and ran under the AIX operating system. It was capable of evaluating 200 million positions per second, twice as fast as the 1996 version. In June 1997, Deep Blue was the 259th most powerful supercomputer according to the TOP500 list, achieving 11.38 GFLOPS on the High-Performance LINPACK benchmark. [16]

The Deep Blue chess computer that defeated Kasparov in 1997 would typically search to a depth of between six and eight moves to a maximum of twenty or even more moves in some situations. [17] David Levy and Monty Newborn estimate that one additional ply (half-move) increases the playing strength 50 to 70 Elo points. [18]

Kasparov in 1985 Kasparov Magath 1985 Hamburg-2.png
Kasparov in 1985

Deep Blue's evaluation function was initially written in a generalized form, with many to-be-determined parameters (e.g. how important is a safe king position compared to a space advantage in the center, etc.). The optimal values for these parameters were then determined by the system itself, by analyzing thousands of master games. The evaluation function had been split into 8,000 parts, many of them designed for special positions. In the opening book there were over 4,000 positions and 700,000 grandmaster games. The endgame database contained many six piece endgames and five or fewer piece positions. Before the second match, the chess knowledge of the program was fine tuned by grandmaster Joel Benjamin. The opening library was provided by grandmasters Miguel Illescas, John Fedorowicz, and Nick de Firmian. [19] When Kasparov requested that he be allowed to study other games that Deep Blue had played so as to better understand his opponent, IBM refused. However, Kasparov did study many popular PC games to become familiar with computer game play in general.[ citation needed ]

Writer Nate Silver suggests that a bug in Deep Blue's software led to a seemingly random move (the 44th in the first game of the second match) which Kasparov misattributed to "superior intelligence". [20] [21] Subsequently, Kasparov experienced a decline in performance due to anxiety in the following game. [21] Kasparov rejects this interpretation. [22]

Aftermath

Computer scientists believed that playing chess was a good measurement for the effectiveness of artificial intelligence, and by beating a world champion chess player, IBM showed that they had made significant progress. [23]

After the loss, Kasparov said that he sometimes saw deep intelligence and creativity in the machine's moves, suggesting that during the second game, human chess players had intervened on behalf of the machine, which would be a violation of the rules. IBM denied that it cheated, saying the only human intervention occurred between games. The rules provided for the developers to modify the program between games, an opportunity they said they used to shore up weaknesses in the computer's play that were revealed during the course of the match. Kasparov requested printouts of the machine's log files, but IBM refused, although the company later published the logs on the Internet. [24] Kasparov demanded a rematch, but IBM refused and dismantled Deep Blue. [25] Owing to an insufficient sample of games between Deep Blue and officially rated chess players, a chess rating for Deep Blue was not established.[ citation needed ]

In 2003 a documentary film was made that explored these claims. Entitled Game Over: Kasparov and the Machine , the film interviewed some people who suggest that Deep Blue's victory was a ploy by IBM to boost its stock value. [25]

One of the cultural impacts of Deep Blue was the creation of a new game called Arimaa designed to be much more difficult for computers than chess. [26]

One of the two racks that made up Deep Blue is on display at the National Museum of American History in their exhibit about the Information Age; [27] the other rack appears at the Computer History Museum in the "Artificial Intelligence and Robotics" gallery of the Revolution exhibit. [28] Reports that Deep Blue was sold to United Airlines appear to originate from confusion between Deep Blue itself and other RS6000/SP2 systems. [29]

Feng-hsiung Hsu later claimed in his book Behind Deep Blue that he had the rights to use the Deep Blue design to build a bigger machine independently of IBM to take Kasparov's rematch offer, but Kasparov refused a rematch. [30]

Deep Blue, with its capability of evaluating 200 million positions per second, was the fastest computer to face a world chess champion. Today, in computer-chess research and matches of world-class players against computers, the focus of play has often shifted to software chess programs, rather than using dedicated chess hardware. Modern chess programs like Houdini, Rybka, Deep Fritz or Deep Junior are more efficient than the programs during Deep Blue's era. In a November 2006 match between Deep Fritz and world chess champion Vladimir Kramnik, the program ran on a computer system containing a dual-core Intel Xeon 5160 CPU, capable of evaluating only 8 million positions per second, but searching to an average depth of 17 to 18 plies in the middlegame thanks to heuristics; it won 4–2. [31] [32]

See also

Related Research Articles

Brains in Bahrain was an eight-game chess match between World Chess Champion Vladimir Kramnik and the computer program Deep Fritz 7, held in October 2002. The match ended in a tie 4-4, with two wins for each participant and four draws.

Junior is a computer chess program written by the Israeli programmers Amir Ban and Shay Bushinsky. Grandmaster Boris Alterman assisted, in particular with the opening book. Junior can take advantage of multiple processors, taking the name Deep Junior when competing this way in tournaments.

Arimaa is a two-player strategy board game that was designed to be playable with a standard chess set and difficult for computers while still being easy to learn and fun to play for humans. Since 2004, the Arimaa community has held three annual tournaments: a World Championship, a Computer Championship, and the Arimaa Challenge. In 2015, the challenge was won decisively by the computer, with top players agreeing that computers had become better at the game than humans. As it was a prerequisite for the prize to be awarded, Wu published a paper describing the algorithm and most of ICGA Journal Issue 38/1 was dedicated to this topic. The algorithm combined traditional alpha–beta pruning with heuristic functions manually written while analysing human expert games.

In computer chess, a chess engine is a computer program that analyzes chess or chess variant positions, and generates a move or list of moves that it regards as strongest. A chess engine is usually a back end with a command-line interface with no graphics nor windowing. Engines are usually used with a front end, a windowed graphical user interface such as Chessbase or WinBoard that the user can interact with via a keyboard, mouse or touchscreen. This allows the user to play against multiple engines without learning a new user interface for each, and allows different engines to play against each other. Over the last years, there are chess engines available for mobile phones and tablets, which makes their usage easier. The list includes chess engines like Stockfish, Komodo, Texel, Bagatur and many others. For more information about the chess engines available for Android visit Google Play.

Fritz is a German chess program originally developed for Chessbase by Frans Morsch based on his Quest program, ported to DOS, and then Windows by Mathias Feist. With version 13, Morsch retired, and his engine was first replaced by Gyula Horvath's Pandix, and then with Fritz 15, Vasik Rajlich's Rybka.

<i>Game Over: Kasparov and the Machine</i> 2003 documentary film directed by Vikram Jayanti

Game Over: Kasparov and the Machine is a 2003 documentary film by Vikram Jayanti about the match between Garry Kasparov, the highest rated chess player in history and the World Champion for 15 years (1985–2000), and Deep Blue, a chess-playing computer created by IBM. It was coproduced by Alliance Atlantis and the National Film Board of Canada.

Deep Blue versus Garry Kasparov Chess matches between Deep Blue and Kasparov

Deep Blue versus Garry Kasparov was a pair of six-game chess matches between world chess champion Garry Kasparov and an IBM supercomputer called Deep Blue. The first match was played in Philadelphia in 1996 and won by Kasparov. The second was played in New York City in 1997 and won by Deep Blue. The 1997 match was the first defeat of a reigning world chess champion by a computer under tournament conditions.

Anti-computer tactics are methods used by humans to try to beat computer opponents at various games, especially in board games such as chess and Arimaa. It often involves playing conservatively for a long-term advantage that the computer is unable to find in its game tree search. This will frequently involve selecting moves that appear sub-optimal in the short term in order to exploit known weaknesses in the way computer players evaluate positions.

This article documents the progress of significant human–computer chess matches.

Computer Arimaa refers to the playing of the board game Arimaa by computer programs.

References

  1. "IBM's Deep Blue beats chess champion Garry Kasparov in 1997". NY Daily News. Retrieved 3 August 2017.
  2. Saletan, William (11 May 2007). "Chess Bump: The triumphant teamwork of humans and computers". Slate. Archived from the original on 13 May 2007.
  3. Hsu, Feng-Hsiung (2004). Behind Deep Blue: Building the Computer that Defeated the World Chess Champion (revised ed.). Princeton University Press. p. Preface page x. ISBN   9780691118185.
  4. "A Brief History of Deep Blue, IBM's Chess Computer". 29 July 2017. Retrieved 3 August 2017.
  5. Hsu 2002, pp.92–95
  6. Hsu 2002, p.107
  7. Hsu 2002, p.132
  8. IBM. "Deep Blue – Overview". IBM Research. Archived from the original on 12 December 2008. Retrieved 19 August 2008.
  9. Hsu 2002, p.136
  10. Hsu 2002, pp.126–127
  11. Hsu 2002, pp.160–161, 174, 177, 193
  12. Deep blue had white and lost to Fritz in 39 moves Archived 7 October 2008 at the Wayback Machine
  13. Hsu, Feng-hsiung; Campbell, Murray (1995). "Deep Blue System Overview" (PDF). Proceedings of the 9th international conference on Supercomputing. ACM. pp. 240–244.
  14. Press, Gil (7 February 2018). "The Brute Force of IBM Deep Blue And Google DeepMind". forbes.com. Retrieved 12 May 2018.
  15. IBM Research Game 2 Archived 19 October 2007 at the Wayback Machine , Deep Blue IBM
  16. TOP500 Super Computer List – June 1997 (201–300) Archived 13 February 2009 at the Wayback Machine Top500.org
  17. Campbell 1998, p. 88.
  18. Levy & Newborn 1991, p. 192
  19. Weber, Bruce (18 May 1997). "What Deep Blue Learned in Chess School". The New York Times. ISSN   0362-4331 . Retrieved 4 July 2017.
  20. Roberts, Jacob (2016). "Thinking Machines: The Search for Artificial Intelligence". Distillations. 2 (2): 14–23. Retrieved 22 March 2018.
  21. 1 2 Plumer, Brad (26 September 2012). "Nate Silver's 'The Signal and the Noise'". Washingtonpost.com. Archived from the original on 9 November 2012. Retrieved 5 January 2014.
  22. https://lccn.loc.gov/2017304768
  23. Greenemeier, Larry. "20 Years after Deep Blue: How AI Has Advanced Since Conquering Chess". Scientific American. Retrieved 29 June 2018.
  24. Deep Blue the Match Replay the games. IBM.
  25. 1 2 'Game Over' : Did IBM Cheat Kasparov? Archived 12 October 2007 at the Wayback Machine , by Mark Weeks, About.com, June 2005.
  26. Deep Blue Cultural Impacts. Archived 30 March 2014 at the Wayback Machine IBM.
  27. "Deep Blue Supercomputer Tower". National Museum of American History. Retrieved 1 February 2019.
  28. Deep Blue II. Archived 3 July 2013 at the Wayback Machine Computer History Museum collections database. Retrieved 10 January 2014.
  29. "Deep Blue Skies: Ibm Helps Airline". Orlando Sentinel. 7 December 1997. Archived from the original on 11 May 2013.
  30. "Owen Williams replies to Feng-hsiung Hsu". The Week in Chess. 13 January 2000. Archived from the original on 29 July 2012. Retrieved 11 May 2012
  31. "The last match man vs machine?". English translation of Spiegel Article. ChessBase. 23 November 2006. Archived from the original on 16 October 2012.
  32. "Chess champion loses to computer". BBC News. 5 December 2006. Archived from the original on 31 December 2007. Retrieved 4 May 2008.

Bibliography

Further reading