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.

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.

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.

Deep Blue
Deep Blue, at the Computer History Museum

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]

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]

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]

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 Magath 1985 Hamburg-2
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.

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.

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

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. ^ a b 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. ^ a b '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

  • Hsu, Feng-hsiung (2002). "Behind Deep Blue: Building the Computer that Defeated the World Chess Champion". Princeton University Press. ISBN 0-691-09065-3.
  • Levy, David; Newborn, Monty (1991). "How Computers Play Chess". Computer Science Press. ISBN 0-7167-8121-2.
  • 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

Further reading

  • Newborn, Monty (1997). "Kasparov versus Deep Blue: Computer Chess Comes of Age". Springer. ISBN 0-387-94820-1.
  • King, Daniel (1997). "Kasparov v. Deeper Blue: The Ultimate Man v. Machine Challenge". Batsford. ISBN 0-7134-8322-9.
  • 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: 57–59. doi:10.1016/S0004-3702(01)00129-1.

External links

  • 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.
  • Chessclub.com, ICC Interview with Feng-Hsiung Hsu, an online interview with Hsu in 2002 (annotated)
ChipTest

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.

ChipTest was based on a special VLSI-technology move generator chip developed by Hsu. ChipTest was controlled by a Sun-3/160 workstation and capable of searching approximately 50,000 moves per second. Hsu and Anantharaman entered ChipTest in the 1986 North American Computer Chess Championship, and it was only partially tested when the tournament began. It lost its first two rounds, but finished with an even score. In August 1987 ChipTest was overhauled and renamed ChipTest-M, M standing for microcode. The new version had eliminated ChipTest's bugs and was ten times faster, searching 500,000 moves per second and running on a Sun-4 workstation. ChipTest-M won the North American Computer Chess Championship in 1987 with a 4-0 sweep. ChipTest was invited to play in the 1987 American Open, but the team did not enter due to an objection by the HiTech team, also from Carnegie Mellon University. HiTech and ChipTest shared some code, and Hitech was already playing in the tournament. The two teams became rivals.Designing and implementing ChipTest revealed many possibilities for improvement, so the designers started on a new machine. Deep Thought 0.01 was created in May 1988 and the version 0.02 in November the same year. This new version had two customized VLSI chess processors and it was able to search 720,000 moves per second. With the "0.02" dropped from its name, Deep Thought won the World Computer Chess Championship with a perfect 5-0 score in 1989.

Chris Sander (scientist)

Chris Sander is a computational biologist and chair of the Computational Biology Programme at the Memorial Sloan–Kettering Cancer Center in New York City. Recently, he moved his lab to the Dana–Farber Cancer Institute and the Cell Biology Department at Harvard Medical School.

Computer Go

Computer Go is the field of artificial intelligence (AI) dedicated to creating a computer program that plays the traditional board game Go. The game of Go has been a fertile subject of artificial intelligence research for decades, culminating in 2017 with AlphaGo winning three of three games against Ke Jie, who at the time continuously held the world No. 1 ranking for two years.

Computer programming

Computer programming is the process of designing and building an executable computer program for accomplishing a specific computing task. Programming involves tasks such as: analysis, generating algorithms, profiling algorithms' accuracy and resource consumption, and the implementation of algorithms in a chosen programming language (commonly referred to as coding). The source code of a program is written in one or more languages that are intelligible to programmers, rather than machine code, which is directly executed by the central processing unit. The purpose of programming is to find a sequence of instructions that will automate the performance of a task (which can be as complex as an operating system) on a computer, often for solving a given problem. The process of programming thus often requires expertise in several different subjects, including knowledge of the application domain, specialized algorithms, and formal logic.

Tasks accompanying and related to programming include: testing, debugging, source code maintenance, implementation of build systems, and management of derived artifacts, such as the machine code of computer programs. These might be considered part of the programming process, but often the term software development is used for this larger process with the term programming, implementation, or coding reserved for the actual writing of code. Software engineering combines engineering techniques with software development practices. Reverse engineering is the opposite process. A hacker is any skilled computer expert that uses their technical knowledge to overcome a problem, but it can also mean a security hacker in common language.

Deep Blue

Deep Blue may refer to:

Deep Blue (chess computer), a chess-playing computer developed by IBM that defeated world champion Garry Kasparov in 1997

EFF DES cracker

In cryptography, the EFF DES cracker (nicknamed "Deep Crack") is a machine built by the Electronic Frontier Foundation (EFF) in 1998, to perform a brute force search of the Data Encryption Standard (DES) cipher's key space – that is, to decrypt an encrypted message by trying every possible key. The aim in doing this was to prove that the key size of DES was not sufficient to be secure.

Feng-hsiung Hsu

Feng-hsiung Hsu (Chinese: 許峰雄; pinyin: Xǔ Fēng Xióng) (nicknamed Crazy Bird) 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.

Hsu was the architect and the principal designer of the IBM Deep Blue chess computer. He was the recipient of the 1990 Mephisto Award for his doctoral dissertation and also the 1991 ACM Grace Murray Hopper Award for his contributions in architecture and algorithms for chess machines.

History of computing hardware (1960s–present)

The history of computing hardware starting at 1960 is marked by the conversion from vacuum tube to solid-state devices such as the transistor and later the integrated circuit. By 1959 discrete transistors were considered sufficiently reliable and economical that they made further vacuum tube computers uncompetitive. Computer main memory slowly moved away from magnetic core memory devices to solid-state static and dynamic semiconductor memory, which greatly reduced the cost, size and power consumption of computers.

IBM Blue Gene

Blue Gene is an IBM project aimed at designing supercomputers that can reach operating speeds in the petaFLOPS (PFLOPS) range, with low power consumption.

The project created three generations of supercomputers, Blue Gene/L, Blue Gene/P, and Blue Gene/Q. Blue Gene systems have often led the TOP500 and Green500 rankings of the most powerful and most power efficient supercomputers, respectively. Blue Gene systems have also consistently scored top positions in the Graph500 list. The project was awarded the 2009 National Medal of Technology and Innovation.As of 2015, IBM seems to have ended the development of the Blue Gene family though no public announcement has been made. IBM's continuing efforts of the supercomputer scene seems to be concentrated around OpenPower, using accelerators such as FPGAs and GPUs to battle the end of Moore's law.

IBM Deep Thunder

Deep Thunder is a research project by IBM that aims to improve short-term local weather forecasting through the use of high-performance computing. It is part of IBM's Deep Computing initiative that also produced the Deep Blue chess computer.

Deep Thunder is intended to provide local, high-resolution weather predictions customized to weather-sensitive specific business operations. For example, it could be used to predict the wind velocity at an Olympic diving platform, destructive thunderstorms, and combined with other physical models to predict where there will be flooding, damaged power lines and algal blooms. The project is now headquartered at IBM's Thomas J. Watson Research Center in Yorktown Heights, New York.

Joel Benjamin

Joel Benjamin (born March 11, 1964) 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.

Larry Christiansen

Larry M. Christiansen (born June 27, 1956) is an American chess player. He was awarded the title Grandmaster by FIDE in 1977. Christiansen was the U.S. champion in 1980, 1983, and 2002. He competed in the FIDE World Championship in 1998 and 2002, and in the FIDE World Cup in 2013.

List of pioneers in computer science

This article presents a list of individuals who made transformative breakthroughs in the creation, development and imagining of what computers and electronics could do.

Outline of chess

The following outline is provided as an overview of and topical guide to chess:

Chess is a two-player board game played on a chessboard (a square-checkered board with 64 squares arranged in an eight-by-eight grid). In a chess game, each player begins with sixteen pieces: one king, one queen, two rooks, two knights, two bishops, and eight pawns. The object of the game is to checkmate the opponent's king, whereby the king is under immediate attack (in "check") and there is no way to remove or defend it from attack, or force the opposing player to forfeit.

Ply (game theory)

In two-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".

The word "turn" can be a problem since it means different things in different traditions. For example, in standard chess terminology, one move consists of a turn by each player; therefore a ply in chess is a half-move. Thus, after 20 moves in a chess game, 40 plies have been completed—20 by white and 20 by black. In the game of Go, by contrast, a ply is the normal unit of counting moves; so for example to say that a game is 250 moves long is to imply 250 plies.

The word "ply" used as a synonym for "layer" goes back to the 15th century. Arthur Samuel first used the term in its game-theoretic sense in his seminal paper on machine learning in checkers in 1959, but with a slightly different meaning: the "ply", in Samuel's terminology, is actually the depth of analysis ("Certain expressions were introduced which we will find useful. These are: Ply, defined as the number of moves ahead, where a ply of two consists of one proposed move by the machine and one anticipated reply by the opponent").

In computing, the concept of ply is important because one ply corresponds to one level of the game tree. The Deep Blue chess computer which defeated Kasparov in 1997 would typically search to a depth of between six and sixteen plies to a maximum of forty plies in some situations.

Ruy Lopez

The Ruy Lopez (; Spanish: [ˈruj ˈlopeθ]), also called the Spanish Opening or Spanish Game, is a chess opening characterised by the moves:

1. e4 e5

2. Nf3 Nc6

3. Bb5The Ruy Lopez is named after 16th-century Spanish priest Ruy López de Segura. It is one of the most popular openings, with such a vast number of variations that all codes from C60 to C99 in the Encyclopaedia of Chess Openings (ECO) are assigned to them.

Outline
Equipment
Rules
Terms
Tactics
Strategy
Openings
Endgames
Tournaments
Related
History
Products
Business entities
Facilities
Initiatives
Inventions
Terminology
CEOs
Board of directors
Other

This page is based on a Wikipedia article written by authors (here).
Text is available under the CC BY-SA 3.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.