M. Campbell et al. / Artificial Intelligence 134 (2002) 57–83
69
Table 3
Search characteristics, Position 2
Iteration
Minimum
Maximum
Estimated maximum
software depth
software depth
combined depth
6
2
5
11–21
7
3
6
12–22
8
4
10
16–26
9
5
16
22–32
10
6
19
25–35
11
7
20
26–36
12
8
24
30–40
machine is striving for a draw or the count will be negative if the machine is trying to avoid
a draw.
Another idea in Deep Blue, implemented in both hardware and software, is a pruning
mechanism we call “no progress”. It is based on the assumption that if a move is good
for a given side, it is best to play it earlier rather than later. “No progress” is implemented
by detecting if the current position could have been reached by playing an alternate move
at some earlier position on the search path. If so, the search is terminated with a fail low.
Although this algorithm has only limited effect in most positions, situations which are
somewhat blocked and have few pieces present can observe noticeable benefits.
5. Hardware search
The hardware search is that part of the Deep Blue search that takes place on the
chess chip. A chess chip carries out a fixed-depth null-window search, which includes
a quiescence search. There are also various types of search extension heuristics, both for
the full-width and the quiescence portions of the search, which are described below.
The hardware search is fast, but is relatively simple in the Deep Blue system
configuration. To strike a balance between the speed of the hardware search and the
efficiency and complexity of the software search, we limit the chess chips to carry out
only shallow searches. This typically results in 4- or 5-ply searches plus quiescence in
middlegame positions and somewhat deeper searches in endgames.
Once a hardware search is initiated, the host processor controlling that chip is free to do
other work, including performing the software search and initiating hardware searches on
other chips. The host polls the chips to determine when a hardware search has completed.
The host can abort a hardware search if needed, e.g., if the search is taking too long, or is
no longer relevant.
The fact that the hardware search uses a null window requires special handling in the
case where an exact value within a range is needed, rather than a bound. The host can carry
out a binary search, initiating a series of null-window searches to determine the value. In
many cases it is possible to use multiple chess chips simultaneously to speed this operation.
70
M. Campbell et al. / Artificial Intelligence 134 (2002) 57–83
The main parameters of the hardware search are described below:
1. Depth of search, which controls the depth of the full-width portion of the hardware
search. This is the primary parameter for controlling the size of search.
2. Depth of offset searches, to detect singular, binary, trinary conditions at the root
node of the hardware search tree.
3. Endgame rules assertions off or on (always on in Deep Blue software code). The
switch is mainly for debugging purposes.
4. Endgame ROM assertions off or on (always on in Deep Blue software code). The
switch is mainly for debugging purposes. The endgame ROMs on the chess chip
had the goal of improving the evaluation of common endgames where the natural
evaluation was inaccurate. The particular endgames included were king and pawn
vs. king, rook and pawn vs. rook, queen vs. pawn, and rook vs. pawn. Each endgame
has certain characteristic patterns which are drawn, and some of these patterns are
encoded in the ROMs.
5. Number of “mating” checks allowed for each side in the quiescence search.
A mating check is a checking move which allows zero escape squares for the king
or any checking move which is a “contact”
15
check by the queen. This parameter is
used to control the size of the quiescence search.
6. Number of singular checking moves allowed in the quiescence search (king has one
escape square, or queen or rook contact check, or any check given while the checked
side has a hung
16
piece). This parameter is used to control the size of the quiescence
search.
7. Flags to enable testing of singular, binary, or trinary conditions at the search root.
These extensions are only implemented at the root of the hardware search. Without
access to a transposition table, more general implementations could suffer from
non-terminating searches.
8. Flag to ignore stalemate at one ply above quiescence.
9. Flag to allow a one-ply extension in the quiescence search after a pawn moves to
the 7th rank or, in some cases, pawn moves to the 6th rank.
10. Flag to allow a one-ply extension in the quiescence search when the side to move
has multiple hung pieces or a piece that is pinned and hung.
11. Flag to allow a one-ply extension in the quiescence search when the side to move
has one hung piece for consecutive plies.
12. Flag to allow a one-ply extension in the quiescence search if opponent has any hung
pieces.
6. Parallel search
Deep Blue is composed of a 30-node RS/6000 SP computer and 480 chess chips, with
16 chips per node. The SP nodes communicate with each other using the MPI (Message
Passing Interface) standard [10]. Communication is via a high-speed switch. The chess
15
A contact check is a checking move to a square immediately adjacent to the opposing king.
16
A hung piece can be captured by the opponent with apparent safety.