/***************************************************************************/ /* micro-Max, */ /* A chess program smaller than 2KB (of non-blank source), by H.G. Muller */ /* Port to Atmel ATMega644 and AVR GCC, by Andre Adrian */ /***************************************************************************/ /* version 4.8 (1953 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 detection */ /* - better defense against passers through gradual promotion */ /* - extend check evasions in inner nodes */ /* - reduction of all non-Pawn, non-capture moves except hash move (LMR) */ /* - full FIDE rules (expt under-promotion) and move-legality checking */ /* 26nov2008 no hash table */ /* 29nov2008 all IO via myputchar(), mygetchar(), pseudo random generator */ // #define UNIX // #define VERBOSE #ifdef UNIX #include #include #endif #define W while #define M 0x88 #define S 128 #define I 8000 long N, T; /* N=evaluated positions+S, T=recursion limit */ short Q,O,K,R,k=16; /* k=moving side */ char *p,c[5],Z; /* p=pointer to c, c=user input, computer output, Z=recursion counter */ 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[]={ /* board is left part, center-pts table is right part, and dummy */ 22, 19, 21, 23, 20, 21, 19, 22, 28, 21, 16, 13, 12, 13, 16, 21, 18, 18, 18, 18, 18, 18, 18, 18, 22, 15, 10, 7, 6, 7, 10, 15, 0, 0, 0, 0, 0, 0, 0, 0, 18, 11, 6, 3, 2, 3, 6, 11, 0, 0, 0, 0, 0, 0, 0, 0, 16, 9, 4, 1, 0, 1, 4, 9, 0, 0, 0, 0, 0, 0, 0, 0, 16, 9, 4, 1, 0, 1, 4, 9, 0, 0, 0, 0, 0, 0, 0, 0, 18, 11, 6, 3, 2, 3, 6, 11, 9, 9, 9, 9, 9, 9, 9, 9, 22, 15, 10, 7, 6, 7, 10, 15, 14, 11, 13, 15, 12, 13, 11, 14, 28, 21, 16, 13, 12, 13, 16, 21, 0 }; volatile char breakpoint; /* for debugger */ /* User interface routines */ void myputchar(char c) { #ifdef UNIX putchar(c); #endif } void myputs(const char *s) { while(*s) myputchar(*s++); myputchar('\n'); } char mygetchar(void) { #ifdef VERBOSE return getchar(); #else return 10; /* self play computer with computer */ #endif } /* 16bit pseudo random generator */ #define MYRAND_MAX 65535 unsigned short r = 1; /* pseudo random generator seed */ void mysrand(unsigned short r_) { r = r_; } unsigned short myrand(void) { return r=((r<<11)+(r<<7)+r)>>1; } short D(q,l,e,E,z,n) /* recursive minimax search */ short q,l,e; /* (q,l)=window, e=current eval. score, */ unsigned char E,z,n; /* E=e.p. sqr.z=prev.dest, n=depth; return score */ { short m,v,i,P,V,s; unsigned char t,p,u,x,y,X,Y,H,B,j,d,h,F,G,C; signed char r; if (++Z>30) { /* stack underrun check */ breakpoint=1; /* AVR Studio 4 Breakpoint for stack underrun */ myputchar('u'); --Z;return e; } q--; /* adj. window: delay bonus */ k^=24; /* change sides */ d=Y=0; /* start iter. from scratch */ X=myrand()&~M; /* start at random field */ W(d++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); /* end-game Pawn-push bonus */ V=y+r+1&S?647-p:2*(u&y+16&32); /* promotion or 6/7th bonus */ b[y]+=V;i+=V; /* change piece, add score */ } v+=e+i;V=m>q?m:q; /* new eval and alpha */ C=d-1-(d>5&p>2&!t&!h); C=R>29|d<3|P-I?C:d; /* extend 1 ply if in check */ do s=C>2|v>V?-D(-l,-V,-v, /* recursive eval. of reply */ F,0,C):v; /* or fail low if futile */ W(s>q&++C>7;--Z;return l; /* captured non-P material */ } 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|m2) {*c='a'+(X&7);c[1]='8'-(X>>4);c[2]='a'+(Y&7);c[3]='8'-(Y>>4&7);c[4]=0; breakpoint=2; /* AVR Studio 4 Breakpoint for moves, watch c[] */ #ifdef VERBOSE 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 */ #endif } } /* encoded in X S,8 bits */ k^=24; /* change sides back */ --Z;return m+=m10); /* 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 */ N=0;T=0x3F; /* T=Computer Play strength */ }W(D(-I,I,Q,O,1,3)>-I+1); /* think or check & do*/ #ifdef UNIX print_board(); #endif }