Previous Next
A check is often a delaying move: the side that is in check has to do something about it. This can go either way: it might cause him to postpone cashing in on an irrefutable threat, pushing that threat over the horizon. Giving the check then looks good, while in fact it solves nothing. Another possibility is that the check is the first step towards total breakdown of the King safety, hunting down the King in a chase over the board until it is checkmated.
So the search score of a checking move is subject to larger uncertainty than for other moves, because the potential prize is the highest of all, but on the other hand it is the ideal delaying tactic. Attacking other high pieces is not nearly as effective for the latter purpose, as such pieces can save themselves much more easily, often delivering a new threat as a side effect, or even immediately starting a capture exchange. A check evasion is not likely to do something useful, as a King is usually not in a position to threaten something, and interposing a piece pins that piece. (This logic holds less for interposing a piece that 'fight back' along the line of attack, or for capturing the checker. In a more advanced scheme one might consider not extending these evasions.)
To reduce the uncertainty, a deeper search is needed. Branches with checks in them are therefore extended, i.e. the search is deepened by a number of ply (usually one). If the check happens somewhere in the middle of the branch, it doesn't make a difference if you decide ion the extension in the node where the check is delivered, or in the move where it is evaded. Near the leave nodes, however, it does: awarding it for the evasion might not award it at all if the evasion is just over the horizon. That would leave you in check in a leaf node guessing what will come of it, rather than searching one more ply to find out.
Although awarding the extension when the move is done that delivers the check is thus preferable, it is beyond the capacity of micro-Max to recognize moves as checks. Even detecting it is in check is not easy: it requires a null move with a Quiescence Search on the reply to determine if the opponent can capture our King. This is as expensive as searching our own moves at QS level, and is thus done only when the remaining search depth is at least one ply. In QS nodes, micro-Max is unaware of being in check, and stands pat in blissful ignorance even when checkmated.
So checks are only extended as soon as micro-Max becomes aware of them, which is in the IID iterations that search to one ply. After having tried the null move there, we can then decide to increment the search depth. One-ply searches are then extended to 2-ply searches, etc., forcing at least one more move of our opponent after the evasion. This will tell us if that opponent can do something devastating (e.g. the check was a fork), or if he has been just delaying an inevitable loss when we have a good capture in the QS following his move no matter what he plays. At QS level, the extension is not triggered, however. Horizon checks (and in particular checkmates) therefore remain a major weakness in micro-Max.
The listing below highlights the check-extension code in micro-Max 4.7, which takes 13 charactes.
/***************************************************************************/
/* micro-Max, */
/* A chess program smaller than 2KB (of non-blank source), by H.G. Muller */
/***************************************************************************/
/* version 4.7 (1922 characters) features: */
/* - recursive negamax search */
/* - all-capture MVV/LVA quiescence search */
/* - (internal) iterative deepening */
/* - best-move-first 'sorting' */
/* - a hash table storing score and best move */
/* - futility pruning */
/* - king safety through magnetic, frozen king in middle-game */
/* - R=2 null-move pruning */
/* - Check-evasion extension in full-width nodes */
/* - keep hash and repetition-draw recognition at game level */
/* - evaluation distinguishing B/N, and more distributed promotion bonus */
/* - full FIDE rules (expt under-promotion) and move-legality checking */
#define W while
#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 (1<<24)
struct _ {int K,V;char X,Y,D;} A[U]; /* hash table, 16M+8 entries*/
int M=136,S=128,I=8e3,Q,O,K,N,R,J,Z,k=8,*p,c[9]; /* M=0x88 */
char L,
w[]={0,2,2,7,-1,8,12,23}, /* 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,E,n) /* recursive minimax search, k=moving side, n=depth*/
int k,q,l,e,E,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,F,G,V,P,f=J,g=Z;
char t,p,u,x,y,X,Y,H,B;
struct _*a=A+(J+k*E&U-1); /* lookup pos. in hash table*/
q--; /* adj. window: delay bonus */
d=a->D;m=a->V;X=a->X;Y=a->Y; /* resume at stored depth */
if(a->K-Z|l>I| /* miss: other pos. or empty*/
!(m<=q|X&8&&m>=l|X&S)) /* or window incompatible */
d=Y=0; /* start iter. from scratch */
X&=~M; /* start at best-move hint */
W(d++<n||d<3|| /* iterative deepening loop */
l>I&K==I&&(N<1e6&d<98|| /* root: deepen upto time */
(K=X,L=Y&~M,d=3))) /* time's up: go do best */
{x=B=X; /* start scan at prev. best */
h=Y&S; /* request try noncastl. 1st*/
P=d<3?-I:D(24-k,-l,1-l,-e,S,d-3); /* Search null move */
n+=d==3&P==I; /* Extend 1 ply if in check */
m=-P<l|R>35?d-2?-I:e:-P; /* Prune or stand-pat */
N++; /* node count (for timing) */
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{ /* y traverses ray, or: */
H=y=h?Y^h:y+r; /* sneak in prev. best move */
if(y&M)break; /* board edge hit */
m=E-S&b[E]&&y-E<2&E-y<2?I:m; /* bad castling */
if(p<3&y==E)H^=16; /* shift capt.sqr. H if e.p.*/
t=b[H];if(t&k|p<3&!(y-x&7)-!t)break; /* capt. own, bad pawn mode */
i=37*w[t&7]+(t&192); /* value of capt. piece t */
m=i<0?I:m; /* K capture */
if(m>=l&d>1)goto C; /* abort on fail high */
v=d-1?e:i-p; /* MVV/LVA scoring */
if(d-!t>1) /* remaining depth */
{v=p<6?b[x+8]-b[y+8]:0; /* center positional pts. */
b[G]=b[H]=b[x]=0;b[y]=u|32; /* do move, set non-virgin */
if(!(G&M))b[F]=k+6,v+=50; /* castling: put R & score */
v-=p-4|R>29?0:20; /* penalize mid-game K move */
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 */
+(b[x^16]==k+36)) /* kling to non-virgin King */
-(R>>2); /* Pawn-push bonus in ending*/
V=y+r+1&S?647-p:2*(u&y+16&32); /* Promotion or 6/7th bonus */
b[y]+=V;i+=V;} /* upgrade, or promote to Q */
J+=J(0);Z+=J(8)+G-S; /* update hash key(s) */
v+=e+i;V=m>q?m:q; /* new eval and alpha */
v=d>3|v>V?-D(24-k,-l,-V,-v, /* recursive eval. of reply */
F,d-1):v; /* or fail low if futile */
if(K-I&&v+I&&l>I&x==K&y==L) /* move pending. if legal, */
{Q=-e-i;O=F; /* in root & found, exit D */
R+=i>>7;return I; /* captured non-P material */
}
J=f;Z=g; /* restore hash key(s) */
b[G]=k+6;b[F]=b[y]=0;b[x]=u;b[H]=t; /* undo move,G can be dummy */
}
if(v>m) /* new best, update max,best*/
m=v,X=x,Y=y|S&F; /* mark double move with S */
if(h){h=0;goto A;} /* redo after doing old best*/
if(x+r-y|u&32| /* not 1st step,moved before*/
p>2&(p-4|j-7|| /* no P & no lateral K move,*/
b[G=x+3^r>>1&7]-k-6 /* no virgin R in corner G, */
||b[G^1]|b[G^2]) /* no 2 empty sq. next to R */
)t+=p<5; /* fake capt. for nonsliding*/
else F=y; /* 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-M|m<M-I)d=98; /* mate holds to any depth */
m=m+I|P==I?m:0; /* best loses K: (stale)mate*/
if(a->D<99) /* protect game history */
a->K=Z,a->V=m,a->D=d, /* always store in hash tab */
a->X=X|8*(m>q)|S*(m<l),a->Y=Y; /* move, type (bound/exact),*/
/*if(l>I)printf("%2d ply, %9d searched, score=%6d by %c%c%c%c\n",d-1,N-S,m,
'a'+(X&7),'8'-(X>>4),'a'+(Y&7),'8'-(Y>>4&7)); /* uncomment for Kibitz */
} /* encoded in X S,8 bits */
return m+=m<e; /* delayed-loss bonus */
}
main()
{
K=8;W(K--)
{b[K]=(b[K+112]=o[K+24]+8)+8;b[K+16]=18;b[K+96]=9; /* initial board setup*/
L=8;W(L--)b[16*L+K+8]=(K-4)*(K-4)+(L-3.5)*(L-3.5); /* center-pts table */
} /*(in unused half b[])*/
N=1035;W(N-->M)T[N]=rand()>>9;
W(1) /* play loop */
{N=-1;W(++N<121)
printf(" %c",N&8&&(N+=7)?10:n[b[N]&15]); /* print board */
p=c;W((*p++=getchar())>10); /* read input line */
K=I; /* invalid move */
if(*c-10)K=*c-16*c[1]+799,L=c[2]-16*c[3]+799; /* parse entered move */
k^=D(k,-I,I+1,Q,O,3)-I?0:24; /* think or check & do*/
}
}
Previous Next