Author: Don Beal
Date: 16:44:31 10/02/04
Go up one level in this thread
On October 01, 2004 at 19:13:55, Stuart Cracraft wrote:
>I see your point and have put it under a "NULLBEAL" conditional
>compilation. Initial testing gave a 5% worse result and I think
>all the settings are correct. The extra search does seem to have
>some bad effects:
>
>Before double-search
>
>+ 7.23/22.74 82% 247/300 ha=33 302.85 69122512 230408/1/228240
>0/414899/376597/0/16986524/259220
>
>After double-search
>
>+ 5.63/20.38 77% 232/300 ha=26 303.42 75126144 250420/1/247600
>0/419336/230182/0/26909694/210430
>
>So about 1.6 fewer plies searched on average in main search and
>2 plies less deep for maximum ply researched. Although speed was
>up from 228k to 247k nps the total nodes search jumped from 69M
>to 75M.
>
>Here is the code:
> if (null move okay to do) {
>#ifndef NULLBEAL
> value = -search(bd,sdepth-1-reduction,ply,-beta,-beta+1,
> NULLNOTOK,mvstr,SAVETOP,verify,REDUCENOTOK,checked);
> if (value == -MATE+ply+2) threat=1;
>#endif
>#ifdef NULLBEAL
> // test for mate extension
> value = -search(bd,sdepth-1-reduction,ply,MATE-1,MATE,
> NULLNOTOK,mvstr,SAVETOP,verify,REDUCENOTOK,checked);
> if (value < -MATE) { threat=1; printf("threat\n"); pbd(bd); getchar(); }
> // test for null move prune
> value = -search(bd,sdepth-1-reduction,ply,-beta,-beta+1,
> NULLNOTOK,mvstr,SAVETOP,verify,REDUCENOTOK,checked);
>#endif
> if (value >= beta) {
> :
What was the result on WAC141? Did that solve faster?
The post I originally replied to, asked about getting your
mate threat extensions working and was about WAC141 in
particular.
Either way, your test on the complete WAC suite shows that
the new version isn't beneficial. However, my interpetation
of your test is that it's not the "double search" which
has degraded performance on WAC. Rather, I would guess the new
code detected mate threats that were not being detected before,
and the mate threat extensions have degraded your program's
WAC performance overall instead of inproving it. (Against
expectations, but that's not uncommon with chess programs.)
A few minor things before firm conclusions, though:
(1)
I notice you set the alpha-beta bounds for the mate detection
search to (MATE-1,MATE), whereas I had (MATEV,MATEV+1). If you
always return mate values which are *above* the discrimination
value "MATE" (so you return a value >MATE, even though the
upper bound is MATE), then the functionality is the same,
but if you are working with strict bounds, then your version
is incorrect.
(2)
I see you have printf's and other I/O in the NULLBEAL code,
and not in the original. (Unfair!) The additional execution
time might be insignificant, but I think you should eliminate that
difference before drawing firm conclusions.
(3)
In my last post I placed the tests in the order "mate-threat?"
followed by "null-prune?" This is a slight inefficiency (since
null prunes render the mate test unnecessary), although it
had the advantage of less change to the structure of your program
and I would expect the inefficiency to be very minor. But if you
change the order, there will be fewer "double searches" and
greater efficiency.
You might like to try the more efficient order, i.e.:
// test for null move prune
value = -search(bd,sdepth-1-reduction,ply,-beta,-beta+1,
NULLNOTOK,mvstr,SAVETOP,verify,REDUCENOTOK,checked);
if (value >= beta) { /* do null move prune stuff */ }
// if we haven't pruned, test for mate threat extension
value = -search(bd,sdepth-1-reduction,ply,MATEV,MATEV+1,
NULLNOTOK,mvstr,SAVETOP,verify,REDUCENOTOK,checked);
if (value < -MATEV) threat=1;
// do main search
Assuming you didn't change anything else for this test, and
mate threat extensions really are detrimental to your program's
WAC performance, then I guess your request shifts to any
modification that improves WAC overall.
I would start by looking at the quiescence search, to ensure it is
cost effective. I suggest it should be limited to captures (and further
limited to captures with a non-losing SEE, if you have SEE), except
at the root of the qsearch where it would be desirable to include checks,
so that mate-in-1 would be seen at the endpoints of the main search.
I.e., something equivalent to the following pseudo code:
mainsearch(...)
{ ... v= - qsearch_root(-beta,-bestv); ... }
qsearch_root(alpha,beta)
{ if(incheck) return( qsearch_evade(alpha,beta) );
bestv= stand_pat(alpha,beta); if(bestv >= beta) return(bestv);
mlist= capts_and_checks();
while( /* mlist not empty */ && bestv < beta )
{ m= /* best from list according to SEE, discarding noncheck losing SEE's
*/;
makemv(m);
if(incheck) v= -qsearch_evade(-beta,-bestv);
else v= -qsearch_simple(-beta,-bestv);
unmakemv(m);
if(v > bestv) bestv= v;
}
return(bestv);
}
qsearch_evade(alpha,beta)
{ bestv= -CHECKMATE; mlist= check_evasions();
while( /* mlist not empty */ && bestv < beta )
{ m= /* next from list */;
makemv(m); v= - qsearch_simple(-beta,-bestv); unmakemv(m);
if(v > bestv) bestv= v;
}
return(bestv);
}
qsearch_simple(alpha,beta)
{ bestv= stand_pat(alpha,beta); if(bestv >= beta) return(bestv);
mlist= capts_only();
while( /* mlist not empty */ && bestv < beta )
{ m= /* best from list according to SEE, discarding losing SEE's */ ;
makemv(m); v= - qsearch_simple(-beta,-bestv); unmakemv(m);
if(v > bestv) bestv= v;
}
return(bestv);
}
The pseudo code above is arranged so that most of the searching
will be done by qsearch_simple. qsearch_simple deals only
with captures, and never considers checks or whether it is
in check, and so it should be relatively few nodes and run fast.
(Of course, the code could be arranged to be functionally equivalent
with only one recursive routine and suitable conditional code
within the routine. I think the code above is easier to understand.)
If this is what you do already, or is no help, I guess Steve
will have to look elsewhere for an extra $50 :-).
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.