Deep Blue (chess computer)

Last updated

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

Deep Blue was a chess-playing expert system run on a unique purpose-built IBM supercomputer. 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 at Carnegie Mellon University under the name ChipTest. It then moved to IBM, where it was first renamed Deep Thought, then again in 1989 to Deep Blue. It first played world champion Garry Kasparov in a six-game match in 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 the history of artificial intelligence and has been the subject of several books and films.

Contents

History

While a doctoral student at Carnegie Mellon University, Feng-hsiung Hsu began development of a chess-playing supercomputer under the name ChipTest. The machine won the North American Computer Chess Championship in 1987 and Hsu and his team followed up with a successor, Deep Thought, in 1988. [2] [3] After receiving his doctorate in 1989, Hsu and Murray Campbell joined IBM Research to continue their project to build a machine that could defeat a world chess champion. [4] Their colleague Thomas Anantharaman briefly 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 by Peter Fitzhugh Brown, [8] was a play on IBM's nickname, "Big Blue". [lower-alpha 1] After a scaled-down version of Deep Blue played Grandmaster Joel Benjamin, [10] Hsu and Campbell decided that Benjamin was the expert they were looking for to help develop Deep Blue's opening 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 eighth World Computer Chess Championship, playing Wchess to a draw before ultimately losing to Fritz in round five, despite playing as White. [12]

In 1997, the Chicago Tribune mistakenly reported that Deep Blue had been sold to United Airlines, a confusion based upon its physical resemblance to IBM's mainstream RS6000/SP2 systems. [13]

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

Deep Blue versus Kasparov

Garry Kasparov playing a simultaneous exhibition in 1985 Kasparov Magath 1985 Hamburg-2.png
Garry Kasparov playing a simultaneous exhibition in 1985

Subsequent to its predecessor Deep Thought's 1989 loss to Garry 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 win a chess game against a reigning world champion under regular 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. [17]

Deep Blue's hardware was subsequently upgraded, [3] [18] [lower-alpha 2] doubling its speed before it faced Kasparov again in May 1997, when it won the six-game rematch 3½–2½. Deep Blue won the deciding game after 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. [20] [21] 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. [22] David Levy and Monty Newborn estimate that each additional ply (half-move) of forward insight increases the playing strength between 50 and 70 Elo points. [23]

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

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. [26] [27] Kasparov demanded a rematch, but IBM had dismantled Deep Blue after its victory and refused the rematch. [28] 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. [29]

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

Aftermath

Chess

Kasparov initially called Deep Blue an "alien opponent" but later belittled it, stating that it was "as intelligent as your alarm clock". [31] According to Martin Amis, two grandmasters who played Deep Blue agreed that it was "like a wall coming at you". [32] [33] Hsu had the rights to use the Deep Blue design independently of IBM, but also independently declined Kasparov's rematch offer. [34] In 2003, the documentary film Game Over: Kasparov and the Machine investigated 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. [35]

Other games

Following Deep Blue's victory, AI specialist Omar Syed designed a new game, Arimaa, which was intended to be very simple for humans but very difficult for computers to master; [36] [37] however, in 2015, computers proved capable of defeating strong Arimaa players. [38] Since Deep Blue's victory, computer scientists have developed software for other complex board games with competitive communities. AlphaGo defeated top Go players in the 2010s. [39] [40]

Computer science

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 of IBM Watson or AlphaGo. [41]

While Deep Blue, with its capability of evaluating 200 million positions per second, [42] was the first computer to face a world chess champion in a formal match, [3] it was a then-state-of-the-art expert system, relying upon rules and variables defined and fine-tuned by chess masters and computer scientists. In contrast, current chess engines such as Leela Chess Zero typically use reinforcement machine learning systems that train a neural network to play, developing its own internal logic rather than relying upon rules defined by human experts. [39]

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 (half-moves) in the middlegame thanks to heuristics; it won 4–2. [43] [44]

Design

One of Deep Blue's processors One of Deep Blue's processors (2586060990).jpg
One of Deep Blue's processors

Software

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.). 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,000 grandmaster games, 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. [45]

Before the second match, the program's rules were fine-tuned by grandmaster Joel Benjamin. The opening library was provided by grandmasters Miguel Illescas, John Fedorowicz, and Nick de Firmian. [46] 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. [47]

Hardware

Deep Blue used custom VLSI chips to parallelize the alpha–beta search algorithm, [48] an example of symbolic AI. [49] The system derived its playing strength mainly from brute force computing power. It was a massively parallel IBM RS/6000 SP Supercomputer with 30 PowerPC 604e processors and 480 custom 600 µm CMOS VLSI "chess chips" designed to execute the chess-playing expert system, as well as FPGAs intended 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 8x8 combinational logic circuit, a chess board in miniature. [50] [51] [52] [53]

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 1997, Deep Blue was upgraded again to become the 259th most powerful supercomputer according to the TOP500 list, achieving 11.38 GFLOPS on the parallel high performance LINPACK benchmark. [54]

See also

Related Research Articles

<span class="mw-page-title-main">Chess</span> Strategy board game

Chess is a board game for two players, called White and Black, each controlling an army of chess pieces, with the objective to checkmate the opponent's king. It is sometimes called international chess or Western chess to distinguish it from related games such as xiangqi and shogi. The recorded history of chess goes back at least to the emergence of a similar game, chaturanga, in seventh century India. The rules of chess as they are known today emerged in Europe at the end of the 15th century, with standardization and universal acceptance by the end of the 19th century. Today, chess is one of the world's most popular games, and is played by millions of people worldwide.

<span class="mw-page-title-main">Garry Kasparov</span> Russian chess grandmaster, political activist and writer (born 1963)

Garry Kimovich Kasparov is a Russian chess grandmaster, former World Chess Champion (1985–2000), political activist and writer. His peak FIDE chess rating of 2851, achieved in 1999, was the highest recorded until being surpassed by Magnus Carlsen in 2013. From 1984 until his retirement from regular competitive chess in 2005, Kasparov was ranked world no. 1 for a record 255 months overall. Kasparov also holds records for the most consecutive professional tournament victories (15) and Chess Oscars (11).

<span class="mw-page-title-main">Computer chess</span> 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. Computer chess applications that play at the level of a chess grandmaster or higher are available on hardware from supercomputers to smart phones. Standalone chess-playing machines are also available. Stockfish, Leela Chess Zero, GNU Chess, Fruit, and other free open source applications are available for various platforms.

Feng-hsiung Hsu is a Taiwanese-American 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.

<span class="mw-page-title-main">Deep Blue versus Kasparov, 1996, Game 1</span> Computer vs. human chess match

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.

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.

In chess, the threefold repetition rule states that a player may claim a draw if the same position occurs three times during the game. The rule is also known as repetition of position and, in the USCF rules, as triple occurrence of position. Two positions are by definition "the same" if the same types of pieces occupy the same squares, the same player has the move, the remaining castling rights are the same and the possibility to capture en passant is the same. The repeated positions need not occur in succession. The reasoning behind the rule is that if the position occurs three times, no real progress is being made and the game could hypothetically continue indefinitely.

<span class="mw-page-title-main">David Levy (chess player)</span> English chess player, writer, and entrepreneur

David Neil Laurence Levy is an International Master of chess who plays for Scotland, and a businessman. He is noted for his involvement with computer chess and artificial intelligence, and as the founder of the Computer Olympiads and the Mind Sports Olympiads. He has written more than 40 books on chess and computers.

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.

<i>Game Over: Kasparov and the Machine</i> 2003 Canadian film

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, the World Champion for 15 years (1985–2000) and an anti-communist politician, and Deep Blue, a chess-playing computer created by IBM. It was coproduced by Alliance Atlantis and the National Film Board of Canada.

Advanced chess is a form of chess in which each human player uses a computer chess program to explore the possible results of candidate moves. Despite this computer assistance, it is the human player who controls and decides the game.

<span class="mw-page-title-main">Deep Blue versus Kasparov, 1997, Game 6</span> Chess game 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.

<span class="mw-page-title-main">Maxim Dlugy</span> American chess player

Maxim Alexandrovich Dlugy is an American chess player with the FIDE title of Grandmaster.

In two-or-more-player sequential games, a ply is one turn taken by one of the players. The word is used to clarify what is meant when one might otherwise say "turn".

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 to 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 known for being part of the team that created Deep Blue; the first computer to defeat a world chess champion.

<span class="mw-page-title-main">Deep Blue versus Garry Kasparov</span> 1996 and 1997 chess matches

Deep Blue versus Garry Kasparov was a pair of six-game chess matches between then-world chess champion Garry Kasparov and an IBM supercomputer called Deep Blue. Kasparov won the first match, held in Philadelphia in 1996, by 4–2. Deep Blue won a 1997 rematch held in New York City by 3½–2½. The second match was the first defeat of a reigning world chess champion by a computer under tournament conditions, and was the subject of a documentary film, Game Over: Kasparov and the Machine.

<span class="mw-page-title-main">Anti-computer tactics</span> Human methods against game-playing computers

Anti-computer tactics are methods used by humans to try to beat computer opponents at various games, most typically board games such as chess and Arimaa. They are most associated with competitions against computer AIs that are playing to their utmost to win, rather than AIs merely programmed to be an interesting challenge that can be given intentional weaknesses and quirks by the programmer. Such tactics are most associated with the era when AIs searched a game tree with an evaluation function looking for promising moves, often with Alpha–beta pruning or other minimax algorithms used to narrow the search. Against such algorithms, a common tactic is to play conservatively aiming for a long-term advantage. The theory is that this advantage will manifest slowly enough that the computer is unable to notice in its search, and the computer won't play around the threat correctly. This may result in, for example, a subtle advantage that eventually turns into a winning chess endgame with a passed pawn.

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

The history of chess began nearly 150 years ago, and over the past century and a half the game has changed drastically. No technology or strategy, however, has changed chess as much as the introduction of chess engines. Despite only coming into existence within the previous 70 years, the introduction of chess engines has molded and defined how top chess is played today.

References

Notes

  1. ↑ IBM renamed "Deep Thought" because the name resembled the title of the hit pornographic film Deep Throat. [9]
  2. ↑ Unofficially nicknamed "Deeper Blue". [19]

Citations

  1. ↑ "Deep Thought (Chess)". ICGA Tournaments. Archived from the original on 6 November 2020. Retrieved 11 January 2022.
  2. ↑ Newborn 2002 , pp. 11–20
  3. 1 2 3 4 Greenemeier, Larry (2 June 2017). "20 Years after Deep Blue: How AI Has Advanced Since Conquering Chess". Scientific American. Archived from the original on 30 June 2018. Retrieved 29 June 2018.
  4. ↑ Hsu 2002 , pp. 92–95
  5. ↑ Hsu 2002 , p. 107
  6. ↑ Hsu 2002 , p. 132
  7. ↑ IBM. "Deep Blue – Overview". IBM Research. Archived from the original on 12 December 2008. Retrieved 19 August 2008.
  8. ↑ Hsu 2002 , pp. 126–127
  9. ↑ Zuckerman 2019, p. 178
  10. ↑ "Joel Benjamin playing a practice game with Deep Blue". Computer History Museum. Archived from the original on 17 February 2020. Retrieved 17 February 2020.
  11. ↑ Hsu 2002 , pp. 160–161, 174, 177, 193
  12. ↑ "8th World Computer Chess Championship". ICGA Tournaments. Archived from the original on 7 October 2008. Retrieved 4 June 2020.
  13. ↑ Schmeltzer, John (7 December 1997). "Deep Blue Skies: Ibm Helps Airline". Orlando Sentinel . Archived from the original on 11 May 2013.{{cite news}}: CS1 maint: unfit URL (link)
  14. ↑ "Deep Blue Supercomputer Tower". National Museum of American History. Archived from the original on 2 February 2019. Retrieved 1 February 2019.
  15. ↑ "Deep Blue II". Computer History Museum. Archived from the original on 4 October 2019. Retrieved 8 June 2020.
  16. ↑ ( Hsu 2004 )
  17. ↑ Newborn 1997 , p. 287
  18. ↑ 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. Archived from the original on 3 August 2017. Retrieved 3 August 2017.
  19. ↑ IBM Research Game 2 Archived 19 October 2007 at the Wayback Machine , Deep Blue IBM
  20. ↑ Saletan, William (11 May 2007). "Chess Bump: The triumphant teamwork of humans and computers". Slate . Archived from the original on 13 May 2007.
  21. 1 2 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.
  22. ↑ Campbell 1998 , p. 88
  23. ↑ Levy & Newborn 1991 , p. 192
  24. 1 2 Plumer, Brad (26 September 2012). "Nate Silver's 'The Signal and the Noise'". The Washington Post. Archived from the original on 9 November 2012. Retrieved 18 August 2021.
  25. ↑ LC Catalog – Item Information (Full Record). LCCN   2017304768.
  26. ↑ Silver, Albert (19 February 2015). "Deep Blue's cheating move". Chess Base. Chess News. Archived from the original on 29 July 2020. Retrieved 3 June 2020.
  27. ↑ Hsu 2004 , p. x
  28. ↑ Warwick 2004 , p. 95
  29. ↑ "Deep Blue – Replay the Games". IBM Research. Archived from the original on 1 July 2008. Retrieved 10 June 2020.
  30. ↑ Boyle, Alan (16 June 2004). "How prizes pushed progress". NBC News. Retrieved 23 January 2024.
  31. ↑ Baldwin, Alan (11 April 2020). "On this day: Born April 13, 1963; Russian chess champion Garry Kasparov". Reuters. Archived from the original on 2 November 2020. Retrieved 18 August 2021.
  32. ↑ Amis 2011 , p. vii
  33. ↑ Barrat 2013 , p. 13
  34. ↑ "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.
  35. ↑ "'Game Over' : Did IBM Cheat Kasparov?". About.com: Chess. June 2005. Archived from the original on 12 October 2007. Retrieved 4 June 2020.
  36. ↑ Syed & Syed 2003 , p. 138
  37. ↑ "Deep Blue: Cultural Impacts". IBM100. IBM. Archived from the original on 30 March 2014. Retrieved 5 June 2020.
  38. ↑ Wu 2015 , p. 19
  39. 1 2 Silver, 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. PMID   30523106. S2CID   54457125. Archived (PDF) from the original on 1 September 2019. Retrieved 4 January 2022.
  40. ↑ "Google's AlphaGo retires on top after humbling world No. 1". phys.org. 27 May 2017. Archived from the original on 28 May 2017. Retrieved 4 January 2022.
  41. ↑ 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 .
  42. ↑ Strogatz, Steven (26 December 2018). "One Giant Step for a Chess-Playing Machine". The New York Times. ISSN   0362-4331. Archived from the original on 4 January 2022. Retrieved 4 January 2022.
  43. ↑ 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. Archived from the original on 16 October 2012. Retrieved 18 August 2021.
  44. ↑ "Chess champion loses to computer". BBC News . 5 December 2006. Archived from the original on 31 December 2007. Retrieved 4 May 2008.
  45. ↑ Campbell 1999 , p. 66
  46. ↑ Weber, Bruce (18 May 1997). "What Deep Blue Learned in Chess School". The New York Times. ISSN   0362-4331. Archived from the original on 17 May 2017. Retrieved 4 July 2017.
  47. ↑ Weber, Bruce (5 May 1997). "Computer Defeats Kasparov, Stunning the Chess Experts". The New York Times . Archived from the original on 24 April 2020. Retrieved 18 May 2020.
  48. ↑ Hsu, Campbell & Hoane 1995 p. 240
  49. ↑ Greenemeier, Larry. "20 Years after Deep Blue: How AI Has Advanced Since Conquering Chess". Scientific American. Archived from the original on 20 December 2021. Retrieved 3 January 2022.
  50. ↑ 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 from the original (PDF) on 28 December 2004. Retrieved 11 January 2022.
  51. ↑ Festa, Paul (2 September 1997). "IBM upgrades Deep Blue". Clnet. Archived from the original on 3 January 2022. Retrieved 11 January 2022.
  52. ↑ Gonsalves 2017 , p. 234
  53. ↑ Hsu, Feng-hsiung (3 May 2022). Behind Deep Blue: Building the Computer That Defeated the World Chess Champion. Princeton University Press. ISBN   978-0-691-23514-1.
  54. ↑ "TOP500 List – June 1997 (201–300)". Top 500. 13 February 2009. Archived from the original on 13 February 2009. Retrieved 10 June 2020.

Bibliography

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.