engine.c (14678B)
1 /* engine.c - motor: alfa-beta (PVS) con profundizacion iterativa, quietud, 2 * tabla de transposicion, killers/historia, movida nula y LMR. 3 * 4 * Sin malloc: la tabla de transposicion la pasa el que llama (grande en Linux, 5 * chica en la Pico) y el resto del estado es estatico. */ 6 #include <string.h> 7 #include "chess.h" 8 9 enum { TT_EXACT = 1, TT_LOWER, TT_UPPER }; 10 #define INF 32000 11 #define MAX_SPLY 64 12 13 static const int PVAL[7] = { 0, 100, 320, 330, 500, 900, 20000 }; 14 15 /* Pila de jugadas compartida por todos los nodos (sin listas en el stack: la 16 * Pico tiene poco). Si no alcanza, el nodo se trata como hoja. */ 17 #ifndef ENGINE_ARENA 18 #define ENGINE_ARENA 4096 19 #endif 20 21 typedef struct { 22 Engine *e; 23 Pos pos; 24 uint64_t keys[MAX_PLY + MAX_SPLY + 2]; /* hashes de la partida + los de la busqueda */ 25 int nkeys; 26 uint32_t nodes, max_nodes, deadline; 27 bool stop, timed; 28 Move killers[MAX_SPLY][2]; 29 int16_t hist[2][64][64]; 30 Move am[ENGINE_ARENA]; 31 int16_t as[ENGINE_ARENA]; 32 int top; 33 } Search; 34 35 static Search S; /* estado de la busqueda (estatico: la Pico no tiene heap) */ 36 37 void engine_init(Engine *e, TTEntry *tt, uint32_t tt_size, uint32_t (*now_ms)(void)) 38 { 39 chess_init(); 40 memset(e, 0, sizeof *e); 41 e->tt = tt; 42 e->tt_size = tt_size; 43 e->now_ms = now_ms; 44 rng_seed(&e->rng, now_ms ? now_ms() : 1, 0x5eed); 45 engine_clear(e); 46 } 47 48 void engine_clear(Engine *e) 49 { 50 if (e->tt) memset(e->tt, 0, sizeof(TTEntry) * e->tt_size); 51 } 52 53 /* ------------------------------------------------------------------ tabla */ 54 55 static TTEntry *tt_probe(uint64_t key) 56 { 57 if (!S.e->tt) return 0; 58 TTEntry *t = &S.e->tt[key & (S.e->tt_size - 1)]; 59 return t->key == key ? t : 0; 60 } 61 62 static void tt_store(uint64_t key, int depth, int score, int flag, Move m, int ply) 63 { 64 if (!S.e->tt) return; 65 TTEntry *t = &S.e->tt[key & (S.e->tt_size - 1)]; 66 if (t->key == key && t->depth > depth && flag != TT_EXACT) return; 67 /* los mates se guardan relativos a este nodo */ 68 if (score > MATE - 500) score += ply; 69 else if (score < -MATE + 500) score -= ply; 70 if (!m && t->key == key) m = t->move; 71 t->key = key; 72 t->move = m; 73 t->score = (int16_t)score; 74 t->depth = (int8_t)depth; 75 t->flag = (uint8_t)flag; 76 } 77 78 static int tt_score(int s, int ply) 79 { 80 if (s > MATE - 500) return s - ply; 81 if (s < -MATE + 500) return s + ply; 82 return s; 83 } 84 85 /* ------------------------------------------------------------------ utilidades */ 86 87 static bool time_up(void) 88 { 89 if ((S.nodes & 1023) == 0) { 90 if (S.timed && S.e->now_ms && (int32_t)(S.e->now_ms() - S.deadline) >= 0) S.stop = true; 91 if (S.e->poll && S.e->poll(S.e->ctx)) S.stop = true; 92 } 93 if (S.max_nodes && S.nodes >= S.max_nodes) S.stop = true; 94 return S.stop; 95 } 96 97 static bool is_repetition(void) 98 { 99 int n = S.nkeys - 1; 100 uint64_t k = S.keys[n]; 101 int lim = n - S.pos.halfmove; 102 if (lim < 0) lim = 0; 103 for (int i = n - 2; i >= lim; i -= 2) 104 if (S.keys[i] == k) return true; 105 return false; 106 } 107 108 static bool has_pieces(const Pos *p, int c) 109 { 110 for (int s = 0; s < 64; s++) { 111 uint8_t pc = p->sq[s]; 112 if (pc && PCOLOR(pc) == c && PTYPE(pc) != PAWN && PTYPE(pc) != KING) return true; 113 } 114 return false; 115 } 116 117 static void make(Move m, Undo *u) 118 { 119 pos_make(&S.pos, m, u); 120 S.keys[S.nkeys++] = S.pos.hash; 121 } 122 123 static void unmake(Move m, const Undo *u) 124 { 125 S.nkeys--; 126 pos_unmake(&S.pos, m, u); 127 } 128 129 /* puntaje para ordenar: jugada de la tabla, capturas (MVV-LVA), killers, historia */ 130 static void score_moves(int base, int n, Move ttm, int ply) 131 { 132 for (int i = base; i < base + n; i++) { 133 Move m = S.am[i]; 134 int v; 135 if (m == ttm) v = 32000; 136 else if (MIS_CAPTURE(m) || MIS_PROMO(m)) { 137 int victim = MFLAG(m) == MF_EP ? PAWN : PTYPE(S.pos.sq[MTO(m)]); 138 int attacker = PTYPE(S.pos.sq[MFROM(m)]); 139 v = 20000 + PVAL[victim] * 10 - PVAL[attacker] / 10 + (MIS_PROMO(m) ? PVAL[MPROMO(m)] : 0); 140 } else if (ply < MAX_SPLY && m == S.killers[ply][0]) v = 19000; 141 else if (ply < MAX_SPLY && m == S.killers[ply][1]) v = 18900; 142 else v = S.hist[S.pos.side][MFROM(m)][MTO(m)]; 143 S.as[i] = (int16_t)v; 144 } 145 } 146 147 static Move pick(int i, int end) 148 { 149 int best = i; 150 for (int j = i + 1; j < end; j++) if (S.as[j] > S.as[best]) best = j; 151 Move m = S.am[best]; 152 int16_t sc = S.as[best]; 153 S.am[best] = S.am[i]; S.as[best] = S.as[i]; 154 S.am[i] = m; S.as[i] = sc; 155 return m; 156 } 157 158 /* reserva lugar en la pila y genera; -1 si no hay lugar */ 159 static int gen_moves(bool captures, int *n) 160 { 161 if (S.top + MAX_MOVES > ENGINE_ARENA) return -1; 162 int base = S.top; 163 *n = pos_gen(&S.pos, S.am + base, captures); 164 S.top += *n; 165 return base; 166 } 167 168 /* ------------------------------------------------------------------ busqueda */ 169 170 static int qsearch(int alpha, int beta, int ply) 171 { 172 S.nodes++; 173 if (time_up()) return 0; 174 int stand = evaluate(&S.pos); 175 if (ply >= MAX_SPLY - 1) return stand; 176 if (stand >= beta) return stand; 177 if (stand > alpha) alpha = stand; 178 int n, base = gen_moves(true, &n); 179 if (base < 0) return stand; 180 score_moves(base, n, MOVE_NONE, MAX_SPLY); 181 int side = S.pos.side, end = base + n; 182 for (int i = base; i < end; i++) { 183 Move m = pick(i, end); 184 /* poda delta: ni ganando la pieza llega a alpha */ 185 if (!MIS_PROMO(m)) { 186 int victim = MFLAG(m) == MF_EP ? PAWN : PTYPE(S.pos.sq[MTO(m)]); 187 if (stand + PVAL[victim] + 200 < alpha) continue; 188 } 189 Undo u; 190 make(m, &u); 191 if (pos_attacked(&S.pos, S.pos.king[side], side ^ 1)) { unmake(m, &u); continue; } 192 int v = -qsearch(-beta, -alpha, ply + 1); 193 unmake(m, &u); 194 if (S.stop) { alpha = 0; break; } 195 if (v > alpha) { 196 alpha = v; 197 if (v >= beta) break; 198 } 199 } 200 S.top = base; 201 return alpha; 202 } 203 204 static int search(int depth, int alpha, int beta, int ply, bool null_ok) 205 { 206 bool pv = beta - alpha > 1; 207 if (ply > 0) { 208 if (S.pos.halfmove >= 100 || is_repetition() || pos_insufficient(&S.pos)) return 0; 209 /* no puede ser mejor que dar mate ya */ 210 if (alpha < -MATE + ply) alpha = -MATE + ply; 211 if (beta > MATE - ply - 1) beta = MATE - ply - 1; 212 if (alpha >= beta) return alpha; 213 } 214 bool check = pos_in_check(&S.pos); 215 if (check) depth++; 216 if (depth <= 0 || ply >= MAX_SPLY - 1) return qsearch(alpha, beta, ply); 217 S.nodes++; 218 if (time_up()) return 0; 219 220 Move ttm = MOVE_NONE; 221 TTEntry *t = tt_probe(S.pos.hash); 222 if (t) { 223 ttm = t->move; 224 if (!pv && ply > 0 && t->depth >= depth) { 225 int s = tt_score(t->score, ply); 226 if (t->flag == TT_EXACT || (t->flag == TT_LOWER && s >= beta) || (t->flag == TT_UPPER && s <= alpha)) return s; 227 } 228 } 229 230 int side = S.pos.side; 231 /* movida nula: si pasando igual supero beta, esto no se va a jugar */ 232 if (null_ok && !pv && !check && depth >= 3 && has_pieces(&S.pos, side) && evaluate(&S.pos) >= beta) { 233 Undo u; 234 pos_null(&S.pos, &u); 235 S.keys[S.nkeys++] = S.pos.hash; 236 int r = depth > 6 ? 3 : 2; 237 int v = -search(depth - 1 - r, -beta, -beta + 1, ply + 1, false); 238 S.nkeys--; 239 pos_unnull(&S.pos, &u); 240 if (S.stop) return 0; 241 if (v >= beta) return v >= MATE - 500 ? beta : v; 242 } 243 244 int n, base = gen_moves(false, &n); 245 if (base < 0) return evaluate(&S.pos); 246 score_moves(base, n, ttm, ply); 247 int best = -INF, legal = 0, a0 = alpha, end = base + n; 248 Move bestm = MOVE_NONE; 249 for (int i = base; i < end; i++) { 250 Move m = pick(i, end); 251 Undo u; 252 make(m, &u); 253 if (pos_attacked(&S.pos, S.pos.king[side], side ^ 1)) { unmake(m, &u); continue; } 254 legal++; 255 bool quiet = !MIS_CAPTURE(m) && !MIS_PROMO(m); 256 int v; 257 if (legal == 1) v = -search(depth - 1, -beta, -alpha, ply + 1, true); 258 else { 259 /* LMR: las jugadas tranquilas del final de la lista se miran menos */ 260 int red = 0; 261 if (depth >= 3 && legal > 4 && quiet && !check && !pos_in_check(&S.pos)) red = legal > 12 ? 2 : 1; 262 v = -search(depth - 1 - red, -alpha - 1, -alpha, ply + 1, true); 263 if (v > alpha && red) v = -search(depth - 1, -alpha - 1, -alpha, ply + 1, true); 264 if (v > alpha && v < beta) v = -search(depth - 1, -beta, -alpha, ply + 1, true); 265 } 266 unmake(m, &u); 267 if (S.stop) { S.top = base; return 0; } 268 if (v > best) { 269 best = v; 270 bestm = m; 271 if (v > alpha) { 272 alpha = v; 273 if (v >= beta) { 274 if (quiet && ply < MAX_SPLY) { 275 if (S.killers[ply][0] != m) { S.killers[ply][1] = S.killers[ply][0]; S.killers[ply][0] = m; } 276 int16_t *h = &S.hist[side][MFROM(m)][MTO(m)]; 277 int nh = *h + depth * depth; 278 *h = (int16_t)(nh > 18000 ? 18000 : nh); 279 } 280 break; 281 } 282 } 283 } 284 } 285 S.top = base; 286 if (!legal) return check ? -MATE + ply : 0; 287 tt_store(S.pos.hash, depth, best, best >= beta ? TT_LOWER : best > a0 ? TT_EXACT : TT_UPPER, bestm, ply); 288 return best; 289 } 290 291 /* raiz: busca cada jugada y deja su puntaje (para elegir con ruido) */ 292 static int search_root(int depth, int alpha, int beta, MoveList *root, int *scores, bool full_window, Move *bestm) 293 { 294 int best = -INF, a0 = alpha; 295 *bestm = MOVE_NONE; 296 for (int i = 0; i < root->n; i++) { 297 Move m = root->m[i]; 298 Undo u; 299 make(m, &u); 300 int v; 301 if (full_window) v = -search(depth - 1, -INF, INF, 1, true); 302 else if (i == 0) v = -search(depth - 1, -beta, -alpha, 1, true); 303 else { 304 v = -search(depth - 1, -alpha - 1, -alpha, 1, true); 305 if (v > alpha && v < beta) v = -search(depth - 1, -beta, -alpha, 1, true); 306 } 307 unmake(m, &u); 308 if (S.stop) return best; 309 scores[i] = v; 310 if (v > best) { 311 best = v; 312 *bestm = m; 313 if (!full_window && v > alpha) alpha = v; 314 if (!full_window && v >= beta) break; 315 } 316 } 317 if (*bestm) tt_store(S.pos.hash, depth, best, best >= beta ? TT_LOWER : best > a0 ? TT_EXACT : TT_UPPER, *bestm, 0); 318 return best; 319 } 320 321 static void extract_pv(SearchResult *r) 322 { 323 Pos p = S.pos; 324 r->npv = 0; 325 Move m = r->best; 326 while (m && r->npv < 16) { 327 if (!pos_is_legal(&p, m)) break; 328 r->pv[r->npv++] = m; 329 Undo u; 330 pos_make(&p, m, &u); 331 TTEntry *t = tt_probe(p.hash); 332 m = t ? t->move : MOVE_NONE; 333 } 334 } 335 336 void engine_search(Engine *e, const Game *g, const SearchLimits *lim, SearchResult *r) 337 { 338 memset(r, 0, sizeof *r); 339 memset(&S.killers, 0, sizeof S.killers); 340 memset(&S.hist, 0, sizeof S.hist); 341 S.e = e; 342 S.pos = g->pos; 343 S.nkeys = 0; 344 for (int i = 0; i <= g->nply; i++) S.keys[S.nkeys++] = g->hist[i]; 345 S.nodes = 0; 346 S.top = 0; 347 S.max_nodes = lim->max_nodes; 348 S.stop = false; 349 uint32_t t0 = e->now_ms ? e->now_ms() : 0; 350 S.timed = lim->movetime > 0 && e->now_ms; 351 S.deadline = t0 + (uint32_t)lim->movetime; 352 353 MoveList root; 354 pos_legal(&S.pos, &root); 355 if (!root.n) return; 356 r->best = root.m[0]; 357 if (lim->use_book) { 358 Move b = book_move(g->mv, g->nply, &g->start, &e->rng); 359 if (b) { r->best = b; r->pv[0] = b; r->npv = 1; return; } 360 } 361 int scores[MAX_MOVES], done_scores[MAX_MOVES]; 362 bool noisy = lim->noise > 0; 363 int maxd = lim->max_depth > 0 ? lim->max_depth : MAX_SPLY - 2; 364 int prev = 0; 365 for (int d = 1; d <= maxd; d++) { 366 /* la mejor de la iteracion anterior va primero */ 367 for (int i = 0; i < root.n; i++) 368 if (root.m[i] == r->best) { Move t = root.m[0]; root.m[0] = root.m[i]; root.m[i] = t; break; } 369 for (int i = 0; i < root.n; i++) scores[i] = -INF; 370 Move bm; 371 int v; 372 if (noisy) v = search_root(d, -INF, INF, &root, scores, true, &bm); 373 else { 374 /* ventana de aspiracion alrededor del resultado anterior */ 375 int w = 40, a = d > 3 ? prev - w : -INF, b = d > 3 ? prev + w : INF; 376 for (;;) { 377 v = search_root(d, a, b, &root, scores, false, &bm); 378 if (S.stop) break; 379 if (v <= a) { a = a - w * 4 < -INF ? -INF : a - w * 4; w *= 4; continue; } 380 if (v >= b) { b = b + w * 4 > INF ? INF : b + w * 4; w *= 4; continue; } 381 break; 382 } 383 } 384 if (S.stop && d > 1) break; 385 if (!bm) break; 386 r->best = bm; 387 r->score = v; 388 r->depth = d; 389 prev = v; 390 memcpy(done_scores, scores, sizeof(int) * (size_t)root.n); 391 if (MATE_IN(v) && d >= 4) break; 392 if (S.timed) { 393 /* si ya se uso mas de la mitad del tiempo, la siguiente no termina */ 394 uint32_t used = e->now_ms() - t0; 395 if (used * 2 > (uint32_t)lim->movetime) break; 396 } 397 } 398 if (noisy && r->depth > 0) { 399 /* elige al azar entre las que estan a menos de `noise` de la mejor */ 400 int best = -INF; 401 for (int i = 0; i < root.n; i++) if (done_scores[i] > best) best = done_scores[i]; 402 /* con un mate a mano no se regala: solo las que lo mantienen */ 403 int margin = best > MATE - 500 ? 0 : lim->noise; 404 Move cand[MAX_MOVES]; 405 int nc = 0; 406 for (int i = 0; i < root.n; i++) 407 if (done_scores[i] > -INF && done_scores[i] >= best - margin) cand[nc++] = root.m[i]; 408 if (nc) { 409 r->best = cand[rng_below(&e->rng, (uint32_t)nc)]; 410 for (int i = 0; i < root.n; i++) if (root.m[i] == r->best) r->score = done_scores[i]; 411 } 412 } 413 r->nodes = S.nodes; 414 r->ms = e->now_ms ? e->now_ms() - t0 : 0; 415 extract_pv(r); 416 } 417 418 void level_limits(int level, SearchLimits *lim) 419 { 420 memset(lim, 0, sizeof *lim); 421 lim->use_book = true; 422 switch (level) { 423 case 0: lim->max_depth = 1; lim->noise = 150; lim->movetime = 300; break; 424 case 1: lim->max_depth = 2; lim->noise = 60; lim->movetime = 500; break; 425 case 2: lim->max_depth = 3; lim->noise = 40; lim->movetime = 600; break; 426 case 3: lim->max_depth = 4; lim->noise = 20; lim->movetime = 800; break; 427 default: lim->movetime = 1500; break; /* mas tiempo casi no suma (medido contra Stockfish) */ 428 } 429 }