Author: Stuart Cracraft
Date: 09:11:56 10/04/04
Go up one level in this thread
Hi Don -- the bet is still on! My complete relevant code is below
so there can be no doubt we are talking about apples or oranges.
Well, alpha or beta! Code is main search(), quiescence quiesce(),
hash store(), and hash probe()
I tried settings as you described but did not get a speedup but that doesn't
mean I am implementing it incorrectly. Normally currently WAC 141 solves in 64
seconds or so without the NULLBEAL setting (see below) and 282 seconds with
NULLBEAL. Obviously I do not have it implemented correctly. Maybe you
can have a look at that and anything else you'd like.
My search window is normally eval-delta,eval+delta where delta is 1/3 pawn
and if no faillow/faillhigh is readjusted to lastiterationvalue-delta to
lastiteration+delta as iterative deepening continues.
If I get a faillow or failhigh, rather than widening only one side
or researching for a faillow , I widen the entire window to
MINNUM,MAXNUM. My MATE value is MAXNUM+100, which is outside of
the minnum number and maximum number MINNUM and MAXNUM. Note,
MINNUM and MAXNUM are not the highest and lowest numbers for an
integer on this architecture. They are just high numbers guaranteed
to be outside of the range of if one side captured everything belonging
to the other, etc. MATE is a positive term MAXNUM+100 and MATESCORE(x)
returns true if x > MATE-100 or x < -MATE+100. Not sure if all this
is accurate though.
Quiescence doesn't do anything with MATE, just the main search.
While it scores 250/300 on WAC at 1 second per move on a 1ghz P3
and 270/300 on WAC at 10 seconds per move which is getting within
ballpark figures, I still have a sense that things are off. Note:
the evaluation is material and pc/sq only.
Currently WAC 141 is solved in 65 seconds (down from 95) but not within
the 10 second bet window. Previously, when I had checks-evasions-extensions
instead of my current check-giving extensions, by disabling my null move, it
brought WAC 141 to within a few seconds (5 or so) for solution. Since going to
check-giving extensions in main search (nothing in quiescence), WAC 141
is now out of reach without null move, which I found interesting.
My default settings are below. The ones that are commented out
ar not used. But the code is shown. Currently my quiescence is
one recursive routine to reduce extra function call overhead.
I tried combinations CXX, CXX+QCXX, CX, CX+QCX, and <none> for the
quiescence ideas and the current one, CXX, gives the best results
on WAC for me. I wish I could uncomment QCXX but it seems expensive
to my search for some reason.
Note -- I didn't use the printf's in the actual search and sent those
#define TT // transposition table of course
#define SEE // see for captures in quiescence winning or even captures
#define MAXHASH (1<<19)
#define NULLMV
#define R 2
#define CXX // extend on giving checks in main search
#define HASHNULLMV // hash the null move position as well
#define ONEX // one-reply extension (seems okay)
#define RECAP // recapture extension (not sure if implemented optimally)
#define MTHR // mate-threat (not sure if implemented correctly)
//// Not currently used
//#define NULLBEAL // too soon to tell on this one.
//#define QCXX // extend on giving checks in quiescence at 1st ply
//#define QCX // extend on escaping checks in quiescence
//#define CX // extend on escaping checks in main search
//#define NULLMVADAPTIVE // adaptive null move
//#define HASHFIRST // search hash move first (may have conflict with others)
//#define TTTWOTIER // two tier transposition (default is single tier for TT)
//#define PAWNX // pawn extension for promotion in main search
//#define QPAWNX // pawn extension for promotion in quiescence search
//#define VERIFYNULLMV // verified null move (not sure if implemented right)
//#define ETC // enhanced transposition cutoff (not sure if implemented right)
//#define IID // internal iterative deepening (not sure if implemented right)
Here is the complete/actual/current code for my quiescence, search,
and hash retrieve/store routines. I welcome your comments.
int quiesce(int *bd, int ply, int alpha, int beta, char *mvstr,int checked,
int qdepth)
{
int bestmvi=-1,mvi,value,seeval,baseval,delta,usesee,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;
}
#ifdef QCX
if (checked==2)
checked=incheck(bd);
if (checked) {
qcheckext++;
return(search(bd,1,ply,alpha,beta,NULLOK,
"incheck",DONTSAVETOP,VERIFYOK,REDUCENOTOK,checked));
}
#endif
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); else gencap(bd,qml,stm);
#endif
again:
mvi = 0;
while (qml[mvi].from != -1) {
#ifdef SEE
// First time only
delta = MAX(alpha-maxposnscore[stm]-baseval,0);
seeval=qml[mvi].see;
usesee=0;
if (bd[qml[mvi].to] != MT || qml[mvi].flg == ENPASSANT) usesee=1;
if (usesee) {
if (seeval < delta) { futilityext++; mvi++; continue; }
if (seeval < 0) { futilityext++; mvi++; continue; }
}
#endif
if (1) {
if (timethru == 1 && !usesee) { mvi++; continue; }
makemv(bd,qml[mvi]);
strcpy(mvs,sqnames[qml[mvi].from]);
strcat(mvs,sqnames[qml[mvi].to]);
if (!incheckopp(bd))
if ((timethru == 1 && usesee)
#ifdef QCXX
|| (timethru == 2 && qdepth == 0 && incheck(bd))
#endif
)
value = -quiesce(bd,ply+1,-beta,-alpha,mvs,2,qdepth+1);
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++;
}
if (timethru == 1 && qdepth == 0) { timethru = 2; goto again; }
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
float extend=0;
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=0;
if (ply>0) 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 (checked == 2)
checked=incheck(bd);
#ifdef CX
// Extend on check as long as not entered from quiescence search
// otherwise avoid any extension and maintain an unchanged depth.
if (checked && sdepth > 0) {
if (strncmp(mvstr,"incheck",7)!=0) {
// printf("main search, in check and depth=%d\n",sdepth);
// pbd(bd); listmvs(hist); getchar();
checkext++;
ChkExt[ply]+=1.00;
}
}
#endif
#ifdef RECAP
// Extend if a recapture
if (histptr >= 2 && hist[histptr-1].cap != 0 &&
hist[histptr-2].cap != 0 && hist[histptr-1].to == hist[histptr-2].to
////// && RecapExt[ply-1] < 1
//// && mat_value[hist[histptr-1].cap+6] == mat_value[hist[histptr-2].pc+6]
&& ply<=iply+1
#ifdef NEVER
&& ABS(hist[histptr-2].pc) == ABS(hist[histptr-1].cap)
&& ABS(hist[histptr-2].cap) == ABS(hist[histptr-1].cap)
#endif
) {
#ifdef NEVER
printf("recapture after %s%s\n:",
sqnames[hist[histptr-1].from],sqnames[hist[histptr-1].to]);
listmvs(hist);
pbd(bd);
getchar();
#endif
recapext++;
RecapExt[ply]+=1.00;
}
#endif
#ifdef PAWNX
// Extension for pawn promotion
if (histptr > 0) {
if ((hist[histptr-1].pc == WP && W8RANK(hist[histptr-1].to))||
(hist[histptr-1].pc == BP && B8RANK(hist[histptr-1].to))) {
pawnext++;
PawnExt[ply]+=0.5;
}
}
#endif
AllExt[ply]=ChkExt[ply]+RecapExt[ply]+PawnExt[ply];
if (LastExt==0&&AllExt[ply]>=1) depth++;
if (depth <= 0) {
value = quiesce(bd,ply+1,alpha,beta,mvstr,checked,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;
inpv = insidepv(ply);
donulllocal = 1;
if (material[stm]+material[stm^1]<=weights[0][stm][rook] ||
hashed && MATESCORE(score) ||
ply == 0 ||
(ply > 0 && hist[histptr-1].flg == NULLMOVE) ||
threat ||
checked ||
inpv
)
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 (sdepth > 6) reduction = 3;
#endif
// test for null move prune
value = -search(bd,sdepth-1-reduction,ply,-beta,-beta+1,
mvstr,SAVETOP,verify,REDUCENOTOK,checked);
#ifndef NULLBEAL
if (value == -MATE+ply+2) threat=1;
#endif
if (value >= beta) {
#ifdef VERIFYNULLMV
if (verify) {
depth--;
verify = VERIFYNOTOK;
failhigh = 1;
} else {
#endif
unmakenullmv();
#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
}
unmakenullmv();
nulled=1;
}
#ifdef NULLBEAL
// test for mate extension
value = -search(bd,sdepth-1-reduction,ply,MATE,MATE+1,
NULLNOTOK,mvstr,SAVETOP,verify,REDUCENOTOK,checked);
// if (value < -MATE) {
if (MATESCORE(value)) {
threat=1;
// printf("threat\n"); pbd(bd); getchar();
}
#endif
#endif
#ifdef MTHR
if (threat && MATESCORE(beta)) ThreatExt[ply]+=1.00;
#endif
#ifdef HASHFIRST
if (hashed)
savemove(&sml[0],hashmv);
else if (legalmove2(bd,pv[ply])) {
savemove(&sml[0],pv[ply]);
hashed = 2;
} else { genmv(bd,sml,stm,SORT); localmove=move; }
#endif
#ifndef HASHFIRST
genmv(bd,sml,stm,SORT);
localmove=move;
#ifdef SORTMOVES
if (ply == 0 && iply > 1) {
i = 0;
while (sml[i].from != -1) { sml[i].score += xml[i].nodes; i++; }
qsort(sml,localmove,sizeof(mv),compare);
}
#endif
#endif
#ifdef ONEXXX
if (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) {
// printf("one move only ONEXXX\n");
// pbd(bd); getchar();
extend=1.0;
OneExt[ply]++;
onereplyext++;
}
}
#endif
#ifndef HASHFIRST
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);
}
#endif
#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
if (LastExt==0&&AllExt[ply]<1&&AllExt[ply]+OneExt[ply]+ThreatExt[ply]>=1)
depth++;
AllExt[ply]+=OneExt[ply]+ThreatExt[ply];
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
#ifdef SORTMOVES
if (ply == 0) xml[mvi].nodes=qnodes+snodes;
#endif
#ifdef CXX
if (AllExt[ply]==0 && incheck(bd))
best = -search(bd,depth,ply+1,-beta,-alpha,mvs,SAVETOP,verify,reduced,2);
else
#endif
best =
-search(bd,depth-1,ply+1,-beta,-alpha,mvs,SAVETOP,verify,reduced,2);
#ifdef SORTMOVES
if (ply == 0) xml[mvi].nodes=qnodes+snodes-xml[mvi].nodes;
#endif
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);
#ifdef HASHFIRST
if (hashed && mvi == 0) {
genmv(bd,sml,stm,NOSORT);
localmove=move;
mvi = movematch(sml,hashmv);
sml[mvi].score = 100000001; // make hash move top move
if (hashed != 2)
if ((mvi = movematch(sml,pv[ply])) != -1)
sml[mvi].score = 100000000; // make pv 2nd
qsort(sml,localmove,sizeof(mv),compare); // finalize it
mvi = 1; // start out at pv or 2nd move
hashed = 0; // don't execute this code again
goto research2;
}
#endif
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]);
#ifdef SORTMOVES
if (ply == 0) xml[mvi].nodes=qnodes+snodes;
#endif
#ifdef CXX
if (AllExt[ply]==0 && incheck(bd))
value =
-search(bd,depth,ply+1,-alpha-1,-alpha,mvs,SAVETOP,verify,reduced,2);
else
#endif
value =
-search(bd,depth-1,ply+1,-alpha-1,-alpha,mvs,SAVETOP,verify,reduced,2);
#ifdef SORTMOVES
if (ply == 0) xml[mvi].nodes=qnodes+snodes-xml[mvi].nodes;
#endif
if (value > alpha && value < beta) {
#ifdef SORTMOVES
nodes = qnodes+snodes;
#endif
#ifdef CXX
if (AllExt[ply]==0 && incheck(bd))
best = -search(bd,depth,ply+1,-beta,-value,mvs,SAVETOP,verify,reduced,2);
else
#endif
best =
-search(bd,depth-1,ply+1,-beta,-value,mvs,SAVETOP,verify,reduced,2);
#ifdef SORTMOVES
if (ply == 0) xml[mvi].nodes+=qnodes+snodes-nodes;
#endif
} 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);
}
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
This page took 0.14 seconds to execute
Last modified: Thu, 07 Jul 11 08:48:38 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.