Previous Next Version 4
The efficiency of the alpha-beta search is strongly enhanced (in terms of the number of nodes searched) if the best move is tried first, and trying idiotic moves first (such as both Queens getting berserk) can easily lead to an explosion of the search. Rather than aggressively starting a search of the required depth, proceed carefully and first invest some time doing a search of shallower depth. Then use the result to determine the order in which you are going to try the moves in the full search. The time you save because of the good move ordering pays back many times the time you invested in the shallower search.
This concept, known as internal iterative deepening, works like a charm, because the completely stupid full-width search in principle tries anything, even the most idiotic moves like taking a defended Pawn with a Queen. Such moves can cause tremendous tactical complications if you refrain from taking the Queen back immediately, a move that a one-ply search would already recommend. So the power of iterative deepening is that it immediately finds the solutions for problems that do have trivial solutions, so that in the deeper searches their subtrees are quickly and decisively pruned though the alpha-beta mechnism. Going into the search 'depth first', on the other hand, tends to dive deep into idiotic variations before realizing they were idiotic, when accidentally hitting upon the proper refutation.
Of course one could implement a satic way to find out what likely refutations are for idiotic moves, but there are many levels of idiocy. Some, like taking a defended piece with a higher one, are refuted in the next ply, but if the apparently defending piece happened to be a pinned one, it is the opponent who turns out to be the idiot on ply number two. Judging this statically becomes progressively more difficult. With iterative deepening the results vary wildly with depth until the entire relevant tactics are within the horizon (e.g. including the capture of the piece on which the defender was pinned), and stabilize after that.
To implement the iterative deepening there is (of course) a loop around the search code,
that executes it with a depth left d running from 1 to n-1,
rather than just for d=n-1, like this:
int D(int k, int q, int l, int n)
{
int m, /* score of best move so far */
d=0, /* iteratively improved depth */
while(++d<n)
{ m = d>1 ? -I : EVAL(); /* if d==1 no moves will be tried */
INITIALIZE_MOVE_GENERATION(B); /* start with moves that go from B */
DO{{{
GENERATE_NEXT_MOVE;
IF_KING_CAPTURE m=I;
if(m>=l) goto C;
h = d-1; /* new depth left */
if(h)
{ DO_MOVE;
v = -D(24-k, -l, q>m?-q:-m, h);
UNDO_MOVE;
if(v>m) { m=v; } /* account maximum */
}
}}} WHILE_MOVES_LEFT;
C: ;
}
return m;
}
The information returned by the pevious, shallower searches can be used in two ways. The score obtained can be used to set the window more appropriately, leading to a more efficient search. In addition the order of looking at the moves can be inspired by it. Micro-Max uses only the second method, in a minimal way: it tries the best move from the previous iteration first, but all other moves in the order they hppen to be generated. There are no manipulations with the window.
In internal nodes the maximum depth is set by the caller,
but at the root we want to deepen until time runs out.
How many ply that is depends strongly on the position and the stage of the game.
To take account of this micro-Max deepens in the root node
(which is recognized because it is the only instance of D() that is called
with the invalid square code 8 for the 'recapture square' z)
until a certain number of nodes,
counted in N, has been reached.
In the sample listing this is after 10 million nodes (1e7),
to change the average time per move this number should be changed.
To prevent problems with stack overflow in a tree that does not branch,
an absolute maximum of 98 ply is set to the depth.
One could also set a fixed depth here,
by simply writing while(d++<n)),
and calling D() from main with n set to the required value
(saving many characters...).
But then micro-Max starts to play very fast (and poorly) in the end-game.
Iterative deepening makes no sense if the search has already reached the legal end of the game, through checkmate. If mate-in-three is certain, nothing can be gained by looking deeper, we are not interested anymore in mate-in-four. So if the score tells us that a checkmate is discovered, we immediately set the depth d to the maximum (i.e. 99), so that no new iterations are started.
Below the code that implements the iterative deepening is highlighted:
/***************************************************************************/
/* micro-Max, */
/* A chess program smaller than 2KB (of non-blank source), by H.G. Muller */
/***************************************************************************/
/* version 3.2 (2000 characters) features: */
/* - recursive negamax search */
/* - quiescence search with recaptures */
/* - recapture extensions */
/* - (internal) iterative deepening */
/* - best-move-first 'sorting' */
/* - a hash table storing score and best move */
/* - full FIDE rules (expt minor ptomotion) and move-legality checking */
#define F(I,S,N) for(I=S;I<N;I++)
#define W(A) while(A)
#define K(A,B) *(int*)(T+A+(B&8)+S*(B&7))
#define J(A) K(y+A,b[y])-K(x+A,u)-K(H+A,t)
#define U 16777224
struct _ {int K,V;char X,Y,D;} A[U]; /* hash table, 16M+8 entries*/
int V=112,M=136,S=128,I=8e3,C=799,Q,N,i; /* V=0x70=rank mask, M=0x88 */
char O,K,L,
w[]={0,1,1,3,-1,3,5,9}, /* relative piece values */
o[]={-16,-15,-17,0,1,16,0,1,16,15,17,0,14,18,31,33,0, /* step-vector lists */
7,-1,11,6,8,3,6, /* 1st dir. in o[] per piece*/
6,3,5,7,4,5,3,6}, /* initial piece setup */
b[129], /* board: half of 16x8+dummy*/
T[1035], /* hash translation table */
n[]=".?+nkbrq?*?NKBRQ"; /* piece symbols on printout*/
D(k,q,l,e,J,Z,E,z,n) /* recursive minimax search, k=moving side, n=depth*/
int k,q,l,e,J,Z,E,z,n; /* (q,l)=window, e=current eval. score, E=e.p. sqr.*/
{ /* e=score, z=prev.dest; J,Z=hashkeys; return score*/
int j,r,m,v,d,h,i=9,F,G;
char t,p,u,x,y,X,Y,H,B;
struct _*a=A;
/* lookup pos. in hash table*/
j=(k*E^J)&U-9; /* try 8 consec. locations */
W((h=A[++j].K)&&h-Z&&--i); /* first empty or match */
a+=i?j:0; /* dummy A[0] if miss & full*/
if(a->K) /* hit: pos. is in hash tab */
{d=a->D;v=a->V;X=a->X; /* examine stored data */
if(d>=n) /* if depth sufficient: */
{if(v>=l|X&S&&v<=q|X&8)return v; /* use if window compatible */
d=n-1; /* or use as iter. start */
}X&=~M;Y=a->Y; /* with best-move hint */
Y=d?Y:0; /* don't try best at d=0 */
}else d=X=Y=0; /* start iter., no best yet */
N++; /* node count (for timing) */
while(d++<n|z==8&N<1e7&d<98) /* iterative deepening loop */
{x=B=X; /* start scan at prev. best */
Y|=8&Y>>4; /* request try noncastl. 1st*/
m=d>1?-I:e; /* unconsidered:static eval */
do{u=b[x]; /* scan board looking for */
if(u&k) /* own piece (inefficient!)*/
{r=p=u&7; /* p = piece type (set r>0) */
j=o[p+16]; /* first step vector f.piece*/
W(r=p>2&r<0?-r:-o[++j]) /* loop over directions o[] */
{A: /* resume normal after best */
y=x;F=G=S; /* (x,y)=move, (F,G)=castl.R*/
do{H=y+=r; /* y traverses ray */
if(Y&8)H=y=Y&~M; /* sneak in prev. best move */
if(y&M)break; /* board edge hit */
if(p<3&y==E)H=y^16; /* shift capt.sqr. H if e.p.*/
t=b[H];if(t&k|p<3&!(r&7)!=!t)break; /* capt. own, bad pawn mode */
i=99*w[t&7]; /* value of capt. piece t */
if(i<0||E-S&&b[E]&&y-E<2&E-y<2)m=I; /* K capt. or bad castling */
if(m>=l)goto C; /* abort on fail high */
if(h=d-(y!=z)) /* remaining depth(-recapt.)*/
{v=p<6?b[x+8]-b[y+8]:0; /* center positional pts. */
b[G]=b[H]=b[x]=0;b[y]=u&31; /* do move, strip virgin-bit*/
if(!(G&M)){b[F]=k+6;v+=30;} /* castling: put R & score */
if(p<3) /* pawns: */
{v-=9*(((x-2)&M||b[x-2]!=u)+ /* structure, undefended */
((x+2)&M||b[x+2]!=u)-1); /* squares plus bias */
if(y+r+1&S){b[y]|=7;i+=C;} /* promote p to Q, add score*/
}
v=-D(24-k,-l-(l>e),m>q?-m:-q,-e-v-i, /* recursive eval. of reply */
J+J(0),Z+J(8)+G-S,F,y,h); /* J,Z: hash keys */
v-=v>e; /* delayed-gain penalty */
if(z==9) /* called as move-legality */
{if(v!=-I&x==K&y==L) /* checker: if move found */
{Q=-e-i;O=F;return l;} /* & not in check, signal */
v=m; /* (prevent fail-lows on */
} /* K-capt. replies) */
b[G]=k+38;b[F]=b[y]=0;b[x]=u;b[H]=t; /* undo move,G can be dummy */
if(Y&8){m=v;Y&=~8;goto A;} /* best=1st done,redo normal*/
if(v>m){m=v;X=x;Y=y|S&G;} /* update max, mark with S */
} /* if non castling */
t+=p<5; /* fake capt. for nonsliding*/
if(p<3&6*k+(y&V)==S /* pawn on 3rd/6th, or */
||(u&~24)==36&j==7&& /* virgin K moving sideways,*/
G&M&&b[G=(x|7)-(r>>1&7)]&32 /* 1st, virgin R in corner G*/
&&!(b[G^1]|b[G^2]) /* 2 empty sqrs. next to R */
){F=y;t--;} /* unfake capt., enable e.p.*/
}W(!t); /* if not capt. continue ray*/
}}}W((x=x+9&~M)-B); /* next sqr. of board, wrap */
C:if(m>I/4|m<-I/4)d=99; /* mate is indep. of depth */
m=m+I?m:-D(24-k,-I,I,0,J,K,S,z,1)/2; /* best loses K: (stale)mate*/
if(!a->K|(a->X&M)!=M|a->D<=d) /* if new/better type/depth:*/
{a->K=Z;a->V=m;a->D=d;A->K=0; /* store in hash,dummy stays*/
a->X=X|8*(m>q)|S*(m<l);a->Y=Y; /* empty, type (limit/exact)*/
} /* encoded in X S,8 bits */
/*if(z==8)printf("%2d ply, %9d searched, %6d by (%2x,%2x)\n",d-1,N,m,X,Y&0x77);*/
}
if(z&8){K=X;L=Y&~M;}
return m;
}
main()
{
int j,k=8,*p,c[9];
F(i,0,8)
{b[i]=(b[i+V]=o[i+24]+40)+8;b[i+16]=18;b[i+96]=9; /* initial board setup*/
F(j,0,8)b[16*j+i+8]=(i-4)*(i-4)+(j-3.5)*(j-3.5); /* center-pts table */
} /*(in unused half b[])*/
F(i,M,1035)T[i]=random()>>9;
W(1) /* play loop */
{F(i,0,121)printf(" %c",i&8&&(i+=7)?10:n[b[i]&15]); /* print board */
p=c;W((*p++=getchar())>10); /* read input line */
N=0;
if(*c-10){K=c[0]-16*c[1]+C;L=c[2]-16*c[3]+C;}else /* parse entered move */
D(k,-I,I,Q,1,1,O,8,0); /* or think up one */
F(i,0,U)A[i].K=0; /* clear hash table */
if(D(k,-I,I,Q,1,1,O,9,2)==I)k^=24; /* check legality & do*/
}
}
Previous Next Version 4