jjone 2007-11-23 08:18
晕, 只有133行的象棋程序
[table][tr]Micro-Max, a 133-line Chess Source[td=1,1,200][url=][img]http://home.hccnet.nl/h.g.muller/winboardF.jpg[/img][/url] [td=1,1,300]Newly released beta version!There now is a [url=http://home.hccnet.nl/h.g.muller/winboardF.html]Winboard[/url] version that can handle bigger boards, and a Fairy-Max engine that can run under it ([url=http://home.hccnet.nl/h.g.muller/dwnldpage.html]download[/url])
The GUI knows the rules of Capablanca Chess, while Fairy-Max can play a wide variety of board sizes and piece types, as it allows user-defined pieces.
[/td][/tr][/table]My original aim was to write a chess program smaller than 1024 characters. I could not do it, so far. Even when I dropped the nitty gritty details of the FIDE rules, like castling and en-passant capture, I could not get the size much below [url=http://home.hccnet.nl/h.g.muller/max1.html]1200 characters[/url].
So I shifted my aim somewhat, and wrote something less minimalistic in up to 2000 characters of source-code. This gave me enough space to implement a (hash) transposition table, checking of the legality of the input moves, and full FIDE rules. Except for under-promotions, which I considered a dull input problem, since the program is unlikely to ever find itself in a situation where it would be useful to play one.
(For real purists: a close-to-minimal version that does understand full FIDE rules including under-promotion can be found [url=http://home.hccnet.nl/h.g.muller/umax1_6.c]here[/url]. It measures 1433 characters. The under-promotions are implemented in a single line that wastes 32 characters. To play one, type 1, 2, or 3 as the 5th character of the input move, for promotion to R, B, or N, respectively. If you type nothing, or 0, promotion is to Q.)
As far as I am aware, this still makes micro-Max the smallest C [url=http://home.hccnet.nl/h.g.muller/definition.txt]Chess program[/url] in existence. A close competitor for this honor, [url=http://www.mailcom.com/ioccc/toledo/toledo2.c]Toledo[/url], measures 2168 characters. Despite its smaller size, micro-Max seems to [url=http://home.hccnet.nl/h.g.muller/tolmax.txt]beat[/url] Toledo easily.
On these pages various aspects of micro-Max are described:
[table][tr][td=1,1,300][list][*]Basic Data Representations[list][*][url=http://home.hccnet.nl/h.g.muller/encode.html]Piece Encoding[/url][*][url=http://home.hccnet.nl/h.g.muller/board.html]Board Representation[/url][/list][*]Move Generation[list][*][url=http://home.hccnet.nl/h.g.muller/movgen.html]Basic Moves[/url][*][url=http://home.hccnet.nl/h.g.muller/ep.html]En Passant Capture[/url][*][url=http://home.hccnet.nl/h.g.muller/castle.html]Castling[/url][*][url=http://home.hccnet.nl/h.g.muller/queen.html]Pawn Promotions[/url][/list][*]Search Algorithm[list][*][url=http://home.hccnet.nl/h.g.muller/minimax.html]Alpha-Beta Minimax[/url][*][url=http://home.hccnet.nl/h.g.muller/quiet.html]Quiescence Search[/url][*][url=http://home.hccnet.nl/h.g.muller/move.html]Do and Undo Move[/url][*][url=http://home.hccnet.nl/h.g.muller/deepen.html]Iterative Deepening[/url][*][url=http://home.hccnet.nl/h.g.muller/sort.html]Move Sorting[/url][/list][*]Transposition Table[list][*][url=http://home.hccnet.nl/h.g.muller/hash.html]Hashing[/url][*][url=http://home.hccnet.nl/h.g.muller/replace.html]Replacement[/url][/list][*]Evaluation[list][*][url=http://home.hccnet.nl/h.g.muller/eval.html]Material[/url][*][url=http://home.hccnet.nl/h.g.muller/pcsqr.html]Piece-Square Table[/url][*][url=http://home.hccnet.nl/h.g.muller/mate.html]Checkmate and Stalemate[/url][*][url=http://home.hccnet.nl/h.g.muller/delay.html]Delay Penalty[/url][/list][*]The Interface[list][*][url=http://home.hccnet.nl/h.g.muller/legal.html]Move Legality Checking[/url][/list][/list][/td][td][list][*]Version 4[list][*][url=http://home.hccnet.nl/h.g.muller/progress.html]General & Hash Table[/url][*][url=http://home.hccnet.nl/h.g.muller/futile.html]Futility Pruning[/url][*][url=http://home.hccnet.nl/h.g.muller/mvv.html]All-captures Quiescence Search[/url][*][url=http://home.hccnet.nl/h.g.muller/safe.html]King Safety[/url][*][url=http://home.hccnet.nl/h.g.muller/null.html]Null-Move Pruning[/url][*][url=http://home.hccnet.nl/h.g.muller/deepen.html]Self-Deepening IID[/url][/list][/list][/td][/tr][/table]An overview of the meaning of all variables in the program can be found [url=http://home.hccnet.nl/h.g.muller/var.html]here[/url]. To make it easier for those who want to study the algorithm, there now also is a [url=http://home.hccnet.nl/h.g.muller/maximax.txt]version[/url] that uses more meaningful (and much longer...) variable names. DownloadingIf you want to try micro-Max on your PC, you can copy-paste the source and compile it yourself. Details on how to do this can be found [url=http://home.hccnet.nl/h.g.muller/download.html]here[/url].
FutureThere are still plenty places where I can scavenge a few characters off the source code. (E.g. [font=NSimsun]A->K[/font] in stead of [font=NSimsun]A[0].K[/font], and [font=NSimsun]a->X&M^M[/font] in stead of [font=NSimsun](a->X&M)!=M[/font], and perhaps combining the two Zobrist keys in a 64-bit type.) The castling code is also rather dumb and bulky. I hope to be able to compact the code enough (without loss of functionality) to make room for new features, in particular null-move threat detection. I will post the [url=http://home.hccnet.nl/h.g.muller/progress.html]progress of this project[/url] regularly on separate pages, so that it does not mess up the tutorial on micro-Max 3.2. If some clearly defined feature is added to future versions of micro-Max, the page explaining it will be included in the index above. Below is the complete source code of micro-Max 3.2. (Click on the various code lines to go directly to their explanation.) If you want to copy-paste it, it is recommended you do it from here, because if I correct a small bug or typo I am generally too lazy to do it on all other pages where the source occurs. So I do it here, and on the page where the particular feature needing the correction is discussed and 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 ptomotion) and move-legality checking */#define F(I,S,N) for(I=S;I<N;I++)#define W(A) while(A)[url=http://home.hccnet.nl/h.g.muller/hash.html]#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 16777224struct _ {int K,V;char X,Y,D;} A[U]; /* hash table, 16M+8 entries*/[/url]int V=112,M=136,S=128,I=8e4,C=799,Q,N,i; /* V=0x70=rank mask, M=0x88 */char O,K,L,[url=http://home.hccnet.nl/h.g.muller/eval.html]w[]={0,1,1,3,-1,3,5,9}, /* relative piece values */[/url][url=http://home.hccnet.nl/h.g.muller/movgen.html]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*/[/url][url=http://home.hccnet.nl/h.g.muller/Encode.html]6,3,5,7,4,5,3,6}, /* initial piece setup */[/url][url=http://home.hccnet.nl/h.g.muller/board.html]b[129], /* board: half of 16x8+dummy*/[/url][url=http://home.hccnet.nl/h.g.muller/hash.html]T[1035], /* hash translation table */[/url][url=http://home.hccnet.nl/h.g.muller/encode.html]n[]=".?+nkbrq?*?NKBRQ"; /* piece symbols on printout*/[/url]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=9,F,G; char t,p,u,x,y,X,Y,H,B;[url=http://home.hccnet.nl/h.g.muller/hash.html]struct _*a=A; /* lookup pos. in hash table*/ j=(k*E^J)&U-9; /* try 8 consec. locations */ W((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 */[/url][url=http://home.hccnet.nl/h.g.muller/deepen.html]N++; /* node count (for timing) */ W(d++<n|z==8&N<1e7&d<98) /* iterative deepening loop */[/url][url=http://home.hccnet.nl/h.g.muller/movgen.html]{x=B=X; /* start scan at prev. best */[/url][url=http://home.hccnet.nl/h.g.muller/sort.html]Y|=8&Y>>4; /* request try noncastl. 1st*/[/url][url=http://home.hccnet.nl/h.g.muller/minimax.html]m=d>1?-I:e; /* unconsidered:static eval */[/url][url=http://home.hccnet.nl/h.g.muller/movgen.html]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 */[/url][url=http://home.hccnet.nl/h.g.muller/sort.html]if(Y&8)H=y=Y&~M; /* sneak in prev. best move */[/url][url=http://home.hccnet.nl/h.g.muller/movgen.html]if(y&M)break; /* board edge hit */[/url][url=http://home.hccnet.nl/h.g.muller/ep.html]if(p<3&y==E)H=y^16; /* shift capt.sqr. H if e.p.*/[/url][url=http://home.hccnet.nl/h.g.muller/movgen.html]t=b[H];if(t&k|p<3&!(r&7)!=!t)break; /* capt. own, bad pawn mode */[/url][url=http://home.hccnet.nl/h.g.muller/eval.html]i=99*w[t&7]; /* value of capt. piece t */[/url][url=http://home.hccnet.nl/h.g.muller/mate.html]if(i<0[/url]||[url=http://home.hccnet.nl/h.g.muller/castle.html]E-S&&b[E]&&y-E<2&E-y<2)m=I; /* K capt. or bad castling */[/url][url=http://home.hccnet.nl/h.g.muller/minimax.html]if(m>=l)goto C; /* abort on fail high */ if(h=d-(y!=z)) /* remaining depth(-recapt.)*/[/url][url=http://home.hccnet.nl/h.g.muller/eval.html]{v=p<6?b[x+8]-b[y+8]:0; /* center positional pts. */[/url][url=http://home.hccnet.nl/h.g.muller/move.html]b[G]=b[H]=b[x]=0;b[y]=u&31; /* do move, strip virgin-bit*/ if(!(G&M)){b[F]=k+6;[/url][url=http://home.hccnet.nl/h.g.muller/eval.html]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 */[/url][url=http://home.hccnet.nl/h.g.muller/queen.html]if(y+r+1&S){b[y]|=7;[/url][url=http://home.hccnet.nl/h.g.muller/eval.html]i+=C;} /* promote p to Q, add score*/ }[/url][url=http://home.hccnet.nl/h.g.muller/minimax.html]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 */[/url][url=http://home.hccnet.nl/h.g.muller/delay.html]v-=v>e; /* delayed-gain penalty */[/url][url=http://home.hccnet.nl/h.g.muller/legal.html]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) */[/url][url=http://home.hccnet.nl/h.g.muller/move.html]b[G]=k+38;b[F]=b[y]=0;b[x]=u;b[H]=t; /* undo move,G can be dummy */[/url][url=http://home.hccnet.nl/h.g.muller/sort.html]if(Y&8){m=v;Y&=~8;goto A;} /* best=1st done,redo normal*/[/url][url=http://home.hccnet.nl/h.g.muller/minimax.html]if(v>m){m=v;X=x;Y=y|S&G;} /* update max, mark with S */[/url] } /* if non castling */[url=http://home.hccnet.nl/h.g.muller/movgen.html]t+=p<5; /* fake capt. for nonsliding*/[/url][url=http://home.hccnet.nl/h.g.muller/ep.html]if(p<3&6*k+(y&V)==S /* pawn on 3rd/6th, or */[/url][url=http://home.hccnet.nl/h.g.muller/castle.html]||(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.*/[/url] }W(!t); /* if not capt. continue ray*/ }}}W((x=x+9&~M)-B); /* next sqr. of board, wrap */[url=http://home.hccnet.nl/h.g.muller/deepen.html]C:if(m>I/4|m<-I/4)d=99; /* mate is indep. of depth */[/url][url=http://home.hccnet.nl/h.g.muller/mate.html]m=m+I?m:-D(24-k,-I,I,0,J,Z,S,S,1)/2; /* best loses K: (stale)mate*/[/url][url=http://home.hccnet.nl/h.g.muller/replace.html]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 */[/url]/*if(z==8)printf("%2d ply, %9d searched, %6d by (%2x,%2x)\n",d-1,N,m,X,Y&0x77);*/ }[url=http://home.hccnet.nl/h.g.muller/legal.html]if(z&8){K=X;L=Y&~M;}[/url][url=http://home.hccnet.nl/h.g.muller/minimax.html]return m; }[/url]main(){ int j,k=8,*p,c[9];[url=http://home.hccnet.nl/h.g.muller/board.html]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*/[/url][url=http://home.hccnet.nl/h.g.muller/pcsqr.html]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[])*/[/url][url=http://home.hccnet.nl/h.g.muller/hash.html]F(i,M,1035)T[i]=random()>>9;[/url] W(1) /* play loop */[url=http://home.hccnet.nl/h.g.muller/board.html]{F(i,0,121)printf(" %c",i&8&&(i+=7)?10:n[b[i]&15]); /* print board */[/url][url=http://home.hccnet.nl/h.g.muller/legal.html]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 */[/url] D(k,-I,I,Q,1,1,O,8,0); /* or think up one */[url=http://home.hccnet.nl/h.g.muller/replace.html]F(i,0,U)A[i].K=0; /* clear hash table */[/url][url=http://home.hccnet.nl/h.g.muller/legal.html]if(D(k,-I,I,Q,1,1,O,9,2)==I)k^=24; /* check legality & do*/[/url] }}In the following pages you will find a detailed discussion of the various features of Micro-Max, and how they are implemented.
jjone 2007-11-23 08:18
[img]http://home.hccnet.nl/h.g.muller/logo.jpg[/img] [url=http://home.hccnet.nl/h.g.muller/max-src2.html]Previous[/url] [url=http://home.hccnet.nl/h.g.muller/board.html]Next[/url]Basic Data RepresentationsPiece EncodingPieces are encoded as integers, which (like anything else on a binary digital computer) are eventually bitpatterns. The encoding makes use of the binary representation by assigning a specific meaning to some bits of the integer encoding: the '8'-bit is used (i.e. set) to indicate a white piece, the '16'-bit indicates a black piece. This makes it easy to test if a piece u belongs to white, by bitwise anding with 8 ([font=NSimsun]u&8[/font]). The code uses a variable k to indicate the side that should move, which has the value 8 on white's turn, or 16 for black, so that [font=NSimsun]u&k[/font] tells us if a piece belongs to the side to move. The '32'-bit is used to indicate that a piece is in the original position (the 'virgin bit'). (Since this is only important for Kings and Rooks in connection with castling, Micro-Max doesn't bother to set the virgin bit on pawns.
The three low-order bits can be interpreted as a number 0-7 that indicates the piece type, and have a meaning that is independent of piece color. This makes tables that do not have to distingush by color (like piece value [font=NSimsun]w[u&7][/font]) half as small. Tables that would like to make this distinction (like the character to used to representthe piece on printout) can simply be indexed with the 4 low-order bits ([font=NSimsun]n[u&15][/font]).
Upstream moving pawns are considered different pieces than downstream moving pawns (type 1 and 2, respectively). Each side has only one of the types of pawns, moving in the appropriate direction, although the engine would not frown at putting pieces on the board that move 'backwards'. The encoding is further chosen such that tests if a piece belongs to a certain group is easy: the sliding pieces (BRQ) are giving the highest type numbers (5,6,7), so that crawling pieces can be recognized by piece type p ([font=NSimsun]=u&7[/font]) [font=NSimsun]p<5[/font]. Pieces that are awarded for moving towards the center of the board (everything but RQ) are recognized by [font=NSimsun]p<6[/font], pawns by [font=NSimsun]p<3[/font]. The complete list thus is {1,2,3,4,5,6,7} = {P+,P-,N,K,B,R,Q}. Type 0 is not used, so it can indicate empty squares on the board.
The following highlights places that show how the piece encoding is used in Micro-Max. /***************************************************************************//* 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 ptomotion) 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 16777224struct _ {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,[b][color=#0000ff]w[]={0,1,1,3,-1,3,5,9}, /* relative piece values */[/color][/b][b][color=#0000ff]o[]={[/color][/b]-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*/ [b][color=#0000ff]6,3,5,7,4,5,3,6}, /* initial piece setup */[/color][/b]b[129], /* board: half of 16x8+dummy*/T[1035], /* hash translation table */[b][color=#0000ff]n[]=".?+nkbrq?*?NKBRQ"; /* piece symbols on printout*/[/color][/b]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=9,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 */ W((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 */ [b][color=#0000ff]if(u&k)[/color][/b] /* [b][color=#0000ff]own piece[/color][/b] (inefficient!)*/ {r=[b][color=#0000ff]p=u&7;[/color][/b] /* [b][color=#0000ff]p = piece type[/color][/b] (set r>0) */ j=o[p+16]; /* first step vector f.piece*/ W(r=[b][color=#0000ff]p>2[/color][/b]&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([b][color=#0000ff]p<3[/color][/b]&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 */ [b][color=#0000ff]i=99*w[t&7]; /* value of capt. piece t */[/color][/b] 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=[b][color=#0000ff]p<6[/color][/b]?b[x+8]-b[y+8]:0; /* center positional pts. */ b[G]=b[H]=b[x]=0;b[y][b][color=#0000ff]=u&31;[/color][/b] /* do move, [b][color=#0000ff]strip virgin-bit[/color][/b]*/ if(!(G&M)){b[F]=k+6;v+=30;} /* castling: put R & score */ [b][color=#0000ff]if(p<3) /* pawns: */[/color][/b] {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+=[b][color=#0000ff]p<5[/color][/b]; /* fake capt. for [b][color=#0000ff]nonsliding[/color][/b]*/ if([b][color=#0000ff]p<3[/color][/b]&6*k+(y&V)==S /* [b][color=#0000ff]pawn[/color][/b] on 3rd/6th, or */ ||[b][color=#0000ff](u&~24)==36[/color][/b]&j==7&& /* [b][color=#0000ff]virgin K[/color][/b] moving sideways,*/ G&M&&b[G=(x|7)-(r>>1&7)][b][color=#0000ff]&32[/color][/b] /* 1st, [b][color=#0000ff]virgin[/color][/b] 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][b][color=#0000ff]=o[i+24]+40[/color][/b])[b][color=#0000ff]+8[/color][/b];b[i+16][b][color=#0000ff]=18;[/color][/b]b[i+96][b][color=#0000ff]=9;[/color][/b] /* 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*/ }}The initial boad setup might deserve some explanation: the piece types in the back of the array [font=NSimsun]o[][/font] are copied to the 1st and 8th rank of the board. On the 1st rank 40 = 8 + 32 is added, which sets the 'white' and the 'virgin' bit. On the 8th rank an extra 8 is added, for a total of 48 = 16 + 32, the 'black' and 'virgin' bits. The 18 = 16 + 2 and 9 = 8 + 1 are the encodings for a black P- and a white P+, respectively.
[url=http://home.hccnet.nl/h.g.muller/max-src2.html]Previous[/url] [url=http://home.hccnet.nl/h.g.muller/board.html]Next[/url]
jjone 2007-11-23 08:19
Basic Representations: the BoardSquare NumberingSquares are designated by a 'square-number'. The '0x88' system is used, meaning that the the board actually has ranks of 16 squares, but only the first 8 squares of each rank are valid and correspond to the 8 files of the board. The two-dimensional board is mapped into a one-dimensional array, rank after rank. Due to this the 4 lowest-order bits of the square number indicate the file, and the higher-order bits the rank. This makes it easy to recognize moves that fall off the board. On the left and they move to invalid square numbers (e.g. from the h-file to the 'i-file'), that have the '8'-bit set (the i-p file have numbers 8-15). Furthermore, all moves that move off the board at the front or back move to invalid rank, and have the 128 bit set (0x80, in hexadecimal). The validity of a square-number can thus be tested by bitwise anding with 0x88 (=136). This constant (which has given the system its name) is held in the global variable M, since it is used quite a lot, thus saving a lot of characters. (If the aim would not be source size, but speed, one would of course do the opposite!)
The Board ArrayThe principal data structure of the program thus is the board array [font=NSimsun]b[129][/font], a one-dimensional array indexed by square-number. Because of the invalid square-numbers, only half of the array is used to store the current chess position. Blocks of 8 used and 8 unused elements alternate, the highest valid square-number is 0x77=119. A dummy square with square-number 0x80=128 (a value held in the global variable S) is included in the array. This square number is sometimes used to indicate an invalid square (e.g. in the variable that indicates on which square e.p. capture is possible when no e.p. captures are possible), to make sure there are no crashes if the program inadvertently stores something there (saving us the trouble of testing the validity of the square number before we store).
Printing the BoardDespite the non-contiguous mapping of the chess board into the [font=NSimsun]b[][/font] array, it is quite easy to step through all squares on the board, skipping the invalid ones. The expression to step from a field xto the next field, which can, for instance, be used in th increment part of a for-loop, is [font=NSimsun]x = x+9 & ~8;[/font]. Due to adding 9 = 8 + 1 in stead of 1 to a square number of a square in the 'a'-'g' file, its '8'-bit gets set, which is taken care of by the [font=NSimsun]& ~8[/font], which clears it again. But doing the same in the 'h' file also gives a carry into the '8'-bit due to the addition of 1. This resets the '8'-bit, and passes the carry through to the more-significant bits, i.e. the rank number. (The [font=NSimsun]& ~8[/font] then has no effect.) If we want the board scan to 'wrap around' from h8 back to a1, we can and with [font=NSimsun]~M[/font] in stead of [font=NSimsun]~8[/font], clearing the '128'-bit together with the '8'-bit when the rank number overflows. In the line that prints out the board (in [font=NSimsun]main()[/font]) things are done a little differently, because the fact that we 'overflow' to a new rank also has to result in the printing of a new-line. Thus it uses a normal for-loop (with [font=NSimsun]i++[/font] increment, but tests the '8'-bit to see if we run off the board inside the [font=NSimsun]printf()[/font] to know what to print (a new-line character, 10, or the representation of the piece on the square, [font=NSimsun]n[b[i]&15][/font]). If this tests true, an extra [font=NSimsun]i += 7[/font] (which always evaluates non-zero, and thus considered true as well) positions us back in front of the next valid square.
Below the declaration and use of the board are highlighted. (Where the original source contained macro's for for or while loops, these are shown expanded for readability.)
/***************************************************************************//* 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 ptomotion) 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 16777224struct _ {int K,V;char X,Y,D;} A[U]; /* hash table, 16M+8 entries*/int [b][color=#0000ff]V=112,M=136,S=128[/color][/b],I=8e3,C=799,Q,N,i; [b][color=#0000ff]/* V=0x70=rank mask, M=0x88 */[/color][/b][b][color=#0000ff]char[/color][/b] 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][color=#0000ff]b[129], /* board: half of 16x8+dummy*/[/color][/b]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=9,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 */ W((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 */ {[b][color=#0000ff]x=B[/color][/b]=X[b][color=#0000ff];[/color][/b] /* [b][color=#0000ff]start scan[/color][/b] at prev. best */ Y|=8&Y>>4; /* request try noncastl. 1st*/ m=d>1?-I:e; /* unconsidered:static eval */ [b][color=#0000ff]do{[/color][/b]u=b[x]; /* [b][color=#0000ff]scan board[/color][/b] 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*/ }}[b][color=#0000ff]}while((x=x+9&~M)-B); /* next sqr. of board, wrap */[/color][/b]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,K,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]; [b][color=#0000ff]for(i=0;i<8;i++)[/color][/b] [b][color=#0000ff]{b[i]=(b[i+V]=o[i+24]+40)+8;b[i+16]=18;b[i+96]=9; /* initial board setup*/[/color][/b] F(j,0,8)b[16*j+i+8]=(i-4)*(i-4)+(j-3.5)*(j-3.5); /* center-pts table */ [b][color=#0000ff]}[/color][/b] /*(in unused half b[])*/ F(i,M,1035)T[i]=random()>>9; W(1) /* play loop */ {[b][color=#0000ff]for(i=0;i<121;i++)printf(" %c",i&8&&(i+=7)?10:n[b[i]&15]); /* print board */[/color][/b] 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*/ }}[url=http://home.hccnet.nl/h.g.muller/encode.html]Previous[/url] [url=http://home.hccnet.nl/h.g.muller/movgen.html]Next[/url]
jjone 2007-11-23 08:19
[img]http://home.hccnet.nl/h.g.muller/logo.jpg[/img] [url=http://home.hccnet.nl/h.g.muller/board.html]Previous[/url] [url=http://home.hccnet.nl/h.g.muller/ep.html]Next[/url]Move Generation: Simple MovesThree Nested LoopsMove generation is done by three nested loops: [list][*]over the pieces[*]over all directions for that piece[*]over all squares in that direction[/list]For crawling pieces (PNK) the loop over squares is usually terminated after the first iteration, although Pawns and Kings (castling!) sometimes also make more than one step in a particular direction. For any piece this inner loop can be aborted because we run off the board or into an obstructing piece, although for obstructing enemy pieces the move might still be legal. Before discussing the nitty-gritty details of the implementation in micro-Max below, we give the general outline of the basic move generator:
[b][color=#0000ff]static int o[] = { -16,-15,17,0, /* downstream pawn */ 16,15,17,0, /* upstream pawn */ 1,-1,16,-16,0, /* rook */ 1,-1,16,-16,15,-15,17,-17,0, /* king, queen and bishop */ 14,-14,18,-18,31,-31,33,-33,0, /* knight */ -1,3,21,12,16,7,12 /* directory */ };x = 0;do{ /* LOOP OVER PIECES */ u = b[x]; /* contents of square */ if(u&k) /* only do something if it contains a piece of mine */ { p = u&7; /* extract piece type */ j = o[p+30]; /* look up first direction it moves in directory */ while(r=o[++j]) /* LOOP OVER DIRECTIONS r taken from vector list */ { y = x; /* start ray at current piece location */ do{ /* LOOP OVER SQUARES */ y += r; /* add one step */ if(y&M) break; /* terminate ray if off board */ t = b[y]; /* contents of target square */ if(t&k) break; /* terminate ray if own piece */ if(p<3&&!(r&7)!=!t) break; /* terminate if pawn and inappropiate mode */ .... /* valid move available: u@x -> t@y. Use it! */ t += p<5; /* make sure t!=0 for crawling pieces */ }while(!t) /* ray continues if move was not capture */ } }}while(i=i+9&~M); /* next square of board */[/color][/b]The Loop over PiecesIn micro-Max the loop over pieces is implemented as a loop over all valid squares of the board, searching for pieces of the side to move. This is rather inefficient, especially if the board gets more empty during the game. Even in the beginning only on 25% of the squares it finds own pieces. The board array is a direct way of finding out what we find where we go, (a question that has to be answered frequently once we try to move a piece), but it leaves us unfortunately unaware of where our pieces are. For that a 'piece list', a table listing the square number and piece type for each piece we (still) have, would be better suited. The outer loop of the move generator would then simply scan this piece list, and find a piece every time, rather than only occasionally finding a piece on a board square. Because of the minimalist approach we decided to sacrifice the piece list. This is the best of two evils: sacrificing the board array would be completely disastrous, because for every attempted move the program could only find out if the move was to an occupied square by scanning the piece lists of both sides. And there are many more attempted moves than there are pieces to move.
For reasons that will become apparent [url=http://home.hccnet.nl/h.g.muller/sort.html]later[/url], the board scan does not begin in a corner, but can begin anywhere on the board, as indicated by variable B. It then wraps around until it reaches that starting square again.
The Loop over DirectionsIf the scan of the board discovers a friendly piece, we start generating moves for this piece. To this end we loop through a list of move vectors, one for every direction a piece of that type can move in. An initialized global array [font=NSimsun]o[][/font] contains the move vectors r (numbers that have to be added to the current square to make one step in that direction). This list is scanned by the loop index j until a 0 is encountered (which obviously is an invalid move vector, since it would make no step at all). The move-vector lists for all piece types are all placed in the same array, one after the other, separated by zeroes. Lists are combined where possible: in the list for a Queen (which is also used for the King) the straight directions all preceed the diagonal directions, so that the final part of the list can be used for a Bishop, by starting it in the middle. For each piece type we need to know where to start scanning the [font=NSimsun]o[][/font] array, this information is stored further in the [font=NSimsun]o[][/font] array itself, so that a piece of type p finds its starting direction index j at [font=NSimsun]o[p+30][/font]. We could say that [font=NSimsun]o[][/font] summarizes most of the rules for chess.
To save some characters in the initializer for the list, we make use of the fact that allowed directions usually come in pairs of opposite directions. The list contains then only contains the positive one, and in the loop over directions each step vector is tried with both signs. Unless the piece is a Pawn, of course. This explains the obfuscated expression [font=NSimsun]p>2&r<0?-r:-o[++j][/font] for the next direction r: first the negative version is tried, and the second time such a negative value is negated and used again.
The Loop over SquaresOnce a move vector r is selected, the inner loop of the move generator repeatedly adds this to the location of the piece, to sweep the destination square y over the board along a ray. Each new y is tested for being on the board ([font=NSimsun]y&M==0[/font]), and if it is, the piece t on the destination square ([font=NSimsun]t=b[y][/font]) is checked. If it is one of our own or if we fall off the board, we break out of the loop immediately. If the piece belongs to the opponent, the move is a capture, and in general valid. So in that case we finish that iteration of the loop, but the test at the end of this do-while loop only continues looping if there was no capture ([font=NSimsun]t==0[/font], written compactly as [font=NSimsun]!t[/font]).
For crawling pieces the loop has to terminate after the first iteration irrespective of the fact if the last move was a capture or not. To this end we [i]fake[/i] a capture for those pieces ([font=NSimsun]p<5[/font]) at the end of the loop, by incrementing t. We still have to deal with the complication that some of the moves generated for pawns are forbidden. In particular straight pawn moves can't be captures, and diagonal moves can't be non-captures. We therefore break out of the loop at the beginning if we detect that the emptyness of the target sqaure (quantified by the expression [font=NSimsun]!t[/font]) matches the straightness of the move vector (quantified as the expression [font=NSimsun]!(r&7)[/font], i.e. if the least significant bits of the move vector, the file displacement, equals zero or not).
Below the basic move-generator code 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 ptomotion) 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 16777224struct _ {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 */[b][color=#0000ff]char[/color][/b] O,K,L,w[]={0,1,1,3,-1,3,5,9}, /* relative piece values */[b][color=#0000ff]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[/color][/b],[b][color=#0000ff] /* 1st dir. in o[] per piece*/[/color][/b] 6,3,5,7,4,5,3,6[b][color=#0000ff]}[/color][/b], /* 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=9,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 */ W((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 */ {[b][color=#0000ff]x=B[/color][/b]=X[b][color=#0000ff];[/color][/b] /* start scan at prev. best */ Y|=8&Y>>4; /* request try noncastl. 1st*/ m=d>1?-I:e; /* unconsidered:static eval */ [b][color=#0000ff]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*/ while(r=p>2&r<0?-r:-o[++j]) /* loop over directions o[] */ {[/color][/b]A: /* resume normal after best */ [b][color=#0000ff]y=x;[/color][/b]F=G=S; /* [b][color=#0000ff](x,y)=move[/color][/b], (F,G)=castl.R*/ [b][color=#0000ff]do{H=y+=r; /* y traverses ray */ [/color][/b]if(Y&8)H=y=Y&~M; /* sneak in prev. best move */ [b][color=#0000ff]if(y&M)break; /* board edge hit */ [/color][/b]if(p<3&y==E)H=y^16; /* shift capt.sqr. H if e.p.*/ [b][color=#0000ff]t=b[H];if(t&k|p<3&!(r&7)!=!t)break; /* capt. own, bad pawn mode */[/color][/b] 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 */ [b][color=#0000ff]t+=p<5; /* fake capt. for nonsliding*/[/color][/b] 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.*/ [b][color=#0000ff]}while(!t); /* if not capt. continue ray*/ }}}while((x=x+9&~M)-B); /* next sqr. of board, wrap */[/color][/b]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,K,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*/ }}[url=http://home.hccnet.nl/h.g.muller/board.html]Previous[/url] [url=http://home.hccnet.nl/h.g.muller/ep.html]Next[/url]
jjone 2007-11-23 08:20
[img]http://home.hccnet.nl/h.g.muller/logo.jpg[/img] [url=http://home.hccnet.nl/h.g.muller/movgen.html]Previous[/url] [url=http://home.hccnet.nl/h.g.muller/castle.html]Next[/url]Move Generation: En PassantThe basic move generator only plays chess as it used to be several hundred years ago, before e.p. capture and castling where invented. It does not even allow pawns to move two squares from their initial position. These 'advanced moves' unfortunately add a relatively large amount of complexity to the move generator, because they violate the basic philosophy of most chess moves. In castling two pieces move, in e.p. capture one does not capture the piece by stepping in its place. In addition, these moves cannot be performed at just any time, and we have to test all the conditions that have to be obeyed.
Pawn's Double MoveThe discussion of the pawn's double move was deferred to this page, because it is intimately tied to the e.p. capture. The basic move generator terminates the inner loop for crawling pieces after the first iteration, by faking a capture through incrementing the captured piece t. Pawns on the 2nd/7th row have to be given one extra iteration, though. This is simply done by decrementing t back to its original value if the target square y of the current iteration is on the 3rd/6th row. To test this for both colors simultaneaously the expressions [font=NSimsun]p<3&6*k+(y&V)==S[/font] is used. It effectively compares the rank number of the pawn, [font=NSimsun](y&V)[/font] with the rank from which they have to make the extra step. Which rank this is, is derived from the color k of the pawn: by multiplying this by 6 we obtain either 0x30 or 0x60, which are subtracted from [font=NSimsun]S=0x80[/font] to optain the sought rank numbers 0x50 (2nd) and 0x20 (6th). In addition the field from which the move was extended is remembered in F, which normally holds the invalid square code S, for passing it to the next ply so that the move generator there knows where it can try an e.p. capture.
E.p. CaptureThe e.p. square is thus passed as a parameter E to the next level of the search tree. If a pawn tries to move to this square, ([font=NSimsun]p<3 & y==E[/font]) it must be through a diagonal step (it cannot come from the square to which the opponent just moved!). For e.p. capture this move does have to be executed, and we have to be able to make a piece disappear that is not in the target square y when the move is later performed. To this end the square of the captured piece is held in a separete variable H, which is normally set to y, but for e.p. capture is set to the 'companion square' [font=NSimsun]E^16[/font], by flipping the lowest bit of the rank number.
Below the code lines involved in Pawn double move and e.p. capture are 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 ptomotion) 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 16777224struct _ {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,[b][color=#0000ff]E,[/color][/b]z,n) /* recursive minimax search, k=moving side, n=depth*/[b][color=#0000ff]int[/color][/b] k,q,l,e,J,Z,[b][color=#0000ff]E,[/color][/b]z,n; /* (q,l)=window, e=current eval. score, E=e.p. sqr.*/{ /* e=score, z=prev.dest; J,Z=hashkeys; return score*/ [b][color=#0000ff]int[/color][/b] j,r,m,v,d,h,i=9,[b][color=#0000ff]F,[/color][/b]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 */ W((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;[b][color=#0000ff]F=[/color][/b]G=[b][color=#0000ff]S;[/color][/b] /* (x,y)=move, (F,G)=castl.R*/ do{[b][color=#0000ff]H=y[/color][/b]+=r; /* y traverses ray */ if(Y&8)H=y=Y&~M; /* sneak in prev. best move */ if(y&M)break; /* board edge hit */ [b][color=#0000ff]if(p<3&y==E)H=y^16; /* shift capt.sqr. H if e.p.*/[/color][/b] 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,[b][color=#0000ff]F,[/color][/b]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*/ [b][color=#0000ff]if(p<3&6*k+(y&V)==S /* pawn on 3rd/6th, or */[/color][/b] ||(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 */ [b][color=#0000ff]){F=y;t--;} /* unfake capt., enable e.p.*/[/color][/b] }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*/ }}[url=http://home.hccnet.nl/h.g.muller/movgen.html]Previous[/url] [url=http://home.hccnet.nl/h.g.muller/castle.html]Next[/url]
jjone 2007-11-23 08:20
[img]http://home.hccnet.nl/h.g.muller/logo.jpg[/img] [url=http://home.hccnet.nl/h.g.muller/ep.html]Previous[/url] [url=http://home.hccnet.nl/h.g.muller/queen.html]Next[/url]Move Generation: CastlingKing CaptureBefore we discuss castling, it is good to point out that micro-Max is a King-capture engine: At any level it generates all pseudo-legal moves, including those that put his own King in check. Since this is a condition that depends on which moves the opponent has, it seems more logical to test it on the next ply, when we generate the opponent's moves anyway. Usually all opponent's moves are generated before micro-Max starts to think about any of them, and if a King capture is found the branch is aborted and the caller is informed (by the move's score) that the move was an illegal one.
Castling and e.p. CaptureCastling and e.p. capture share an underlying philosophy: a piece (Pawn or King) moves farther than it is ordinarily allowed to, and if the square it skips in doing so is under attack by the enemy, it can be captured there anyway. For castling this of course results in the move being declared illegal, since you are not allowed to expose your King to capture.
Micro-Max exploits this similarity: the field that is skipped over with these moves is communicated to the next ply as the recursion argument E, to indicate that something can be captured there. Castling and Pawn e.p. can be easily distinguished by the contents [font=NSimsun]b[E][/font]of the e.p. square: after castling it contains a Rook, after a Pawn double move it is empty. King captures never have to be executed. They lead to termination of the move generation altogether, because the previous move was apparently already an illegal one and we are working on a phantom branch of the search tree. This holds just as much for the 'e.p.' capture of a King after castling, as for ordinary king captures. In fact we can also cover the rule that you are not allowed to castle when in check easily by the same mechanism, by not only testing if the subsequent move goes to the e.p. square, but also to either square next to it [font=NSimsun](y-E<2&E-y<2)[/font].
Thus, in line with the King-capture philosophy, several conditions for castling are checked in hindsight, on the reply move.
Castl