Artificial Intelligence 134 (2002) 57-83



Yüklə 259,28 Kb.
Pdf görüntüsü
səhifə1/10
tarix16.11.2017
ölçüsü259,28 Kb.
#10667
  1   2   3   4   5   6   7   8   9   10


Artificial Intelligence 134 (2002) 57–83

Deep Blue

Murray Campbell

a,



, A. Joseph Hoane Jr.

b

, Feng-hsiung Hsu



c

a

IBM T.J. Watson Research Center, Yorktown Heights, NY 10598, USA

b

Sandbridge Technologies, 1 N. Lexington Avenue, White Plains, NY 10601, USA

c

Compaq Computer Corporation, Western Research Laboratory, 250 University Avenue,



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

1.1. ChipTest and Deep Thought

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

1.2. Deep Thought 2

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

1.4. Deep Blue II

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ş:
  1   2   3   4   5   6   7   8   9   10




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©genderi.org 2022
rəhbərliyinə müraciət

    Ana səhifə