/** * Chess AI Engine — deterministic negamax with alpha-beta pruning, * piece-square tables (PST), MVV-LVA move ordering, and quiescence search. * Differentiated depth and strategic profiles for Easy, Basic, and Hard. */ import type { Rng } from "@3miz/game-server-sdk"; import { isMoveLegalFor, isKingInCheck, isCheckmate, hasInsufficientMaterial, type State, type Piece, type PieceType, } from "./game.ts"; // Material values in centipawns const PIECE_VALUES: Record = { p: 100, n: 320, b: 330, r: 500, q: 900, k: 20000, }; // Piece-Square Tables (White perspective: rank 1 at index 0..7, rank 8 at index 56..63) const PAWN_PST = [ 0, 0, 0, 0, 0, 0, 0, 0, // rank 1 5, 10, 10, -20, -20, 10, 10, 5, // rank 2 5, -5, -10, 0, 0, -10, -5, 5, // rank 3 0, 0, 0, 25, 25, 0, 0, 0, // rank 4 5, 5, 10, 25, 25, 10, 5, 5, // rank 5 10, 10, 20, 30, 30, 20, 10, 10, // rank 6 50, 50, 50, 50, 50, 50, 50, 50, // rank 7 0, 0, 0, 0, 0, 0, 0, 0, // rank 8 ]; const KNIGHT_PST = [ -50, -40, -30, -30, -30, -30, -40, -50, -40, -20, 0, 5, 5, 0, -20, -40, -30, 5, 15, 20, 20, 15, 5, -30, -30, 5, 20, 30, 30, 20, 5, -30, -30, 5, 20, 30, 30, 20, 5, -30, -30, 5, 15, 20, 20, 15, 5, -30, -40, -20, 0, 5, 5, 0, -20, -40, -50, -40, -30, -30, -30, -30, -40, -50, ]; const BISHOP_PST = [ -20, -10, -10, -10, -10, -10, -10, -20, -10, 5, 0, 0, 0, 0, 5, -10, -10, 10, 10, 10, 10, 10, 10, -10, -10, 0, 10, 15, 15, 10, 0, -10, -10, 5, 5, 15, 15, 5, 5, -10, -10, 0, 5, 10, 10, 5, 0, -10, -10, 0, 0, 0, 0, 0, 0, -10, -20, -10, -10, -10, -10, -10, -10, -20, ]; const ROOK_PST = [ 0, 0, 0, 5, 5, 0, 0, 0, -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, 5, 10, 10, 10, 10, 10, 10, 5, 0, 0, 0, 0, 0, 0, 0, 0, ]; const QUEEN_PST = [ -20, -10, -10, -5, -5, -10, -10, -20, -10, 0, 5, 0, 0, 0, 0, -10, -10, 5, 5, 5, 5, 5, 0, -10, 0, 0, 5, 5, 5, 5, 0, -5, -5, 0, 5, 5, 5, 5, 0, -5, -10, 0, 5, 5, 5, 5, 0, -10, -10, 0, 0, 0, 0, 0, 0, -10, -20, -10, -10, -5, -5, -10, -10, -20, ]; const KING_PST = [ 20, 30, 10, 0, 0, 10, 30, 20, 20, 20, 0, 0, 0, 0, 20, 20, -10, -20, -20, -20, -20, -20, -20, -10, -20, -30, -30, -40, -40, -30, -30, -20, -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, ]; function getPstScore(type: PieceType, color: "w" | "b", sq: number): number { const pstSq = color === "w" ? sq : (7 - Math.floor(sq / 8)) * 8 + (sq % 8); switch (type) { case "p": return PAWN_PST[pstSq] ?? 0; case "n": return KNIGHT_PST[pstSq] ?? 0; case "b": return BISHOP_PST[pstSq] ?? 0; case "r": return ROOK_PST[pstSq] ?? 0; case "q": return QUEEN_PST[pstSq] ?? 0; case "k": return KING_PST[pstSq] ?? 0; default: return 0; } } /** * Static position evaluation from White's perspective. * Positive favors White, negative favors Black. */ function evaluateStatic(s: State): number { let material = 0; let positional = 0; for (let sq = 0; sq < 64; sq++) { const p = s.board[sq]; if (!p) continue; const val = PIECE_VALUES[p.type] ?? 0; if (p.color === "w") { material += val; positional += getPstScore(p.type, p.color, sq); } else { material -= val; positional -= getPstScore(p.type, p.color, sq); } } if (isKingInCheck(s, "w")) positional -= 40; if (isKingInCheck(s, "b")) positional += 40; return material + positional; } interface MoveCandidate { from: number; to: number; promotion?: PieceType; score: number; } interface UndoRecord { from: number; to: number; moving: Piece; captured: Piece | null; prevEp: number | null; prevRights: { wk: boolean; wq: boolean; bk: boolean; bq: boolean }; isCastling: boolean; rookFrom?: number; rookTo?: number; isEp: boolean; epVictimSq?: number; epVictimPiece?: Piece | null; } function makeMove(s: State, from: number, to: number, promotion?: PieceType): UndoRecord { const moving = s.board[from]!; const captured = s.board[to]; const undo: UndoRecord = { from, to, moving, captured, prevEp: s.ep, prevRights: { ...s.rights }, isCastling: false, isEp: false, }; // En passant if (moving.type === "p" && to === s.ep && !captured) { undo.isEp = true; undo.epVictimSq = to + (moving.color === "w" ? -8 : 8); undo.epVictimPiece = s.board[undo.epVictimSq]; s.board[undo.epVictimSq] = null; } // Castling if (moving.type === "k" && Math.abs((to % 8) - (from % 8)) === 2) { undo.isCastling = true; undo.rookFrom = to > from ? to + 1 : to - 2; undo.rookTo = to > from ? to - 1 : to + 1; s.board[undo.rookTo] = s.board[undo.rookFrom]; s.board[undo.rookFrom] = null; } // Double step opening en passant s.ep = null; if (moving.type === "p" && Math.abs(to - from) === 16) { s.ep = from + (moving.color === "w" ? 8 : -8); } // Promotion const lastRank = moving.color === "w" ? 7 : 0; if (moving.type === "p" && Math.floor(to / 8) === lastRank) { s.board[to] = { type: promotion ?? "q", color: moving.color }; } else { s.board[to] = moving; } s.board[from] = null; // Rights decay if (moving.type === "k") { if (moving.color === "w") { s.rights.wk = false; s.rights.wq = false; } else { s.rights.bk = false; s.rights.bq = false; } } else if (moving.type === "r") { if (from === 0) s.rights.wq = false; else if (from === 7) s.rights.wk = false; else if (from === 56) s.rights.bq = false; else if (from === 63) s.rights.bk = false; } return undo; } function unmakeMove(s: State, undo: UndoRecord) { s.board[undo.from] = undo.moving; s.board[undo.to] = undo.captured; s.ep = undo.prevEp; s.rights = undo.prevRights; if (undo.isCastling && undo.rookFrom !== undefined && undo.rookTo !== undefined) { s.board[undo.rookFrom] = s.board[undo.rookTo]; s.board[undo.rookTo] = null; } if (undo.isEp && undo.epVictimSq !== undefined) { s.board[undo.epVictimSq] = undo.epVictimPiece ?? null; } } /** * Generate all legal moves for a given color, ordered using MVV-LVA heuristics. * Uses isMoveLegalFor so it is independent of whose turn it currently is in the root state. */ function generateOrderedMoves(s: State, color: "w" | "b", prioritizeCaptures = true): MoveCandidate[] { const moves: MoveCandidate[] = []; for (let from = 0; from < 64; from++) { const p = s.board[from]; if (!p || p.color !== color) continue; for (let to = 0; to < 64; to++) { if (isMoveLegalFor(s, from, to, color)) { const target = s.board[to]; let moveScore = 0; if (prioritizeCaptures) { // MVV-LVA: Most Valuable Victim - Least Valuable Attacker if (target) { moveScore = 1000 + (PIECE_VALUES[target.type] ?? 0) * 10 - (PIECE_VALUES[p.type] ?? 0); } else if (to === s.ep && p.type === "p") { moveScore = 1000 + 100 * 10 - 100; } // Promotion bonus const lastRank = color === "w" ? 7 : 0; const isPromo = p.type === "p" && Math.floor(to / 8) === lastRank; if (isPromo) { moveScore += 900; } // Positional gain const pstGain = getPstScore(p.type, color, to) - getPstScore(p.type, color, from); moveScore += pstGain; } const isPawnPromo = p.type === "p" && Math.floor(to / 8) === (color === "w" ? 7 : 0); moves.push({ from, to, promotion: isPawnPromo ? "q" : undefined, score: moveScore, }); } } } if (prioritizeCaptures) { moves.sort((a, b) => b.score - a.score); } return moves; } /** * Quiescence search for loud capture sequences */ function quiescence( s: State, alpha: number, beta: number, color: "w" | "b", depthLimit: number ): number { if (hasInsufficientMaterial(s)) return 0; const standPat = (color === "w" ? 1 : -1) * evaluateStatic(s); if (standPat >= beta) return beta; if (standPat > alpha) alpha = standPat; if (depthLimit <= 0) return alpha; const oppColor = color === "w" ? "b" : "w"; const moves = generateOrderedMoves(s, color, true).filter( (m) => s.board[m.to] !== null || m.to === s.ep ); for (const move of moves) { const undo = makeMove(s, move.from, move.to, move.promotion); const score = -quiescence(s, -beta, -alpha, oppColor, depthLimit - 1); unmakeMove(s, undo); if (score >= beta) return beta; if (score > alpha) alpha = score; } return alpha; } /** * Negamax with Alpha-Beta Pruning */ function negamax( s: State, depth: number, alpha: number, beta: number, color: "w" | "b", ply: number, quiesceDepth: number ): number { const oppColor = color === "w" ? "b" : "w"; if (isCheckmate(s, color)) { // Current side to move is mated -> large penalty scaled by distance to root return -100000 + ply; } if (hasInsufficientMaterial(s)) { return 0; // Drawn position } if (depth <= 0) { if (quiesceDepth > 0) { return quiescence(s, alpha, beta, color, quiesceDepth); } return (color === "w" ? 1 : -1) * evaluateStatic(s); } const moves = generateOrderedMoves(s, color, true); if (moves.length === 0) { // Stalemate is a draw (0) return 0; } for (const move of moves) { const undo = makeMove(s, move.from, move.to, move.promotion); const score = -negamax(s, depth - 1, -beta, -alpha, oppColor, ply + 1, quiesceDepth); unmakeMove(s, undo); if (score >= beta) return beta; if (score > alpha) alpha = score; } return alpha; } /** * Standard opening book moves */ const OPENING_BOOK_WHITE = [ { from: 12, to: 28 }, // e2 -> e4 { from: 11, to: 27 }, // d2 -> d4 { from: 6, to: 21 }, // g1 -> f3 { from: 10, to: 26 }, // c2 -> c4 ]; const OPENING_BOOK_BLACK: Record = { // Against e2-e4: "28": [ { from: 52, to: 36 }, // e7 -> e5 { from: 50, to: 34 }, // c7 -> c5 (Sicilian) { from: 52, to: 44 }, // e7 -> e6 (French) ], // Against d2-d4: "27": [ { from: 51, to: 35 }, // d7 -> d5 { from: 62, to: 45 }, // g8 -> f6 (Indian) ], }; /** * Main bot decision engine */ export function decideBot( s: State, seat: number, rng: Rng ): { fromIdx: number; toIdx: number; promotion?: PieceType } | null { const player = s.players[seat]; if (!player) return null; const color = player.color; const rawLevel = (player.level || "").toLowerCase().trim(); const legalMoves = generateOrderedMoves(s, color, true); if (legalMoves.length === 0) return null; if (legalMoves.length === 1) { return { fromIdx: legalMoves[0].from, toIdx: legalMoves[0].to, promotion: legalMoves[0].promotion, }; } // Difficulty profiles: easy (آسون), basic (معمولی), hard (سخت) let searchDepth = 2; let quiesceDepth = 1; let noiseRange = 0; let useOpeningBook = true; let blunderChancePercent = 0; if (rawLevel === "hard" || rawLevel === "expert" || rawLevel === "master") { // Hard (سخت): Depth 3 + 2 plies quiescence. Sharp, tactical, 0 blunders (~160ms). searchDepth = 3; quiesceDepth = 2; noiseRange = 0; useOpeningBook = true; blunderChancePercent = 0; } else if (rawLevel === "basic" || rawLevel === "normal") { // Basic / Normal (معمولی): Depth 2 + 1 ply quiescence. Solid play, small noise (~2ms). searchDepth = 2; quiesceDepth = 1; noiseRange = 10; useOpeningBook = true; blunderChancePercent = 5; } else { // Easy (آسون): Depth 1, no quiescence, higher noise & 25% casual blunders (~1ms). searchDepth = 1; quiesceDepth = 0; noiseRange = 50; useOpeningBook = false; blunderChancePercent = 25; } // 1. Opening book selection on the first 2 moves of the game (if enabled) if (useOpeningBook) { if (s.moves_played === 0 && color === "w") { const pick = OPENING_BOOK_WHITE[rng.int(OPENING_BOOK_WHITE.length)]; if (isMoveLegalFor(s, pick.from, pick.to, color)) { return { fromIdx: pick.from, toIdx: pick.to }; } } else if (s.moves_played === 1 && color === "b") { const cand = s.board[28]?.type === "p" && s.board[28]?.color === "w" ? OPENING_BOOK_BLACK["28"] : (s.board[27]?.type === "p" && s.board[27]?.color === "w" ? OPENING_BOOK_BLACK["27"] : null); if (cand) { const pick = cand[rng.int(cand.length)]; if (isMoveLegalFor(s, pick.from, pick.to, color)) { return { fromIdx: pick.from, toIdx: pick.to }; } } } } // 2. Beginner blunder mechanism: integer-based check using rng.int(100) (never rng.float) if (blunderChancePercent > 0 && rng.int(100) < blunderChancePercent) { const nonCaptures = legalMoves.filter((m) => s.board[m.to] === null); if (nonCaptures.length > 0) { const pick = nonCaptures[rng.int(nonCaptures.length)]; return { fromIdx: pick.from, toIdx: pick.to, promotion: pick.promotion }; } } // 3. Negamax evaluation over all candidate root moves const oppColor = color === "w" ? "b" : "w"; let bestScore = -Infinity; let bestMoves: MoveCandidate[] = []; for (const move of legalMoves) { const undo = makeMove(s, move.from, move.to, move.promotion); let evalScore = -negamax(s, searchDepth - 1, -Infinity, Infinity, oppColor, 1, quiesceDepth); unmakeMove(s, undo); // Apply difficulty noise if (noiseRange > 0) { const jitter = rng.int(noiseRange * 2 + 1) - noiseRange; evalScore += jitter; } if (evalScore > bestScore) { bestScore = evalScore; bestMoves = [move]; } else if (Math.abs(evalScore - bestScore) <= 2) { bestMoves.push(move); } } const selected = bestMoves.length > 0 ? bestMoves[rng.int(bestMoves.length)] : legalMoves[0]; return { fromIdx: selected.from, toIdx: selected.to, promotion: selected.promotion, }; }