Artificial Intelligence 134 (2002) 57-83



Yüklə 259,28 Kb.
Pdf görüntüsü
səhifə5/10
tarix16.11.2017
ölçüsü259,28 Kb.
#10667
1   2   3   4   5   6   7   8   9   10

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.




Yüklə 259,28 Kb.

Dostları ilə paylaş:
1   2   3   4   5   6   7   8   9   10




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©genderi.org 2024
rəhbərliyinə müraciət

    Ana səhifə