Artificial Intelligence 134 (2002) 57-83



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

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.




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ə