Author: Stuart Cracraft
Date: 16:42:48 10/08/04
Go up one level in this thread
On October 08, 2004 at 19:15:02, Michael Henderson wrote:
>On October 08, 2004 at 18:43:04, Stuart Cracraft wrote:
>
>>Okay so on the one hand I am supposed to do a reduced
>>search for null move with bounds -beta,-beta+1, and
>>return if the value is >= beta.
>>
>>The mate threat has to be compared with a mate value
>>but the beta's above aren't relevant. Do I need to
>>do a second reduced search after the above with bounds
>>-MATE,-MATE+1 and see if it is >= MATE and if so set
>>the mate threat flag to trigger the extension???
>
>Hi Stuart,
>
>No second search is needed. If you get a -MATE in 1 value (or whatever) as a
>fail low, then you extend. However, if you use bounded mate scores in the hash
>table, this does not work because it is not possible to get exact mate scores.
>This is why I am giving up using it.
>
>Could you please explain/post code for how you store/retrieve mate scores in the
>hash table? It's easy to get bugs when doing that and hash bugs can definitely
>mess up your threat detection. I think I could help you out then :)
>
>Michael
Okay here's basically the whole shebang for extension settings,
transposition store() and retrieve() functions and capture search
quiesce() and main search search(). I don't use these flags:
QCZZ, QCXX, TWOTIER, *ETC*, IID, NULLMVADAPTIVE, VERIFYNULLMV, BITS.
I do use TT, NULLMV and these extension flags.
Current solution time of WAC 141 is about 7 seconds without mate threat
and within 3% of best alltime overall on WAC 300 set which to me is not
a bad tradeoff. But I see people solving WAC 141 in less than a second
and want to get there.
Note -- since the bet of $100 was for getting WAC 141 under 10 seconds
and I did this by a reorg of the recaptures to be per-move rather than
at node-entry, there is no winner.
However, to renew the bet, I will renew at $25 for the first to help
get WAC 141 under 1 second from the current 7 seconds.
Stuart
#define RECAP // Extend recaptures in the main search
#define RECAP_EXT 1.00
#define MTHR // Extend mate threats in the main search
#define MTHR_EXT 1.00
#define PAWNX // Extend pawn moves to the 7th rank in the main search
#define PAWNX_EXT 1.00
#define CXX // Extend checking moves in the main search
#define CXX_EXT 1.00
#define ONEX // Extend positions with only one legal move
#define ONEX_EXT 1.00
#ifdef TT
int retrieve(int *length, int *score, char *flag, mv *hashmv, int *threat)
{
HASHE * phashe = &hash_table[hashkey % MAXHASH];
ttprobes++;
if (phashe->key == hashkey) {
*threat = phashe->threat;
*length = phashe->depth;
*score = phashe->val;
*flag = phashe->flags;
savemove(hashmv, phashe->best);
ttmatches++;
return(1);
}
#ifdef TTTWOTIER
else if ((phashe+1)->key == hashkey) {
*threat = (phashe+1)->threat;
*length = (phashe+1)->depth;
*score = (phashe+1)->val;
*flag = (phashe+1)->flags;
savemove(hashmv, (phashe+1)->best);
ttmatches++;
return(1);
}
#endif
return(0);
}
void store(int length, int score, char flag, mv hashmv, int threat)
{
HASHE * phashe = &hash_table[hashkey % MAXHASH];
// If position to be stored has depth greater than or equal to entry
// backup 1st level to 2nd level and then store at 1st level.
// If position to be stored has depth less than entry, store at 2nd level.
if (length >= phashe->depth) {
#ifdef TTTWOTIER
(phashe+1)->threat = phashe->threat;
(phashe+1)->key = phashe->key;
(phashe+1)->val = phashe->val;
(phashe+1)->flags = phashe->flags;
(phashe+1)->depth = phashe->depth;
savemove(&(phashe+1)->best,phashe->best);
#endif
phashe->threat = threat;
phashe->key = hashkey;
savemove(&phashe->best,hashmv);
phashe->val = score;
phashe->flags = flag;
phashe->depth = length;
#ifdef TTTWOTIER
} else {
(phashe+1)->threat = threat;
(phashe+1)->key = hashkey;
(phashe+1)->val = score;
(phashe+1)->flags = flag;
(phashe+1)->depth = length;
savemove(&(phashe+1)->best,hashmv);
#endif
}
}
#endif
int search(int *bd, int depth, int ply, int alpha, int beta,
char *mvstr, int savetop, int verify, int reduced,int achecked);
int quiesce(int *bd, int ply, int alpha, int beta, char *mvstr,int checked,
int qdepth)
{
int bestmvi=-1,mvi,value,seeval,baseval,delta,capture,tto,ok=0,j,timethru=1;
char flag, mvs[10];
mv qml[MAXMOVES],hashmv;
npvl[ply]=ply;
qnodes++;
if (ply > maxply) maxply = ply;
if (reps()==2 || pawndrawn()) return(DRAW);
if (ply >= MAXPLY) {
#ifdef ASSERT1
printf("ASSERT, quiesce, ply(%d) >= MAXPLY(%d)\n",ply,MAXPLY);
pbd(bd);
listmvs(hist);
getchar();
#endif
return alpha;
}
baseval = value = eval(bd,QUIET);
if (value >= beta)
return(value); // was beta 1
if (value > alpha)
alpha = value;
#ifndef QCXX
gencap(bd,qml,stm);
#endif
#ifdef QCXX
if (qdepth == 0) genmv(bd,qml,stm,SORT,SEEOK);
else gencap(bd,qml,stm);
#endif
again:
mvi = 0;
while (qml[mvi].from != -1) {
capture=0;
if (bd[qml[mvi].to] != MT || qml[mvi].flg == ENPASSANT) capture=1;
if (timethru == 1 && !capture) { mvi++; continue; }
if (timethru == 2 && capture) { mvi++; continue; }
#ifdef SEE
if (timethru == 1) {
delta = MAX(alpha-maxposnscore[stm]-baseval,0);
seeval=qml[mvi].see;
if (capture && qdepth != 0) {
if (seeval < delta) { futilityext++; mvi++; continue; }
if (seeval < 0) { futilityext++; mvi++; continue; }
}
}
#endif
makemv(bd,qml[mvi]);
strcpy(mvs,sqnames[qml[mvi].from]);
strcat(mvs,sqnames[qml[mvi].to]);
if (!incheckopp(bd))
if (timethru == 1 && capture
#ifdef QCZZ
&& ((qdepth != 0 && seeval >= 0) ||
(qdepth == 0 && seeval >= 0) ||
(qdepth == 0 && seeval < 0 && incheck(bd)))
#endif
#ifdef QCXX
|| (timethru == 2 && incheck(bd))
#endif
) {
value = -quiesce(bd,ply+1,-beta,-alpha,mvs,2,qdepth+1);
if (timethru == 2) qcheckext++;
}
unmakemv(bd);
if (value >= beta)
return(value); // was beta 2
if (value > alpha) {
bestmvi = mvi;
alpha = value;
savemove(&npv[ply][ply],qml[mvi]);
for (j=ply+1;j<npvl[ply+1];++j) savemove(&npv[ply][j],npv[ply+1][j]);
npvl[ply]=npvl[ply+1];
}
mvi++;
}
#ifdef QCXX
if (timethru == 1 && qdepth == 0) {
timethru = 2;
goto again;
}
#endif
return(alpha);
}
void rescore(mv ml[MAXMOVES])
{
register i;
i = 0;
while (ml[i].from != -1) {
ml[i].score += hheuristic[stm][ml[i].from][ml[i].to];
i++;
}
}
int search(int *bd, int depth, int ply, int alpha, int beta,
char *mvstr, int savetop, int verify, int reduced,int checked)
{
#ifdef ETC
int etcmvi, etcscore, etclength, etcalpha, etcbeta;
char etcflag;
mv etchashmv;
#endif
BitBoard bb_pieces;
float extend;
int extension;
int i,j,rc,mvi,bestmvi,movelegal,legals=0,length=0,sdepth,baseval;
int best,value,score,hashed=0,nulled=0,failhigh=0,foundone=-1,reduction;
int inpv=0,fscore,fprune=0,fmax,selective,localmove,threat=0,LastExt;
int donulllocal;
long qnodecnt[MAXPLY],nodes;
char flag, mvs[10];
mv nullmv2,hashmv,sml[MAXMOVES],localbest;
LastExt=AllExt[ply-1];
AllExt[ply]=ChkExt[ply]=RecapExt[ply]=PawnExt[ply]=OneExt[ply]=ThreatExt[ply]=0;
npvl[ply]=ply;
sdepth=depth;
hashmv.from=hashmv.to=0;
if (reps()==2 || pawndrawn()) return(DRAW);
snodes++;
if (ply > maxply) maxply = ply;
if (ply >= MAXPLY) {
#ifdef ASSERT
printf("ASSERT, search, ply(%d) >= MAXPLY(%d)\n",ply,MAXPLY);
#ifdef ASSERT1
pbd(bd);
listmvs(hist);
getchar();
#endif
#endif
return(alpha);
}
if (depth <= 0) {
value = quiesce(bd,ply+1,alpha,beta,mvstr,2,0);
return(value);
}
#ifdef TT
// Probe hash table. If seen before with equal or greater draft, return.
// Otherwise, set alpha and beta bounds if available.
// Last, if alpha exceeds or equals beta, return.
if (retrieve(&length, &score, &flag, &hashmv, &threat)) {
// if (flag == UBOUND && depth-R <= length && score < beta) donull = 0;
if (length >= sdepth) {
if (flag == VALID) {
savemove(&npv[ply][ply],hashmv);
for (j=ply+1;j<npvl[ply+1];++j) savemove(&npv[ply][j],npv[ply+1][j]);
npvl[ply]=npvl[ply+1];
return(score);
}
if (flag == LBOUND) alpha = MAX(alpha, score);
if (flag == UBOUND) beta = MIN(beta, score);
if (alpha >= beta) return(score);
if (legalmove2(bd,hashmv)) hashed = 1;
}
}
#endif
best = alpha;
donulllocal = 1;
#ifdef BITS
bb_pieces=b[white][knight]|b[white][bishop]|b[white][rook]|b[white][queen]|
b[black][knight]|b[black][bishop]|b[black][rook]|b[black][queen];
#endif
if (!donull ||
#ifndef BITS
material[stm]+material[stm^1]<=weights[0][stm][rook] ||
#endif
(hashed && MATESCORE(alpha)) ||
ply == 0 ||
(ply > 0 && hist[histptr-1].flg == NULLMOVE) ||
threat
#ifdef BITS
|| !bb_pieces
#endif
)
donulllocal = 0;
if (donull && donulllocal == 1) {
inpv = insidepv(ply);
if (inpv) donulllocal = 0;
}
if (donull && donulllocal == 1) {
if (checked == 2) checked=incheck(bd);
if (checked) donulllocal = 0;
}
#ifdef NULLMV
if (donull && donulllocal
#ifdef VERIFYNULLMV
&& (!verify || sdepth > 1)) {
#endif
#ifndef VERIFYNULLMV
) {
#endif
makenullmv();
#ifndef NULLMVADAPTIVE
reduction = R;
#endif
#ifdef NULLMVADAPTIVE
reduction = 2;
if (depth > 6
#ifdef BITS
&& nbits(bb_pieces)>9
#endif
) reduction = 3;
#endif
// test for null move prune
value = -search(bd,sdepth-1-reduction,ply+1,-beta,-beta+1,
mvstr,SAVETOP,verify,REDUCENOTOK,checked);
unmakenullmv();
if (value >= beta) {
#ifdef VERIFYNULLMV
if (verify) {
depth--;
verify = VERIFYNOTOK;
failhigh = 1;
} else {
#endif
#ifdef HASHNULLMV
// Store null move in hash table. Increase ha rate but dropped 2 positions.
best = value;
bestmvi = 0;
if (hashed) savemove(&sml[0],hashmv);
else if (legalmove2(bd,pv[ply])) savemove(&sml[0],pv[ply]);
else savemove(&sml[0],nullmv);
flag = NULLM;
goto donenull;
#endif
return(value); // was beta 3. value gives +1 wac result
#ifdef VERIFYNULLMV
}
#endif
}
#ifdef MTHR
if (MTHR_EXT != 0.0 && value == MATE+ply+2) { threat=1; }
#endif
nulled=1;
}
#endif
genmv(bd,sml,stm,SORT,SEEOK);
localmove=move;
#ifdef ONEX
if (ONEX_EXT != 0.0 && ply<=3*iply) {
movelegal=0;
mvi=0;
while(sml[mvi].from!=-1) {
makemv(bd,sml[mvi]);
if (!incheckopp(bd)) movelegal++;
unmakemv(bd);
if (movelegal>1) break;
mvi++;
}
if (movelegal == 1) OneExt[ply]=1;
}
#endif
if ((mvi = movematch(sml,hashmv)) != -1) { // Hash move
sml[mvi].score = 100000000;
qsort(sml,localmove,sizeof(mv),compare);
} else if ((mvi = movematch(sml,pv[ply])) != -1) { // PV move
// Put PV move first if it exists
sml[mvi].score = 100000000;
qsort(sml,localmove,sizeof(mv),compare);
}
#ifdef IID
} else if (donull && donulllocal && sdepth >= 3 && beta != alpha+1) { // IID
#ifdef ASSERT
printf("no hash or pv move at depth = %d:\n",sdepth);
#ifdef ASSERT1
pbd(bd);
getchar();
#endif
#endif
value = -search(bd,sdepth-2,ply+1,alpha,beta,
mvstr,SAVETOP,verify,REDUCENOTOK,checked);
if (value < alpha)
value = -search(bd,sdepth-2,ply+1,-MATE,alpha+1,
mvstr,SAVETOP,verify,REDUCENOTOK,checked);
if (retrieve(&length, &score, &flag, &hashmv, &threat)) {
// if (length >= sdepth) {
if (legalmove2(bd,hashmv)) {
if ((mvi = movematch(sml,hashmv)) != -1) {
sml[mvi].score = 100000000;
qsort(sml,localmove,sizeof(mv),compare);
}
}
// }
}
}
#endif
#ifdef ETC
if (depth > 2) {
etcmvi = 0;
while (sml[etcmvi].from != -1) {
makemv(bd,sml[etcmvi]);
if (retrieve(&etclength,&etcscore,&etcflag,&etchashmv,&threat)) {
if (etclength >= depth) {
etcscore = -etcscore;
if (etcflag == LBOUND && etcscore < beta)
beta = etcscore;
if (etcflag == UBOUND && etcscore > alpha)
alpha = etcscore;
if (etcflag == VALID || alpha >= beta) {
unmakemv(bd);
return(alpha); // was alpha
}
}
}
unmakemv(bd);
etcmvi++;
}
}
#endif
#ifdef OLDETC
if (depth > 2) {
etcmvi = 0;
while (sml[etcmvi].from != -1) {
makemv(bd,sml[etcmvi]);
if (retrieve(&etclength,&etcscore,&etcflag,&etchashmv,&threat)) {
if (etclength >= depth) {
if (etcflag == VALID) {
unmakemv(bd);
if (etcscore > beta)
return(etcscore);
}
}
}
unmakemv(bd);
etcmvi++;
}
}
#endif
research:
bestmvi = -1;
mvi = 0;
legals=0;
research2:
makemv(bd,sml[mvi]);
movelegal = 0;
if (!incheckopp(bd)) {
bestmvi = mvi;
legals++;
movelegal = 1;
strcpy(mvs,sqnames[sml[mvi].from]);
strcat(mvs,sqnames[sml[mvi].to]);
#ifdef ASSERT
if (!hashed && sml[mvi].from == -1) {
printf("ASSERT: search() from = -1 WOOPS!!! legals=%d\n",legals);
pbd(bd);
fflush(stdout);
#ifdef ASSERT1
getchar();
#endif
}
#endif
checked=2;
extend=0.0;
#ifdef RECAP
if (RECAP_EXT != 0.0 && extend<1.0 && histptr>=2 && hist[histptr-1].cap != 0
&&
sml[mvi].cap != 0 && hist[histptr-1].to == sml[mvi].to && ply <= iply+1) {
extend+=RECAP_EXT;
recapext++;
}
#endif
#ifdef PAWNX
if (PAWNX_EXT != 0.0 && extend<1.0&&
( (sml[mvi].pc==WP&&W7RANK(sml[mvi].to)) ||
(sml[mvi].pc == BP&&B7RANK(sml[mvi].to)) ))
{
extend+=PAWNX_EXT;
pawnext++;
}
#endif
#ifdef ONEX
if (ONEX_EXT != 0.0 && extend<1.0&&OneExt[ply]==1) {
extend+=ONEX_EXT;
onereplyext++;
}
#endif
#ifdef CXX
if (CXX_EXT != 0.0 && extend<1.0) {
checked = incheck(bd);
if (checked == 1) {
extend+=CXX_EXT;
checkext++;
}
}
#endif
#ifdef MTHR
if (MTHR_EXT != 0.0 && threat && extend<1.0) {
extend+=MTHR_EXT;
mthrext++;
}
#endif
if (extend>=1.00) extension=1; else extension=0;
best =
-search(bd,depth-1+extension,ply+1,-beta,-alpha,mvs,SAVETOP,verify,reduced,checked);
if (ply == 0 && savetop) {
savebest(sml[mvi],best,SHOWMVNOTOK);
}
#ifdef TEMP
savemove(&npv[ply][ply],sml[mvi]);
for (j=ply+1;j<npvl[ply+1];++j) savemove(&npv[ply][j],npv[ply+1][j]);
npvl[ply]=npvl[ply+1];
#endif
searches++; totsearches++;
if (best >= beta) betacuts++;
} else sml[mvi].score = -999999;
unmakemv(bd);
while (best < beta || (bestmvi == -1 && mvi == 0)) {
if (best > alpha && movelegal == 1) {
bestmvi = mvi;
alpha = best;
savemove(&npv[ply][ply],sml[mvi]);
for (j=ply+1;j<npvl[ply+1];++j) savemove(&npv[ply][j],npv[ply+1][j]);
npvl[ply]=npvl[ply+1];
hheuristic[stm][sml[mvi].from][sml[mvi].to]+=(1<<depth);
if (ply == 0 && savetop) {
savebest(sml[mvi],alpha,SHOWMVNOTOK);
}
}
if (!testing && timeout())
return(best);
mvi++;
if (sml[mvi].from == -1) break;
makemv(bd,sml[mvi]);
movelegal=0;
if (!incheckopp(bd)) {
legals++;
movelegal=1;
strcpy(mvs,sqnames[sml[mvi].from]);
strcat(mvs,sqnames[sml[mvi].to]);
checked=2;
extend=0.0;
#ifdef RECAP
if (RECAP_EXT != 0.0 && extend<1.0 && histptr>0 && hist[histptr-1].cap !=
0 &&
sml[mvi].cap != 0 && hist[histptr-1].to == sml[mvi].to && ply <= iply+1) {
extend+=RECAP_EXT;
recapext++;
}
#endif
#ifdef PAWNX
if (PAWNX_EXT != 0.0 && extend<1.0&&
((sml[mvi].pc==WP&&W7RANK(sml[mvi].to)) || (sml[mvi].pc ==
BP&&W7RANK(sml[mvi].to))))
{
extend+=PAWNX_EXT;
pawnext++;
}
#endif
#ifdef ONEX
if (ONEX_EXT != 0.0 && extend<1.0&&OneExt[ply]==1) {
extend+=ONEX_EXT;
onereplyext++;
}
#endif
#ifdef CXX
if (CXX_EXT != 0.0 && extend<1.0) {
checked = incheck(bd);
if (checked == 1) {
extend+=CXX_EXT;
checkext++;
}
}
#endif
#ifdef MTHR
if (MTHR_EXT != 0.0 && threat && extend<1.0) {
extend+=MTHR_EXT;
mthrext++;
}
#endif
if (extend>=1.00) extension=1; else extension=0;
value =
-search(bd,depth-1+extension,ply+1,-alpha-1,-alpha,mvs,SAVETOP,verify,reduced,checked);
if (value > alpha && value < beta) {
checked=2;
extend=0.0;
#ifdef RECAP
if (RECAP_EXT != 0.0 && extend<1.0 && histptr>=2 && hist[histptr-1].cap != 0 &&
sml[mvi].cap != 0 && hist[histptr-1].to == sml[mvi].to && ply <= iply+1) {
extend+=RECAP_EXT;
recapext++;
}
#endif
#ifdef PAWNX
if (PAWNX_EXT != 0.0 && extend<1.0 &&
((sml[mvi].pc==WP&&W7RANK(sml[mvi].to)) || (sml[mvi].pc ==
BP&&W7RANK(sml[mvi].to))))
{
extend+=PAWNX_EXT;
pawnext++;
}
#endif
#ifdef ONEX
if (ONEX_EXT != 0.0 && extend<1.0 && OneExt[ply]==1) {
extend+=ONEX_EXT;
onereplyext++;
}
#endif
#ifdef CXX
if (CXX_EXT != 0.0 && extend<1.0) {
checked = incheck(bd);
if (checked == 1) {
extend+=CXX_EXT;
checkext++;
}
}
#endif
#ifdef MTHR
if (MTHR_EXT != 0.0 && threat && extend<1.0) {
extend+=MTHR_EXT;
mthrext++;
}
#endif
if (extend>=1.00) extension=1; else extension=0;
best =
-search(bd,depth-1+extension,ply+1,-beta,-value,mvs,SAVETOP,verify,reduced,checked);
} else if (value > best) {
best = value;
bestmvi = mvi;
if (ply == 0 && savetop) {
savebest(sml[mvi],best,SHOWMVNOTOK);
}
savemove(&npv[ply][ply],sml[mvi]);
for (j=ply+1;j<npvl[ply+1];++j) savemove(&npv[ply][j],npv[ply+1][j]);
npvl[ply]=npvl[ply+1];
} else sml[mvi].score = -999999;
}
unmakemv(bd);
}
#ifdef VERIFYNULLMV
if (failhigh && best < beta) {
extend=1;
depth++;
failhigh=0;
verify=VERIFYOK;
goto research;
}
#endif
if (legals == 0) {
if (checked) {
best = MATE+ply;
} else {
best = STALEMATE;
}
goto done;
}
#ifdef TT
done:
flag = VALID;
donenull:
if (best <= alpha) flag = UBOUND;
if (best >= beta) flag = LBOUND;
if (length <= depth && bestmvi != -1) {
#ifdef NEVER
#ifdef ASSERT
makemv(bd,sml[bestmvi]);
if (incheckopp(bd)) {
printf("TT WOOPS, legals=%d!\n",legals);
pbd(bd);
#ifdef ASSERT1
getchar();
#endif
}
unmakemv(bd);
#endif
#endif
store(depth,best,flag,sml[bestmvi],threat);
}
#endif
return(best);
}
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.