Deep Quiesence Searching
Steve Dicks
Both myself and a friend have each developed a fairly low-power chess
program over the years - mine in Z80, his in 'C' (guess which plays better!)
However they both suffer from the same basic problem, that having done a
fixed-ply look-ahead they then go into a quiesence search - and spend loads
of time following stupid multi-capture lines, going 30-ply deep sometimes.
Is there a known technique for dealing with such a situation?
--
Steve Dicks - Starswan Systems Ltd
Hertfordshire's premier one-man Systems Consultancy
... Claravoiant meeting canceled due to unforseen events.
Joe Stella
Steve Dicks <st...@starswan.demon.co.uk> wrote:
Eeek, a *real* chess programming question! What's this doing here in
this newsgroup! :)
You have to be sure that you cut off the search when it no longer
makes sense to continue. Here's what I have found useful:
Quies (int alpha, int beta...)
{
..
if (score >= beta) return score;
if (score > alpha) alpha = score
generate_captures();
best_score = score;
for (all captures && !cutoff) {
make_move();
search_score = -quies (-beta, -alpha, ...);
unmake_move();
if (search_score > best_score) best_score = search_score;
if (search_score > alpha) alpha = score;
if (search_score >= beta) cutoff = 1;
...
}
}
There are some things missing here (left as an exercise to the reader :)
but the idea is in the "if" statements. The ones at the top of the
routine will cause an immediate beta cutoff if the current score is already
greater than beta, or will update alpha to get the max number of cutoffs.
The "if" statements inside the loop are just the usual beta cutoff/alpha
update in normal alpha/beta search.
Joe Stella
Robert Hyatt
Steve Dicks (st...@starswan.demon.co.uk) wrote:
: Both myself and a friend have each developed a fairly low-power chess
: program over the years - mine in Z80, his in 'C' (guess which plays better!)
: However they both suffer from the same basic problem, that having done a
: fixed-ply look-ahead they then go into a quiesence search - and spend loads
: of time following stupid multi-capture lines, going 30-ply deep sometimes.
: Is there a known technique for dealing with such a situation?
A couple of things...
1. throw out losing captures, so you don't follow bizarre sacrificing
lines forever. You can use a static exchange evaluator here.
2. If the current score is way below alpha, and capturing this piece
won't pull the score back above alpha, there's no need in searching this
capture at all. You might want to add in a fudge for what your eval might
add in, but the idea is easy.
3. deep in the qsearch, what what captures what. Richard Lang once let
something slip about not letting the queen rip pawns way down in the search,
since often somethingxQ is the reply...
Martin Borriss
In article <5enk24$g...@juniper.cis.uab.edu>,
hy...@crafty.cis.uab.edu (Robert Hyatt) writes:
>: However they both suffer from the same basic problem, that having done a
>: fixed-ply look-ahead they then go into a quiesence search - and spend loads
>: of time following stupid multi-capture lines, going 30-ply deep sometimes.
>: Is there a known technique for dealing with such a situation?
>
>1. throw out losing captures, so you don't follow bizarre sacrificing
>lines forever. You can use a static exchange evaluator here.
>
>2. If the current score is way below alpha, and capturing this piece
>won't pull the score back above alpha, there's no need in searching this
>capture at all. You might want to add in a fudge for what your eval might
>add in, but the idea is easy.
>
The static exchange evaluator should have the knowledge (e.g. bounds) to
handle this, so no extra code in quies() required.
>3. deep in the qsearch, what what captures what. Richard Lang once let
>something slip about not letting the queen rip pawns way down in the search,
>since often somethingxQ is the reply...
>
Of course one should listen to Richard Lang - but who wants to miss the
cases where there is no "something x Q" ?
Since having a slim quiescence search seems important, here are quiescence
percentages from Gullydeckel running the BK suite. E.g., in the first
position 73% of the positions searched were searched in quiescence.
(72.98%) (78.45%) (86.93%) (79.91%) (85.24%) (64.95%)
(85.17%) (70.61%) (85.92%) (86.70%) (86.26%) (83.47%)
(83.91%) (80.84%) (76.99%) (83.47%) (89.52%) (87.27%)
(81.53%) (84.75%) (81.64%) (90.46%) (86.91%) (87.43%)
Martin
Robert Hyatt
Martin Borriss (bor...@inf.tu-dresden.de) wrote:
: In article <5enk24$g...@juniper.cis.uab.edu>,
: hy...@crafty.cis.uab.edu (Robert Hyatt) writes:
: Martin
: --
: Martin....@inf.tu-dresden.de
How are you counting quiesce nodes? IE how do you count the nodes wither
depth=0 (the ones right below positions where depth=1 and you look at all
moves?) With that, I'll try the test and post the same values...
Martin Borriss
In article <5es4b6$f...@juniper.cis.uab.edu>,
hy...@crafty.cis.uab.edu (Robert Hyatt) writes:
>Martin Borriss (bor...@inf.tu-dresden.de) wrote:
>: In article <5enk24$g...@juniper.cis.uab.edu>,
>: hy...@crafty.cis.uab.edu (Robert Hyatt) writes:
>
>: >: However they both suffer from the same basic problem, that having done a
>: >: fixed-ply look-ahead they then go into a quiesence search - and spend loads
>: >: of time following stupid multi-capture lines, going 30-ply deep sometimes.
>: >: Is there a known technique for dealing with such a situation?
>
[...]
>
>: Since having a slim quiescence search seems important, here are quiescence
>: percentages from Gullydeckel running the BK suite. E.g., in the first
>: position 73% of the positions searched were searched in quiescence.
>
>: (72.98%) (78.45%) (86.93%) (79.91%) (85.24%) (64.95%)
>: (85.17%) (70.61%) (85.92%) (86.70%) (86.26%) (83.47%)
>: (83.91%) (80.84%) (76.99%) (83.47%) (89.52%) (87.27%)
>: (81.53%) (84.75%) (81.64%) (90.46%) (86.91%) (87.43%)
>
>
>How are you counting quiesce nodes? IE how do you count the nodes wither
>depth=0 (the ones right below positions where depth=1 and you look at all
>moves?) With that, I'll try the test and post the same values...
>
At depth == 0 I go into into quiescence and count this as quies node.
Below is a pseudo code fragment which tries to show how I count those.
Martin
P.S.: There is another very interesting number which is not shown; This is
the branching factor (for the full search) measured by relating the number
of moves executed to the number of moves generated per search() call.
Agreed?
int
search(const int alpha,const int beta,int n,const int index)
{
gamestat.search_nodes++; /* search nodes */
n--; // ignore extensions here
while(makemove()) {
if(n)
value = -search(-beta,-best,n,new_index);
else
value = -quies(-beta, -best,new_index);
unmake();
}
int
quies(const int alpha,const int beta,const int index)
{
gamestat.quies_nodes++; /* quiescence nodes */
// fix a value by evaluating
// do certain selective searching (captures)
// note: we might get back to search() if we are in check here
}
Vincent Diepeveen
>Both myself and a friend have each developed a fairly low-power chess
>program over the years - mine in Z80, his in 'C' (guess which plays better!)
>However they both suffer from the same basic problem, that having done a
>fixed-ply look-ahead they then go into a quiesence search - and spend loads
>of time following stupid multi-capture lines, going 30-ply deep sometimes.
>Is there a known technique for dealing with such a situation?
Just do 2 ply maximum of captures to
a) pieces of higher rank
b) pieces standing on squares you already captured.
then do only x-ply recaptures on the squares you captured in q-search.
That will easily limit it.
>--
>Steve Dicks - Starswan Systems Ltd
>Hertfordshire's premier one-man Systems Consultancy
>... Claravoiant meeting canceled due to unforseen events.
>
>
--
+----------------------------------------------------+
| Vincent Diepeveen email: vdie...@cs.ruu.nl |
| http://www.students.cs.ruu.nl/~vdiepeve/ |
+----------------------------------------------------+