Efficient quiescence

Hans Bogaards

unread,

Jan 18, 1994, 1:59:56 PM1/18/94

to

Hi all,

My chess program is almost finished (at least the first playing version),
but when i test it, the quiescence search takes a lot of time (+-60%)

In the quiescence search my program tries out all captures and promotions,
except those whose capture value + constant does not reach the alfa-beta
window. (capture value= the value of the captured piece, not a value that
came from an exchange evaluator).

Is there a way of making the quiescence search more efficient, without
losing playing strength?

I have heard of some way, but my feeling with that is that it will lose
strength (I'm not sure):
Ply 1 of capture search: all captures
other plies: only captures to squares on which a piece was captured
earlier in the variation.

Is this a good way??

Stuart Cracraft

unread,

Jan 19, 1994, 1:38:26 AM1/19/94

to

Try an all-capture search. I've found it to be self-limiting
and, with a good time-interrupt algorithm, results in reasonable
move selections.

--Stuart

Robert Hyatt

unread,

Jan 19, 1994, 10:17:35 AM1/19/94

to

In article <2hhbjc$l...@tuegate.tue.nl> han...@stack.urc.tue.nl (Hans Bogaards) writes:
>Hi all,
>
>My chess program is almost finished (at least the first playing version),
>but when i test it, the quiescence search takes a lot of time (+-60%)
>
>In the quiescence search my program tries out all captures and promotions,
>except those whose capture value + constant does not reach the alfa-beta
>window. (capture value= the value of the captured piece, not a value that
>came from an exchange evaluator).
>
>Is there a way of making the quiescence search more efficient, without
>losing playing strength?
>
>I have heard of some way, but my feeling with that is that it will lose
>strength (I'm not sure):
> Ply 1 of capture search: all captures
> other plies: only captures to squares on which a piece was captured
> earlier in the variation.
>
>Is this a good way??
>
>I hope you can help me.
>bye,

In Cray Blitz, we have a static exchange evaluator that we use to control
the capture part of the quiscence search. The idea is that you generate
the captures, then use the exchange evaluator to look at captures
ON THAT SQUARE (where the capturing move ends up) to see if the capture
seems to (a) win (b) be even (c) loses material. This exchange
code does not worry about pins, overloaded pieces, just captures on
the square in question. For the first couple of plies, we use (a) and (b)
moves but not (c) and then we switch to (a) only. Don't really have any
data as to how much this helps now, but when we did it it apparently was
enough that we kept the idea...

--
!Robert Hyatt Computer and Information Sciences !
!hy...@cis.uab.edu University of Alabama at Birmingham !

Gijsb. Wiesenekker

unread,

Jan 21, 1994, 1:52:23 PM1/21/94

to

Hans Bogaards (han...@stack.urc.tue.nl) wrote:
: Hi all,

In ZZZZZZ the quiescence looks something like:

#define QUIES_MAX 2

int quies(int depth, int alpha, int beta)
{
int best, temp;

best = eval();
if (best >= beta) return(best);
for (all your pieces)
{
if ((depth >= QUIES_MAX) and
(no capture flag set on your piece)) continue;
for (all my ways to capture your piece)
{
temp = -quies(depth + 1, -beta, -MAX(alpha, best));
best = MAX(temp, best);
if (best >= beta) return(best);
}
}
return(best);
}

When a piece captures, a capture flag is set on that piece.
In the quiescence I allow QUIES_MAX free captures (so any piece
may capture any other piece), but after these QUIES_MAX free
captures only captures to pieces with the capture flag set are
allowed. In this way the quiescence search always terminates and
many exchanges like 'I capture your queen, you capture my queen etc.'
are evaluated correctly. Higher QUIES_MAX values give better
results, but also makes the program slower, so there is a trade off
here. In ZZZZZZ the quiescence search hardly takes time:
the quiescence search usually already terminates after the first eval() call
(depth = 0) (an evaluation you would have to do any way) and only about 10%
of the eval() calls come from deeper inner nodes.
I also experimented with null moves in the quiescence search, but that
did not help much.

Gijsbert Wiesenekker
wiese...@sara.nl
ZZZZZZ author