Deep Blue (chess computer)

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.

This article is part of the series on
Chess programming
Board representations
0x88
Bitboards
Chess computers
Belle
Deep Blue
Chess engines
Fritz
GNU Chess
Leela Chess Zero
Stockfish
One of 2 racks of Deep Blue, at the Computer History Museum

Development for Deep Blue began in 1985 with the ChipTest project at Carnegie Mellon University; Grandmaster Joel Benjamin was part of the development team. IBM hired the development team when the project was briefly given the name Deep Thought. In 1989 it was renamed Deep Blue.

Deep Blue won its first game against world champion Garry Kasparov in game one of a six-game match on 10 February 1996. However, Kasparov won three and drew two of the following five games, defeating Deep Blue by a score of 4–2. Deep Blue was heavily upgraded before playing against Kasparov again in May 1997. Deep Blue won game six, thereby 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. Kasparov accused IBM of cheating.

Origins

The project started under the name ChipTest at Carnegie Mellon University by Feng-hsiung Hsu and was followed by ChipTest’s successor, Deep Thought.[1] After graduating the university, Hsu, Thomas Anantharaman, and Murray Campbell were asked by IBM Research to continue their project to build a chess machine that could defeat a world champion.[2] Hsu and Campbell joined IBM in fall 1989, with Anantharaman following later.[3] Anantharaman subsequently left IBM for Wall Street and Arthur Joseph Hoane joined the team to perform programming tasks.[4] Jerry Brody, a long-time employee of IBM Research, was recruited to the team in 1990.[5] The team was first managed by Randy Moulic, followed by Chung-Jen (C J) Tan.[6]

After Deep Thought's 1989 match against Kasparov, IBM held a contest to rename the chess machine: the winning name was "Deep Blue", a play on IBM's nickname, "Big Blue".[7] After a scaled-down version of Deep Blue—Deep Blue Jr.—played Grandmaster Joel Benjamin,[8] 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.[9]

In 1995 "Deep Blue prototype" played in the 8th World Computer Chess Championship. The Deep Blue prototype played Wchess to a draw. In round 5, Deep Blue prototype played as White and lost to Fritz.[10]

Design

Deep Blue used custom VLSI chips to execute the alpha-beta search algorithm in parallel,[11] 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 search approach, and one of its developers even denied that it was artificial intelligence.[12][13]

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.[14] 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.[15]

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 system determined the optimal values for these parameters 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 program's chess knowledge was fine-tuned by grandmaster Joel Benjamin. The opening library was provided by grandmasters Miguel Illescas, John Fedorowicz, and Nick de Firmian.[16] 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 studied many popular PC games to become familiar with computer gameplay in general.[17]

Deep Blue takes an approach using the opening information in its database. It creates an additional database called the “extended book.” The extended book summarizes previous Grandmaster games in any of the several million opening positions in its game database. The system can combine its big searching ability (200 million chess positions per second) with the summary information in the extended book to select opening moves.[18]

Deep Blue versus Kasparov
Main article: Deep Blue versus Garry 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 as 1 point, draws count as a ½ point). The match concluded on 17 February 1996.[19]

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

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

Kasparov in 1985

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".[25][26] Subsequently, Kasparov experienced a decline in performance due to anxiety in the following game,[26] though he rejects this interpretation.[27]

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.[28][29] and demanded a rematch, who refused and dismantled Deep Blue.[30] The rules allowed 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.[31]

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.[32] Kasparov called Deep Blue an "alien opponent" but later stated that "It was as intelligent as your alarm clock".[33] According to Martin Amis, two grandmasters who played Deep Blue agreed with each other that "It's like a wall coming at you".[34][35]

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

One of the cultural impacts of Deep Blue was the creation of a new game called Arimaa, which was designed to be much more difficult for computers than chess.[37] Computers proved capable of defeating strong Arimaa players in 2015.[38]

One of the two racks that made up Deep Blue is on display at the National Museum of American History's exhibit about the Information Age;[39] the other rack is displayed at the Computer History Museum in the Revolution exhibit's "Artificial Intelligence and Robotics" gallery.[40] Deep Blue was mistakenly reported to be sold to United Airlines as it was confused with other RS6000/SP2 systems systems.[41]

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.[42]

Deep Blue, with its capability of evaluating 200 million positions per second, was the first and 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 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.[43][44]

gollark: I think just making kristpay send back to the return address in the meta would work, assuming there is one.
gollark: Couldn't you fix it?
gollark: It has a `ps` command, which takes arguments really unsafely (they're just passed to `system`), so you can do `ps ; sh -c`.
gollark: I do have a router lying around somewhere which allows root access to anyone who knows the password, because of an exploit I discovered while just fiddling around with its telnet interface.
gollark: Hmm, PotatOS on Routers? Interesting idea.

See also

References
  1. Warwick, Kevin (29 July 2017). "A Brief History of Deep Blue, IBM's Chess Computer". Mental Floss. Retrieved 3 August 2017.
  2. Hsu 2002, pp. 92–95
  3. Hsu 2002, p. 107
  4. Hsu 2002, p. 132
  5. IBM. "Deep Blue – Overview". IBM Research. Archived from the original on 12 December 2008. Retrieved 19 August 2008.
  6. Hsu 2002, p. 136
  7. Hsu 2002, pp. 126–127
  8. "Joel Benjamin playing a practice game with Deep Blue | Mastering the Game | Computer History Museum". www.computerhistory.org. Retrieved 17 February 2020.
  9. Hsu 2002, pp. 160–161, 174, 177, 193
  10. "8th World Computer Chess Championship". ICGA Tournaments. Archived from the original on 7 October 2008. Retrieved 4 June 2020.
  11. Hsu, Feng-hsiung; Campbell, Murray (1995). "Deep Blue System Overview" (PDF). Proceedings of the 9th International Conference on Supercomputing. ACM. pp. 240–244. Archived from the original on 17 October 2018.CS1 maint: unfit url (link)
  12. Press, Gil (7 February 2018). "The Brute Force of IBM Deep Blue And Google DeepMind". forbes.com. Retrieved 12 May 2018.
  13. Hsu, Feng-hsiung (199). "IBM's Deep Blue Chess Grandmaster Chips" (PDF). Retrieved 17 June 2020.
  14. Khosrow-Pour, Mehdi (2017). Encyclopedia of Information Science and Technology. p. 234. Retrieved 19 June 2020.
  15. "TOP500 List - June 1997 (201-300)". Top 500. 13 February 2009. Retrieved 10 June 2020.
  16. Weber, Bruce (18 May 1997). "What Deep Blue Learned in Chess School". The New York Times. ISSN 0362-4331. Retrieved 4 July 2017.
  17. Weber, Bruce (5 May 1997). "Computer Defeats Kasparov, Stunning the Chess Experts". New York Times.
  18. Campbell, Murray (November 1999). "COMMUNICATIONS OF THE ACM". Retrieved 3 June 2020.
  19. Newborn, Monty (1997). Kasparov versus Deep Blue: Computer Chess Comes of Age (1st ed.). p. 287. Retrieved 12 June 2020.
  20. Mcphee, Michele; K.C. Baker; Siemaszko, Corky (10 May 2015). "IBM's Deep Blue beats chess champion Garry Kasparov in 1997". NY Daily News. Retrieved 3 August 2017.
  21. IBM Research Game 2 Archived 19 October 2007 at the Wayback Machine, Deep Blue IBM
  22. Saletan, William (11 May 2007). "Chess Bump: The triumphant teamwork of humans and computers". Slate. Archived from the original on 13 May 2007.
  23. Campbell 1998, p. 88.
  24. Levy & Newborn 1991, p. 192
  25. Roberts, Jacob (2016). "Thinking Machines: The Search for Artificial Intelligence". Distillations. 2 (2): 14–23. Archived from the original on 19 August 2018. Retrieved 22 March 2018.
  26. 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.
  27. LC Catalog - Item Information (Full Record). LCCN 2017304768.
  28. Silver, Albert (19 February 2015). "Deep Blue's cheating move". Chess Base. Chess News. Retrieved 3 June 2020.
  29. Hsu, Feng-Hsiung (2004). Behind Deep Blue: Building the Computer that Defeated the World Chess Champion (revised ed.). Princeton University Press. p. x (Preface). ISBN 978-0691118185.
  30. Warwick, Kevin (2004). I, Cyborg. University of Illinois Press. p. 95. ISBN 0252072154. Retrieved 10 June 2020.
  31. "Deep Blue - Replay the Games". IBM Research. Archived from the original on 1 July 2008. Retrieved 10 June 2020.
  32. Greenemeier, Larry. "20 Years after Deep Blue: How AI Has Advanced Since Conquering Chess". Scientific American. Retrieved 29 June 2018.
  33. "On this day: Born April 13, 1963; Russian chess champion Garry Kasparov". Reuters. 12 April 2020. Retrieved 28 June 2020.
  34. Mann, Windsor, ed. (2011). The Quotable Hitchens: From Alcohol to Zionism. Da Capo Press/Hachette Books. p. vii. ISBN 9780306819834.
  35. Barrat, James (2013). Our Final Invention (Kindle ed.). St. Martin's Press. p. 13.
  36. "'Game Over' : Did IBM Cheat Kasparov?". Archived from the original on 12 October 2008. Retrieved 4 June 2020.
  37. "IBM100". Archived from the original on 30 March 2014. Retrieved 5 June 2020.
  38. Wu, David J. "Designing a winning Arimaa program." ICGA Journal 38, no. 1 (2015): 19-40.
  39. "Deep Blue Supercomputer Tower". National Museum of American History. Retrieved 1 February 2019.
  40. "Deep Blue II". Computer History Museum. Retrieved 8 June 2020.
  41. "Deep Blue Skies: Ibm Helps Airline". Orlando Sentinel. 7 December 1997. Archived from the original on 11 May 2013.
  42. "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. Cite journal requires |journal= (help)
  43. "The last match man vs machine?". English translation of Spiegel Article. ChessBase. 23 November 2006. Archived from the original on 16 October 2012.
  44. "Chess champion loses to computer". BBC News. 5 December 2006. Archived from the original on 31 December 2007. Retrieved 4 May 2008.

Bibliography
  • Hsu, Feng-hsiung (2002). Behind Deep Blue: Building the Computer that Defeated the World Chess Champion. Princeton University Press. ISBN 0-691-09065-3.CS1 maint: ref=harv (link)
  • Levy, David; Newborn, Monty (1991). How Computers Play Chess. Computer Science Press. ISBN 0-7167-8121-2.CS1 maint: ref=harv (link)
  • Campbell, Murray (1998). "An Enjoyable Game". In Stork, D. G. (ed.). HAL's Legacy: 2001's Computer as Dream and Reality. Cambridge, Massachusetts: MIT Press.
  • Syed, Omar; Syed, Aamir (2003). "Arimaa – a New Game Designed to be Difficult for Computers". International Computer Games Association Journal 26: 138–139. Cite journal requires |journal= (help)

Further reading
  • Newborn, Monty (1997). Kasparov versus Deep Blue: Computer Chess Comes of Age. Springer. ISBN 0-387-94820-1.CS1 maint: ref=harv (link)
  • King, Daniel (1997). Kasparov v. Deeper Blue: The Ultimate Man v. Machine Challenge. Batsford. ISBN 0-7134-8322-9.CS1 maint: ref=harv (link)
  • Newborn, Monty (2002). Deep Blue. Springer. ISBN 0-387-95461-9.
  • Campbell, M.; Hoane, A. J.; Hsu, F. H. (2002). "Deep Blue". Artificial Intelligence. 134 (1–2): 57–59. doi:10.1016/S0004-3702(01)00129-1.
  • Deep Blue player profile and games at Chessgames.com
  • IBM.com, IBM Research pages on Deep Blue
  • IBM.com, IBM page with the computer logs from the games
  • Chesscenter.com, Open letter from Feng-hsiung Hsu on the aborted rematch with Kasparov, The Week in Chess Magazine, issue 270, 10 January 2000
  • Chesscenter.com, Open Letter from Owen Williams (Gary Kasparov's manager), responding to Feng-hsiung Hsu, 13 January 2000
  • Sjeng.org, Deep Blue system described by Feng-hsiung Hsu, Murray Campbell and A. Joseph Hoane Jr. (PDF)
  • Chessclub.com, ICC Interview with Feng-Hsiung Hsu, an online interview with Hsu in 2002 (annotated)
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.