Author: Stuart Cracraft
Date: 16:15:05 09/26/04
Hi -- I am posting this code so that if anyone wants to look at it
and sees anything wrong, there might be some flowover benefit. Feel
free to be as critical as you like -- the program wouldn't be where
it is without CCC and most if not all the comments have been incredibly
sharp. Sorry for the lack of comments and all the #ifdef's.
Just trying out various things.
Thanks --
Stuart Cracraft
#ifdef TT
int retrieve(int *length, int *score, char *flag, mv *hashmv)
{
HASHE * phashe = &hash_table[hashkey % MAXHASH];
ttprobes++;
if (phashe->key == hashkey) {
*length = phashe->depth;
*score = phashe->val;
*flag = phashe->flags;
savemove(hashmv, phashe->best);
ttmatches++;
return(1);
}
#ifdef TTTWOTIER
else if ((phashe+1)->key == hashkey) {
*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)
{
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)->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->key = hashkey;
savemove(&phashe->best,hashmv);
phashe->val = score;
phashe->flags = flag;
phashe->depth = length;
#ifdef TTTWOTIER
} else {
(phashe+1)->key = hashkey;
(phashe+1)->val = score;
(phashe+1)->flags = flag;
(phashe+1)->depth = length;
savemove(&(phashe+1)->best,hashmv);
#endif
}
}
#endif
#define SAVETOP 1
#define DONTSAVETOP 0
#define MATE MAXNUM
#define MATESCORE(x) (x > MATE-1000 || x < -MATE+1000)
#define STALEMATE 0
#define DRAW 0
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;
char flag, mvs[10];
mv qml[MAXMOVES],hashmv;
#ifdef UTM
pvl[ply]=ply;
#endif
qnodes++;
if (reps()==2 || pawndrawn()) return(DRAW);
#ifdef QCX
if (checked==2)
checked=incheck(bd);
if (checked) {
qcheckext++;
#ifdef UTM
return(search(bd,1,ply,alpha,beta,NULLOK,
"incheck",DONTSAVETOP,VERIFYOK,REDUCENOTOK,checked));
#endif
#ifndef UTM
return(search(bd,1,ply+1,alpha,beta,NULLOK,
"incheck",DONTSAVETOP,VERIFYOK,REDUCENOTOK,checked));
#endif
}
#endif
if (ply > maxply) maxply = ply;
baseval = value = eval(bd,QUIET);
if (value >= beta)
#ifdef MTDF
return value;
#endif
#ifdef PVSNEGASCOUT
return(beta); // was beta 1
#endif
if (value > alpha)
alpha = value;
if (ply >= MAXPLY) {
#ifdef ASSERT1
printf("ASSERT, quiesce, ply(%d) >= MAXPLY(%d)\n",ply,MAXPLY);
pbd(bd);
listmvs(hist);
getchar();
#endif
#ifdef MTDF
return value;
#endif
#ifdef PVSNEGASCOUT
return alpha;
#endif
}
#ifdef QCMX
if (qdepth != 0) gencap(bd,qml,stm); else genmv(bd,qml,stm,SORT);
#endif
#ifndef QCMX
gencap(bd,qml,stm);
#endif
#ifdef NEVER
if (move>2) {
printf("quiesce, captures sorted as:\n");
listmvs(qml);
pbd(bd);
getchar();
}
#endif
mvi = 0;
while (qml[mvi].from != -1) {
#ifdef SEE
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;
#ifdef SEEFUTILITY
if (usesee && seeval < delta) { futilityext++; mvi++; continue; }
#endif
#ifdef SEELOSS
if (usesee && seeval < 0) { futilityext++; mvi++; continue; }
#endif
#endif
if (1) {
#ifdef QCMX
ok=0;
if (qml[mvi].flg==CAPTURE||qml[mvi].flg==PROMOTE&&qml[mvi].flg==ENPASSANT)
ok=1;
if (qdepth != 0 && !ok) { mvi++; continue; }
#endif
makemv(bd,qml[mvi]);
strcpy(mvs,sqnames[qml[mvi].from]);
strcat(mvs,sqnames[qml[mvi].to]);
if (!incheckopp(bd)) {
#ifdef QCMX
if (qdepth == 0 && !(ok || incheck(bd))) {
unmakemv(bd);
mvi++;
continue;
}
#endif
value = -quiesce(bd,ply+1,-beta,-alpha,mvs,2,qdepth++);
}
unmakemv(bd);
if (value >= beta)
#ifdef MTDF
return(value);
#endif
#ifdef PVSNEGASCOUT
return(beta); // was beta 2
#endif
if (value > alpha) {
bestmvi = mvi;
alpha = value;
#ifdef UTM
savemove(&npv[ply][ply],qml[mvi]);
for (j=ply+1;j<pvl[ply+1];++j) savemove(&npv[ply][j],npv[ply+1][j]);
pvl[ply]=pvl[ply+1];
#endif
}
}
mvi++;
}
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,
int donull, 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,extended=0,baseval;
int best,value,score,hashed=0,nulled=0,failhigh=0,foundone=-1,reduction;
int inpv=0,fscore,fprune=0,fmax,selective,localmove;
long qnodecnt[MAXPLY];
char flag, mvs[10];
mv nullmv2,hashmv,sml[MAXMOVES],localbest,xml[MAXMOVES];
#ifdef UTM
pvl[ply]=ply;
#endif
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
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();
extend+=1.00;
checkext++;
extended=1;
}
}
#endif
#ifdef RECAP
// Extend if a recapture
if (!extended && histptr >= 2 && hist[histptr-1].cap != 0 &&
hist[histptr-2].cap != 0 && hist[histptr-1].to == hist[histptr-2].to
#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++;
extend+=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++;
extend+=0.5;
}
}
#endif
if (extend>=1.0) { depth++; extend=0.0; extended=1;} else extended=0;
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)) {
// if (flag == UBOUND && depth-R <= length && score < beta) donull = 0;
if (length >= sdepth) {
if (flag == VALID) {
#ifdef UTM
savemove(&npv[ply][ply],hashmv);
for (j=ply+1;j<pvl[ply+1];++j) savemove(&npv[ply][j],npv[ply+1][j]);
pvl[ply]=pvl[ply+1];
#endif
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);
if (hashed && MATESCORE(score)) donull = 0;
// if (flag == NULLM) donull = 0;
#ifdef NULLMV
if (donull && (material[stm^1]>weights[0][stm^1][rook]) && !checked
&& !inpv
// && eval(bd,QUIET)+weights[0][stm][pawn] > beta
#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
value = -search(bd,sdepth-1-reduction,ply,-beta,-beta+1,
NULLNOTOK,mvstr,SAVETOP,verify,REDUCENOTOK,checked);
if (value >= beta) {
#ifdef VERIFYNULLMV
if (verify) {
depth--;
verify = VERIFYNOTOK;
failhigh = 1;
} else {
#endif
unmakenullmv();
#ifdef MTDF
return(value);
#endif
#ifdef PVSNEGASCOUT
#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;
goto done;
#endif
return(value); // was beta 3. value gives +1 wac result
#endif
#ifdef VERIFYNULLMV
}
#endif
}
unmakenullmv();
nulled=1;
}
#endif
#ifdef BM
if (!extended && value <= -2000 && ply >= 2 &&
((threat[ply].from==threat[ply-2].from&&
threat[ply].to==threat[ply-2].to&&
threat[ply].pro==threat[ply-2].pro) ||
(threat[ply].to==threat[ply-2].to&&threat[ply].cap==threat[ply-2].cap))) {
extend=1;
extended=1;
depth++;
}
#endif
#ifdef MTHR
if (!extended && value == -MATE+ply+2) {
// printf("mate threat:\n");listmvs(hist);pbd(bd);getchar();
extend=1;
extended=1;
depth++;
}
#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 QSORTPLY0
if (ply == 0) {
mvi=0;
while(sml[mvi].from!=-1) {
makemv(bd,sml[mvi]);
if (!incheckopp(bd))
sml[mvi].score=-quiesce(bd,ply+1,INT_MIN,INT_MAX,mvstr,2,0);
unmakemv(bd);
mvi++;
}
qsort(sml,localmove,sizeof(mv),compare);
// listmvs(sml);
// getchar();
}
#endif
#ifdef ONEXXX
if (!extended && 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;
extended=1;
depth++;
onereplyext++;
}
}
#endif
#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 && 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,
NULLNOTOK,mvstr,SAVETOP,verify,REDUCENOTOK,checked);
if (value < alpha)
value = -search(bd,sdepth-2,ply+1,-MATE,alpha+1,
NULLNOTOK,mvstr,SAVETOP,verify,REDUCENOTOK,checked);
if (retrieve(&length, &score, &flag, &hashmv)) {
// 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 (sdepth > 3) {
etcmvi = 1;
while (sml[etcmvi].from != -1) {
makemv(bd,sml[etcmvi]);
if (retrieve(&etclength,&etcscore,&etcflag,&etchashmv)) {
if (etclength >= sdepth) {
if (etcflag == VALID) {
unmakemv(bd);
return(etcscore);
}
}
}
unmakemv(bd);
etcmvi++;
}
}
#endif
// printf("search, moves sorted as:\n");
// listmvs(sml);
// pbd(bd);
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 FUTILITY
#define FRONTIER 1
#define MARGIN weights[0][white][knight]
fscore = material[stm]-material[stm^1]+MARGIN;
if (!incheck(bd) && depth == FRONTIER && fscore <= alpha) {
fprune = selective = 1;
score = fmax = fscore;
}
#endif
best =
-search(bd,depth-1,ply+1,-beta,-alpha,NULLOK,mvs,SAVETOP,verify,reduced,2);
if (ply == 0 && savetop) {
savebest(sml[mvi],best,SHOWMVNOTOK);
savemove(&threat[ply],sml[mvi]);
}
#ifdef TEMP
#ifdef UTM
savemove(&npv[ply][ply],sml[mvi]);
for (j=ply+1;j<pvl[ply+1];++j) savemove(&npv[ply][j],npv[ply+1][j]);
pvl[ply]=pvl[ply+1];
#endif
#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;
#ifdef UTM
savemove(&npv[ply][ply],sml[mvi]);
for (j=ply+1;j<pvl[ply+1];++j) savemove(&npv[ply][j],npv[ply+1][j]);
pvl[ply]=pvl[ply+1];
#endif
hheuristic[stm][sml[mvi].from][sml[mvi].to]+=(1<<depth);
if (ply == 0 && savetop) {
savebest(sml[mvi],alpha,SHOWMVNOTOK);
savemove(&threat[ply],sml[mvi]);
}
}
if (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
#ifdef SORTPLY0
if (ply == 0) {
sml[mvi].searched = 1;
// printf("searched %s%s\n",sqnames[sml[mvi].from],sqnames[sml[mvi].to]);
// getchar();
rescore(sml);
qsort(sml,localmove,sizeof(mv),compare);
i = 0;
while (i < localmove) {
if (sml[i].from == -1) { mvi = i; break; }
if (sml[i].searched == 0) { mvi = i; break; }
i++;
}
mvi = i;
} else
#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 FUTILITY
fscore = material[stm]-material[stm^1]+MARGIN;
if (!incheck(bd) && depth == FRONTIER && fscore <= alpha) {
fprune = selective = 1;
score = fmax = fscore;
}
#endif
value = -search(bd,depth-1,ply+1,-alpha-1,-alpha,
NULLOK,mvs,SAVETOP,verify,reduced,2);
if (value > alpha && value < beta) {
#ifdef FUTILITY
fscore = material[stm]-material[stm^1]+MARGIN;
if (!incheck(bd) && depth == FRONTIER && fscore <= alpha) {
fprune = selective = 1;
score = fmax = fscore;
}
#endif
if (!fprune)
best = -search(bd,depth-1,ply+1,-beta,-value,
NULLOK,mvs,SAVETOP,verify,reduced,2);
} else if (value > best) {
best = value;
bestmvi = mvi;
if (ply == 0 && savetop) {
savebest(sml[mvi],best,SHOWMVNOTOK);
savemove(&threat[ply],sml[mvi]);
}
#ifdef UTM
savemove(&npv[ply][ply],sml[mvi]);
for (j=ply+1;j<pvl[ply+1];++j) savemove(&npv[ply][j],npv[ply+1][j]);
pvl[ply]=pvl[ply+1];
#endif
} 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+depth;
} else {
best = STALEMATE;
}
goto done;
}
#ifdef ONEX
if (legals == 1 && !extended && sml[mvi].from==-1) {
// printf("one reply (%s%s)\n",sqnames[sml[bestmvi].from],
// sqnames[sml[bestmvi].to]); listmvs(hist); pbd(bd); getchar();
extended=1;
onereplyext++;
depth++;
goto research;
}
#endif
// if (checked && bestmvi == -1) {
// printf("incheck, no best move, alpha=%d, beta=%d\n",alpha,beta);
// pbd(bd);
// getchar();
// }
#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]);
}
#endif
return(best);
}
This page took 0 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.