Arduino UNO MicroMax Chess

1/***************************************************************************/
2/*  Ported chess program to Arduino UNO by rom3                             */
3/*  Based on:         micro-Max,       version 4.8                          */
4/*  A chess program smaller than 2KB (of non-blank source), by H.G. Muller  */
5/*  Chessuino by Diego Cueva                                                */ 
6/*  Atmel ATMega644 and AVR GCC, by Andre Adrian                            */
7/*  May 12 2019        Germany                                              */
8/***************************************************************************/
9
10#define  W while
11#define M 0x88
12#define S 128
13#define I 8000
14
15#define MYRAND_MAX  65535     /* 16bit pseudo random generator */
16long  N, T;                  /*  N=evaluated positions+S, T=recursion limit */
17short Q, O, K, R, k=16;      /*  k=moving side */
18char *p, c[5], Z;            /* p=pointer to c, c=user input,  computer output, Z=recursion counter */
19
20char L,
21w[]={0,2,2,7,-1,8,12,23},                             /* relative piece values    */
22o[]={-16,-15,-17,0,1,16,0,1,16,15,17,0,14,18,31,33,0,  /* step-vector lists */
23     7,-1,11,6,8,3,6,                                 /*  1st dir. in o[] per piece*/
24     6,3,5,7,4,5,3,6};                                /*  initial piece setup      */
25/* board is left part, center-pts table is right  part, and dummy */  
26
27char b[]={     
28  22, 19, 21, 23, 20, 21, 19, 22,  28, 21, 16, 13, 12, 13, 16, 21,
29  18, 18, 18, 18, 18, 18, 18, 18, 22, 15, 10,  7,  6,  7, 10, 15,
30   0,  0,  0,  0,  0,  0,  0,  0, 18, 11,  6,  3,  2,  3,  6, 11,
31   0,  0,  0,  0,  0,  0,  0,  0, 16,  9,  4,  1,  0,  1,  4,  9,
32   0,  0,  0,  0,  0,  0,  0,  0, 16,  9,  4,  1,  0,  1,  4,  9,
33   0,  0,  0,  0,  0,  0,  0,  0, 18, 11,  6,  3,  2,  3,  6, 11,
34   9,  9,  9,  9,  9,  9,  9,  9, 22, 15, 10,  7,  6,  7, 10, 15,
35  14, 11, 13, 15, 12, 13, 11, 14, 28,  21, 16, 13, 12, 13, 16, 21, 0
36};
37
38char bk[16*8+1];
39
40unsigned int  seed=0;
41uint32_t  byteBoard[8];
42
43char sym[17] = {".?pnkbrq?P?NKBRQ"};
44int  mn=1;
45char lastH[5], lastM[5];
46unsigned short ledv=1;
47
48String inputString  = "";
49bool stringComplete = false;  // whether the string is complete
50
51void  setup() {
52  Serial.begin(9600);
53  Serial.println("*** MicroMaxChess ***");
54  lastH[0] = 0;
55  serialBoard();
56}
57
58void loop() {
59  int r;
60  //  Take move from human
61  while (stringComplete == false) {
62    getserialchar();
63  }
64  Serial.print(mn);
65  Serial.print(". ");
66  Serial.print(inputString.substring(0,4));
67  c[0] = inputString.charAt(0);
68  c[1] = inputString.charAt(1);
69  c[2] = inputString.charAt(2);
70  c[3] = inputString.charAt(3);
71  c[4] = 0;
72  // clear the string:
73  inputString  = "";
74  stringComplete = false;
75  Serial.print(" Think ");                       /*  Turn for ARDUINO */
76
77  K = *c - 16 * c[1] + 799, L = c[2] - 16 * c[3] + 799;  /* parse entered move */
78  N = 0;
79  T = 0x3F;                                 /*  T=Computer Play strength */
80  bkp();                                    /* Save  the board just in case */
81  r = D(-I, I, Q, O, 1, 3);                 /* Check  & do the human movement */
82  if ( !(r > -I + 1) ) {
83    Serial.println("Lose  ");
84    gameOver();
85  }
86  if (k == 0x10) {                          /*  The flag turn must change to 0x08 */
87    Serial.println("No valid move");
88    return;
89  }
90
91  strcpy(lastH, c);                         /* Valid human  movement */
92
93  mn++;                                     /* Next move */
94
95  K = I;
96  N = 0;
97  T = 0x3F;                                 /* T=Computer  Play strength */
98  r = D(-I, I, Q, O, 1, 3);                 /* Think & do*/
99  if ( !(r > -I + 1) ) {
100    Serial.println("Lose*");
101    gameOver();
102  }
103
104  strcpy(lastM, c);                         /* Valid ARDUINO movement  */
105  r = D(-I, I, Q, O, 1, 3);
106  if ( !(r > -I + 1) ) {
107    Serial.println(lastM);
108    gameOver();
109  }
110Serial.println(lastM);
111   serialBoard();
112}
113
114
115/*  User interface routines */
116
117void getserialchar() {
118  while (Serial.available()  > 0) {
119    // get the new byte:
120    char inChar = (char)Serial.read();
121    // add it to the inputString:
122    inputString += inChar;
123    // if the  incoming character is a newline, set a flag so the main loop can
124    // do something  about it:
125    if (inChar == '\n') {
126      stringComplete = true;
127    }
128  }
129}
130unsigned short myrand(void) {
131  unsigned short r = (unsigned short)(seed  % MYRAND_MAX);
132  return r = ((r << 11) + (r << 7) + r) >> 1;
133}
134/* recursive  minimax search */
135/* (q,l)=window, e=current eval. score, */
136/* E=e.p. sqr.z=prev.dest,  n=depth; return score */
137short D(short q, short l, short e, unsigned char E,  unsigned char z, unsigned char n) {
138  short m, v, i, P, V, s;
139  unsigned char  t, p, u, x, y, X, Y, H, B, j, d, h, F, G, C;
140  signed char r;
141  if (++Z >  30) {                                   /* stack underrun check */
142    --Z; return  e;
143  }
144  q--;                                          /* adj. window: delay  bonus */
145  k ^= 24;                                      /* change sides             */
146  d = Y = 0;                                    /* start iter. from scratch */
147  X = myrand() & ~M;                            /* start at random field    */
148  W(d++ < n || d < 3 ||                         /* iterative deepening loop */
149    z & K == I && (N < T & d < 98 ||            /* root: deepen upto time   */
150                   (K = X, L = Y & ~M, d = 3)))                /* time's up: go  do best    */
151  { x = B = X;                                   /* start scan  at prev. best */
152    h = Y & S;                                   /* request  try noncastl. 1st*/
153    P = d < 3 ? I : D(-l, 1 - l, -e, S, 0, d - 3); /* Search  null move         */
154    m = -P < l | R > 35 ? d > 2 ? -I : e : -P;   /* Prune  or stand-pat       */
155    ++N;                                         /* node  count (for timing)  */
156    do {
157      u = b[x];                                   /*  scan board looking for   */
158      if (u & k) {                                /*  own piece (inefficient!)*/
159        r = p = u & 7;                             /*  p = piece type (set r>0) */
160        j = o[p + 16];                             /*  first step vector f.piece*/
161        W(r = p > 2 & r < 0 ? -r : -o[++j])        /*  loop over directions o[] */
162        { A:                                        /*  resume normal after best */
163          y = x; F = G = S;                         /*  (x,y)=move, (F,G)=castl.R*/
164          do {                                      /*  y traverses ray, or:     */
165            H = y = h ? Y ^ h : y + r;               /*  sneak in prev. best move */
166            if (y & M)break;                         /*  board edge hit           */
167            m = E - S & b[E] && y - E < 2 & E - y  < 2 ? I : m; /* bad castling             */
168            if (p < 3 & y == E)H  ^= 16;              /* shift capt.sqr. H if e.p.*/
169            t = b[H]; if (t  & k | p < 3 & !(y - x & 7) - !t)break; /* capt. own, bad pawn mode */
170            i  = 37 * w[t & 7] + (t & 192);           /* value of capt. piece t   */
171            m  = i < 0 ? I : m;                       /* K capture                */
172            if  (m >= l & d > 1)goto C;               /* abort on fail high       */
173            v  = d - 1 ? e : i - p;                   /* MVV/LVA scoring          */
174            if  (d - !t > 1)                          /* remaining depth          */
175            {  v = p < 6 ? b[x + 8] - b[y + 8] : 0;    /* center positional pts.   */
176              b[G]  = b[H] = b[x] = 0; b[y] = u | 32;  /* do move, set non-virgin  */
177              if  (!(G & M))b[F] = k + 6, v += 50;     /* castling: put R & score  */
178              v  -= p - 4 | R > 29 ? 0 : 20;           /* penalize mid-game K move */
179              if  (p < 3)                              /* pawns:                   */
180              {  v -= 9 * ((x - 2 & M || b[x - 2] - u) + /* structure, undefended    */
181                          (x  + 2 & M || b[x + 2] - u) - 1  /*        squares plus bias */
182                          +  (b[x ^ 16] == k + 36))          /* kling to non-virgin King */
183                     -  (R >> 2);                       /* end-game Pawn-push bonus */
184                V  = y + r + 1 & S ? 647 - p : 2 * (u & y + 16 & 32); /* promotion or 6/7th bonus */
185                b[y] += V; i += V;                     /* change piece, add score  */
186              }
187              v += e + i; V = m > q ? m : q;          /*  new eval and alpha       */
188              C = d - 1 - (d > 5 & p > 2 & !t & !h);
189              C = R > 29 | d < 3 | P - I ? C : d;     /* extend 1 ply if in check  */
190              do
191                s = C > 2 | v > V ? -D(-l, -V, -v,     /*  recursive eval. of reply */
192                                       F, 0, C) :  v;    /* or fail low if futile    */
193              W(s > q&++C < d); v = s;
194              if (z && K - I && v + I && x == K & y == L) /* move pending & in root:  */
195              { Q = -e - i; O = F;                     /*   exit if legal  & found  */
196                R += i >> 7; --Z; return l;            /* captured  non-P material  */
197              }
198              b[G] = k + 6; b[F] = b[y]  = 0; b[x] = u; b[H] = t; /* undo move,G can be dummy */
199            }
200            if  (v > m)                               /* new best, update max,best*/
201              m  = v, X = x, Y = y | S & F;            /* mark double move with S  */
202            if  (h) {
203              h = 0;  /* redo after doing old best*/
204              goto  A;
205            }
206            if (x + r - y | u & 32 |                 /* not  1st step,moved before*/
207                p > 2 & (p - 4 | j - 7 ||             /*  no P & no lateral K move,*/
208                         b[G = x + 3 ^ r >> 1 & 7]  - k - 6     /* no virgin R in corner G, */
209                         || b[G ^  1] | b[G ^ 2])               /* no 2 empty sq. next to R */
210               )t  += p < 5;                           /* fake capt. for nonsliding*/
211            else  F = y;                              /* enable e.p.              */
212          }  W(!t);                                  /* if not capt. continue ray*/
213        }
214      }
215    } W((x = x + 9 & ~M) - B);                 /* next sqr. of board,  wrap */
216C: if (m > I - M | m < M - I)d = 98;           /* mate holds to any depth  */
217    m = m + I | P == I ? m : 0;                  /* best loses K: (stale)mate*/
218    if (z && d > 2)
219    { *c = 'a' + (X & 7); c[1] = '8' - (X >> 4); c[2] = 'a'  + (Y & 7); c[3] = '8' - (Y >> 4 & 7); c[4] = 0;
220      char buff[150];
221    }
222  }                                             /*    encoded in X S,8 bits */
223  k ^= 24;                                      /* change sides back        */
224  --Z; return m += m < e;                       /* delayed-loss bonus       */
225}
226void  gameOver() {
227  for (;;);
228}
229void bkp() {
230  for (int i = 0; i < 16 * 8  + 1; i++) {
231    bk[i] = b[i];
232  }
233}
234void serialBoard(){
235  Serial.println("  +-----------------+");
236  for(int i=0; i<8; i++){
237        Serial.print('  ');
238        Serial.print(8-i);
239        Serial.print("| ");
240        for(int  j=0; j<8; j++){
241            char c = sym[b[16*i+j]&15];
242            Serial.print(c);
243            Serial.print(' ');
244        }
245        Serial.println('|');
246  }
247  Serial.println("  +-----------------+");
248  Serial.println("   a b  c d e f g h");
249}