Backgammon Club
engine.js13.6 KB
1// Backgammon engine: pure rules + AI. No DOM. Works in node (module.exports) and in the browser (window.BG).2(function () {3 'use strict';4 // Board: pts[0..23]; player 0 (white) = positive counts and moves 23 -> 0 (home idx 0-5);5 // player 1 (black) = negative counts and moves 0 -> 23 (home idx 18-23).6 // Move: {f: 0..23 | 24 (bar), t: 0..23 | 25 (off), d: die, hit: bool}7 const BAR = 24, OFF = 25;8 9 function newState() {10 const pts = new Array(24).fill(0);11 pts[23] = 2; pts[12] = 5; pts[7] = 3; pts[5] = 5;12 pts[0] = -2; pts[11] = -5; pts[16] = -3; pts[18] = -5;13 return { pts, bar: [0, 0], off: [0, 0] };14 }15 function clone(s) { return { pts: s.pts.slice(), bar: s.bar.slice(), off: s.off.slice() }; }16 function key(s) { return s.pts.join(',') + '|' + s.bar[0] + ',' + s.bar[1] + '|' + s.off[0] + ',' + s.off[1]; }17 const sgn = (p) => (p === 0 ? 1 : -1);18 // point number as seen by player p (1 = their last point, 24 = furthest)19 function pointNo(p, idx) { return p === 0 ? idx + 1 : 24 - idx; }20 function pips(s, p) {21 let n = s.bar[p] * 25;22 for (let i = 0; i < 24; i++) { const c = s.pts[i] * sgn(p); if (c > 0) n += c * pointNo(p, i); }23 return n;24 }25 function allHome(s, p) {26 if (s.bar[p] > 0) return false;27 const g = sgn(p);28 if (p === 0) { for (let i = 6; i < 24; i++) if (s.pts[i] * g > 0) return false; }29 else { for (let i = 0; i < 18; i++) if (s.pts[i] * g > 0) return false; }30 return true;31 }32 function checkerCount(s, p) {33 let n = s.bar[p] + s.off[p];34 for (let i = 0; i < 24; i++) { const c = s.pts[i] * sgn(p); if (c > 0) n += c; }35 return n;36 }37 38 function singleMoves(s, p, die) {39 const g = sgn(p), dir = p === 0 ? -1 : 1, res = [];40 if (s.bar[p] > 0) {41 const t = p === 0 ? 24 - die : die - 1;42 const oc = -s.pts[t] * g;43 if (oc < 2) res.push({ f: BAR, t, d: die, hit: oc === 1 });44 return res;45 }46 const home = allHome(s, p);47 let farthest = -1; // idx of farthest own checker (for higher-die bear off)48 if (home) {49 if (p === 0) { for (let i = 5; i >= 0; i--) if (s.pts[i] > 0) { farthest = i; break; } }50 else { for (let i = 18; i < 24; i++) if (s.pts[i] < 0) { farthest = i; break; } }51 }52 for (let i = 0; i < 24; i++) {53 if (s.pts[i] * g <= 0) continue;54 const t = i + dir * die;55 if (t >= 0 && t <= 23) {56 const oc = -s.pts[t] * g;57 if (oc < 2) res.push({ f: i, t, d: die, hit: oc === 1 });58 } else if (home) {59 const dist = pointNo(p, i);60 if (die === dist || (die > dist && i === farthest)) res.push({ f: i, t: OFF, d: die, hit: false });61 }62 }63 return res;64 }65 function applyMove(s, p, m) {66 const n = clone(s), g = sgn(p);67 if (m.f === BAR) n.bar[p]--; else n.pts[m.f] -= g;68 if (m.t === OFF) n.off[p]++;69 else {70 if (n.pts[m.t] * g < 0) { n.pts[m.t] = 0; n.bar[1 - p]++; }71 n.pts[m.t] += g;72 }73 return n;74 }75 function removeDie(dice, i) { const r = dice.slice(); r.splice(i, 1); return r; }76 function maxPlay(s, p, dice) {77 if (!dice.length) return 0;78 let best = 0; const seen = {};79 for (let i = 0; i < dice.length; i++) {80 const d = dice[i]; if (seen[d]) continue; seen[d] = 1;81 const rest = removeDie(dice, i), ms = singleMoves(s, p, d);82 for (const m of ms) {83 const v = 1 + maxPlay(applyMove(s, p, m), p, rest);84 if (v > best) best = v;85 if (best === dice.length) return best;86 }87 }88 return best;89 }90 // Legal next single moves given the remaining dice. maxLen = max dice usable at turn start, played = moves made so far.91 function legalMoves(s, p, dice, maxLen, played) {92 const need = maxLen - played;93 if (need <= 0 || !dice.length) return [];94 let res = []; const seen = {};95 for (let i = 0; i < dice.length; i++) {96 const d = dice[i]; if (seen[d]) continue; seen[d] = 1;97 const rest = removeDie(dice, i);98 for (const m of singleMoves(s, p, d)) {99 if (need === 1 || 1 + maxPlay(applyMove(s, p, m), p, rest) >= need) res.push(m);100 }101 }102 if (played === 0 && maxLen === 1 && dice.length === 2 && dice[0] !== dice[1]) {103 const big = Math.max(dice[0], dice[1]);104 const bigMoves = res.filter((m) => m.d === big);105 if (bigMoves.length) res = bigMoves;106 }107 return res;108 }109 function turnDice(dice) { return dice[0] === dice[1] ? [dice[0], dice[0], dice[0], dice[0]] : [dice[0], dice[1]]; }110 function remainingDice(dice, moves) {111 const r = turnDice(dice);112 for (const m of moves) { const i = r.indexOf(m.d); if (i >= 0) r.splice(i, 1); }113 return r;114 }115 116 // Every maximal play (deduplicated by resulting position): [{moves, state}]117 function genPlays(s, p, dice) {118 const orders = dice[0] === dice[1] ? [turnDice(dice)] : [[dice[0], dice[1]], [dice[1], dice[0]]];119 const finals = new Map(); let maxLen = 0;120 for (const order of orders) {121 let level = new Map(); level.set(key(s), { state: s, moves: [] });122 for (let i = 0; i <= order.length; i++) {123 if (i === order.length) { for (const [k, e] of level) addFinal(k, e, i); break; }124 const next = new Map();125 for (const [k, e] of level) {126 const ms = singleMoves(e.state, p, order[i]);127 if (!ms.length) { addFinal(k, e, i); continue; }128 for (const m of ms) {129 const ns = applyMove(e.state, p, m), nk = key(ns);130 if (!next.has(nk)) next.set(nk, { state: ns, moves: e.moves.concat([m]) });131 }132 }133 level = next;134 if (!level.size) break;135 }136 }137 function addFinal(k, e, len) {138 if (len > maxLen) { maxLen = len; finals.clear(); }139 if (len === maxLen && !finals.has(k)) finals.set(k, e);140 }141 let out = [...finals.values()];142 if (maxLen === 0) return [];143 if (maxLen === 1 && dice[0] !== dice[1]) {144 const big = Math.max(dice[0], dice[1]);145 const bm = singleMoves(s, p, big);146 if (bm.length) {147 const seen = new Map();148 for (const m of bm) { const ns = applyMove(s, p, m), k = key(ns); if (!seen.has(k)) seen.set(k, { state: ns, moves: [m] }); }149 out = [...seen.values()];150 }151 }152 return out;153 }154 155 function winner(s) { return s.off[0] === 15 ? 0 : s.off[1] === 15 ? 1 : -1; }156 // Points multiplier for a finished game (1 single, 2 gammon, 3 backgammon)157 function gameResult(s) {158 const w = winner(s); if (w < 0) return null;159 const l = 1 - w;160 let mult = 1;161 if (s.off[l] === 0) {162 mult = 2;163 let bg = s.bar[l] > 0;164 if (!bg) {165 // loser has checker in winner's home board166 if (w === 0) { for (let i = 0; i < 6; i++) if (s.pts[i] < 0) bg = true; }167 else { for (let i = 18; i < 24; i++) if (s.pts[i] > 0) bg = true; }168 }169 if (bg) mult = 3;170 }171 return { winner: w, mult, kind: mult === 3 ? 'backgammon' : mult === 2 ? 'gammon' : 'single' };172 }173 174 // ---------- dice ----------175 function makeRng(seed) {176 let a = seed >>> 0;177 return function () { a = (a + 0x6D2B79F5) >>> 0; let t = a; t = Math.imul(t ^ (t >>> 15), t | 1); t ^= t + Math.imul(t ^ (t >>> 7), t | 61); return ((t ^ (t >>> 14)) >>> 0) / 4294967296; };178 }179 function seedRng() {180 let seed = (Date.now() ^ ((Math.random() * 4294967296) >>> 0)) >>> 0;181 try { if (typeof crypto !== 'undefined' && crypto.getRandomValues) { const a = new Uint32Array(1); crypto.getRandomValues(a); seed ^= a[0]; } } catch (e) {}182 return makeRng(seed);183 }184 let defaultRng = seedRng();185 function rollDie(rng) { return 1 + Math.floor((rng || defaultRng)() * 6); }186 function rollDice(rng) { return [rollDie(rng), rollDie(rng)]; }187 function openingRoll(rng) { let a, b; do { a = rollDie(rng); b = rollDie(rng); } while (a === b); return { dice: [a, b], first: a > b ? 0 : 1 }; }188 189 // ---------- evaluation ----------190 const SHOT = [0, 11, 12, 14, 15, 15, 17, 6, 6, 5, 3, 2, 3].map((x) => x / 36);191 const HOME_W = [0, 3, 4, 6, 8, 9, 7]; // by point number 1..6192 function hasContact(s) {193 let max0 = -1, min1 = 99;194 if (s.bar[0] > 0) max0 = 24; else for (let i = 23; i >= 0; i--) if (s.pts[i] > 0) { max0 = i; break; }195 if (s.bar[1] > 0) min1 = -1; else for (let i = 0; i < 24; i++) if (s.pts[i] < 0) { min1 = i; break; }196 return max0 > min1;197 }198 function side(s, p) {199 const g = sgn(p), q = 1 - p, pip = pips(s, p);200 let sc = -pip;201 if (!hasContact(s)) return sc;202 // opponent checker positions (bar as virtual point)203 const oppPos = [];204 for (let i = 0; i < 24; i++) if (s.pts[i] * g < 0) oppPos.push(i);205 if (s.bar[q] > 0) oppPos.push(q === 0 ? 24 : -1);206 let run = 0, best = 0;207 const order = []; for (let n = 1; n <= 24; n++) order.push(p === 0 ? n - 1 : 24 - n);208 for (let n = 1; n <= 24; n++) {209 const idx = order[n - 1], c = s.pts[idx] * g;210 if (c >= 2) {211 run++; if (run > best) best = run;212 sc += n <= 6 ? HOME_W[n] : n <= 12 ? (n === 7 ? 6 : 3) : n >= 19 && n <= 21 ? 5 : 2;213 if (c > 4) sc -= (c - 4) * 2;214 } else run = 0;215 if (c === 1) {216 let miss = 1;217 for (const o of oppPos) {218 const dist = q === 0 ? o - idx : idx - o;219 if (dist >= 1 && dist <= 12) miss *= 1 - SHOT[dist];220 }221 const pHit = 1 - miss;222 const opBarBonus = s.bar[q] > 0 ? 0.6 : 1;223 sc -= pHit * opBarBonus * ((25 - n) + 8);224 }225 }226 if (best >= 3) sc += 2 * best * best;227 if (s.bar[p] > 0) {228 let blocked = 0;229 for (let n = 1; n <= 6; n++) { const idx = q === 0 ? n - 1 : 24 - n; if (s.pts[idx] * sgn(q) >= 2) blocked++; }230 sc -= s.bar[p] * (5 + 4 * blocked);231 }232 return sc;233 }234 function evaluate(s, p) {235 const w = winner(s);236 if (w >= 0) { const r = gameResult(s); return (w === p ? 1 : -1) * (1000 + r.mult * 50); }237 return side(s, p) - side(s, 1 - p);238 }239 function winProb(s, p) {240 const w = winner(s); if (w >= 0) return w === p ? 1 : 0;241 if (!hasContact(s)) {242 const mine = pips(s, p), theirs = pips(s, 1 - p), L = Math.min(mine, theirs);243 const z = (theirs - mine) / (1.3 * Math.sqrt(Math.max(L, 4)));244 return 1 / (1 + Math.exp(-1.7 * z));245 }246 return 1 / (1 + Math.exp(-evaluate(s, p) / 30));247 }248 // Cube AI. Doubler p about to roll; taker q.249 function aiShouldDouble(s, p, level) {250 if (level === 'easy') return false;251 const w = winProb(s, p);252 return w >= (level === 'hard' ? 0.7 : 0.75) && w <= 0.9;253 }254 function aiShouldTake(s, taker, level) {255 const w = winProb(s, taker);256 return w >= (level === 'easy' ? 0.15 : 0.25);257 }258 259 // ---------- AI ----------260 function randomPlay(plays, rng) { return plays[Math.floor((rng || defaultRng)() * plays.length)]; }261 const ROLLS = []; for (let a = 1; a <= 6; a++) for (let b = a; b <= 6; b++) ROLLS.push({ dice: [a, b], w: a === b ? 1 / 36 : 2 / 36 });262 263 function choosePlay(s, p, dice, level, rng) {264 const plays = genPlays(s, p, dice);265 if (!plays.length) return { moves: [], state: s };266 if (level === 'easy') return randomPlay(plays, rng);267 let best = null, bv = -Infinity;268 for (const pl of plays) { const v = evaluate(pl.state, p) + (rng || defaultRng)() * 0.01; if (v > bv) { bv = v; best = pl; } }269 return best;270 }271 // Time-sliced choice. cb(play) is always called asynchronously (setTimeout).272 function choosePlayAsync(s, p, dice, level, opts, cb) {273 opts = opts || {};274 const now = () => (typeof performance !== 'undefined' ? performance.now() : Date.now());275 const rng = opts.rng;276 const budget = opts.budgetMs == null ? 1200 : opts.budgetMs;277 const sliceMs = opts.sliceMs || 10;278 const t0 = now();279 setTimeout(function start() {280 const plays = genPlays(s, p, dice);281 if (!plays.length) return cb({ moves: [], state: s });282 if (level !== 'hard' || plays.length === 1) return cb(level === 'easy' ? randomPlay(plays, rng) : choosePlay(s, p, dice, level, rng));283 for (const pl of plays) pl.v1 = evaluate(pl.state, p);284 plays.sort((a, b) => b.v1 - a.v1);285 const K = Math.min(plays.length, dice[0] === dice[1] ? 7 : 10);286 const cands = plays.slice(0, K);287 let ci = 0, ri = 0, acc = 0;288 let bestPlay = cands[0], bestVal = -Infinity, done = 0;289 function finish() { cb(bestPlay); }290 (function slice() {291 const sliceEnd = now() + sliceMs;292 while (ci < cands.length) {293 if (now() - t0 > budget && done > 0) return finish();294 const c = cands[ci];295 if (winner(c.state) >= 0) { c.v2 = c.v1; }296 else {297 while (ri < ROLLS.length) {298 const R = ROLLS[ri], reply = genPlays(c.state, 1 - p, R.dice);299 let m = -Infinity;300 if (!reply.length) m = evaluate(c.state, p);301 else for (const rp of reply) { const v = -evaluate(rp.state, 1 - p); if (v < m || m === -Infinity) m = v; }302 acc += R.w * m; ri++;303 if (now() > sliceEnd) break;304 }305 if (ri < ROLLS.length) return setTimeout(slice, 0);306 c.v2 = acc;307 }308 const val = 0.25 * c.v1 + 0.75 * c.v2;309 done++;310 if (val > bestVal) { bestVal = val; bestPlay = c; }311 ci++; ri = 0; acc = 0;312 if (now() > sliceEnd && ci < cands.length) return setTimeout(slice, 0);313 }314 finish();315 })();316 }, 0);317 }318 319 const api = {320 BAR, OFF, newState, clone, key, pointNo, pips, allHome, checkerCount, singleMoves, applyMove, maxPlay, legalMoves, turnDice,321 remainingDice, genPlays, winner, gameResult, makeRng, rollDie, rollDice, openingRoll, evaluate, winProb, hasContact,322 aiShouldDouble, aiShouldTake, choosePlay, choosePlayAsync,323 };324 if (typeof module !== 'undefined' && module.exports) module.exports = api;325 if (typeof window !== 'undefined') window.BG = api;326})();327