Artificial Intelligence 134 (2002) 57-83
Yüklə 259,28 Kb. Pdf görüntüsü
|
- Bu səhifədəki naviqasiya:
- 1. Introduction
| Artificial Intelligence 134 (2002) 57–83 Deep Blue Murray Campbell a, ∗ , A. Joseph Hoane Jr. b , Feng-hsiung Hsu c a
b
c
Palo Alto, CA 94301, USA Abstract Deep Blue is the chess machine that defeated then-reigning World Chess Champion Garry Kasparov in a six-game match in 1997. There were a number of factors that contributed to this success, including: • a single-chip chess search engine, • a massively parallel system with multiple levels of parallelism, • a strong emphasis on search extensions, • a complex evaluation function, and • effective use of a Grandmaster game database. This paper describes the Deep Blue system, and gives some of the rationale that went into the design decisions behind Deep Blue. 2001 Elsevier Science B.V. All rights reserved. Keywords: Computer chess; Game tree search; Parallel search; Selective search; Search extensions; Evaluation function
1. Introduction This paper describes the Deep Blue ® computer chess system, developed at IBM ® Research during the mid-1990s. Deep Blue is the culmination of a multi-year effort to build a world-class chess machine. There was a series of machines that led up to Deep Blue, which we describe below. In fact there are two distinct versions of Deep Blue, one which lost to Garry Kasparov in 1996 and the one which defeated him in 1997. This paper will refer primarily to the 1997 version, and comparisons with the 1996 version, which we * Corresponding author. The ordering of the authors is alphabetic. E-mail addresses: mcam@us.ibm.com (M. Campbell), Joe.Hoane@SandbridgeTech.com (A.J. Hoane Jr.), Feng-hsiung.Hsu@compaq.com (F.-h. Hsu). 0004-3702/01/$ – see front matter 2001 Elsevier Science B.V. All rights reserved. PII: S 0 0 0 4 - 3 7 0 2 ( 0 1 ) 0 0 1 2 9 - 1 58 M. Campbell et al. / Artificial Intelligence 134 (2002) 57–83 will call Deep Blue I, will be made where appropriate. For clarity, we will sometimes refer to the 1997 version as Deep Blue II. A brief summary of the chess machines described here can be found in Appendix B. A fuller history of the Deep Blue project can be found in [15].
Earlier efforts in building a chess machine, ChipTest and Deep Thought, took place at Carnegie Mellon University in the 1980s. In 1988 Deep Thought was the first chess machine to beat a Grandmaster in tournament play. These systems used a single-chip chess move generator [12] to achieve search speeds in the neighborhood of 500,000 positions per second (ChipTest) to 700,000 positions per second (Deep Thought). Deep Thought is described in detail in [16,17].
In 1989–90, part of the Deep Thought team (Anantharaman, Campbell, Hsu) moved to the IBM T.J. Watson Research Center to continue the effort to build a world-class chess machine. In late 1990, Joe Hoane replaced Thomas Anantharaman in the group. Deep Thought 2, aka Deep Blue prototype, was the first result of this effort. Although the primary purpose of the system was as an intermediate stepping stone to Deep Blue, Deep Thought 2 played in a number of public events from 1991 through 1995. Although Deep Thought 2 used the same move-generator chip as Deep Thought, it had four improvements: 1. Medium-scale multiprocessing. Deep Thought 2 initially had 24 chess engines, although over time that number decreased as processors failed and were not replaced. This compares with Deep Thought, which usually used two processors (although there were four- and six-processor versions that made a few appearances). 2. Enhanced evaluation hardware. The Deep Thought 2 evaluation hardware used larger RAMs and was able to include a few additional features in the evaluation function. Nonetheless, the evaluation function was relatively simple. For example, the Deep Thought 2 hardware was not able to recognize “bishops of opposite color”, a feature that chess players know greatly increases the chance for a drawn endgame. In order to address this (and other similar problems), the Deep Thought 2 system implemented a software “band-aid” mechanism. Unfortunately this slowed down the overall system speed and created numerous search anomalies at the hardware/software boundary. In spite of these drawbacks, the missing evaluation function features were sufficiently important to use this evaluation patch. 3. Improved search software. The search software was rewritten entirely for Deep Thought 2, and was designed to deal better with the parallel search, as well as implement a number of new search extension ideas. This code would later form the initial basis for the Deep Blue search software. 4. Extended book [6]. The extended book (see Section 8.2) allowed Deep Thought 2 to make reasonable opening moves even in the absence of an opening book. This feature was also inherited by Deep Blue. M. Campbell et al. / Artificial Intelligence 134 (2002) 57–83 59 The major competitive successes of Deep Thought 2 included victories in the 1991 and 1994 ACM Computer Chess Championships, and a 3–1 win against the Danish national team in 1993. 1.3. Deep Blue I Deep Blue I was based on a single-chip chess search engine, designed over a period of three years. The first chips were received in September of 1995. A number of problems were found with these chips, and a revised version was received in January of 1996. Deep Blue I ran on a 36-node IBM RS/6000 ® SP TM computer, and used 216 chess chips. The chips each searched about 1.6–2 million chess positions per second. Overall search speed was 50–100 million chess positions per second. The full 36-node Deep Blue I played only six games under tournament conditions, all in the February 1996 match with Garry Kasparov. This match was won by Kasparov by a fairly decisive 4–2 score, although the match was tied at 2–2 after the first four games. Three additional tournament-condition matches were played in preparation for the 1996 Kasparov match, all using a single-node version of Deep Blue with 24 chess chips. This system, aka Deep Blue Jr., beat Grandmaster Ilya Gurevich 1.5–0.5, drew Grandmaster Patrick Wolff 1–1, and lost to Grandmaster Joel Benjamin 0–2. 1
After the 1996 match with Kasparov, it was clear that there were a number of deficiencies in the play of Deep Blue I. A series of changes were made in preparation for the rematch which took place in May of 1997. First, a new, significantly enhanced, chess chip was designed. The new chess chip had a completely redesigned evaluation function, going from around 6400 features to over 8000. A number of the new features were in response to specific problems observed in the 1996 Kasparov games, as well as in test games against Grandmaster Joel Benjamin. The new chip also added hardware repetition detection, a number of specialized move generation modes (e.g., generate all moves that attack the opponent’s pieces: see Section 3.1), and some efficiency improvements that increased the per chip search speed to 2–2.5 million positions per second. The second major change was to more than double the number of chess chips in the system, and use the newer generation of SP computer to support the higher processing demands thereby created. A third change was the development of a set of software tools to aid in debugging and match preparation, e.g., evaluation tuning and visualization tools. Finally, we concluded that the searching ability of Deep Blue was acceptable, and we spent the vast majority of our time between the two matches designing, testing, and tuning the new evaluation function. Deep Blue defeated Garry Kasparov in the 1997 match by a score of 3.5–2.5. For this victory, the Deep Blue team was awarded the Fredkin prize for defeating the human world champion in a regulation match. There were two additional matches played by Deep Blue Jr. in preparation for the Kasparov match. The two matches, against Grandmasters 1 This last match went a long way to convincing us that Joel Benjamin would be an excellent Grandmaster consultant to the Deep Blue team. Yüklə 259,28 Kb. Dostları ilə paylaş:
|