board.c (16623B)
1 /* board.c - tablero, generacion de jugadas, jugar/deshacer, FEN. 2 * 3 * Tablero de 64 casillas (a1 = 0) con un "mailbox" de 10x12 para no salirse 4 * del tablero al generar: MB64 lleva de casilla a indice 120 y MB120 vuelve 5 * (-1 = afuera). Arriba (hacia la fila 8) es +10. */ 6 #include <string.h> 7 #include "chess.h" 8 9 static const int8_t MB120[120] = { 10 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 11 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 12 -1, 0, 1, 2, 3, 4, 5, 6, 7, -1, 13 -1, 8, 9, 10, 11, 12, 13, 14, 15, -1, 14 -1, 16, 17, 18, 19, 20, 21, 22, 23, -1, 15 -1, 24, 25, 26, 27, 28, 29, 30, 31, -1, 16 -1, 32, 33, 34, 35, 36, 37, 38, 39, -1, 17 -1, 40, 41, 42, 43, 44, 45, 46, 47, -1, 18 -1, 48, 49, 50, 51, 52, 53, 54, 55, -1, 19 -1, 56, 57, 58, 59, 60, 61, 62, 63, -1, 20 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 21 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 22 }; 23 static const int8_t MB64[64] = { 24 21, 22, 23, 24, 25, 26, 27, 28, 25 31, 32, 33, 34, 35, 36, 37, 38, 26 41, 42, 43, 44, 45, 46, 47, 48, 27 51, 52, 53, 54, 55, 56, 57, 58, 28 61, 62, 63, 64, 65, 66, 67, 68, 29 71, 72, 73, 74, 75, 76, 77, 78, 30 81, 82, 83, 84, 85, 86, 87, 88, 31 91, 92, 93, 94, 95, 96, 97, 98 32 }; 33 34 static const int8_t OFF_N[8] = { -21, -19, -12, -8, 8, 12, 19, 21 }; 35 static const int8_t OFF_K[8] = { -11, -10, -9, -1, 1, 9, 10, 11 }; 36 static const int8_t OFF_B[4] = { -11, -9, 9, 11 }; 37 static const int8_t OFF_R[4] = { -10, -1, 1, 10 }; 38 39 /* derechos de enroque que sobreviven a mover desde/hacia cada casilla */ 40 static uint8_t castle_mask[64]; 41 42 static uint64_t Z_piece[16][64], Z_castle[16], Z_ep[8], Z_side; 43 static bool ready; 44 45 void chess_init(void) 46 { 47 if (ready) return; 48 Rng r; 49 rng_seed(&r, 0x43484553534a5545ULL, 7); 50 for (int p = 0; p < 16; p++) 51 for (int s = 0; s < 64; s++) Z_piece[p][s] = ((uint64_t)rng_next(&r) << 32) | rng_next(&r); 52 for (int i = 0; i < 16; i++) Z_castle[i] = ((uint64_t)rng_next(&r) << 32) | rng_next(&r); 53 for (int i = 0; i < 8; i++) Z_ep[i] = ((uint64_t)rng_next(&r) << 32) | rng_next(&r); 54 Z_side = ((uint64_t)rng_next(&r) << 32) | rng_next(&r); 55 Z_castle[0] = 0; 56 for (int s = 0; s < 64; s++) castle_mask[s] = 15; 57 castle_mask[SQ(0, 0)] &= (uint8_t)~CASTLE_WQ; 58 castle_mask[SQ(7, 0)] &= (uint8_t)~CASTLE_WK; 59 castle_mask[SQ(4, 0)] &= (uint8_t)~(CASTLE_WK | CASTLE_WQ); 60 castle_mask[SQ(0, 7)] &= (uint8_t)~CASTLE_BQ; 61 castle_mask[SQ(7, 7)] &= (uint8_t)~CASTLE_BK; 62 castle_mask[SQ(4, 7)] &= (uint8_t)~(CASTLE_BK | CASTLE_BQ); 63 ready = true; 64 } 65 66 /* ------------------------------------------------------------------ hash */ 67 68 /* La casilla de al paso solo entra al hash si el que mueve tiene un peon al 69 * lado para capturar: asi dos posiciones iguales "de hecho" repiten. */ 70 static bool ep_capturable(const Pos *p) 71 { 72 if (p->ep < 0) return false; 73 int s = p->side, dir = s == WHITE ? -8 : 8; 74 int from = p->ep + dir, f = FILE_OF(p->ep); 75 uint8_t pawn = PIECE(s, PAWN); 76 return (f > 0 && p->sq[from - 1] == pawn) || (f < 7 && p->sq[from + 1] == pawn); 77 } 78 79 static uint64_t ep_key(const Pos *p) { return ep_capturable(p) ? Z_ep[FILE_OF(p->ep)] : 0; } 80 81 uint64_t pos_hash(const Pos *p) 82 { 83 uint64_t h = 0; 84 for (int s = 0; s < 64; s++) if (p->sq[s]) h ^= Z_piece[p->sq[s]][s]; 85 h ^= Z_castle[p->castle]; 86 h ^= ep_key(p); 87 if (p->side == BLACK) h ^= Z_side; 88 return h; 89 } 90 91 /* ------------------------------------------------------------------ ataques */ 92 93 bool pos_attacked(const Pos *p, int sq, int by) 94 { 95 int m = MB64[sq]; 96 if (by == WHITE) { 97 int a = MB120[m - 9], b = MB120[m - 11]; 98 if ((a >= 0 && p->sq[a] == PIECE(WHITE, PAWN)) || (b >= 0 && p->sq[b] == PIECE(WHITE, PAWN))) return true; 99 } else { 100 int a = MB120[m + 9], b = MB120[m + 11]; 101 if ((a >= 0 && p->sq[a] == PIECE(BLACK, PAWN)) || (b >= 0 && p->sq[b] == PIECE(BLACK, PAWN))) return true; 102 } 103 for (int i = 0; i < 8; i++) { 104 int t = MB120[m + OFF_N[i]]; 105 if (t >= 0 && p->sq[t] == PIECE(by, KNIGHT)) return true; 106 t = MB120[m + OFF_K[i]]; 107 if (t >= 0 && p->sq[t] == PIECE(by, KING)) return true; 108 } 109 for (int i = 0; i < 4; i++) { 110 for (int x = m + OFF_B[i];; x += OFF_B[i]) { 111 int t = MB120[x]; 112 if (t < 0) break; 113 uint8_t q = p->sq[t]; 114 if (!q) continue; 115 if (q == PIECE(by, BISHOP) || q == PIECE(by, QUEEN)) return true; 116 break; 117 } 118 for (int x = m + OFF_R[i];; x += OFF_R[i]) { 119 int t = MB120[x]; 120 if (t < 0) break; 121 uint8_t q = p->sq[t]; 122 if (!q) continue; 123 if (q == PIECE(by, ROOK) || q == PIECE(by, QUEEN)) return true; 124 break; 125 } 126 } 127 return false; 128 } 129 130 bool pos_in_check(const Pos *p) { return pos_attacked(p, p->king[p->side], p->side ^ 1); } 131 132 /* ------------------------------------------------------------------ generacion */ 133 134 typedef struct { Move *m; int n; } Out; 135 136 static void add(Out *l, int from, int to, int flag) { l->m[l->n++] = MOVE(from, to, flag); } 137 138 static void add_promos(Out *l, int from, int to, bool cap) 139 { 140 for (int k = 3; k >= 0; k--) add(l, from, to, MF_PROMO + k + (cap ? 4 : 0)); 141 } 142 143 /* genera en out (hasta MAX_MOVES) y devuelve cuantas */ 144 int pos_gen(const Pos *p, Move *out, bool captures_only) 145 { 146 Out o = { out, 0 }, *l = &o; 147 int s = p->side, them = s ^ 1; 148 int up = s == WHITE ? 8 : -8; 149 int start_rank = s == WHITE ? 1 : 6, promo_rank = s == WHITE ? 6 : 1; 150 for (int sq = 0; sq < 64; sq++) { 151 uint8_t pc = p->sq[sq]; 152 if (!pc || PCOLOR(pc) != s) continue; 153 int t = PTYPE(pc), m = MB64[sq]; 154 if (t == PAWN) { 155 int to = sq + up, r = RANK_OF(sq); 156 if (!p->sq[to]) { 157 if (r == promo_rank) add_promos(l, sq, to, false); 158 else if (!captures_only) { 159 add(l, sq, to, MF_QUIET); 160 if (r == start_rank && !p->sq[to + up]) add(l, sq, to + up, MF_DOUBLE); 161 } 162 } 163 for (int df = -1; df <= 1; df += 2) { 164 int f = FILE_OF(sq) + df; 165 if (f < 0 || f > 7) continue; 166 int c = to + df; 167 if (p->sq[c] && PCOLOR(p->sq[c]) == them) { 168 if (r == promo_rank) add_promos(l, sq, c, true); 169 else add(l, sq, c, MF_CAPTURE); 170 } else if (c == p->ep) add(l, sq, c, MF_EP); 171 } 172 continue; 173 } 174 const int8_t *off; 175 int noff; 176 bool slide; 177 switch (t) { 178 case KNIGHT: off = OFF_N; noff = 8; slide = false; break; 179 case BISHOP: off = OFF_B; noff = 4; slide = true; break; 180 case ROOK: off = OFF_R; noff = 4; slide = true; break; 181 case QUEEN: off = OFF_K; noff = 8; slide = true; break; 182 default: off = OFF_K; noff = 8; slide = false; break; 183 } 184 for (int i = 0; i < noff; i++) 185 for (int x = m + off[i];; x += off[i]) { 186 int to = MB120[x]; 187 if (to < 0) break; 188 uint8_t q = p->sq[to]; 189 if (q) { 190 if (PCOLOR(q) == them) add(l, sq, to, MF_CAPTURE); 191 break; 192 } 193 if (!captures_only) add(l, sq, to, MF_QUIET); 194 if (!slide) break; 195 } 196 if (t == KING && !captures_only) { 197 int home = s == WHITE ? 4 : 60; 198 if (sq != home || pos_attacked(p, home, them)) continue; 199 int kf = s == WHITE ? CASTLE_WK : CASTLE_BK, qf = s == WHITE ? CASTLE_WQ : CASTLE_BQ; 200 if ((p->castle & kf) && !p->sq[home + 1] && !p->sq[home + 2] && p->sq[home + 3] == PIECE(s, ROOK) && 201 !pos_attacked(p, home + 1, them) && !pos_attacked(p, home + 2, them)) 202 add(l, home, home + 2, MF_OO); 203 if ((p->castle & qf) && !p->sq[home - 1] && !p->sq[home - 2] && !p->sq[home - 3] && 204 p->sq[home - 4] == PIECE(s, ROOK) && !pos_attacked(p, home - 1, them) && !pos_attacked(p, home - 2, them)) 205 add(l, home, home - 2, MF_OOO); 206 } 207 } 208 return o.n; 209 } 210 211 void pos_moves(const Pos *p, MoveList *l) { l->n = pos_gen(p, l->m, false); } 212 void pos_captures(const Pos *p, MoveList *l) { l->n = pos_gen(p, l->m, true); } 213 214 /* ------------------------------------------------------------------ jugar */ 215 216 static void put(Pos *p, int sq, uint8_t pc) { p->sq[sq] = pc; p->hash ^= Z_piece[pc][sq]; } 217 static void take(Pos *p, int sq) { p->hash ^= Z_piece[p->sq[sq]][sq]; p->sq[sq] = EMPTY; } 218 219 void pos_make(Pos *p, Move m, Undo *u) 220 { 221 int from = MFROM(m), to = MTO(m), fl = MFLAG(m), s = p->side; 222 uint8_t pc = p->sq[from]; 223 u->castle = p->castle; 224 u->ep = p->ep; 225 u->half = p->halfmove; 226 u->hash = p->hash; 227 p->hash ^= ep_key(p) ^ Z_castle[p->castle]; 228 uint8_t cap = EMPTY; 229 if (fl == MF_EP) { 230 int cs = to + (s == WHITE ? -8 : 8); 231 cap = p->sq[cs]; 232 take(p, cs); 233 } else if (p->sq[to]) { 234 cap = p->sq[to]; 235 take(p, to); 236 } 237 u->cap = cap; 238 take(p, from); 239 put(p, to, fl >= MF_PROMO ? PIECE(s, MPROMO(m)) : pc); 240 if (fl == MF_OO) { take(p, to + 1); put(p, to - 1, PIECE(s, ROOK)); } 241 else if (fl == MF_OOO) { take(p, to - 2); put(p, to + 1, PIECE(s, ROOK)); } 242 if (PTYPE(pc) == KING) p->king[s] = (uint8_t)to; 243 p->castle &= castle_mask[from] & castle_mask[to]; 244 p->ep = fl == MF_DOUBLE ? (int8_t)((from + to) / 2) : -1; 245 p->halfmove = (PTYPE(pc) == PAWN || cap) ? 0 : (uint16_t)(p->halfmove + 1); 246 if (s == BLACK) p->fullmove++; 247 p->side ^= 1; 248 p->hash ^= Z_side ^ Z_castle[p->castle] ^ ep_key(p); 249 } 250 251 void pos_unmake(Pos *p, Move m, const Undo *u) 252 { 253 int from = MFROM(m), to = MTO(m), fl = MFLAG(m); 254 p->side ^= 1; 255 int s = p->side; 256 if (s == BLACK) p->fullmove--; 257 uint8_t pc = fl >= MF_PROMO ? PIECE(s, PAWN) : p->sq[to]; 258 p->sq[from] = pc; 259 p->sq[to] = EMPTY; 260 if (fl == MF_EP) p->sq[to + (s == WHITE ? -8 : 8)] = u->cap; 261 else p->sq[to] = u->cap; 262 if (fl == MF_OO) { p->sq[to + 1] = PIECE(s, ROOK); p->sq[to - 1] = EMPTY; } 263 else if (fl == MF_OOO) { p->sq[to - 2] = PIECE(s, ROOK); p->sq[to + 1] = EMPTY; } 264 if (PTYPE(pc) == KING) p->king[s] = (uint8_t)from; 265 p->castle = u->castle; 266 p->ep = u->ep; 267 p->halfmove = u->half; 268 p->hash = u->hash; 269 } 270 271 void pos_null(Pos *p, Undo *u) 272 { 273 u->ep = p->ep; 274 u->hash = p->hash; 275 u->half = p->halfmove; 276 p->hash ^= ep_key(p); 277 p->ep = -1; 278 p->side ^= 1; 279 p->hash ^= Z_side; 280 p->halfmove++; 281 } 282 283 void pos_unnull(Pos *p, const Undo *u) 284 { 285 p->side ^= 1; 286 p->ep = u->ep; 287 p->hash = u->hash; 288 p->halfmove = u->half; 289 } 290 291 void pos_legal(const Pos *p, MoveList *l) 292 { 293 MoveList all; 294 pos_moves(p, &all); 295 Pos q = *p; 296 l->n = 0; 297 for (int i = 0; i < all.n; i++) { 298 Undo u; 299 pos_make(&q, all.m[i], &u); 300 if (!pos_attacked(&q, q.king[p->side], q.side)) l->m[l->n++] = all.m[i]; 301 pos_unmake(&q, all.m[i], &u); 302 } 303 } 304 305 bool pos_is_legal(const Pos *p, Move m) 306 { 307 MoveList l; 308 pos_legal(p, &l); 309 for (int i = 0; i < l.n; i++) if (l.m[i] == m) return true; 310 return false; 311 } 312 313 uint64_t perft(Pos *p, int depth) 314 { 315 MoveList l; 316 pos_moves(p, &l); 317 uint64_t n = 0; 318 int s = p->side; 319 for (int i = 0; i < l.n; i++) { 320 Undo u; 321 pos_make(p, l.m[i], &u); 322 if (!pos_attacked(p, p->king[s], s ^ 1)) n += depth <= 1 ? 1 : perft(p, depth - 1); 323 pos_unmake(p, l.m[i], &u); 324 } 325 return n; 326 } 327 328 /* ------------------------------------------------------------------ material */ 329 330 bool pos_insufficient(const Pos *p) 331 { 332 int minors = 0, knights = 0, bishop_colors = 0; 333 for (int s = 0; s < 64; s++) { 334 int t = PTYPE(p->sq[s]); 335 if (t == PAWN || t == ROOK || t == QUEEN) return false; 336 if (t == KNIGHT) { knights++; minors++; } 337 if (t == BISHOP) { minors++; bishop_colors |= 1 << ((FILE_OF(s) + RANK_OF(s)) & 1); } 338 } 339 if (minors <= 1) return true; /* K vs K, K+menor vs K */ 340 return knights == 0 && bishop_colors != 3; /* solo alfiles, todos del mismo color */ 341 } 342 343 /* ------------------------------------------------------------------ FEN */ 344 345 static const char PCH[] = " PNBRQK pnbrqk"; 346 347 void pos_start(Pos *p) 348 { 349 pos_from_fen(p, "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1"); 350 } 351 352 static const char *skip_sp(const char *s) { while (*s == ' ' || *s == '\t') s++; return s; } 353 354 bool pos_from_fen(Pos *out, const char *fen) 355 { 356 chess_init(); 357 Pos p; 358 memset(&p, 0, sizeof p); 359 const char *s = skip_sp(fen); 360 int rank = 7, file = 0, kings[2] = { 0, 0 }; 361 for (; *s && *s != ' '; s++) { 362 if (*s == '/') { 363 if (file != 8 || rank == 0) return false; 364 rank--; 365 file = 0; 366 } else if (*s >= '1' && *s <= '8') { 367 file += *s - '0'; 368 if (file > 8) return false; 369 } else { 370 const char *q = strchr(PCH, *s); 371 if (!q || *s == ' ' || file > 7) return false; 372 int pc = (int)(q - PCH); 373 if (PTYPE(pc) == PAWN && (rank == 0 || rank == 7)) return false; 374 if (PTYPE(pc) == KING) { kings[PCOLOR(pc)]++; p.king[PCOLOR(pc)] = (uint8_t)SQ(file, rank); } 375 p.sq[SQ(file, rank)] = (uint8_t)pc; 376 file++; 377 } 378 } 379 if (rank != 0 || file != 8 || kings[0] != 1 || kings[1] != 1) return false; 380 s = skip_sp(s); 381 if (*s == 'w') p.side = WHITE; 382 else if (*s == 'b') p.side = BLACK; 383 else return false; 384 s = skip_sp(s + 1); 385 p.ep = -1; 386 p.fullmove = 1; 387 if (*s) { 388 if (*s == '-') s++; 389 else 390 for (; *s && *s != ' '; s++) { 391 const char *q = strchr("KQkq", *s); 392 if (!q) return false; 393 p.castle |= (uint8_t)(1 << (q - "KQkq")); 394 } 395 s = skip_sp(s); 396 } 397 if (*s) { 398 if (*s == '-') s++; 399 else { 400 if (s[0] < 'a' || s[0] > 'h' || (s[1] != '3' && s[1] != '6')) return false; 401 int e = SQ(s[0] - 'a', s[1] - '1'); 402 if ((p.side == WHITE) != (s[1] == '6')) return false; 403 int pawn_sq = e + (p.side == WHITE ? -8 : 8); 404 if (p.sq[pawn_sq] == PIECE(p.side ^ 1, PAWN) && !p.sq[e]) p.ep = (int8_t)e; 405 s += 2; 406 } 407 s = skip_sp(s); 408 } 409 long v; 410 const char *q; 411 if (*s && (q = str_scan_int(s, &v))) { if (v < 0 || v > 9999) return false; p.halfmove = (uint16_t)v; s = skip_sp(q); } 412 if (*s && (q = str_scan_int(s, &v))) { if (v < 1 || v > 9999) return false; p.fullmove = (uint16_t)v; } 413 /* enroques que no corresponden con el tablero: se descartan */ 414 if (p.sq[4] != PIECE(WHITE, KING)) p.castle &= (uint8_t)~(CASTLE_WK | CASTLE_WQ); 415 if (p.sq[60] != PIECE(BLACK, KING)) p.castle &= (uint8_t)~(CASTLE_BK | CASTLE_BQ); 416 if (p.sq[7] != PIECE(WHITE, ROOK)) p.castle &= (uint8_t)~CASTLE_WK; 417 if (p.sq[0] != PIECE(WHITE, ROOK)) p.castle &= (uint8_t)~CASTLE_WQ; 418 if (p.sq[63] != PIECE(BLACK, ROOK)) p.castle &= (uint8_t)~CASTLE_BK; 419 if (p.sq[56] != PIECE(BLACK, ROOK)) p.castle &= (uint8_t)~CASTLE_BQ; 420 /* el que no mueve no puede estar en jaque */ 421 if (pos_attacked(&p, p.king[p.side ^ 1], p.side)) return false; 422 p.hash = pos_hash(&p); 423 *out = p; 424 return true; 425 } 426 427 int pos_fen(const Pos *p, char *buf, int n) 428 { 429 char t[100]; 430 int k = 0; 431 for (int r = 7; r >= 0; r--) { 432 int empty = 0; 433 for (int f = 0; f < 8; f++) { 434 uint8_t pc = p->sq[SQ(f, r)]; 435 if (!pc) { empty++; continue; } 436 if (empty) { t[k++] = (char)('0' + empty); empty = 0; } 437 t[k++] = PCH[pc]; 438 } 439 if (empty) t[k++] = (char)('0' + empty); 440 if (r) t[k++] = '/'; 441 } 442 t[k++] = ' '; 443 t[k++] = p->side == WHITE ? 'w' : 'b'; 444 t[k++] = ' '; 445 if (!p->castle) t[k++] = '-'; 446 for (int i = 0; i < 4; i++) if (p->castle & (1 << i)) t[k++] = "KQkq"[i]; 447 t[k++] = ' '; 448 if (p->ep >= 0) { t[k++] = (char)('a' + FILE_OF(p->ep)); t[k++] = (char)('1' + RANK_OF(p->ep)); } 449 else t[k++] = '-'; 450 t[k++] = ' '; 451 t[k] = 0; 452 k = str_int(t, sizeof t, k, p->halfmove); 453 k = str_put(t, sizeof t, k, " "); 454 k = str_int(t, sizeof t, k, p->fullmove); 455 return str_put(buf, n, 0, t); 456 }