Previous Next
At first glance it does not seem very important to prefer mate in one over mate in two. A win is a win, isn't it? Well, actually, it isn't...
If a computer prefers mate in two over mate in one, on the next move it will be faced with the same choice again, and what then will be mate in two is now mate in three, and so on. In short, a program that does not prefer the short route, might never get to its destination. Of course implementation of the 50-move rule might make the program see the light after 49 moves, in this particular example. But often the 50-move rule is similar to painting yoursef in a corner: by the time the paint seems awfully close, there is no way out anymore.
Take the KBNK end-game as an example. To enforce the checkmate might take 33 moves (66 ply), and lies usually far beyond the horizon. If we would have a method to directly judge how far each position is from the mate (as in an end-game TableBase) life would be easy and even the shallowest search would be able to run towards the checkmate. But in the absence of a TB we only have an approximate idea how far the bare King is removed from its doom, like its distance from the edge or to the proper corner. In that case the path towards checkmate might not see a monotonous improvement (for the winning side) of the approximate measure for progress. It is as if we have to climb a mountain range: to get to the next, higher summit we have to cross a mountain pass first. In a fogg, just looking at the slope of the local terrain, we wouldn't know in which direction to go. We need at least enough visibility to see the peak across the valley. But it would be stupid to assume that that is the final destination, just because it is the only peak in view. If we would extend our picnic until we can just make that peak before dark, we are in for a cold night indeed!
In computer chess the search delivers the required visibility. But the path might go up for 5 moves to a score +20, than downhill up to move 10, to reach scores above +20 only from move 15 onwards. If the engine can see 10 moves ahead, the tempory setback between move 5 and 10 would not be able to prevent it from finding the path to enlightning. But only when it first goes to the peak at +20 moves, and searches from there. If it would be in no hurry to take the first of those 5 steps towards +20, because there are no paths within its horizon that can reach a score better than +20, and among the many paths that do end at this +20 position in a leaf node a large fraction just fools around for 5 moves before getting to the point, it might fool around forever. Because after wasting the first move on a detour path, it can see upto move 11, extending its time left for fooling around by one more move. After move 40 it will really get worried that all paths suddenly seem to lead to draw...
To prevent such problems it is important that the engine prefers the fastest path to the best position it can foresee. In Micro-Max the drive for this is provided by applying a small penalty (1 centipawn) for any move that you (have to) delay in improving your situation. To see if improvement is possible, it looks at the difference of the score of the best move and the current evaluation. If this is positive and above a certain threshold, one point is deducted from the score. Since the opponent in such cases foresees that it can be forced into a situation that gets worse, delaying tactics are in his favor, and he does not receive a penalty. So every move needed to reach an attractive position depreciates that position by 1 point.
I you adjust the value of a move after the search, you have to be careful to precompensate this adjustment in the (alpha, beta) window. If the move will be chosen as best will be decided after the adjustment, and during the search the adjustment has not been made yet. This is unavoidable, because it depends on the outcome of the search if the adjustment will be made. So if scores larger than current_eval will be depreciated by 1 point, window limits larger than current_eval will have to be increased by one point. It will lead to horrible blunders if you make the window too small, even by 1 point. Making the window too large only wastes time, but not very much if it is only by 1 point. So Micro-Max only increases beta (l), which will be the next ply's -alpha, by 1 point in that case.
Below the code that implements the delay penalty 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 promotion) 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=8,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 */
while((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) */
W(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,Z,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