Artificial Intelligence 134 (2002) 57-83

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

73

7. Evaluation function

7.1. Overview

The Deep Blue evaluation function is essentially a sum of feature values. The chess chip

recognizes roughly 8000 different “patterns”, and each is assigned a value. Features range

from very simple, such as a particular piece on a particular square, to very complex, as will

be described below in Section 7.2. A feature value can be either static or dynamic. Static

values are set once at the beginning of a search. Dynamic values are also initialized at the

beginning of a search, but during the search they are scaled, via table lookup, based on the

value and type of pieces on the board at evaluation time. For example, king safety, passed

pawns, and pawn structure defects are sensitive to the amount of material on the board.

The initialization of the feature values is done by the “evaluation function generator”, a

sub-program which was run on the master node of SP system. The Deep Blue evaluation

function generator is run only at the root of the search tree. It would likely be of great

benefit to run it at other nodes near the root of the tree after a large positional change

has occurred, such as trading queens. Although the dynamic evaluation terms can handle

this type of transition, some static feature values may be left with less than ideal values.

Unfortunately the full evaluation function generator takes measurable wall clock time to

run and download, and partial downloading was considered too complex to implement.

The evaluation function generator has a second role beyond simply adjusting feature

values based on the context of the root position. The large number of distinct feature values

dictate that some sort of abstraction be imposed on the values in order to keep the task

manageable. The evaluation generator makes these abstractions, dictating relationships

between groups of related feature values rather than setting them independently.

There are 54 registers (see Table 4) and 8096 table entries (see Table 5) for a total of 8150

parameters that can be set in the Deep Blue evaluation function.

18

Some of the parameters

correspond to chess situations that are not physically realizable (e.g., pawns on the first

rank), and others are used for control purposes rather than corresponding to a particular

combination of chess features. There are about 8000 actual features that can be detected in

the chess hardware.

It is impossible in a paper like this to describe all the details of the evaluation function.

We will present a detailed example of one table that gives a feel for the nature of

the evaluation function. A brief description of all the registers and tables is given in

Appendix A.

7.2. Extended example: Rooks on files

We now describe in detail the “Rooks on files” table. We will begin by describing the

features that are detected, then discuss the values assigned to each combination of features,

and show how the values are incorporated into the overall position evaluation.

18

In actual fact, the number is even higher than this. Many of the registers and table entries have two, three, or

even four separate values. The extended example in Section 7.2 illustrates one method of using multiple values.

---

74

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

Table 4

Deep Blue evaluation registers

Function

Number of registers

Data bits

Rooks on seventh rank

12

8

Bias

1

8

Opposing rook behind passed

1

9

Mpin and hung

1

7

Pinned and simple hung

1

8

Hung

4

7

Xraying

2

6

Pinned and hung

1

7

Permanent pin and simple hung

1

8

Knight trap

6

8

Rook trap

8

8

Queen trap

2

8

Wasted pawns

2

6

Bishop pair

2

7

Separated passed

2

8

Missing wing

2

10

Bishops of opposite colors

2

6

Evaluation control

2

32

Side to move

2

4

The chessboard is scanned, one file at a time, and a pair of values is looked up, one from

the white rook table and one from the black rook table, for each file. The index bits for

these tables are as follows:

• “unopposed” is a 1-bit subindex, with 0 indicating an enemy pawn on the file, and 1

indicating no enemy pawn on the file.

• “blockage” is a 2-bit subindex with two interpretations, depending on whether or not

there is an enemy pawn on the file. If there are no enemy pawns, 0 indicates that my

rook could safely move to the 7th or 8th ranks, 1 indicates that there is a minor piece

guarded by a pawn that blocks the file, 2 indicates that enemy minor pieces guard the

7th and 8th ranks, and 3 indicates that the 7th and 8th are guarded by the enemy, but

not by minor pieces. If there is an enemy pawn on the file, 0 indicates that the pawn

is unprotected, 1 indicates that there is a minor piece guarded by a pawn that shields

the pawn, 2 indicates that the pawn is protected by a minor piece, and 3 indicates

“granite”, i.e., the pawn is protected by another pawn.

• “semi_open” is a 1-bit subindex, with 0 indicating the presence of a pawn of mine on

the file, and 1 indicating no pawns of mine on the file.

---