Previous Next
The rule for repetition draws can play in important role in two places. For one, if a position has already occurred in the game, repeating it might mean an immediate draw. If we are ahead, such positions are better avoided, or we would score many unnecessary draws. In the second place, positions that have not occurred in the game might be repeated in the tree. This is important for planning a sacrifice to enable giving perpetual check.
Now the latter case occurs a lot less frequently. If micro-Max can give a perpetual, it usually does it anyway, no matter what the score is. It just wouldn't sacrifice anything for it.
For the benifit of a simple implementation we dropped the latter case. So micro-Max only recognizes repetition of positions that have actually been on the board. It scores the first repetition already as a draw, despite the fact that the real draw should occur only on the second repetition (third occurrence). This is not very harmful, as the benificial effect of recognizing the draws is mainly due to the avoidance of completely needless repetitions, and force an alternative if a draw is not desirable. Usually there are many such alternatives of nearly equal score.
In order to recognize repetition draws, a history of some sorts should be kept. The hash table is the logical place for this, as it is made for storing positions and information about them. This of course requires the hash probing to find positions stored on earlier searches, i.e. the keep hash feature is essential for repetition-draw recognition to be possible.
The game history should remain accessible for the remaining duration of the game.
Or at least upto the next reversible move,
but as the number of positions in a game is a totally negligible fraction of the hash size,
it really serves no purpose trying to economize on this.
So all positions that occur in the game are locked in the hash
as soon as the move leading away from them is played at game level.
This is done by giving them the ultimate draft a->D=99,
and making sure that an entry with such draft is never overwritten.
Due to the game-history positions having a draft in their hash entries larger than any other position hashed from the tree, return to such positions in the tree will automatically produce a hash hit with sufficient depth. As in the root the search window is always fully open, the score will also be stored as an exact one. The score will thus be taken from the hash table, and returned without further search. To make sure the position is recognized as a draw, the only thing we have to do is to replace the original score by a draw score of zero when we lock the position into the hash.
The listing below highlights the changes for repetition-draw recognition at game level in micro-Max 4.5. Together with the keep-hash feature, this change expands the source by 32 characters.
/***************************************************************************/
/* micro-Max, */
/* A chess program smaller than 2KB (of non-blank source), by H.G. Muller */
/***************************************************************************/
/* version 4.5 (1866 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 */
/* - keep hash and repetition-draw recognition at game level */
/* - 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,J,Z,k=16,*p,c[9]; /* M=0x88 */
char L,
w[]={0,2,2,7,-1,8,11,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 */
D(q,l,e,E,z,n) /* recursive minimax search, k=moving side, n=depth*/
int q,l,e,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,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 */
k^=24; /* change side */
d=a->D;m=a->V;X=a->X;Y=a->Y; /* resume at stored depth */
if(a->K-Z|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(-l,1-l,-e,S,0,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=37*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 */
-(R>>2); /* Pawn-push bonus in ending*/
if(y+r+1&S)b[y]|=7,i+=C; /* promote p to Q, add score*/
}
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(-l,-V,-v, /* recursive eval. of reply */
F,0,d-1):v; /* or fail low if futile */
if(K-I&&v+I&&z&x==K&y==L) /* move pending. if legal, */
{Q=-e-i;O=F; /* in root & found, exit D */
a->D=99;a->V=0; /* lock in hash, set to draw*/
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-2,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 */
k^=24; /* change side back */
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:".?+nkbrq?*?NKBRQ"[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 */
D(-I,I+1,Q,O,1,3); /* think or check & do*/
}
}
Previous Next