chess.ino 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317
  1. #include <EEPROM.h>
  2. #include <SPI.h>
  3. #include <GD2.h>
  4. #include "chess_assets.h"
  5. static byte sinus(byte x)
  6. {
  7. return 128 + GD.rsin(128, -16384 + (x << 7));
  8. }
  9. void setup()
  10. {
  11. Serial.begin(1000000); // JCB
  12. GD.begin(~GD_STORAGE);
  13. LOAD_ASSETS();
  14. GD.BitmapHandle(1);
  15. GD.BitmapSource(CHECKER);
  16. GD.BitmapSize(NEAREST, REPEAT, REPEAT, 256, 256);
  17. GD.BitmapLayout(L8, CHECKER_WIDTH, CHECKER_HEIGHT);
  18. }
  19. /***************************************************************************/
  20. /* micro-Max, */
  21. /* A chess program smaller than 2KB (of non-blank source), by H.G. Muller */
  22. /* Port to Atmel ATMega644 and AVR GCC, by Andre Adrian */
  23. /***************************************************************************/
  24. /* version 4.8 (1953 characters) features: */
  25. /* - recursive negamax search */
  26. /* - all-capture MVV/LVA quiescence search */
  27. /* - (internal) iterative deepening */
  28. /* - best-move-first 'sorting' */
  29. /* - a hash table storing score and best move */
  30. /* - futility pruning */
  31. /* - king safety through magnetic, frozen king in middle-game */
  32. /* - R=2 null-move pruning */
  33. /* - keep hash and repetition-draw detection */
  34. /* - better defense against passers through gradual promotion */
  35. /* - extend check evasions in inner nodes */
  36. /* - reduction of all non-Pawn, non-capture moves except hash move (LMR) */
  37. /* - full FIDE rules (expt under-promotion) and move-legality checking */
  38. /* 26nov2008 no hash table */
  39. /* 29nov2008 all IO via myputchar(), mygetchar(), pseudo random generator */
  40. #define VERBOSE
  41. #define W while
  42. #define M 0x88
  43. #define S 128
  44. #define I 8000
  45. long N, T; /* N=evaluated positions+S, T=recursion limit */
  46. short Q,O,K,R,k=16; /* k=moving side */
  47. char *p,c[5],Z; /* p=pointer to c, c=user input, computer output, Z=recursion counter */
  48. signed char L,
  49. w[]={0,2,2,7,-1,8,12,23}, /* relative piece values */
  50. o[]={-16,-15,-17,0,1,16,0,1,16,15,17,0,14,18,31,33,0, /* step-vector lists */
  51. 7,-1,11,6,8,3,6, /* 1st dir. in o[] per piece*/
  52. 6,3,5,7,4,5,3,6}, /* initial piece setup */
  53. b[]={ /* board is left part, center-pts table is right part, and dummy */
  54. 22, 19, 21, 23, 20, 21, 19, 22, 28, 21, 16, 13, 12, 13, 16, 21,
  55. 18, 18, 18, 18, 18, 18, 18, 18, 22, 15, 10, 7, 6, 7, 10, 15,
  56. 0, 0, 0, 0, 0, 0, 0, 0, 18, 11, 6, 3, 2, 3, 6, 11,
  57. 0, 0, 0, 0, 0, 0, 0, 0, 16, 9, 4, 1, 0, 1, 4, 9,
  58. 0, 0, 0, 0, 0, 0, 0, 0, 16, 9, 4, 1, 0, 1, 4, 9,
  59. 0, 0, 0, 0, 0, 0, 0, 0, 18, 11, 6, 3, 2, 3, 6, 11,
  60. 9, 9, 9, 9, 9, 9, 9, 9, 22, 15, 10, 7, 6, 7, 10, 15,
  61. 14, 11, 13, 15, 12, 13, 11, 14, 28, 21, 16, 13, 12, 13, 16, 21, 0
  62. };
  63. volatile char breakpoint; /* for debugger */
  64. /* User interface routines */
  65. void myputchar(char c) {
  66. #ifdef DUMPDEV // JCB{
  67. fprintf(stderr, "%c", c);
  68. #endif // }JCB
  69. }
  70. void myputs(const char *s) {
  71. while(*s) myputchar(*s++);
  72. myputchar('\n');
  73. }
  74. char mygetchar(void) {
  75. return 10; /* self play computer with computer */
  76. #ifdef VERBOSE
  77. return getchar();
  78. #else
  79. return 10; /* self play computer with computer */
  80. #endif
  81. }
  82. /* 16bit pseudo random generator */
  83. #define MYRAND_MAX 65535
  84. unsigned short r = 1; /* pseudo random generator seed */
  85. void mysrand(unsigned short r_) {
  86. r = r_;
  87. }
  88. unsigned short myrand(void) {
  89. return r=((r<<11)+(r<<7)+r)>>1;
  90. }
  91. static void sp()
  92. {
  93. void* x;
  94. x = &x;
  95. Serial.println((size_t)x, HEX);
  96. }
  97. short D(short q, short l, short e, byte E,byte z, byte n) /* recursive minimax search */
  98. /* (q,l)=window, e=current eval. score, */
  99. /* E=e.p. sqr.z=prev.dest, n=depth; return score */
  100. {
  101. short m,v,i,P,V,s;
  102. unsigned char t,p,u,x,y,X,Y,H,B,j,d,h,F,G,C;
  103. signed char r;
  104. // if (0) { REPORT(Z); sp(); }
  105. if (++Z>30) { /* stack underrun check */
  106. breakpoint=1; /* AVR Studio 4 Breakpoint for stack underrun */
  107. myputchar('u');
  108. --Z;return e;
  109. }
  110. q--; /* adj. window: delay bonus */
  111. k^=24; /* change sides */
  112. d=Y=0; /* start iter. from scratch */
  113. X=myrand()&~M; /* start at random field */
  114. W(d++<n||d<3|| /* iterative deepening loop */
  115. z&K==I&&(N<T&d<98|| /* root: deepen upto time */
  116. (K=X,L=Y&~M,d=3))) /* time's up: go do best */
  117. {x=B=X; /* start scan at prev. best */
  118. h=Y&S; /* request try noncastl. 1st*/
  119. P=d<3?I:D(-l,1-l,-e,S,0,d-3); /* Search null move */
  120. m=-P<l|R>35?d>2?-I:e:-P; /* Prune or stand-pat */
  121. ++N; /* node count (for timing) */
  122. do{u=b[x]; /* scan board looking for */
  123. if(u&k) /* own piece (inefficient!)*/
  124. {r=p=u&7; /* p = piece type (set r>0) */
  125. j=o[p+16]; /* first step vector f.piece*/
  126. W(r=p>2&r<0?-r:-o[++j]) /* loop over directions o[] */
  127. {A: /* resume normal after best */
  128. y=x;F=G=S; /* (x,y)=move, (F,G)=castl.R*/
  129. do{ /* y traverses ray, or: */
  130. H=y=h?Y^h:y+r; /* sneak in prev. best move */
  131. if(y&M)break; /* board edge hit */
  132. m=E-S&b[E]&&y-E<2&E-y<2?I:m; /* bad castling */
  133. if(p<3&y==E)H^=16; /* shift capt.sqr. H if e.p.*/
  134. t=b[H];if(t&k|p<3&!(y-x&7)-!t)break; /* capt. own, bad pawn mode */
  135. i=37*w[t&7]+(t&192); /* value of capt. piece t */
  136. m=i<0?I:m; /* K capture */
  137. if(m>=l&d>1)goto C; /* abort on fail high */
  138. v=d-1?e:i-p; /* MVV/LVA scoring */
  139. if(d-!t>1) /* remaining depth */
  140. {v=p<6?b[x+8]-b[y+8]:0; /* center positional pts. */
  141. b[G]=b[H]=b[x]=0;b[y]=u|32; /* do move, set non-virgin */
  142. if(!(G&M))b[F]=k+6,v+=50; /* castling: put R & score */
  143. v-=p-4|R>29?0:20; /* penalize mid-game K move */
  144. if(p<3) /* pawns: */
  145. {v-=9*((x-2&M||b[x-2]-u)+ /* structure, undefended */
  146. (x+2&M||b[x+2]-u)-1 /* squares plus bias */
  147. +(b[x^16]==k+36)) /* kling to non-virgin King */
  148. -(R>>2); /* end-game Pawn-push bonus */
  149. V=y+r+1&S?647-p:2*(u&y+16&32); /* promotion or 6/7th bonus */
  150. b[y]+=V;i+=V; /* change piece, add score */
  151. }
  152. v+=e+i;V=m>q?m:q; /* new eval and alpha */
  153. C=d-1-(d>5&p>2&!t&!h);
  154. C=R>29|d<3|P-I?C:d; /* extend 1 ply if in check */
  155. do
  156. s=C>2|v>V?-D(-l,-V,-v, /* recursive eval. of reply */
  157. F,0,C):v; /* or fail low if futile */
  158. W(s>q&++C<d);v=s;
  159. if(z&&K-I&&v+I&&x==K&y==L) /* move pending & in root: */
  160. {Q=-e-i;O=F; /* exit if legal & found */
  161. R+=i>>7;--Z;return l; /* captured non-P material */
  162. }
  163. b[G]=k+6;b[F]=b[y]=0;b[x]=u;b[H]=t; /* undo move,G can be dummy */
  164. }
  165. if(v>m) /* new best, update max,best*/
  166. m=v,X=x,Y=y|S&F; /* mark double move with S */
  167. if(h){h=0;goto A;} /* redo after doing old best*/
  168. if(x+r-y|u&32| /* not 1st step,moved before*/
  169. p>2&(p-4|j-7|| /* no P & no lateral K move,*/
  170. b[G=x+3^r>>1&7]-k-6 /* no virgin R in corner G, */
  171. ||b[G^1]|b[G^2]) /* no 2 empty sq. next to R */
  172. )t+=p<5; /* fake capt. for nonsliding*/
  173. else F=y; /* enable e.p. */
  174. }W(!t); /* if not capt. continue ray*/
  175. }}}W((x=x+9&~M)-B); /* next sqr. of board, wrap */
  176. C:if(m>I-M|m<M-I)d=98; /* mate holds to any depth */
  177. m=m+I|P==I?m:0; /* best loses K: (stale)mate*/
  178. if(z&&d>2)
  179. {*c='a'+(X&7);c[1]='8'-(X>>4);c[2]='a'+(Y&7);c[3]='8'-(Y>>4&7);c[4]=0;
  180. breakpoint=2; /* AVR Studio 4 Breakpoint for moves, watch c[] */
  181. #ifdef DUMPDEV // JCB{
  182. fprintf(stderr, "%2d ply, %9d searched, score=%6d by %c%c%c%c\n",d-1,N-S,m,
  183. 'a'+(X&7),'8'-(X>>4),'a'+(Y&7),'8'-(Y>>4&7)); /* uncomment for Kibitz */
  184. #else
  185. REPORT(d);
  186. Serial.println(c);
  187. #endif // }JCB
  188. }
  189. } /* encoded in X S,8 bits */
  190. k^=24; /* change sides back */
  191. --Z;return m+=m<e; /* delayed-loss bonus */
  192. }
  193. void print_board()
  194. {
  195. short N=-1;
  196. W(++N<121)
  197. myputchar(N&8&&(N+=7)?10:".?inkbrq?I?NKBRQ"[b[N]&15]); /* Pawn is i */
  198. }
  199. static void p2(int &x, int &y, const char *c)
  200. {
  201. x = 16 * (32 + 32 * (c[0] - 'a'));
  202. y = 16 * ( 8 + 32 * ('8' - c[1]));
  203. }
  204. #define MOVETIME 10
  205. #define OVERSAMPLE 8
  206. int clocks[2];
  207. void draw_board()
  208. {
  209. // . ? i n k b r q ? I ? N K B R Q
  210. byte xlat[] = { 0, 0, 0, 1, 5, 2, 3, 4, 0, 6, 0, 7, 11,8, 9,10 };
  211. for (int i = 0; i < MOVETIME; i++) {
  212. GD.cmd_gradient(0, 0, 0x101010, 480, 272, 0x202060);
  213. GD.cmd_bgcolor(0x101020);
  214. GD.Begin(BITMAPS);
  215. GD.SaveContext();
  216. GD.ColorRGB(0xfff0c0);
  217. GD.ColorA(0xc0);
  218. GD.cmd_scale(F16(32), F16(32));
  219. GD.cmd_setmatrix();
  220. GD.Vertex2ii(32, 8, 1, 0);
  221. GD.RestoreContext();
  222. int moving = -1;
  223. if (c[0])
  224. moving = 16 * ('8' - c[3]) + (c[2] - 'a');
  225. GD.Begin(BITMAPS);
  226. GD.ColorRGB(0xe0e0e0);
  227. for (int y = 0; y < 8; y++)
  228. for (int x = 0; x < 8; x++) {
  229. int pos = 16 * y + x;
  230. byte piece = b[pos] & 15;
  231. if (pos != moving && piece != 0)
  232. GD.Vertex2ii(32 + 32 * x, 8 + 32 * y, 0, xlat[piece]);
  233. }
  234. if (c[0]) {
  235. GD.Begin(BITMAPS);
  236. byte piece = b[moving] & 15;
  237. GD.Cell(xlat[piece]);
  238. int x0, y0, x1, y1;
  239. p2(x0, y0, c + 0);
  240. p2(x1, y1, c + 2);
  241. GD.ColorRGB(0xffffff); //' a{
  242. GD.ColorA((255 / OVERSAMPLE) + 50);
  243. for (int j = 0; j < OVERSAMPLE; j++) {
  244. byte linear = 255 * (i * OVERSAMPLE + j) /
  245. (OVERSAMPLE * MOVETIME - 1);
  246. byte scurve = sinus(linear);
  247. int x = x0 + (long)(x1 - x0) * scurve / 255;
  248. int y = y0 + (long)(y1 - y0) * scurve / 255;
  249. GD.Vertex2f(x, y);
  250. } //' }a
  251. GD.ColorA(255);
  252. }
  253. GD.ColorRGB((k == 16) ? 0xffffffUL : 0x606060);
  254. GD.cmd_clock(384, 60, 50, OPT_FLAT | OPT_NOSECS, 0, 0, clocks[0], 0);
  255. GD.ColorRGB((k != 16) ? 0xffffffUL : 0x606060);
  256. GD.cmd_clock(384, 272 - 60, 50, OPT_FLAT | OPT_NOSECS, 0, 0, clocks[1], 0);
  257. GD.ColorRGB(0xffffff);
  258. GD.cmd_text(384, 136, 30, OPT_CENTER, c);
  259. GD.swap();
  260. }
  261. }
  262. void loop()
  263. {
  264. #ifdef VERBOSE // JCB{
  265. print_board();
  266. #endif // }JCB
  267. draw_board();
  268. K=I; /* invalid move */
  269. #if 0 // JCB{
  270. p=c;W((*p++=mygetchar())>10); /* read input line */
  271. if(*c-10)K=*c-16*c[1]+799,L=c[2]-16*c[3]+799; /* parse entered move */
  272. #endif // }JCB
  273. N=0;T=0x9; /* T=Computer Play strength */
  274. long t0 = millis();
  275. if(!(D(-I,I,Q,O,1,3)>-I+1)) /* think or check & do*/
  276. for (;;);
  277. int took = 60 * (millis() - t0) / 1000;
  278. clocks[(k==16)] += took;
  279. }