Wikipedia

Deep Blue (chess computer)

Deep Bluewas achess-playingexpert systemrun on a unique purpose-builtIBMsupercomputer.It was the first computer to win a game, and the first to win a match, against a reigning world champion under regular time controls. Development began in 1985 atCarnegie Mellon Universityunder the nameChipTest.It then moved to IBM, where it was first renamedDeep Thought,then again in 1989 to Deep Blue. It first played world championGarry Kasparovin asix-game matchin 1996, where it lost four games to two. It was upgraded in 1997 and in a six-game re-match, it defeated Kasparov by winning two games and drawing three. Deep Blue's victory is considered a milestone in thehistory of artificial intelligenceand has been the subject of several books and films.

Deep Blue
Active1995 (prototype)
1996 (release)
1997 (upgrade)
Architecture
Operating systemIBM AIX
Space2 cabinets
Speed11.38GFLOPS(1997)
Purposeplaying chess

History

edit

While a doctoral student atCarnegie Mellon University,Feng-hsiung Hsubegan development of a chess-playingsupercomputerunder the nameChipTest.The machine won theNorth American Computer Chess Championshipin 1987 and Hsu and his team followed up with a successor,Deep Thought,in 1988.[2][3]After receiving his doctorate in 1989, Hsu andMurray CampbelljoinedIBM Researchto continue their project to build a machine that could defeat a world chess champion.[4]Their colleagueThomas Anantharamanbriefly joined them at IBM before leaving for the finance industry and being replaced by programmer Arthur Joseph Hoane.[5][6]Jerry Brody, a long-time employee of IBM Research, subsequently joined the team in 1990.[7]

After Deep Thought's two-game 1989 loss to Kasparov, IBM held a contest to rename the chess machine: the winning name was "Deep Blue", submitted byPeter Fitzhugh Brown,[8]was a play on IBM's nickname, "Big Blue".[a]After a scaled-down version of Deep Blue played GrandmasterJoel Benjamin,[10]Hsu and Campbell decided that Benjamin was the expert they were looking for to help develop Deep Blue'sopening book,so hired him to assist with the preparations for Deep Blue's matches against Garry Kasparov.[11]In 1995, a Deep Blue prototype played in the eighthWorld Computer Chess Championship,playingWchessto a draw before ultimately losing toFritzin round five, despite playing asWhite.[12]

Today, one of the two racks that made up Deep Blue is held by theNational Museum of American History,having previously been displayed in an exhibit about theInformation Age,[13]while the other rack was acquired by theComputer History Museumin 1997, and is displayed in the Revolution exhibit's "Artificial Intelligence and Robotics" gallery.[14]Several books were written about Deep Blue, among themBehind Deep Blue: Building the Computer that Defeated the World Chess Championby Deep Blue developer Feng-hsiung Hsu.[15]

Deep Blue versus Kasparov

edit
Main article:Deep Blue versus Garry Kasparov
Garry Kasparovplaying asimultaneous exhibitionin 1985

Subsequent to its predecessor Deep Thought's 1989 loss toGarry Kasparov,Deep Blue played Kasparov twice more. In the first game of the first match, which took place from 10 to 17 February 1996, Deep Blue became the first machine to wina chess game against a reigning world championunderregular time controls.However, Kasparov won three and drew two of the following five games, beating Deep Blue by 4–2 at the close of the match.[16]

Deep Blue's hardware was subsequently upgraded,[3][17][b]doubling its speed before it faced Kasparov again in May 1997, when it won the six-game rematch 3½–2½. Deep Blue won thedeciding gameafter Kasparov failed to secure his position in the opening, thereby becoming the first computer system to defeat a reigning world champion in a match under standard chess tournament time controls.[19][20]The version of Deep Blue that defeated Kasparov in 1997 typically searched to a depth of six to eight moves, and twenty or more moves in some situations.[21]David LevyandMonty Newbornestimate that each additionalply(half-move) of forward insight increases the playing strength between 50 and 70Elopoints.[22]

In the 44th move of the first game of their second match, unknown to Kasparov, abugin Deep Blue's code led it to enter an unintentionalloop,which it exited by taking a randomly selected valid move.[23]Kasparov did not take this possibility into account, and misattributed the seemingly pointless move to "superior intelligence".[20]Subsequently, Kasparov experienced a decline in performance in the following game,[23]though he denies this was due to anxiety in the wake of Deep Blue's inscrutable move.[24]

After his loss, Kasparov said that he sometimes saw unusual creativity in the machine's moves, suggesting that during the second game, human chess players had intervened on behalf of the machine. IBM denied this, saying the only human intervention occurred between games.[25][26]Kasparov demanded a rematch, but IBM had dismantled Deep Blue after its victory and refused the rematch.[27]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.[28]

The 1997 tournament awarded a $700,000 first prize to the Deep Blue team and a $400,000 second prize to Kasparov.Carnegie Mellon Universityawarded an additional $100,000 to the Deep Blue team, a prize created by computer science professorEdward Fredkinin 1980 for the first computer program to beat a reigning world chess champion.[29]

Aftermath

edit

Chess

edit

Kasparov initially called Deep Blue an "alien opponent" but later belittled it, stating that it was "as intelligent as your alarm clock".[30]According toMartin Amis,two grandmasters who played Deep Blue agreed that it was "like a wall coming at you".[31][32]Hsu had the rights to use the Deep Blue design independently of IBM, but also independently declined Kasparov's rematch offer.[33]In 2003, thedocumentary filmGame Over: Kasparov and the Machineinvestigated Kasparov's claims that IBM had cheated. In the film, some interviewees describe IBM's investment in Deep Blue as an effort to boost its stock value.[34]

Other games

edit

Following Deep Blue's victory,AIspecialist Omar Syed designed a new game,Arimaa,which was intended to be very simple for humans but very difficult for computers to master;[35][36]however, in 2015, computers proved capable of defeating strong Arimaa players.[37]Since Deep Blue's victory, computer scientists have developed software for other complex board games with competitive communities. The AlphaGo series (AlphaGo,AlphaGo Zero,AlphaZero) defeated topGoplayers in 2016–2017.[38][39]

Computer science

edit

Computer scientists such as Deep Blue developer Campbell 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.[3]Deep Blue is also responsible for the popularity of using games as a display medium for artificial intelligence, as in the cases ofIBM WatsonorAlphaGo.[40]

While Deep Blue, with its capability of evaluating 200 million positions per second,[41]was the first computer to face a world chess champion in a formal match,[3]it was a then-state-of-the-artexpert system,relying upon rules and variables defined and fine-tuned by chess masters and computer scientists. In contrast, current chess engines such asLeela Chess Zerotypically usereinforcementmachine learningsystems that train aneural networkto play, developing its own internal logic rather than relying upon rules defined by human experts.[38]

In a November 2006 match between Deep Fritz and world chess championVladimir Kramnik,the program ran on a computer system containing a dual-coreIntel Xeon 5160 CPU,capable of evaluating only 8 million positions per second, but searching to an average depth of 17 to 18plies(half-moves) in themiddlegamethanks toheuristics;it won 4–2.[42][43]

Design

edit
One of Deep Blue's processors

Software

edit

Deep Blue'sevaluation functionwas 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.). Values for these parameters were determined by analyzing thousands of master games. The evaluation function was then split into 8,000 parts, many of them designed for special positions. The opening book encapsulated more than 4,000 positions and 700,000grandmastergames, while the endgame database contained many six-piece endgames and all five and fewer piece endgames. An additional database named the "extended book" summarizes entire games played by Grandmasters. The system combines its searching ability of 200 million chess positions per second with summary information in the extended book to select opening moves.[44]

Before the second match, the program's rules were fine-tuned by grandmasterJoel Benjamin.The opening library was provided by grandmastersMiguel Illescas,John Fedorowicz,andNick de Firmian.[45]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, leading Kasparov to study many popular PC chess games to familiarize himself with computer gameplay.[46]

Hardware

edit

Deep Blue used customVLSIchips toparallelizetheAlpha –beta searchalgorithm,[47]an example ofsymbolic AI.[48]The system derived its playing strength mainly frombrute forcecomputing power. It was amassively parallelIBMRS/6000 SPSupercomputerwith 30PowerPC 604eprocessors and 480 custom600 nmCMOSVLSI "chess chips" designed to execute the chess-playing expert system, as well asFPGAsintended to allow patching of the VLSIs (which ultimately went unused) all housed in two cabinets. The chess chip has four parts: the move generator, the smart-move stack, the evaluation function, and the search control. The move generator is a 8x8combinational logiccircuit, a chess board in miniature.[49][50][51][52]

Its chess playing program was written inCand ran under theAIX operating system.It was capable of evaluating 200 million positions per second, twice as fast as the 1996 version.

In 1997, Deep Blue was upgraded again to become the 259th most powerfulsupercomputeraccording to theTOP500list, achieving 11.38GFLOPSon theparallel high performance LINPACKbenchmark.[53]

See also

edit

References

edit

Notes

edit
  1. ^IBM renamed "Deep Thought" because the name resembled the title of the hit pornographic filmDeep Throat.[9]
  2. ^Unofficially nicknamed "Deeper Blue".[18]

Citations

edit
  1. ^"Deep Thought (Chess)".ICGA Tournaments.Archivedfrom the original on 6 November 2020.Retrieved11 January2022.
  2. ^Newborn 2002,pp. 11–20
  3. ^abcdGreenemeier, Larry (2 June 2017)."20 Years after Deep Blue: How AI Has Advanced Since Conquering Chess".Scientific American.Archivedfrom the original on 30 June 2018.Retrieved29 June2018.
  4. ^Hsu 2002,pp. 92–95
  5. ^Hsu 2002,p. 107
  6. ^Hsu 2002,p. 132
  7. ^IBM."Deep Blue – Overview".IBM Research. Archived fromthe originalon 12 December 2008.Retrieved19 August2008.
  8. ^Hsu 2002,pp. 126–127
  9. ^Zuckerman 2019,p. 178
  10. ^"Joel Benjamin playing a practice game with Deep Blue".Computer History Museum.Archivedfrom the original on 17 February 2020.Retrieved17 February2020.
  11. ^Hsu 2002,pp. 160–161, 174, 177, 193
  12. ^"8th World Computer Chess Championship".ICGA Tournaments.Archived fromthe originalon 7 October 2008.Retrieved4 June2020.
  13. ^"Deep Blue Supercomputer Tower".National Museum of American History.Archivedfrom the original on 2 February 2019.Retrieved1 February2019.
  14. ^"Deep Blue II".Computer History Museum.Archivedfrom the original on 4 October 2019.Retrieved8 June2020.
  15. ^(Hsu 2004)
  16. ^Newborn 1997,p. 287
  17. ^McPhee, Michele; Baker, K.C.; Siemaszko, Corky (10 May 2015)."IBM's Deep Blue beats chess champion Garry Kasparov in 1997".Daily News.New York.Archivedfrom the original on 3 August 2017.Retrieved3 August2017.
  18. ^IBM Research Game 2Archived19 October 2007 at theWayback Machine,Deep BlueIBM
  19. ^Saletan, William(11 May 2007)."Chess Bump: The triumphant teamwork of humans and computers".Slate.Archivedfrom the original on 13 May 2007.
  20. ^abRoberts, Jacob (2016)."Thinking Machines: The Search for Artificial Intelligence".Distillations.2(2): 14–23. Archived fromthe originalon 19 August 2018.Retrieved22 March2018.
  21. ^Campbell 1998,p. 88
  22. ^Levy & Newborn 1991,p. 192
  23. ^abPlumer, Brad (26 September 2012)."Nate Silver's 'The Signal and the Noise'".The Washington Post.Archivedfrom the original on 9 November 2012.Retrieved18 August2021.
  24. ^LC Catalog – Item Information (Full Record).LCCN2017304768.
  25. ^Silver, Albert (19 February 2015)."Deep Blue's cheating move".Chess Base.Chess News.Archivedfrom the original on 29 July 2020.Retrieved3 June2020.
  26. ^Hsu 2004,p. x
  27. ^Warwick 2004,p. 95
  28. ^"Deep Blue – Replay the Games".IBM Research.Archived fromthe originalon 1 July 2008.Retrieved10 June2020.
  29. ^Boyle, Alan (16 June 2004)."How prizes pushed progress".NBC News.Retrieved23 January2024.
  30. ^Baldwin, Alan (11 April 2020)."On this day: Born April 13, 1963; Russian chess champion Garry Kasparov".Reuters.Archivedfrom the original on 2 November 2020.Retrieved18 August2021.
  31. ^Amis 2011,p. vii
  32. ^Barrat 2013,p. 13
  33. ^"Owen Williams replies to Feng-hsiung Hsu".The Week in Chess.13 January 2000.Archivedfrom the original on 29 July 2012.Retrieved11 May2012.
  34. ^"'Game Over': Did IBM Cheat Kasparov? ".About: Chess.June 2005. Archived fromthe originalon 12 October 2007.Retrieved4 June2020.
  35. ^Syed & Syed 2003,p. 138
  36. ^"Deep Blue: Cultural Impacts".IBM100.IBM. Archived fromthe originalon 30 March 2014.Retrieved5 June2020.
  37. ^Wu 2015,p. 19
  38. ^abSilver, David; Hubert, Thomas; Schrittwieser, Julian; et al. (6 December 2018)."A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play"(PDF).University College London.362(6419): 1140–1144.Bibcode:2018Sci...362.1140S.doi:10.1126/science.aar6404.PMID30523106.S2CID54457125.Archived(PDF)from the original on 1 September 2019.Retrieved4 January2022.
  39. ^"Google's AlphaGo retires on top after humbling world No. 1".phys.org.27 May 2017.Archivedfrom the original on 28 May 2017.Retrieved4 January2022.
  40. ^Barbierato, Enrico; Zamponi, Maria Enrica (2022)."Shifting Perspectives on AI Evaluation: The Increasing Role of Ethics in Cooperation".AI.3(2): 331–352.doi:10.3390/ai3020021.hdl:10807/259716.
  41. ^Strogatz, Steven (26 December 2018)."One Giant Step for a Chess-Playing Machine".The New York Times.ISSN0362-4331.Archivedfrom the original on 4 January 2022.Retrieved4 January2022.
  42. ^Schulz, André (23 November 2006)."Das letzte Match Mensch gegen Maschine?"[The last man vs machine match?].Der Spiegel(in German). Translated by ChessBase Chess News.Archivedfrom the original on 16 October 2012.Retrieved18 August2021.
  43. ^"Chess champion loses to computer".BBC News.5 December 2006.Archivedfrom the original on 31 December 2007.Retrieved4 May2008.
  44. ^Campbell 1999,p. 66
  45. ^Weber, Bruce (18 May 1997)."What Deep Blue Learned in Chess School".The New York Times.ISSN0362-4331.Archivedfrom the original on 17 May 2017.Retrieved4 July2017.
  46. ^Weber, Bruce (5 May 1997)."Computer Defeats Kasparov, Stunning the Chess Experts".The New York Times.Archivedfrom the original on 24 April 2020.Retrieved18 May2020.
  47. ^Hsu, Campbell & Hoane 1995p. 240
  48. ^Greenemeier, Larry."20 Years after Deep Blue: How AI Has Advanced Since Conquering Chess".Scientific American.Archivedfrom the original on 20 December 2021.Retrieved3 January2022.
  49. ^Hsu, Feng-hsiung (March–April 1999)."IBM's Deep Blue Chess Grandmaster Chips"(PDF).IEEE Micro.19(2): 70–81.doi:10.1109/40.755469.Archived fromthe original(PDF)on 28 December 2004.Retrieved11 January2022.
  50. ^Festa, Paul (2 September 1997)."IBM upgrades Deep Blue".Clnet.Archivedfrom the original on 3 January 2022.Retrieved11 January2022.
  51. ^Gonsalves 2017,p. 234
  52. ^Hsu, Feng-hsiung (3 May 2022).Behind Deep Blue: Building the Computer That Defeated the World Chess Champion.Princeton University Press.ISBN978-0-691-23514-1.
  53. ^"TOP500 List – June 1997 (201–300)".Top 500.13 February 2009. Archived fromthe originalon 13 February 2009.Retrieved10 June2020.

Bibliography

edit
edit
  • Deep Blueplayer profile and games atChessgames
  • IBM,IBM Research pages on Deep Blue
  • IBM,IBM page with the computer logs from the games
  • Chesscenter,Open letter from Feng-hsiung Hsu on the aborted rematch with Kasparov,The Week in ChessMagazine, issue 270, 10 January 2000
  • Chesscenter,Open Letter from Owen Williams (Garry 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,ICC Interview with Feng-Hsiung Hsu, an online interview with Hsu in 2002 (annotated)
Retrieved from "https://en.wikipedia.org/w/index.php?title=Deep_Blue_(chess_computer)&oldid=1251830123"