66
M. Campbell et al. / Artificial Intelligence 134 (2002) 57–83
1
int DC(
2
position p,
3
int alpha, int beta,
4
int depthToGo,
5
∗
float myCredit, float hisCredit)
6
{
7
int numOfSuccessors;
8
int bestScore;
9
int i;
10
int sc;
11
∗
float newCredit;
12
∗
int extensionAmount;
13
14
∗
if (hisCredit >= CREDIT_LIMIT) {
15
∗
extensionAmount = ceiling(hisCredit - CREDIT_LIMIT);
16
∗
hisCredit = hisCredit - extensionAmount;
17
∗
myCredit = max(myCredit - extensionAmount, 0);
18
∗
depthToGo = depthToGo + extensionAmount;
19
∗
}
20
21
if (depthToGo == 0) { return Evaluate(p); }
22
23
bestScore = alpha;
24
numOfSuccessors = GenerateSuccessors(p);
25
for (i = 1; i <= numOfSuccessors; i++) {
26
∗
sc = -DC(p.succ[i], -beta, -alpha, depthToGo - 1,
hisCredit, myCredit);
27
if (sc > bestScore) {
28
∗
newCredit = GenerateCredit();
29
∗
if (newCredit > 0)
30
∗
sc = -DC(p.succ[i], -beta, -alpha, depthToGo - 1,
hisCredit, myCredit + newCredit);
31
∗
if (sc > bestScore)
32
bestScore = sc;
33
}
34
if (bestScore >= beta) { return bestScore; }
35
}
36
return bestScore;
37
}
Fig. 1. The dual credit algorithm.
generated in earlier appearances of this position, and search with at least that amount of
credit. This avoids oscillating searches, as well as significantly reducing the number of
re-searches (line 29). Details such as checkmate and stalemate have also been glossed
over.
M. Campbell et al. / Artificial Intelligence 134 (2002) 57–83
67
4.1. Credit generation mechanisms
There is a large set of mechanisms to identify nodes that should receive credit.
1. Singular, binary, trinary, etc.
12
A singular move is one that is significantly better than all the alternatives [2]. One can
generalize this to the case where there are two, three or more good moves. Of course
the more reasonable moves that are available, the less credit that should be given. It
is clear that a large part of what a strong human chess player would define as forcing
is covered by singularity. It is in just these kinds of positions that Grandmasters are
able to calculate very deeply.
2. Absolute singular.
When there is only one legal move a large credit can be given with very little risk.
The reason is that, if the absolute singular move ends up failing low, there are no
alternatives to examine so the cost is contained. It is reasonable in many cases to give
a full two ply extension. This type of move is usually a check evasion move.
3. Threat, mate threat.
It is relatively simple using a null move search to detect if there is a threat in the
current position [1]. A null move search is a search conducted after one side passes.
The intuition here is that if one side passes, then loses quickly, that side is deemed to
have a pending threat against it which the other side is close to exploiting. Positions
where a threat exists tend to be constrained in the number of reasonable alternatives.
If a large threat exists, such as a threat to checkmate, a higher level of credit can
be given. The Deep Blue implementation required that recent ancestors of a given
position have forcing characteristics before a threat credit is given.
4. Influence.
This mechanism gives credit for moves which are enabled by previous moves. For
example, credit may be given for an apparently good white response to a black
move which was not available the previous time black moved. The idea here is that
we assume black is developing a combination even if we don’t quite see what the
combination is.
5. Domain dependent.
Traditional search extension schemes, such as check evasion and passed pawn pushes,
can also be incorporated into this method. For example, a passed pawn push can be
considered a forcing move, and the response, if it does not fail low, can generate
credit.
Many of these methods require auxiliary computation in order to gather the information
necessary to make extension decisions. This was in line with our philosophy of using the
tremendous raw searching power of Deep Blue to enable a more selective search.
The credit assigned for various conditions is depth dependent, with positions near the
root of the tree generally receiving more credit than positions far from the root. This choice
allowed quicker resolution of moderately deep forcing lines without allowing the search to
explode.
12
This terminology is borrowed from stellar astronomy, where it is used to count the number of stars in a
system.
68
M. Campbell et al. / Artificial Intelligence 134 (2002) 57–83
Table 2
Search characteristics, Position 1
Iteration
Minimum
Maximum
Estimated maximum
software depth
software depth
combined depth
6
2
5
11–21
7
3
6
12–22
8
4
11
17–27
9
5
15
21–31
10
6
17
23–33
11
7
20
26–36
12
8
23
29–39
4.2. Sample behavior
The following gives a sample of the behavior of Deep Blue in two quite different
positions. The first position
13
is before White’s move 37 in the game Deep Blue–Garry
Kasparov, Match game 2, New York, 1997, and contains some forcing tactical lines (see
Table 2). The second position
14
is before Black’s move 11 in the fifth game of the same
match, and would not normally be considered a tactical position (see Table 3). For better
observability, this experiment was run on Deep Blue Jr., a version of Deep Blue that runs
on a single node of an IBM RS/6000 SP computer. For a given iteration i, the software is
assigned i
− 4 ply, which represents the minimum depth search in software. The maximum
depth reached in software is greater than the minimum due to search extensions, and this
value is given in the third column. In these two positions, the maximum software depth is
approximately three times the minimum depth. The last column estimates the maximum
depth reached in hardware and software combined. It is not possible to directly measure
this number, but the estimate is based on results of simulating the hardware search. When
hardware search extensions and quiescence search are taken into account, we typically see
searches of 6 to 16 ply. Thus we can see iteration 12 searches can reach as deep as 40 ply in
positions of this type, which suggests that position 2 is rather tactical after all. This shows
that a superficial analysis of a position does not always assess the forcingness of the key
lines of play.
4.3. Miscellaneous
The Deep Blue scores are composed of two 16-bit signed integers. The regular search
score is in one integer, and the tie breaker score is in the other. Therefore, for a draw, the
regular search score is zero and the tie breaker contains either the static evaluation of a
theoretically drawn position or the count of moves until repetition, which is also useful
choosing draws in the midgame. The count of moves to repetition will be positive if the
13
r1r1q1k1/6p1/3b1p1p/1p1PpP2/1Pp5/2P4P/R1B2QP1/R5K1 w.
14
r2qk2r/pp3ppp/2p1pn2/4n3/1b6/3P2PP/PPPN1PB1/R1BQK2R b.