Previous Next
Currently I am working on a new version of micro-Max: version 4. Since version 3.2 was already close to the maximum size I allowed myself, the first step is to squeeze some air out of it, without losing too much of the functionality. Fortunately there were a number of places where the code was not yet optimally dense. I could squeeze out many characters by replacing for-loops by while-loops, and using a comma rather than the semicolon as statement separator in if-statements saved some braces. To get the best savings I have changed some of the design principles that were used in version 3: the virgin-bit, for instance, will be set in version 4 when the piece moves, rather than cleared. This makes more compact testing of the castling conditions possible.
The delayed-gain penalty has now been moved to the other side of the recursive call, (just before the return, rather than after it), which due to the sign changes in negamax makes it appear as a delayed-loss bonus. In the old place it had the unwanted effect of putting a penalty on any exchange of material, because a recapture is a situation where the score of the move is better than the current evaluation. But recapturing is not a case of postponed gain, one can not recapture pre-emptively. The score should have been compared to the evaluation after the recapture was done. The current position, at the return, takes care of this. If the side to move seems to look at a forced loss, it receives the bonus, because having the initiative of the move is worth more in such a tactical position than in a quiet one.
The test to determine if the rays of crawling pieces should be terminated after the first step,
or once extended for Pawn (double move) or King (castling) has now completely altered logic.
(To make it even more compact and obfuscated.)
The test is now for termination of the ray (before it tested the opposite condition, for continuation).
This is certainly done if the move is not the first step along this ray
or if the piece making that step had moved before.
For Pawns those would be the only two reasons why a double move is illegal,
(on captures rays are terminated anyway).
But for other pieces (p>2) we have to check
One of the places I really cut was the hash-table access and replacement. Although the gain in playstrength the hash table added in the middle game was disappointing, (it speeds up a 6-ply search by a factor 2.5), it remains extremely important in simple end-games (where it can mean the difference between a 10-ply search and a 30-ply search!). So I did not want to remove it completely, but I shrunk the code devoted to it significantly, by going to a less advanced algorithm. In particular, there is no rehashing in version 4, and if a positions hashes to an entry that was already occupied by another position, it simply overwrites it (in stead of looking in eight other places for an empty slot). If the stored score does not match the needs of the current window, (i.e. wrong type of bound), the hash-table information is (almost) completely ignored, and starts iterative deepening from scratch. That way the program does not have to figure out if the best move was valid or at what depth to start.
In the first iteration it does start to scan the board at the origin square of the best move as reported in the table, though. This can never hurt, even if the hash move was invalid (because the hash result had zero depth) and there was no piece on this square. If the best move was valid, starting move generation on this square finds the best move pretty quickly anyway.
In essence the retrieved hash table data is ignored if it was not usable,
while if it was, the iterative deepening simply resumes from the point stored in the hash table.
If the stored result was deeper than the requested one,
the iterative-deepening loop is not even executed, since it tests at the beginning if the requested depth is reached.
It is then skipped and D() immediately returns at the end with the hash result.
The dedicated return on hash-table hits at the beginning of D() is thus no longer needed.
Since hash-table replacement is done inside the iterative-deepening loop,
there is an automatic guarantee that a usable and deeper result will not be overwritten,
since if such a result existed the loop is never executed.
Inside the loop the calculated result is always deeper than the stored result,
and we can overwrite the table unconditionally, saving us an if-statement.
Surprisingly, these simplifications (which reduced the size of micro-Max by 5%) did hardly affect performance: in a middle-game position the number of times the move generator was run stayed nearly the same, in the KPK end-game this number went up from 7.7M to 12M at 30 ply. (All with a 16M-entry hash table.) This seems quite acceptable, in the PKP the promotion is seen at 24 ply.
The hash table is no longer cleared between moves, but invalidated by incrementing the initial value of the second Zobrist key after each move at the game level.
This causes an extra difference of one key with respect to the other,
which guarantees that none of the positions in the hash table will be recognized anymore.
This is needed since the Zobrist keys are not really calculated for the root position,
but set to an arbitrary value, and then differentially updated from there.
If they woud be set to the same values always,
the root position would always have the same keys from one move to the other,
even though it is a different position!
In version 3.2 this was solved by clearing the table between moves.
Not clearing the (big) table saves some time as well!
To be able to retain the hash table from one move to the next would require passing the updated Zobrist keys
back to main() just like the e.p. flag and evaluation are passed via O and Q.
The legality checking is now implemented in a smarter way.
In version 3.2 there were 2 calls to D() for this,
but in version 4 these calls are combined into one.
The call always passes z==8 to indicate the root node.
From the value of the global variable K,
that is filled from the input move or with an invalid square number if there was none,
it can see if it is supposed to merely check the move in K,L,
or think up one himself.
After producing a move (after searching the requested number of nodes,
or reaching the maximum allowed depth)
it automatically copies (as side effect of the loop test) this move to K,L
and resets the depth to the value needed for checking,
which is then done in the final iteration.
More extensive testing revealed a bug:
e.p. capture was sometimes not accepted because a double Pawn move sorted in front as best move
was not recognized as a double move anymore,
just like castlings are not recognized as castlings.
This due to the e.p. flag F not being set if the move is not generated normally,
but sneaked in front.
To solve this, now also Pawn double moves (so any move that has F!=S) are excluded
from being tried as best moves.
If such a Pawn move happens to be best, it is tried as second,
only preceeded by the single move.
Some global variables (notably O) were giving trouble when defined as char.
When passed through an int argument, they underwent the wrong sign extension.
This would lead to hash misses in the root,
(since the e.p. flag passed to it from the global variable is used in the hash key).
In the current version this had no ill effects,
but when using the hash to lock away the game history and check for repetition draws,
it prevented recognition of the draws:
the game history, which was recorded in root nodes, was hidden to the normal search.
So these variables are moved to the list of integers now.
Micro-Max lost two games in automatic play against TSCP because the latter promoted to Knight
in a lost position!
Of course micro-Max assumed it was a Queen, and lost due to an illegal-move error.
Perhaps I should fix this after all, at least in the input...
There also turned out to be a bug in the castling logic:
Version 3.2 would castle out of check if that check was delivered by a Pawn.
In the pseudo-legal move-generation scheme of micro-Max,
such castlings (like other moves that expose the King) are intercepted in the reply:
if the opponent finds a move that captures the King, or, after castling,
the old King square or the skipped square,
it knows the castling was illegal and it aborts that branch.
Problem now was that this test for illegal castling was done after the test for legality of Pawn moves.
Since the old King square is empty by then, the Pawn capture to it
constituting the check on the previous ply, was no longer considered legal.
The fix was to move the test for illegal castlings to before the legality test for Pawn moves.
This took 5 extra characters, because it can no longer share the if-statement with the test for
normal King capture (which should only be applied to Pawn captures).
That Pawn non-captures to any of the three castling squares also outlaw castling is no problem:
if such moves exist the Pawn has always true captures that prevent the castling anyway.
Another bug that did not reveal itself (but led to unjust rejection of input moves in later versions)
was in the insertion of the previous best move:
if this was a Pawn capture, the non-captures of this Pawn would be generated first,
and as a result the Pawn-move legality test would classify them as illegal
(since it uses the step vector of the non-capture, and sees that something is captured
on the target square given by the priority move).
The priority move would simply wait to be substituted for the next move,
(after which this next move would be replayed),
but as a consequence the non-captures would be skipped.
The fix was to simply test the actual step y-x rather than the generation vector r
(2 extra characters).
Below you find the listing of the slimmed-down version of micro-Max. The most important changes compared to version 3.2 are shown in blue. Possible future deletions of tasks that might be done in another way in upcoming versions are underlined. (Last changed January 26, 2007)
/***************************************************************************/
/* micro-Max, */
/* A chess program smaller than 2KB (of non-blank source), by H.G. Muller */
/***************************************************************************/
/* version 4.0 (1752 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 */
/* Rehash sacrificed, simpler retrieval. Some characters squeezed out. */
/* No hash-table clear, single-call move-legality checking based on K==I */
#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; /* 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,s;
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|| /* iterative deepening loop */
z==8&K==I&&(N<1e6&d<98|| /* root: deepen upto time */
(K=X,L=Y&~M,d=2))) /* time's up: go do best */
{x=B=X; /* start scan at prev. best */
h=Y&S; /* request try noncastl. 1st*/
m=d>1?-I:e; /* unconsidered:static eval */
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)goto C; /* abort on fail high */
if(s=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|32; /* do move, set non-virgin */
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,m>q?-m:-q,-e-v-i, /* recursive eval. of reply */
J+J(0),Z+J(8)+G-S,F,y,s); /* J,Z: hash keys */
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;return l;} /* & not in check, signal */
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=99; /* mate holds to any depth */
m=m+I?m:-D(24-k,-I,I,0,J,Z,S,S,1); /* 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,2)-I?0:24; /* think or check & do*/
}
}
Previous Next