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.