Previous Next Downloads
In any iteration of the IID process, before searching any real moves, we figure out what will happen when we pass our turn and give the move to the opponent. If this so-called null move fails high, (i.e. if the current evaluation score is already enough to cut off this branch, and the opponent has no threat that could make this score significantly worse) we accept its score as if it were a legal move. This means we will have a beta cutoff, so we don't get to search any of the real moves. The nice thing now is that we don't search this null move as deep as we would normally have searched the real moves, we reduce its search depth by 2 ply. This saves a lot of search effort, not only because the normal search would eventually go to full depth, but also since this normal search might accidentally pick a move to search first that is worse than the null-move (they do exist!), so that we would have to search multiple moves before we achieve the beta cutoff.
The underlying idea is that if the opponent can not hurt us in N-2 ply when we do nothing, (i.e. null move), the search of our best move to N ply will almost certainly not be able to dig up any dirt either. This because even if there would have been trouble on ply number N-1 after the null-move, (i.e. just beyond the reduced horizon), we almost always can find a real move that postpones this trouble to ply N+1, (i.e. beyond the real horizon), even if it doesn't actually solve the problems pre-emptively. Typical moves that buy you time are exchange of a piece that he has to recapture first, or a counter-threat on a high piece of his, which he then has to withdraw.
These assumptions are dangerous if we have only a few moves, because then there might be zugzwang positions, or the entire situation might be devoid of delaying tactics.
The null-move search is done by a separate recursive call to D(),
before the triply nested loop of the move generator is started.
The earlier versions of micro-Max already contained a null-move search,
for the purpose of determining if we were in check.
This call was done after all real moves had been searched,
and only if no legal one was found amongst them,
to determine check- or stalemate.
For this purpose,
the search could be of minimal depth,
provided the search window was set such that nothing short of King capture could produce a cut-off
(i.e. l=I).
Despite the reduced depth, a null-move search for the benefit of pruning typically goes much deeper. Furthermore, its task is to determine if the null-move score produces a cutoff; if it doesn't, we are not interested in how poor this score is, because we won't use it. Except that we want to know if we leave our King in check by it. Fortunately the new two-pass Quiescence Search never does any beta cutoffs in the first iteration, which serves to identify the capture of the highest piece. Even for the stand-pat cutoff it relies on futility pruning in the parent node.
So by calling the search with any window we are sure to get informed if we are in check. It is very important not to miss any checks, as this might later (if we turn out not to have any legal moves) might lead to misqualification of a checkmate as a stalemate, (which can have a very attractive score), totally wrecking the search. If, on the other hand, we don't recognize the King capture in reply to a normal move, because that move failed low and experienced a beta cutoff for other reasons, we miss the checkmate, but still avoid the node (because it failed low). We might miss the occasional stalemate (to find it on deeper search), but would never misqualify it as checkmate (which would abort any deeper search!).
It is thus safe to use the score of the null-move search as check test,
in case our 'best move' gets stuck at an illegal one after the search.
We should be aware, though, that calling the search is expensive,
since it will always go through all moves of the opponent at least once
(unless it finds a King capture, but this is rare).
We therefore only do it if at least a 1-ply search is requested (d=3),
and never in QS.
In QS we cannot recognize checkmates anyway, so it would not be useful to know if we are in check.
To play it safe, we assume the worst possible score of the null-move in QS, without search.
The null-move reply is thus searched to depth d-3
(which is upgraded to at least QS level anyway in D() itself)
without futility pruning,
with a null-window set at the upper bound l of the original window.
The returned score is saved as P
(which, by negamax, is thus the opposite of the null-move score)
for later use in the mate test.
Apart from this, the result is discarded if it falls below l,
or if the game stage is such that we are afraid for zugzwang
(if the captured material suggests that there are not more than 2 minor Pieces
on the board for both sides together.)
Otherwise we prune,
which is done by setting the best score m to the null-move score.
This will then cause a beta cutoff in the usual place
(directly after the first move is generated).
The listing below highlights the changes important for null-move pruning in micro-Max 4.4. This expanded version 4.3 by only 35 characters, as the captured-material accounting to determine game stage could be shared between King safety and null-move pruning.
/***************************************************************************/
/* micro-Max, */
/* A chess program smaller than 2KB (of non-blank source), by H.G. Muller */
/***************************************************************************/
/* version 4.4 (1865 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 */
/* - 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,C=799,Q,O,K,N,R; /* M=0x88 */
char 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,F,G,V,P;
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| /* 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 */
z==8&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,J,Z,S,S,d-3); /* Search null move */
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=99*w[t&7]; /* 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 */
if(y+r+1&S)b[y]|=7,i+=C; /* promote p to Q, add score*/
}
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 */
J+J(0),Z+J(8)+G-S,F,y,d-1):v; /* or fail low if futile */
if(z&8&&K-I) /* move pending: check legal*/
{if(v+I&&x==K&y==L) /* if move found in root */
{Q=-e-i;O=F; /* & not in check, signal */
R+=i>>7;return l;} /* captured non-P material */
v=m; /* (prevent fail-lows on */
} /* K-capt. replies) */
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*/
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(z==8)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()
{
int j,k=8,*p,c[9];
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]+C,L=c[2]-16*c[3]+C; /* parse entered move */
k^=D(k,-I,I,Q,1,j++,O,8,3)-I?0:24; /* think or check & do*/
}
}
Previous Next Downloads