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.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.