Checkers Classic
engine.js13.2 KB
1// Checkers Classic engine — pure rules + AI. No DOM. English/American draughts.2// Board: 64 squares, index = row*8+col, dark squares are (row+col)%2===1.3// Pieces: 1 black man, 2 black king, -1 red man, -2 red king. Black starts at the top (rows 0-2) and moves first.4(function (root) {5 "use strict";6 const BLACK = 1, RED = -1;7 const DRAW_PLIES = 80; // 40 moves each without a capture or a man move8 9 function initialBoard() {10 const b = new Int8Array(64);11 for (let r = 0; r < 8; r++) for (let c = 0; c < 8; c++) {12 if ((r + c) % 2 !== 1) continue;13 if (r < 3) b[r * 8 + c] = 1; else if (r > 4) b[r * 8 + c] = -1;14 }15 return b;16 }17 18 // ---- zobrist hashing (two 32-bit halves) ----19 function mulberry(seed) { return function () { seed = (seed + 0x6D2B79F5) | 0; let t = Math.imul(seed ^ (seed >>> 15), 1 | seed); t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0); }; }20 const rz = mulberry(20240607);21 const Z1 = new Int32Array(64 * 4), Z2 = new Int32Array(64 * 4);22 for (let i = 0; i < Z1.length; i++) { Z1[i] = rz() | 0; Z2[i] = rz() | 0; }23 const T1 = rz() | 0, T2 = rz() | 0;24 const pidx = (p) => (p === 1 ? 0 : p === 2 ? 1 : p === -1 ? 2 : 3);25 function computeHash(s) {26 let h1 = 0, h2 = 0;27 for (let i = 0; i < 64; i++) { const p = s.b[i]; if (p) { const k = i * 4 + pidx(p); h1 ^= Z1[k]; h2 ^= Z2[k]; } }28 if (s.turn === RED) { h1 ^= T1; h2 ^= T2; }29 s.h1 = h1; s.h2 = h2; return s;30 }31 const keyOf = (s) => (s.h1 >>> 0) * 1048576 + (s.h2 & 0xFFFFF);32 33 function newState(board, turn) {34 return computeHash({ b: board ? Int8Array.from(board) : initialBoard(), turn: turn || BLACK, half: 0, h1: 0, h2: 0 });35 }36 // Build a state from 8 strings: '.' empty, b/B black man/king, r/R red man/king.37 function fromRows(rows, turn) {38 const b = new Int8Array(64);39 for (let r = 0; r < 8; r++) for (let c = 0; c < 8; c++) {40 const ch = rows[r][c]; b[r * 8 + c] = ch === "b" ? 1 : ch === "B" ? 2 : ch === "r" ? -1 : ch === "R" ? -2 : 0;41 }42 return newState(b, turn || BLACK);43 }44 function toRows(s) {45 const ch = { 0: ".", 1: "b", 2: "B", "-1": "r", "-2": "R" }, out = [];46 for (let r = 0; r < 8; r++) { let line = ""; for (let c = 0; c < 8; c++) line += ch[s.b[r * 8 + c]]; out.push(line); }47 return out;48 }49 50 const DN = [[1, -1], [1, 1]], UP = [[-1, -1], [-1, 1]], ALL = [[1, -1], [1, 1], [-1, -1], [-1, 1]];51 const dirsOf = (p) => (p === 2 || p === -2 ? ALL : p === 1 ? DN : UP);52 53 function jumpsFrom(b, sq, p, side, path, caps, out) {54 const r = sq >> 3, c = sq & 7, ds = dirsOf(p), promoRow = side === BLACK ? 7 : 0;55 let found = false;56 for (let i = 0; i < ds.length; i++) {57 const dr = ds[i][0], dc = ds[i][1], r2 = r + 2 * dr, c2 = c + 2 * dc;58 if (r2 < 0 || r2 > 7 || c2 < 0 || c2 > 7) continue;59 const mid = (r + dr) * 8 + c + dc, land = r2 * 8 + c2, mp = b[mid];60 if (mp * side < 0 && b[land] === 0) {61 found = true;62 b[mid] = 0; path.push(land); caps.push(mid);63 if ((p === 1 || p === -1) && r2 === promoRow) out.push({ from: path[0], to: land, path: path.slice(), caps: caps.slice(), promo: true });64 else jumpsFrom(b, land, p, side, path, caps, out);65 path.pop(); caps.pop(); b[mid] = mp;66 }67 }68 if (!found && path.length > 1) out.push({ from: path[0], to: sq, path: path.slice(), caps: caps.slice(), promo: false });69 }70 71 // Legal moves (full jump chains). If any capture exists, only captures are returned.72 function genMoves(s) {73 const b = s.b, side = s.turn, out = [];74 for (let sq = 0; sq < 64; sq++) {75 const p = b[sq];76 if (p * side <= 0) continue;77 b[sq] = 0;78 jumpsFrom(b, sq, p, side, [sq], [], out);79 b[sq] = p;80 }81 if (out.length) return out;82 const promoRow = side === BLACK ? 7 : 0;83 for (let sq = 0; sq < 64; sq++) {84 const p = b[sq];85 if (p * side <= 0) continue;86 const r = sq >> 3, c = sq & 7, ds = dirsOf(p);87 for (let i = 0; i < ds.length; i++) {88 const r2 = r + ds[i][0], c2 = c + ds[i][1];89 if (r2 < 0 || r2 > 7 || c2 < 0 || c2 > 7) continue;90 const to = r2 * 8 + c2;91 if (b[to] === 0) out.push({ from: sq, to, path: [sq, to], caps: [], promo: (p === 1 || p === -1) && r2 === promoRow });92 }93 }94 return out;95 }96 97 function applyMove(s, m) {98 const b = Int8Array.from(s.b);99 let h1 = s.h1, h2 = s.h2;100 let p = b[m.from];101 const wasMan = p === 1 || p === -1;102 let k = m.from * 4 + pidx(p); h1 ^= Z1[k]; h2 ^= Z2[k]; b[m.from] = 0;103 for (let i = 0; i < m.caps.length; i++) { const q = m.caps[i]; k = q * 4 + pidx(b[q]); h1 ^= Z1[k]; h2 ^= Z2[k]; b[q] = 0; }104 if (m.promo) p = p * 2;105 b[m.to] = p; k = m.to * 4 + pidx(p); h1 ^= Z1[k]; h2 ^= Z2[k];106 h1 ^= T1; h2 ^= T2;107 return { b, turn: -s.turn, half: m.caps.length || wasMan ? 0 : s.half + 1, h1, h2 };108 }109 110 function sameMove(a, b) { return a.path.length === b.path.length && a.path.every((v, i) => v === b.path[i]); }111 112 function counts(s) {113 const o = { black: 0, red: 0, blackKings: 0, redKings: 0 };114 for (let i = 0; i < 64; i++) { const p = s.b[i]; if (p > 0) { o.black++; if (p === 2) o.blackKings++; } else if (p < 0) { o.red++; if (p === -2) o.redKings++; } }115 return o;116 }117 118 // hashes: array of keyOf() values for positions reached in the game (including current). Returns result object.119 function gameResult(s, hashes, moves) {120 moves = moves || genMoves(s);121 if (!moves.length) return { over: true, winner: -s.turn, reason: "blocked" };122 if (s.half >= DRAW_PLIES) return { over: true, winner: 0, reason: "40-move rule" };123 if (hashes) { let n = 0; const k = keyOf(s); for (const h of hashes) if (h === k) n++; if (n >= 3) return { over: true, winner: 0, reason: "repetition" }; }124 return { over: false };125 }126 127 function perft(s, depth) {128 if (depth === 0) return 1;129 const ms = genMoves(s);130 if (depth === 1) return ms.length;131 let n = 0;132 for (const m of ms) n += perft(applyMove(s, m), depth - 1);133 return n;134 }135 136 // ---- evaluation (positive = good for black) ----137 function evaluate(s) {138 const b = s.b;139 let score = 0, nb = 0, nr = 0, kb = 0, kr = 0, bs = [], rs = [];140 for (let i = 0; i < 64; i++) {141 const p = b[i];142 if (!p) continue;143 const r = i >> 3, c = i & 7, cen = 3.5 - Math.abs(c - 3.5), cenR = 3.5 - Math.abs(r - 3.5);144 if (p === 1) { nb++; score += 100 + r * r * 0.9 + (r === 6 ? 6 : 0) + cen * 1.5 + (c === 0 || c === 7 ? -3 : 0) + (r === 0 ? 7 : 0); bs.push(i); }145 else if (p === -1) { nr++; score -= 100 + (7 - r) * (7 - r) * 0.9 + (r === 1 ? 6 : 0) + cen * 1.5 + (c === 0 || c === 7 ? -3 : 0) + (r === 7 ? 7 : 0); rs.push(i); }146 else if (p === 2) { nb++; kb++; score += 165 + cen * 3 + cenR * 3; bs.push(i); }147 else { nr++; kr++; score -= 165 + cen * 3 + cenR * 3; rs.push(i); }148 }149 const tot = nb + nr;150 // trade down when ahead151 score += ((nb - nr) * 24 * 12) / Math.max(4, tot);152 // endgame: winner closes in on the opponent's pieces, defender keeps to the long diagonal153 if (tot <= 8 && nb !== nr) {154 const ahead = nb > nr ? 1 : -1, hunters = ahead === 1 ? bs : rs, prey = ahead === 1 ? rs : bs;155 let d = 0;156 for (const h of hunters) { let best = 99; for (const q of prey) best = Math.min(best, Math.abs((h >> 3) - (q >> 3)) + Math.abs((h & 7) - (q & 7))); d += best; }157 score += ahead * -(d / Math.max(1, hunters.length)) * 4;158 }159 return score;160 }161 162 // ---- search ----163 const INF = 1e6, WIN = 1e5, TIMEOUT = { timeout: true };164 const LEVELS = [165 { id: 0, name: "Easy", depth: 2, ms: 150, noise: 45, blunder: 0.22, minThink: 450 },166 { id: 1, name: "Medium", depth: 4, ms: 300, noise: 14, blunder: 0.04, minThink: 450 },167 { id: 2, name: "Hard", depth: 9, ms: 900, noise: 0, blunder: 0, minThink: 300 },168 { id: 3, name: "Master", depth: 40, ms: 2200, noise: 0, blunder: 0, minThink: 300 },169 ];170 171 function makeSearch(cfg, history) {172 const tt = new Map();173 let nodes = 0, deadline = Infinity;174 const hist = history || [];175 176 function order(ms, ttMove) {177 const sc = ms.map((m, i) => ({ m, v: (ttMove && sameMove(m, ttMove) ? 1000 : 0) + m.caps.length * 10 + (m.promo ? 5 : 0) }));178 sc.sort((a, b) => b.v - a.v);179 return sc.map((x) => x.m);180 }181 function ab(s, depth, alpha, beta, ply) {182 if ((++nodes & 1023) === 0 && Date.now() > deadline) throw TIMEOUT;183 if (s.half >= DRAW_PLIES) return 0;184 const ms = genMoves(s);185 if (!ms.length) return -WIN + ply;186 if (depth <= 0) {187 if (ms[0].caps.length && ply < 60) depth = 1; // don't stop in the middle of a forced exchange188 else return evaluate(s) * s.turn;189 }190 const key = keyOf(s), e = tt.get(key);191 let ttMove = null;192 if (e) {193 ttMove = e.m;194 if (e.d >= depth) {195 if (e.f === 0) return e.v;196 if (e.f === 1 && e.v >= beta) return e.v;197 if (e.f === 2 && e.v <= alpha) return e.v;198 }199 }200 const a0 = alpha;201 let best = -INF, bm = null;202 const sorted = order(ms, ttMove);203 for (let i = 0; i < sorted.length; i++) {204 const m = sorted[i];205 const v = -ab(applyMove(s, m), depth - 1, -beta, -alpha, ply + 1);206 if (v > best) { best = v; bm = m; }207 if (v > alpha) alpha = v;208 if (alpha >= beta) break;209 }210 tt.set(key, { d: depth, v: best, f: best <= a0 ? 2 : best >= beta ? 1 : 0, m: bm });211 if (tt.size > 400000) tt.clear();212 return best;213 }214 // ply-1 search as a generator so the driver can yield between subtrees215 function* ply1(s, depth, alpha, beta) {216 const ms = genMoves(s);217 if (!ms.length) return -WIN + 1;218 if (depth <= 0 && !ms[0].caps.length) return evaluate(s) * s.turn;219 const sorted = order(ms, null);220 let best = -INF;221 for (const m of sorted) {222 const v = -ab(applyMove(s, m), Math.max(depth, 1) - 1, -beta, -alpha, 2);223 if (v > best) best = v;224 if (v > alpha) alpha = v;225 if (alpha >= beta) break;226 yield;227 }228 return best;229 }230 function* run(s) {231 const moves = genMoves(s);232 if (!moves.length) return null;233 if (moves.length === 1) return { move: moves[0], depth: 0, score: 0 };234 const start = Date.now();235 deadline = start + cfg.ms;236 let ordered = order(moves, null), scores = new Map(), bestMove = ordered[0], reached = 0, bestScore = 0;237 const exact = cfg.noise > 0;238 for (let depth = 1; depth <= cfg.depth; depth++) {239 const iter = [];240 let alpha = -INF;241 try {242 for (const m of ordered) {243 const child = applyMove(s, m);244 const rep = hist.reduce((n, h) => n + (h === keyOf(child) ? 1 : 0), 0);245 const pen = rep && evaluate(s) * s.turn > 40 ? 35 * rep : 0;246 const v = -(yield* ply1(child, depth - 1, exact ? -INF : -INF, exact ? INF : -alpha)) - pen;247 iter.push({ m, v });248 if (v > alpha) alpha = v;249 yield;250 }251 } catch (e) {252 if (e !== TIMEOUT) throw e;253 // keep a partially searched iteration only if its best-so-far beats nothing better (safe: ignore)254 break;255 }256 iter.sort((a, b) => b.v - a.v);257 ordered = iter.map((x) => x.m);258 scores = new Map(iter.map((x) => [x.m, x.v]));259 bestMove = iter[0].m; bestScore = iter[0].v; reached = depth;260 if (Math.abs(bestScore) > WIN - 100 || Date.now() > start + cfg.ms * 0.85) break;261 }262 let choice = bestMove;263 if (cfg.blunder && Math.random() < cfg.blunder) choice = moves[(Math.random() * moves.length) | 0];264 else if (cfg.noise && scores.size) {265 let bv = -INF;266 for (const [m, v] of scores) { const nv = v + (Math.random() - 0.5) * 2 * cfg.noise; if (nv > bv) { bv = nv; choice = m; } }267 }268 return { move: choice, depth: reached, score: bestScore };269 }270 return run;271 }272 273 function levelCfg(level) { return typeof level === "number" ? LEVELS[Math.max(0, Math.min(3, level))] : level; }274 function chooseMoveSync(s, level, history) {275 const g = makeSearch(levelCfg(level), history)(s);276 let r; while (!(r = g.next()).done);277 return r.value;278 }279 // Sliced so the UI thread stays responsive. cb(result) is called once.280 function chooseMoveAsync(s, level, history, cb, opts) {281 const cfg = levelCfg(level), g = makeSearch(cfg, history)(s), t0 = Date.now();282 let cancelled = false;283 const isPaused = (opts && opts.isPaused) || (() => false);284 function slice() {285 if (cancelled) return;286 if (isPaused()) { setTimeout(slice, 100); return; }287 const end = Date.now() + 10;288 let r;289 do { r = g.next(); } while (!r.done && Date.now() < end);290 if (!r.done) { setTimeout(slice, 0); return; }291 const wait = Math.max(0, (cfg.minThink || 0) - (Date.now() - t0));292 setTimeout(() => { if (!cancelled) cb(r.value); }, wait);293 }294 setTimeout(slice, 0);295 return () => { cancelled = true; };296 }297 298 const API = { BLACK, RED, DRAW_PLIES, LEVELS, initialBoard, newState, fromRows, toRows, genMoves, applyMove, sameMove, counts, gameResult, perft, evaluate, keyOf, chooseMoveSync, chooseMoveAsync };299 if (typeof module !== "undefined" && module.exports) module.exports = API;300 root.CheckersEngine = API;301})(typeof window !== "undefined" ? window : globalThis);302