Royal Chess
engine.js29.8 KB
1// Royal Chess engine — pure rules + AI, no DOM. Works in browsers (window.ChessEngine) and node (module.exports).2(function (global) {3 "use strict";4 const WHITE = 0, BLACK = 1, PAWN = 1, KNIGHT = 2, BISHOP = 3, ROOK = 4, QUEEN = 5, KING = 6;5 const F_EP = 1, F_CASTLE = 2, F_DOUBLE = 4;6 const FILES = "abcdefgh";7 const START_FEN = "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1";8 const sqName = (s) => FILES[s & 7] + ((s >> 3) + 1);9 const parseSq = (n) => FILES.indexOf(n[0]) + 8 * (Number(n[1]) - 1);10 const mkMove = (from, to, promo, flags) => from | (to << 6) | ((promo || 0) << 12) | ((flags || 0) << 15);11 const mFrom = (m) => m & 63, mTo = (m) => (m >> 6) & 63, mPromo = (m) => (m >> 12) & 7, mFlags = (m) => m >> 15;12 13 // ---------- tables ----------14 const KN = [], KG = [], PAT = [[], []], RAYS = [[], [], [], [], [], [], [], []];15 const DIRS = [[0, 1], [0, -1], [1, 0], [-1, 0], [1, 1], [-1, 1], [1, -1], [-1, -1]]; // 0-3 rook, 4-7 bishop16 const KNM = [[1, 2], [2, 1], [-1, 2], [-2, 1], [1, -2], [2, -1], [-1, -2], [-2, -1]];17 for (let sq = 0; sq < 64; sq++) {18 const f = sq & 7, r = sq >> 3;19 KN[sq] = []; KG[sq] = []; PAT[0][sq] = []; PAT[1][sq] = [];20 for (const [df, dr] of KNM) { const nf = f + df, nr = r + dr; if (nf >= 0 && nf < 8 && nr >= 0 && nr < 8) KN[sq].push(nr * 8 + nf); }21 for (const [df, dr] of DIRS) { const nf = f + df, nr = r + dr; if (nf >= 0 && nf < 8 && nr >= 0 && nr < 8) KG[sq].push(nr * 8 + nf); }22 for (const df of [-1, 1]) {23 if (f + df >= 0 && f + df < 8) {24 if (r + 1 < 8) PAT[0][sq].push((r + 1) * 8 + f + df);25 if (r - 1 >= 0) PAT[1][sq].push((r - 1) * 8 + f + df);26 }27 }28 for (let d = 0; d < 8; d++) {29 const ray = []; let nf = f + DIRS[d][0], nr = r + DIRS[d][1];30 while (nf >= 0 && nf < 8 && nr >= 0 && nr < 8) { ray.push(nr * 8 + nf); nf += DIRS[d][0]; nr += DIRS[d][1]; }31 RAYS[d][sq] = ray;32 }33 }34 const castleMask = new Int8Array(64).fill(15);35 castleMask[0] = 13; castleMask[7] = 14; castleMask[4] = 12; castleMask[56] = 7; castleMask[63] = 11; castleMask[60] = 3;36 37 // zobrist38 let seed = 0x9e3779b9;39 const rand32 = () => { 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; };40 const Z1 = new Int32Array(16 * 64), Z2 = new Int32Array(16 * 64), CA1 = new Int32Array(16), CA2 = new Int32Array(16), EP1 = new Int32Array(8), EP2 = new Int32Array(8);41 for (let i = 0; i < Z1.length; i++) { Z1[i] = rand32(); Z2[i] = rand32(); }42 for (let i = 0; i < 16; i++) { CA1[i] = rand32(); CA2[i] = rand32(); }43 for (let i = 0; i < 8; i++) { EP1[i] = rand32(); EP2[i] = rand32(); }44 const SIDE1 = rand32(), SIDE2 = rand32();45 46 // piece-square tables (rank 8 first, white's view)47 const T = {48 1: [0, 0, 0, 0, 0, 0, 0, 0, 50, 50, 50, 50, 50, 50, 50, 50, 10, 10, 20, 30, 30, 20, 10, 10, 5, 5, 10, 25, 25, 10, 5, 5, 0, 0, 0, 20, 20, 0, 0, 0, 5, -5, -10, 0, 0, -10, -5, 5, 5, 10, 10, -20, -20, 10, 10, 5, 0, 0, 0, 0, 0, 0, 0, 0],49 2: [-50, -40, -30, -30, -30, -30, -40, -50, -40, -20, 0, 0, 0, 0, -20, -40, -30, 0, 10, 15, 15, 10, 0, -30, -30, 5, 15, 20, 20, 15, 5, -30, -30, 0, 15, 20, 20, 15, 0, -30, -30, 5, 10, 15, 15, 10, 5, -30, -40, -20, 0, 5, 5, 0, -20, -40, -50, -40, -30, -30, -30, -30, -40, -50],50 3: [-20, -10, -10, -10, -10, -10, -10, -20, -10, 0, 0, 0, 0, 0, 0, -10, -10, 0, 5, 10, 10, 5, 0, -10, -10, 5, 5, 10, 10, 5, 5, -10, -10, 0, 10, 10, 10, 10, 0, -10, -10, 10, 10, 10, 10, 10, 10, -10, -10, 5, 0, 0, 0, 0, 5, -10, -20, -10, -10, -10, -10, -10, -10, -20],51 4: [0, 0, 0, 0, 0, 0, 0, 0, 5, 10, 10, 10, 10, 10, 10, 5, -5, 0, 0, 0, 0, 0, 0, -5, -5, 0, 0, 0, 0, 0, 0, -5, -5, 0, 0, 0, 0, 0, 0, -5, -5, 0, 0, 0, 0, 0, 0, -5, -5, 0, 0, 0, 0, 0, 0, -5, 0, 0, 0, 5, 5, 0, 0, 0],52 5: [-20, -10, -10, -5, -5, -10, -10, -20, -10, 0, 0, 0, 0, 0, 0, -10, -10, 0, 5, 5, 5, 5, 0, -10, -5, 0, 5, 5, 5, 5, 0, -5, 0, 0, 5, 5, 5, 5, 0, -5, -10, 5, 5, 5, 5, 5, 0, -10, -10, 0, 5, 0, 0, 0, 0, -10, -20, -10, -10, -5, -5, -10, -10, -20],53 6: [-30, -40, -40, -50, -50, -40, -40, -30, -30, -40, -40, -50, -50, -40, -40, -30, -30, -40, -40, -50, -50, -40, -40, -30, -30, -40, -40, -50, -50, -40, -40, -30, -20, -30, -30, -40, -40, -30, -30, -20, -10, -20, -20, -20, -20, -20, -20, -10, 20, 20, 0, 0, 0, 0, 20, 20, 20, 30, 10, 0, 0, 10, 30, 20],54 7: [-50, -40, -30, -20, -20, -30, -40, -50, -30, -20, -10, 0, 0, -10, -20, -30, -30, -10, 20, 30, 30, 20, -10, -30, -30, -10, 30, 40, 40, 30, -10, -30, -30, -10, 30, 40, 40, 30, -10, -30, -30, -10, 20, 30, 30, 20, -10, -30, -30, -30, 0, 0, 0, 0, -30, -30, -50, -30, -30, -30, -30, -30, -30, -50],55 };56 const MAT_MG = [0, 100, 320, 330, 500, 900, 0], MAT_EG = [0, 115, 320, 335, 520, 940, 0];57 const VAL = [0, 100, 320, 330, 500, 900, 20000];58 const PHASE = [0, 0, 1, 1, 2, 4, 0];59 const PSTMG = new Int32Array(16 * 64), PSTEG = new Int32Array(16 * 64);60 for (let c = 0; c < 2; c++) for (let t = 1; t <= 6; t++) for (let sq = 0; sq < 64; sq++) {61 const f = sq & 7, r = sq >> 3, idx = c === 0 ? (7 - r) * 8 + f : r * 8 + f, p = c * 8 + t;62 const adv = c === 0 ? r : 7 - r;63 PSTMG[p * 64 + sq] = MAT_MG[t] + (t === 6 ? T[6][idx] : T[t][idx]);64 PSTEG[p * 64 + sq] = MAT_EG[t] + (t === 6 ? T[7][idx] : T[t][idx]) + (t === 1 ? adv * 6 : 0);65 }66 67 const HIST = 8192;68 class Position {69 constructor(fen) {70 this.board = new Int8Array(64); this.kingSq = [4, 60]; this.mg = [0, 0]; this.eg = [0, 0]; this.phase = 0; this.cnt = new Int8Array(16);71 this.h1 = 0; this.h2 = 0; this.turn = WHITE; this.castling = 0; this.ep = -1; this.half = 0; this.full = 1; this.ply = 0;72 this.uM = new Int32Array(HIST); this.uC = new Int8Array(HIST); this.uCa = new Int8Array(HIST); this.uEp = new Int8Array(HIST);73 this.uHf = new Int16Array(HIST); this.uH1 = new Int32Array(HIST); this.uH2 = new Int32Array(HIST);74 this.loadFEN(fen || START_FEN);75 }76 clone() {77 const p = new Position("8/8/8/8/8/8/8/K6k w - - 0 1");78 p.board.set(this.board); p.kingSq = this.kingSq.slice(); p.mg = this.mg.slice(); p.eg = this.eg.slice(); p.phase = this.phase; p.cnt.set(this.cnt);79 p.h1 = this.h1; p.h2 = this.h2; p.turn = this.turn; p.castling = this.castling; p.ep = this.ep; p.half = this.half; p.full = this.full; p.ply = this.ply;80 const n = this.ply;81 p.uM.set(this.uM.subarray(0, n)); p.uC.set(this.uC.subarray(0, n)); p.uCa.set(this.uCa.subarray(0, n)); p.uEp.set(this.uEp.subarray(0, n));82 p.uHf.set(this.uHf.subarray(0, n)); p.uH1.set(this.uH1.subarray(0, n)); p.uH2.set(this.uH2.subarray(0, n));83 return p;84 }85 put(sq, p) {86 this.board[sq] = p; const c = p >> 3, k = p * 64 + sq;87 this.h1 ^= Z1[k]; this.h2 ^= Z2[k]; this.mg[c] += PSTMG[k]; this.eg[c] += PSTEG[k]; this.phase += PHASE[p & 7]; this.cnt[p]++;88 if ((p & 7) === KING) this.kingSq[c] = sq;89 }90 del(sq) {91 const p = this.board[sq]; this.board[sq] = 0; const c = p >> 3, k = p * 64 + sq;92 this.h1 ^= Z1[k]; this.h2 ^= Z2[k]; this.mg[c] -= PSTMG[k]; this.eg[c] -= PSTEG[k]; this.phase -= PHASE[p & 7]; this.cnt[p]--;93 }94 epHashFile() {95 if (this.ep < 0) return -1;96 const t = this.turn, psq = t === WHITE ? this.ep - 8 : this.ep + 8, f = psq & 7, mine = t * 8 + PAWN;97 return ((f > 0 && this.board[psq - 1] === mine) || (f < 7 && this.board[psq + 1] === mine)) ? this.ep & 7 : -1;98 }99 loadFEN(fen) {100 const parts = fen.trim().split(/\s+/);101 this.board.fill(0); this.mg = [0, 0]; this.eg = [0, 0]; this.phase = 0; this.cnt.fill(0); this.h1 = 0; this.h2 = 0; this.ply = 0;102 const map = { p: 1, n: 2, b: 3, r: 4, q: 5, k: 6 };103 const rows = parts[0].split("/");104 for (let i = 0; i < 8; i++) {105 let f = 0; const r = 7 - i;106 for (const ch of rows[i]) {107 if (ch >= "1" && ch <= "8") f += Number(ch);108 else { const lower = ch.toLowerCase(); this.put(r * 8 + f, (ch === lower ? 8 : 0) + map[lower]); f++; }109 }110 }111 this.turn = parts[1] === "b" ? BLACK : WHITE;112 this.castling = 0;113 const cs = parts[2] || "-";114 if (cs.includes("K")) this.castling |= 1; if (cs.includes("Q")) this.castling |= 2; if (cs.includes("k")) this.castling |= 4; if (cs.includes("q")) this.castling |= 8;115 this.ep = parts[3] && parts[3] !== "-" ? parseSq(parts[3]) : -1;116 this.half = Number(parts[4] || 0); this.full = Number(parts[5] || 1);117 this.h1 ^= CA1[this.castling]; this.h2 ^= CA2[this.castling];118 if (this.turn === BLACK) { this.h1 ^= SIDE1; this.h2 ^= SIDE2; }119 const ef = this.epHashFile(); if (ef >= 0) { this.h1 ^= EP1[ef]; this.h2 ^= EP2[ef]; }120 }121 toFEN() {122 let s = "";123 for (let r = 7; r >= 0; r--) {124 let e = 0;125 for (let f = 0; f < 8; f++) {126 const p = this.board[r * 8 + f];127 if (!p) e++; else { if (e) { s += e; e = 0; } const ch = " pnbrqk"[p & 7]; s += p >> 3 ? ch : ch.toUpperCase(); }128 }129 if (e) s += e; if (r) s += "/";130 }131 const c = (this.castling & 1 ? "K" : "") + (this.castling & 2 ? "Q" : "") + (this.castling & 4 ? "k" : "") + (this.castling & 8 ? "q" : "");132 return `${s} ${this.turn ? "b" : "w"} ${c || "-"} ${this.ep >= 0 ? sqName(this.ep) : "-"} ${this.half} ${this.full}`;133 }134 attacked(sq, by) {135 const b = this.board;136 for (const s of PAT[by ^ 1][sq]) if (b[s] === by * 8 + PAWN) return true;137 for (const s of KN[sq]) if (b[s] === by * 8 + KNIGHT) return true;138 for (const s of KG[sq]) if (b[s] === by * 8 + KING) return true;139 const rk = by * 8 + ROOK, bs = by * 8 + BISHOP, qn = by * 8 + QUEEN;140 for (let d = 0; d < 4; d++) { for (const s of RAYS[d][sq]) { const p = b[s]; if (p) { if (p === rk || p === qn) return true; break; } } }141 for (let d = 4; d < 8; d++) { for (const s of RAYS[d][sq]) { const p = b[s]; if (p) { if (p === bs || p === qn) return true; break; } } }142 return false;143 }144 inCheck() { return this.attacked(this.kingSq[this.turn], this.turn ^ 1); }145 // pseudo-legal moves. caps=true: captures + promotions only (for quiescence)146 gen(caps) {147 const out = [], b = this.board, us = this.turn, them = us ^ 1;148 for (let sq = 0; sq < 64; sq++) {149 const p = b[sq];150 if (!p || (p >> 3) !== us) continue;151 const t = p & 7;152 if (t === PAWN) {153 const dir = us ? -8 : 8, start = us ? 6 : 1, last = us ? 0 : 7, r = sq >> 3, to = sq + dir;154 if (!b[to]) {155 if ((to >> 3) === last) { out.push(mkMove(sq, to, QUEEN)); if (!caps) out.push(mkMove(sq, to, ROOK), mkMove(sq, to, BISHOP), mkMove(sq, to, KNIGHT)); }156 else if (!caps) {157 out.push(mkMove(sq, to));158 if (r === start && !b[to + dir]) out.push(mkMove(sq, to + dir, 0, F_DOUBLE));159 }160 }161 for (const t2 of PAT[us][sq]) {162 const q = b[t2];163 if (q && (q >> 3) === them) {164 if ((t2 >> 3) === last) { out.push(mkMove(sq, t2, QUEEN)); out.push(mkMove(sq, t2, ROOK), mkMove(sq, t2, BISHOP), mkMove(sq, t2, KNIGHT)); }165 else out.push(mkMove(sq, t2));166 } else if (t2 === this.ep) out.push(mkMove(sq, t2, 0, F_EP));167 }168 } else if (t === KNIGHT || t === KING) {169 for (const t2 of t === KNIGHT ? KN[sq] : KG[sq]) {170 const q = b[t2];171 if (q ? (q >> 3) === them : !caps) out.push(mkMove(sq, t2));172 }173 if (t === KING && !caps) {174 const home = us ? 60 : 4;175 if (sq === home) {176 const ks = us ? 4 : 1, qs = us ? 8 : 2;177 if ((this.castling & ks) && !b[home + 1] && !b[home + 2] && b[home + 3] === us * 8 + ROOK &&178 !this.attacked(home, them) && !this.attacked(home + 1, them) && !this.attacked(home + 2, them)) out.push(mkMove(home, home + 2, 0, F_CASTLE));179 if ((this.castling & qs) && !b[home - 1] && !b[home - 2] && !b[home - 3] && b[home - 4] === us * 8 + ROOK &&180 !this.attacked(home, them) && !this.attacked(home - 1, them) && !this.attacked(home - 2, them)) out.push(mkMove(home, home - 2, 0, F_CASTLE));181 }182 }183 } else {184 const d0 = t === BISHOP ? 4 : 0, d1 = t === ROOK ? 4 : 8;185 for (let d = d0; d < d1; d++) {186 for (const t2 of RAYS[d][sq]) {187 const q = b[t2];188 if (!q) { if (!caps) out.push(mkMove(sq, t2)); }189 else { if ((q >> 3) === them) out.push(mkMove(sq, t2)); break; }190 }191 }192 }193 }194 return out;195 }196 legalMoves() {197 const moves = this.gen(false), out = [], us = this.turn;198 for (const m of moves) {199 this.make(m);200 if (!this.attacked(this.kingSq[us], us ^ 1)) out.push(m);201 this.unmake();202 }203 return out;204 }205 make(m) {206 const b = this.board, from = m & 63, to = (m >> 6) & 63, promo = (m >> 12) & 7, fl = m >> 15, us = this.turn, p = b[from];207 let cap = b[to], capSq = to;208 if (fl & F_EP) { capSq = us ? to + 8 : to - 8; cap = b[capSq]; }209 const i = this.ply++;210 this.uM[i] = m; this.uC[i] = cap; this.uCa[i] = this.castling; this.uEp[i] = this.ep; this.uHf[i] = this.half; this.uH1[i] = this.h1; this.uH2[i] = this.h2;211 const oe = this.epHashFile();212 if (oe >= 0) { this.h1 ^= EP1[oe]; this.h2 ^= EP2[oe]; }213 this.h1 ^= CA1[this.castling]; this.h2 ^= CA2[this.castling];214 if (cap) this.del(capSq);215 this.del(from);216 this.put(to, promo ? us * 8 + promo : p);217 if (fl & F_CASTLE) {218 const rf = to > from ? to + 1 : to - 2, rt = to > from ? to - 1 : to + 1, rook = b[rf];219 this.del(rf); this.put(rt, rook);220 }221 this.castling &= castleMask[from] & castleMask[to];222 const isPawn = (p & 7) === PAWN;223 this.ep = isPawn && (to - from === 16 || from - to === 16) ? (from + to) >> 1 : -1;224 this.half = isPawn || cap ? 0 : this.half + 1;225 if (us) this.full++;226 this.turn = us ^ 1;227 this.h1 ^= SIDE1 ^ CA1[this.castling]; this.h2 ^= SIDE2 ^ CA2[this.castling];228 const ne = this.epHashFile();229 if (ne >= 0) { this.h1 ^= EP1[ne]; this.h2 ^= EP2[ne]; }230 }231 unmake() {232 const i = --this.ply, m = this.uM[i], b = this.board, from = m & 63, to = (m >> 6) & 63, promo = (m >> 12) & 7, fl = m >> 15, us = this.turn ^ 1;233 this.turn = us;234 let p = b[to]; if (promo) p = us * 8 + PAWN;235 this.del(to); this.put(from, p);236 const cap = this.uC[i];237 if (cap) this.put(fl & F_EP ? (us ? to + 8 : to - 8) : to, cap);238 if (fl & F_CASTLE) {239 const rf = to > from ? to + 1 : to - 2, rt = to > from ? to - 1 : to + 1, rook = b[rt];240 this.del(rt); this.put(rf, rook);241 }242 this.castling = this.uCa[i]; this.ep = this.uEp[i]; this.half = this.uHf[i]; this.h1 = this.uH1[i]; this.h2 = this.uH2[i];243 if (us) this.full--;244 }245 makeNull() {246 const i = this.ply++;247 this.uM[i] = 0; this.uC[i] = 0; this.uCa[i] = this.castling; this.uEp[i] = this.ep; this.uHf[i] = this.half; this.uH1[i] = this.h1; this.uH2[i] = this.h2;248 this.ep = -1; this.turn ^= 1; this.h1 = this.uH1[i] ^ SIDE1; this.h2 = this.uH2[i] ^ SIDE2; this.half++;249 }250 unmakeNull() {251 const i = --this.ply;252 this.turn ^= 1; this.ep = this.uEp[i]; this.half = this.uHf[i]; this.h1 = this.uH1[i]; this.h2 = this.uH2[i];253 }254 // how many times the current position has occurred (including now)255 repetitionCount() {256 let n = 1;257 for (let k = 2; k <= this.half; k += 2) {258 const idx = this.ply - k;259 if (idx < 0) break;260 if (this.uH1[idx] === this.h1 && this.uH2[idx] === this.h2) n++;261 }262 return n;263 }264 isRepetition() {265 for (let k = 2; k <= this.half; k += 2) {266 const idx = this.ply - k;267 if (idx < 0) break;268 if (this.uH1[idx] === this.h1 && this.uH2[idx] === this.h2) return true;269 }270 return false;271 }272 insufficientMaterial() {273 const c = this.cnt;274 if (c[1] || c[9] || c[4] || c[12] || c[5] || c[13]) return false;275 const minors = c[2] + c[10] + c[3] + c[11];276 if (minors <= 1) return true;277 if (c[2] || c[10]) return false; // knights plus something else: mate is possible in theory278 // only bishops: draw if all on same square colour279 let col = -1;280 for (let sq = 0; sq < 64; sq++) {281 const p = this.board[sq];282 if ((p & 7) === BISHOP) { const sc = ((sq >> 3) + (sq & 7)) & 1; if (col < 0) col = sc; else if (col !== sc) return false; }283 }284 return true;285 }286 hasPieces(c) { const k = this.cnt; const o = c * 8; return k[o + 2] + k[o + 3] + k[o + 4] + k[o + 5] > 0; }287 status(legal) {288 legal = legal || this.legalMoves();289 if (!legal.length) return this.inCheck() ? { over: true, result: "checkmate", winner: this.turn ^ 1 } : { over: true, result: "stalemate", winner: -1 };290 if (this.insufficientMaterial()) return { over: true, result: "insufficient", winner: -1 };291 if (this.repetitionCount() >= 3) return { over: true, result: "threefold", winner: -1 };292 if (this.half >= 100) return { over: true, result: "fifty", winner: -1 };293 return { over: false, result: null, winner: -1 };294 }295 evaluate() {296 const ph = this.phase > 24 ? 24 : this.phase, k = this.cnt;297 let mg = this.mg[0] - this.mg[1], eg = this.eg[0] - this.eg[1];298 if (k[3] >= 2) { mg += 30; eg += 45; }299 if (k[11] >= 2) { mg -= 30; eg -= 45; }300 const s = ((mg * ph + eg * (24 - ph)) / 24) | 0;301 return (this.turn ? -s : s) + 8;302 }303 findMove(from, to, promo) {304 for (const m of this.legalMoves()) if (mFrom(m) === from && mTo(m) === to && (mPromo(m) || 0) === (promo || 0)) return m;305 return 0;306 }307 }308 309 function moveToUCI(m) { return sqName(mFrom(m)) + sqName(mTo(m)) + (mPromo(m) ? ["", "", "n", "b", "r", "q"][mPromo(m)] : ""); }310 function moveFromUCI(pos, s) {311 const from = parseSq(s.slice(0, 2)), to = parseSq(s.slice(2, 4)), pc = s[4] ? { n: 2, b: 3, r: 4, q: 5 }[s[4]] : 0;312 return pos.findMove(from, to, pc);313 }314 function moveToSAN(pos, m) {315 const from = mFrom(m), to = mTo(m), promo = mPromo(m), fl = mFlags(m), p = pos.board[from], t = p & 7;316 let s;317 if (fl & F_CASTLE) s = to > from ? "O-O" : "O-O-O";318 else {319 const isCap = pos.board[to] !== 0 || (fl & F_EP) !== 0;320 if (t === PAWN) s = (isCap ? FILES[from & 7] + "x" : "") + sqName(to) + (promo ? "=" + "??NBRQ"[promo] : "");321 else {322 s = "?PNBRQK"[t];323 const others = pos.legalMoves().filter((o) => o !== m && mTo(o) === to && pos.board[mFrom(o)] === p);324 if (others.length) {325 const sameFile = others.some((o) => (mFrom(o) & 7) === (from & 7)), sameRank = others.some((o) => (mFrom(o) >> 3) === (from >> 3));326 if (!sameFile) s += FILES[from & 7]; else if (!sameRank) s += (from >> 3) + 1; else s += sqName(from);327 }328 if (isCap) s += "x";329 s += sqName(to);330 }331 }332 pos.make(m);333 if (pos.inCheck()) s += pos.legalMoves().length ? "+" : "#";334 pos.unmake();335 return s;336 }337 338 function perft(pos, depth) {339 const moves = pos.legalMoves();340 if (depth <= 1) return moves.length;341 let n = 0;342 for (const m of moves) { pos.make(m); n += perft(pos, depth - 1); pos.unmake(); }343 return n;344 }345 346 // ---------- search ----------347 const INF = 30000, MATE = 29000, MAXPLY = 128;348 const ABORT = { abort: true };349 const now = typeof performance !== "undefined" && performance.now ? () => performance.now() : () => Date.now();350 const TT_BITS = 18, TT_MASK = (1 << TT_BITS) - 1;351 let ttKey, ttMv, ttScore, ttDepth, ttFlag;352 function clearTT() {353 if (!ttKey) { ttKey = new Int32Array(1 << TT_BITS); ttMv = new Int32Array(1 << TT_BITS); ttScore = new Int16Array(1 << TT_BITS); ttDepth = new Int8Array(1 << TT_BITS); ttFlag = new Int8Array(1 << TT_BITS); }354 else ttFlag.fill(0);355 }356 const LEVELS = {357 1: { name: "Easy", maxDepth: 1, timeMs: 250, noise: 230 },358 2: { name: "Medium", maxDepth: 3, timeMs: 600, noise: 45 },359 3: { name: "Hard", maxDepth: 8, timeMs: 1200, noise: 0 },360 4: { name: "Master", maxDepth: 24, timeMs: 2600, noise: 0 },361 };362 363 function scoreMoves(pos, moves, ttMove, ply, ctx) {364 const b = pos.board, sc = new Array(moves.length), k = ctx.killers[ply], us = pos.turn;365 for (let i = 0; i < moves.length; i++) {366 const m = moves[i], from = m & 63, to = (m >> 6) & 63, promo = (m >> 12) & 7;367 if (m === ttMove) { sc[i] = 1e7; continue; }368 const victim = b[to] ? b[to] & 7 : (m >> 15) & F_EP ? PAWN : 0;369 if (victim) sc[i] = 1e6 + VAL[victim] * 10 - (b[from] & 7);370 else if (promo) sc[i] = 9.5e5 + promo;371 else if (k && k[0] === m) sc[i] = 9e5;372 else if (k && k[1] === m) sc[i] = 8e5;373 else sc[i] = ctx.history[us * 4096 + from * 64 + to];374 }375 return sc;376 }377 function pick(moves, sc, i) {378 let bi = i;379 for (let j = i + 1; j < moves.length; j++) if (sc[j] > sc[bi]) bi = j;380 if (bi !== i) { const tm = moves[i]; moves[i] = moves[bi]; moves[bi] = tm; const ts = sc[i]; sc[i] = sc[bi]; sc[bi] = ts; }381 }382 function qsearch(pos, alpha, beta, ctx, ply) {383 if ((++ctx.nodes & 1023) === 0 && now() > ctx.hard) throw ABORT;384 const stand = pos.evaluate();385 if (ply >= MAXPLY - 1) return stand;386 if (stand >= beta) return stand;387 if (stand > alpha) alpha = stand;388 const moves = pos.gen(true), sc = new Array(moves.length), b = pos.board, us = pos.turn;389 for (let i = 0; i < moves.length; i++) {390 const m = moves[i], v = b[(m >> 6) & 63] ? b[(m >> 6) & 63] & 7 : (m >> 15) & F_EP ? PAWN : 0;391 sc[i] = VAL[v] * 10 - (b[m & 63] & 7) + ((m >> 12) & 7 ? 5000 : 0);392 }393 for (let i = 0; i < moves.length; i++) {394 pick(moves, sc, i);395 const m = moves[i], to = (m >> 6) & 63, promo = (m >> 12) & 7;396 const victim = b[to] ? b[to] & 7 : promo ? 0 : PAWN;397 if (!promo && stand + VAL[victim] + 200 < alpha) continue;398 pos.make(m);399 if (pos.attacked(pos.kingSq[us], us ^ 1)) { pos.unmake(); continue; }400 const s = -qsearch(pos, -beta, -alpha, ctx, ply + 1);401 pos.unmake();402 if (s >= beta) return s;403 if (s > alpha) alpha = s;404 }405 return alpha;406 }407 function storeKiller(ctx, ply, m, us, from, to, depth) {408 const k = ctx.killers[ply];409 if (k[0] !== m) { k[1] = k[0]; k[0] = m; }410 const h = ctx.history, idx = us * 4096 + from * 64 + to;411 h[idx] += depth * depth; if (h[idx] > 4e5) for (let i = 0; i < h.length; i++) h[i] >>= 1;412 }413 function ab(pos, depth, alpha, beta, ply, ctx, allowNull) {414 if ((++ctx.nodes & 1023) === 0 && now() > ctx.hard) throw ABORT;415 if (pos.half >= 100 || pos.isRepetition()) return 0;416 const us = pos.turn, inCheck = pos.inCheck();417 if (inCheck) depth++;418 if (depth <= 0 || ply >= MAXPLY - 2) return qsearch(pos, alpha, beta, ctx, ply);419 const alphaOrig = alpha; let ttMove = 0;420 const idx = pos.h1 & TT_MASK;421 if (ttFlag[idx] && ttKey[idx] === pos.h2) {422 ttMove = ttMv[idx];423 if (ttDepth[idx] >= depth) {424 let s = ttScore[idx]; if (s > MATE - MAXPLY) s -= ply; else if (s < -MATE + MAXPLY) s += ply;425 const f = ttFlag[idx];426 if (f === 1) return s;427 if (f === 2 && s > alpha) alpha = s; else if (f === 3 && s < beta) beta = s;428 if (alpha >= beta) return s;429 }430 }431 if (allowNull && !inCheck && depth >= 3 && beta < MATE - MAXPLY && pos.hasPieces(us) && pos.evaluate() >= beta) {432 pos.makeNull();433 const s = -ab(pos, depth - 3, -beta, -beta + 1, ply + 1, ctx, false);434 pos.unmakeNull();435 if (s >= beta) return beta;436 }437 const moves = pos.gen(false), sc = scoreMoves(pos, moves, ttMove, ply, ctx), b = pos.board;438 let best = -INF, bestMove = 0, legal = 0;439 for (let i = 0; i < moves.length; i++) {440 pick(moves, sc, i);441 const m = moves[i], from = m & 63, to = (m >> 6) & 63, promo = (m >> 12) & 7;442 const quiet = !b[to] && !promo && !((m >> 15) & F_EP);443 pos.make(m);444 if (pos.attacked(pos.kingSq[us], us ^ 1)) { pos.unmake(); continue; }445 legal++;446 let s;447 if (legal === 1) s = -ab(pos, depth - 1, -beta, -alpha, ply + 1, ctx, true);448 else {449 let red = 0;450 if (depth >= 3 && legal > 4 && quiet && !inCheck) red = legal > 10 && depth > 5 ? 2 : 1;451 s = -ab(pos, depth - 1 - red, -alpha - 1, -alpha, ply + 1, ctx, true);452 if (s > alpha && (red || s < beta)) s = -ab(pos, depth - 1, -beta, -alpha, ply + 1, ctx, true);453 }454 pos.unmake();455 if (s > best) {456 best = s; bestMove = m;457 if (s > alpha) { alpha = s; if (alpha >= beta) { if (quiet) storeKiller(ctx, ply, m, us, from, to, depth); break; } }458 }459 }460 if (!legal) return inCheck ? -MATE + ply : 0;461 ttKey[idx] = pos.h2; ttMv[idx] = bestMove; ttDepth[idx] = depth > 100 ? 100 : depth;462 ttFlag[idx] = best <= alphaOrig ? 3 : best >= beta ? 2 : 1;463 let st = best; if (st > MATE - MAXPLY) st += ply; else if (st < -MATE + MAXPLY) st -= ply;464 ttScore[idx] = st;465 return best;466 }467 // ply-1 node written as a generator so the driver can yield between slices468 function* ab1(pos, depth, alpha, beta, ctx) {469 ctx.nodes++;470 if (pos.half >= 100 || pos.isRepetition()) return 0;471 const us = pos.turn, inCheck = pos.inCheck();472 if (inCheck) depth++;473 if (depth <= 0) return qsearch(pos, alpha, beta, ctx, 1);474 const moves = pos.gen(false), sc = scoreMoves(pos, moves, 0, 1, ctx), b = pos.board;475 let best = -INF, legal = 0;476 for (let i = 0; i < moves.length; i++) {477 pick(moves, sc, i);478 const m = moves[i], from = m & 63, to = (m >> 6) & 63, promo = (m >> 12) & 7;479 const quiet = !b[to] && !promo && !((m >> 15) & F_EP);480 pos.make(m);481 if (pos.attacked(pos.kingSq[us], us ^ 1)) { pos.unmake(); continue; }482 legal++;483 let s;484 if (legal === 1) s = -ab(pos, depth - 1, -beta, -alpha, 2, ctx, true);485 else {486 s = -ab(pos, depth - 1, -alpha - 1, -alpha, 2, ctx, true);487 if (s > alpha && s < beta) s = -ab(pos, depth - 1, -beta, -alpha, 2, ctx, true);488 }489 pos.unmake();490 if (s > best) { best = s; if (s > alpha) { alpha = s; if (alpha >= beta) { if (quiet) storeKiller(ctx, 1, m, us, from, to, depth); break; } } }491 if (now() > ctx.sliceEnd) yield;492 }493 if (!legal) return inCheck ? -MATE + 1 : 0;494 return best;495 }496 497 // Resumable search. Call .step(ms) repeatedly until it returns true, then read .result = {move, score, depth, nodes}498 function createSearch(pos0, opts) {499 opts = opts || {};500 const cfg = Object.assign({}, LEVELS[opts.level || 3], opts);501 const pos = opts.inPlace ? pos0 : pos0.clone();502 const rng = opts.rng || Math.random;503 clearTT();504 const start = now();505 const ctx = { nodes: 0, hard: start + cfg.timeMs, sliceEnd: Infinity, killers: [], history: new Int32Array(2 * 4096) };506 for (let i = 0; i < MAXPLY + 2; i++) ctx.killers.push([0, 0]);507 const basePly = pos.ply;508 function unwind() { while (pos.ply > basePly) { if (pos.uM[pos.ply - 1] === 0) pos.unmakeNull(); else pos.unmake(); } }509 function* run() {510 let moves = pos.legalMoves();511 if (!moves.length) return { move: 0, score: 0, depth: 0, nodes: 0 };512 if (moves.length === 1) return { move: moves[0], score: 0, depth: 0, nodes: 0 };513 const sc0 = scoreMoves(pos, moves, 0, 0, ctx);514 for (let i = 0; i < moves.length; i++) pick(moves, sc0, i);515 let result = { move: moves[0], score: 0, depth: 0, nodes: 0 };516 let scores = moves.map(() => 0);517 for (let depth = 1; depth <= cfg.maxDepth; depth++) {518 const iter = [];519 let alpha = -INF, bestS = -INF;520 try {521 for (let i = 0; i < moves.length; i++) {522 pos.make(moves[i]);523 let s;524 if (cfg.noise > 0) s = -(yield* ab1(pos, depth - 1, -INF, INF, ctx));525 else if (i === 0) s = -(yield* ab1(pos, depth - 1, -INF, -alpha, ctx));526 else {527 s = -(yield* ab1(pos, depth - 1, -alpha - 1, -alpha, ctx));528 if (s > alpha) s = -(yield* ab1(pos, depth - 1, -INF, -alpha, ctx));529 }530 pos.unmake();531 iter.push(s);532 if (s > bestS) bestS = s;533 if (s > alpha) alpha = s;534 if (now() > ctx.sliceEnd) yield;535 }536 } catch (e) { if (e !== ABORT) throw e; unwind(); break; }537 // iteration complete: sort by score (stable, best first)538 const order = moves.map((m, i) => i).sort((a, b2) => iter[b2] - iter[a] || a - b2);539 moves = order.map((i) => moves[i]); scores = order.map((i) => iter[i]);540 result = { move: moves[0], score: scores[0], depth, nodes: ctx.nodes };541 if (Math.abs(scores[0]) > MATE - 100) break;542 if (now() - start > cfg.timeMs * 0.45) break;543 }544 if (cfg.noise > 0) {545 let bestV = -Infinity, bm = moves[0];546 for (let i = 0; i < moves.length; i++) {547 const n = Math.abs(scores[i]) > MATE - 200 ? 0 : (rng() * 2 - 1) * cfg.noise;548 const v = scores[i] + n;549 if (v > bestV) { bestV = v; bm = moves[i]; }550 }551 result.move = bm;552 }553 result.nodes = ctx.nodes;554 return result;555 }556 const gen = run();557 const handle = {558 done: false, result: null, ctx,559 step(ms) {560 if (handle.done) return true;561 ctx.sliceEnd = now() + (ms === undefined ? 10 : ms);562 const r = gen.next();563 if (r.done) { handle.done = true; handle.result = r.value; unwind(); }564 return handle.done;565 },566 cancel() { handle.done = true; },567 };568 return handle;569 }570 function searchSync(pos, opts) {571 const h = createSearch(pos, opts);572 while (!h.step(1e9)) { /* run to completion */ }573 return h.result;574 }575 576 const api = {577 Position, createSearch, searchSync, perft, LEVELS, START_FEN, sqName, parseSq, moveToSAN, moveToUCI, moveFromUCI, mkMove, mFrom, mTo, mPromo, mFlags,578 WHITE, BLACK, PAWN, KNIGHT, BISHOP, ROOK, QUEEN, KING, F_EP, F_CASTLE, F_DOUBLE, VAL, clearTT,579 };580 if (typeof module !== "undefined" && module.exports) module.exports = api;581 if (typeof window !== "undefined") window.ChessEngine = api;582 else if (global) global.ChessEngine = api;583})(typeof globalThis !== "undefined" ? globalThis : this);584