Artificial Intelligence 134 (2002) 57-83

M. Campbell et al. / Artificial Intelligence 134 (2002) 57–83

75

Table 5

Deep Blue evaluation tables

Function

Number of tables

Table entries

Data bits

Multiple pawns

2

80

8

Minor on weak

2

192

12

Self block

2

320

5

Opponent block

2

128

4

Back block

2

160

5

Pinned

2

128

8

Mobility

8

128

9

Pawn structure

2

160

32

Passed pawns

2

320

32

Joint signature

1

256

8

Rooks on files

2

192

10

Bishops

4

128

11

Pawn storm

2

128

18

Pawn shelter

2

384

14

Development

1

256

9

Trapped bishop

1

128

8

Signature

2

128

20

Contempt

1

256

8

Piece placement

1

1024

10

• “rook_count” is a 2-bit subindex, with only the values 0, 1 and 2 being legal.

rook_count indicates the number of rooks for my side that are not behind my own

pawns.

• “centrality” is a 2-bit subindex, with files “a” and “h” receiving value 0, files “b” and

“g” receiving 1, files “c” and “f” receiving 2, and files “d” and “e” receiving 3.

Each table entry is 10 bits, which is divided into three fields:

• “kmodOpp” is a 2-bit field which causes extra points to be added to the king safety

if the sides have castled on opposite sites. The field chooses a multiplier, which is 2

for 0, 1.5 for 1, 1 for 2, and 0.5 for 3. The base value (see below) is multiplied by the

appropriate value and then included in the king safety calculation if the file is adjacent

to the enemy king. As a special case, the rook file is considered adjacent to the bishop

file.

• “kmod” is a 2-bit field, similar to kmodOpp, used when the kings have castled on the

same side.

• “base” is a 6-bit field which gets summed into the overall evaluation. This is the

“value” of the given formation, independent of king safety considerations.

---

76

M. Campbell et al. / Artificial Intelligence 134 (2002) 57–83

There is an additional factor to consider for rooks on files. Under some circumstances,

pawns can be semi-transparent to rooks. For example, if a pawn is “levering”, it is

considered semi-transparent to rooks. For this purpose, levering is defined to be having

the possibility of capturing an enemy pawn. Under such circumstances, rooks get about

half the value of the unblocked file. This feature was of critical importance in Game 2 of

the 1997 match between Garry Kasparov and Deep Blue.

The king-safety component of rooks on files is not directly added to the evaluation of

a position, but is first scaled by the amount of material on the board (via a table lookup).

Positions with most of the pieces still on the board may retain the full king-safety value,

while endgames will have the value scaled to close to zero. This, for example, encourages

Deep Blue to trade pieces in positions where its king is less safe than the opponent’s king.

The king safety term itself is non-linear, and is quite complex, particularly before castling

has taken place.

7.3. Automated evaluation function analysis

Although the large majority of the features and weights in the Deep Blue evaluation

function were created/tuned by hand, there were two instances where automated analysis

tools aided in this process.

The first tool had the goal of identifying features in the Deep Blue I evaluation

function that were “noisy”, i.e., relatively insensitive to the particular weights chosen. The

hypothesis was that noisy features may require additional context in order to be useful. A

hill-climbing approach was used to explore selected features (or feature subsets), and those

that did not converge were candidates for further hand examination. A number of features

in the Deep Blue I evaluation were identified, and significantly modified in Deep Blue II

hardware, including piece mobility, king safety, and rooks on files.

A second tool was developed with the goal of tuning evaluation function weights.

This tool used a comparison training methodology [25] to analyze weights related to

pawn shelter. Training results showed that the hand-tuned weights were systematically

too low [26], and they were increased prior to the 1997 match. There is some evidence that

this change led to improved play [26].

8. Miscellaneous

8.1. Opening book

The opening book in Deep Blue was created by hand, primarily by Grandmaster Joel

Benjamin, with assistance from Grandmasters Nick De Firmian, John Fedorowicz, and

Miguel Illescas. The book consisted of about 4000 positions,

19

and every position had

been checked by Deep Blue in overnight runs. The openings were chosen to emphasize

positions that Deep Blue played well. In general this included tactically complex openings,

19

This may seem surprisingly small. In fact, numerous openings did have minimal preparation, due to our

confidence in the extended book (Section 8.2).

---

M. Campbell et al. / Artificial Intelligence 134 (2002) 57–83

77

but also included more positional openings that Deep Blue handled well in practice.

Opening preparation was most extensive in those openings expected to arise in match play

against Kasparov. In fact, none of the Kasparov-specific preparation arose in the 1997

match.

Prior to a game, a particular repertoire was chosen for Deep Blue. There were a number

of possible repertoires to choose from, and the choice would be made on the basis of

the match situation and the previous experience playing with the same color. Last minute

changes or corrections were made in a small “override” book.

8.2. Extended book

The extended book [6] in Deep Blue is a mechanism that allows a large Grandmaster

game database to influence and direct Deep Blue’s play in the absence of opening book

information. The basic idea is to summarize the information available at each position of

a 700,000 game database, and use the summary information to nudge Deep Blue in the

consensus direction of chess opening theory.

The specific mechanism used in Deep Blue was to assign bonuses (or penalties) to those

moves in a given position that had been played in the Grandmaster game database. For

example, suppose that in the opening position of a chess game the move d4 is given a 10

point bonus. Deep Blue would carry out its regular search, but offset the alpha-beta search

window for d4 by 10 points. Thus d4 would be preferred if it was no more than than 10

points worse the best of the other moves.

A number of factors go into the extended book evaluation function, including:

• The number of times a move has been played. A move frequently played by

Grandmasters is likely to be good.

• Relative number of times a move has been played. If move A has been played many

more times than move B, then A is likely to be better.

• Strength of the players that play the moves. A move played by Kasparov is more

likely to be good than a move played by a low-ranked master.

• Recentness of the move. A recently played move is likely to be good, an effect that

can in some cases dominate other factors.

• Results of the move. Successful moves are likely to be good.

• Commentary on the move. Chess games are frequently annotated, with the annotators

marking strong moves (with “!”) and weak moves (with “?”). Moves marked as strong

are likely to be good; moves marked as weak are likely to be bad.

• Game moves versus commentary moves. Annotators of chess games frequently

suggest alternative moves. In general, game moves are considered more reliable than

commentary moves, and are thus likely to be better.

We developed an ad hoc function that combined these factors in a nonlinear way to

produce a scalar value as output. The value of the bonus can be as high as half a pawn

in favorable situations. In some situations, where the bonus for one move is very large

and other move bonuses are much smaller, Deep Blue has the option of playing a move

immediately, without first carrying out a search.

---