Complete technical documentation for the chess engine's AI system, including algorithms, optimizations, architecture, and implementation details.
- Overview
- Architecture
- Core Algorithm
- Performance Optimizations
- Position Evaluation
- Search Enhancements
- Data Structures
- Performance Metrics
- Future Enhancements
- Developer Guide
The js-chess-engine v2 AI is a competitive chess engine built on classical chess programming techniques, enhanced with modern optimizations. It achieves strong tactical play through efficient search algorithms and sophisticated position evaluation.
Key Features:
- Minimax algorithm with alpha-beta pruning
- Transposition table with Zobrist hashing (configurable size, disable for minimal memory)
- Advanced move ordering (PV moves, MVV-LVA, killer moves)
- Iterative deepening
- Quiescence search for tactical stability
- Configurable difficulty levels (1-5)
- Adaptive depth (position-dependent, capped per level)
- Memory-efficient with tunable cache size (browser and mobile-friendly)
- Configurable randomness for varied, less predictable play (disabled by default)
Performance: 65% faster than baseline implementation (16.3s → 5.6s on test suite)
src/ai/
├── AIEngine.ts # Main AI interface and level configuration
├── Search.ts # Alpha-beta search with optimizations
├── Evaluator.ts # Static position evaluation
├── TranspositionTable.ts # Position caching system
└── MoveOrdering.ts # Move ordering heuristics
Game (API Layer)
↓
AIEngine (Level Configuration)
↓
Search (Alpha-Beta + Optimizations)
↓
├─→ TranspositionTable (Position Cache)
├─→ MoveOrdering (Move Prioritization)
├─→ Evaluator (Position Scoring)
└─→ MoveGenerator (Legal Moves)
- API Call: User calls
game.ai()orgame.aiMove() - Configuration: AIEngine maps level (1-5) to base depth + max adaptive extension + quiescence depth (overridable via
depthoption) - Search: Iterative deepening progressively searches deeper
- Ordering: Moves ordered by PV → Captures → Killers → Quiet
- Evaluation: Positions scored by material + piece-square tables
- Caching: Results stored in transposition table
- Randomness: Optional noise applied to root-level scores after search completes (zero search overhead)
- Return: Best move returned to API layer
Location: src/ai/Search.ts - negamax() method
Description: Classical minimax algorithm that explores the game tree to find the best move, enhanced with alpha-beta pruning to eliminate branches that cannot affect the final decision.
Pseudocode:
function alphaBeta(board, depth, alpha, beta, maximizing):
if depth == 0 or game_over:
return evaluate(board)
if maximizing:
maxEval = -∞
for each move in moves:
eval = alphaBeta(after_move, depth-1, alpha, beta, false)
maxEval = max(maxEval, eval)
alpha = max(alpha, eval)
if beta <= alpha:
break # Beta cutoff
return maxEval
else:
minEval = +∞
for each move in moves:
eval = alphaBeta(after_move, depth-1, alpha, beta, true)
minEval = min(minEval, eval)
beta = min(beta, eval)
if beta <= alpha:
break # Alpha cutoff
return minEval
Key Properties:
- Time Complexity: O(b^d) worst case, O(b^(d/2)) with optimal move ordering
- Space Complexity: O(d) for call stack
- Pruning Efficiency: 50-90% of nodes eliminated with good move ordering
Check Extension:
- When king is in check, search 1 ply deeper
- Prevents horizon effect in tactical positions
- Location:
Search.ts(look forconst extension = child.isCheck ? 1 : 0;)
Quiescence Search:
- Continue searching forcing moves (captures/promotions) at leaf nodes
- Prevents missing tactical sequences at search boundary
qMaxDepthscales by AI level (defaults): 0 (levels 1-2), 1 (level 3), 2 (level 4), 4 (level 5)
Implementation Detail (current):
// When depth reaches 0, switch to quiescence.
if (depth <= 0) {
return quiescence(board, alpha, beta, ply, 0);
}
// Small search extension when giving check.
const extension = child.isCheck ? 1 : 0;
const score = -negamax(child, depth - 1 + extension, -beta, -alpha, ply + 1);Location: src/ai/TranspositionTable.ts
Purpose: Cache previously evaluated positions to avoid redundant computation. Chess positions can be reached through different move orders (transpositions).
Implementation:
interface TTEntry {
zobristHash: bigint; // Position identifier
depth: number; // Search depth
score: Score; // Position score
type: TTEntryType; // EXACT, LOWER_BOUND, UPPER_BOUND
bestMove: InternalMove; // Best move found
age: number; // Search generation
}Configuration:
The transposition table size is auto-configured based on AI level and runtime environment:
| Level | Node.js | Browser | Entries (approx) |
|---|---|---|---|
| 1 | 0.5 MB | 0.25 MB | ~6K |
| 2 | 1 MB | 0.5 MB | ~13K |
| 3 | 4 MB | 2 MB | ~52K |
| 4 | 16 MB | 8 MB | ~210K |
| 5 | 40 MB | 20 MB | ~655K |
You can override the default through AI options:
// Use auto-detected default (recommended)
game.ai({ level: 3 });
// → Node.js: 4 MB cache
// → Browser: 2 MB cache
// Override for specific requirements
game.ai({ level: 4, ttSizeMB: 64 }); // High-performance: 64MB
game.ai({ level: 2, ttSizeMB: 2 }); // Standard mobile: 2MB
game.ai({ level: 1, ttSizeMB: 0.5 }); // Low-end mobile: 512KB
game.ai({ level: 1, ttSizeMB: 0.25 }); // Ultra-lightweight: 256KB
game.ai({ level: 1, ttSizeMB: 0 }); // Disabled: ~16KB base memory
// Custom depth overrides (values not provided fall back to level defaults)
game.ai({ level: 3, depth: { base: 5 } }); // Deeper base search
game.ai({ level: 1, depth: { base: 2, extended: 0, check: false, quiescence: 0 } }); // Full controlEnvironment Detection:
The engine automatically detects the runtime environment using:
process.versions.nodecheck for Node.js- Absence of Node.js globals indicates browser environment
- See
src/utils/environment.tsfor implementation
Key Features:
- Size: Configurable (0 to disable, min 0.25 MB, default: auto-detected - 2 MB in Node.js ~50,000 entries, 1 MB in browser ~25,000 entries)
- Hash Function: Zobrist hashing (see below)
- Replacement Strategy: Always replace if:
- Slot is empty
- Same position (hash collision)
- Greater search depth
- Older generation
- Entry Types:
EXACT: Exact score (search completed within alpha-beta window)LOWER_BOUND: Fail-high (score >= beta)UPPER_BOUND: Fail-low (score <= alpha)
Usage Pattern:
// Before searching
const ttEntry = transpositionTable.probe(hash, depth, alpha, beta);
if (ttEntry && canUseScore(ttEntry)) {
return ttEntry.score; // Cache hit!
}
// After searching
transpositionTable.store(hash, depth, score, type, bestMove);Impact:
- 60-80% cache hit rate in typical positions
- Dramatically reduces nodes searched
- Especially effective in endgames with repeated positions
Location: src/core/zobrist.ts
Purpose: Fast, incremental position identification for transposition table.
Algorithm:
-
Initialize random 64-bit numbers for:
- Each piece type on each square (12 × 64)
- Side to move (1)
- Castling rights (4)
- En passant file (8)
-
Position hash = XOR of all active keys
Properties:
- Speed: O(1) for incremental updates (XOR is reversible)
- Uniqueness: Collision probability ≈ 1 / 2^64 (negligible)
- Incrementality: Add/remove pieces with single XOR operation
Implementation:
// Initial hash computation
let hash = 0n;
for each piece on board:
hash ^= pieceKeys[piece][square];
if (whiteToMove):
hash ^= sideKey;
// ... castling rights, en passant
// Incremental update (move piece)
hash ^= pieceKeys[piece][fromSquare]; // Remove from old square
hash ^= pieceKeys[piece][toSquare]; // Add to new squareInitialization: Seeded PRNG for deterministic hashing across sessions
Location: src/ai/MoveOrdering.ts
Purpose: Order moves to maximize alpha-beta pruning efficiency. Better moves searched first = more cutoffs = less computation.
Implementation: Uses incremental selection sort via MoveSelector class — scores all moves upfront into a parallel Int32Array, then picks the best remaining move on demand. On beta cutoffs, remaining moves are never sorted.
Ordering Priority:
| Priority | Move Type | Score Bonus | Explanation |
|---|---|---|---|
| 1 | TT/PV Move | +10,000,000 | Best move from previous iteration/TT |
| 2 | Queen Promotion | +9,000,000 | Almost always winning |
| 3 | Capture | +5,000,000 + MVV-LVA | Winning captures scored highest |
| 4 | Killer Move | +3,000,000 | Non-capture that caused cutoff |
| 5 | Quiet Move | 0 | Normal moves |
MVV-LVA (Most Valuable Victim - Least Valuable Attacker):
score = victimValue * 16 - attackerValue
// Example:
// Pawn takes Queen: 900*16 - 100 = 14300 (excellent)
// Queen takes Pawn: 100*16 - 900 = 700 (poor)Killer Moves:
- Store 2 non-capture moves per ply that caused beta cutoff
- Heuristic: moves that were good in sibling nodes often work here
- Storage: 2 moves × 64 plies = 128 moves total
Impact:
- 2-3x reduction in nodes searched
- Critical for deep searches (levels 4-5)
- Most effective with PV moves from transposition table
Location: src/ai/Search.ts - findBestMove() method
Purpose: Search progressively deeper depths (1, 2, 3, ..., target) before final search.
Algorithm:
for depth = 1 to targetDepth - 1:
search(board, depth)
// Results stored in transposition table
// Final search with best move ordering
search(board, targetDepth)Benefits:
- Move Ordering: Shallow searches find best moves for deeper searches
- TT Population: Fills transposition table with useful positions
- Minimal Overhead: ~5-10% time cost due to exponential search tree
- Time Management: Can stop early if time limit reached (future feature)
Cost Analysis:
- Depth 1: ~20 nodes
- Depth 2: ~400 nodes
- Depth 3: ~8,000 nodes
- Depth 4: ~160,000 nodes
Total overhead: (20 + 400 + 8,000) / 160,000 ≈ 5%
Implementation:
// Always iterate from depth 1 up to target
for (let d = 1; d <= baseDepth; d++) {
// Search at depth d, populating TT for next iteration
}Location: src/ai/Evaluator.ts
Purpose: Assign a numeric score to a chess position from a player's perspective. Positive = good for player, negative = bad.
Values (in pawns):
- Pawn: 1
- Knight: 3
- Bishop: 3
- Rook: 5
- Queen: 9
- King: 10 (for capture detection)
Multiplier: 10 (scores in centipawns for precision)
Calculation:
let score = 0;
for each piece on board:
value = PIECE_VALUES[piece] * 10;
if (piece belongs to player):
score += value;
else:
score -= value;Purpose: Encourage pieces to occupy strategic squares.
Tables: 8×8 grids with positional bonuses for each piece type
Example - Pawn Table (white perspective):
A B C D E F G H
8 [0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0] Promotion rank
7 [5.0 5.0 5.0 5.0 5.0 5.0 5.0 5.0] Near promotion
6 [1.0 1.0 2.0 3.0 3.0 2.0 1.0 1.0] Advanced
5 [0.5 0.5 1.0 2.5 2.5 1.0 0.5 0.5] Center control
4 [0.0 0.0 0.0 2.0 2.0 0.0 0.0 0.0] Central push
3 [0.5 0.0 1.0 0.0 0.0 1.0 0.0 0.5] Development
2 [0.5 0.0 0.0-2.0-2.0 0.0 0.0 0.5] Starting rank
1 [0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0] Invalid
Key Principles:
- Pawns: Advance toward promotion, control center
- Knights: Avoid edges, prefer center
- Bishops: Long diagonals, avoid corners
- Rooks: 7th rank, open files
- Queen: Active but safe squares
- King: Castle position (middlegame), center (endgame)
Black Pieces: Tables are vertically flipped for black's perspective
Multiplier: 0.5 (half a centipawn per bonus point)
Checkmate:
if (checkmate):
if (player is mated):
return SCORE_MIN + depth // Prefer longer mates (from opponent's view)
else:
return SCORE_MAX - depth // Prefer shorter matesStalemate:
if (stalemate):
return 0 // Draw is neutralfunction evaluate(board, playerColor, depth = 0):
if (checkmate):
return mateScore(board, playerColor, depth)
if (stalemate):
return 0
materialScore = evaluateMaterial(board, playerColor)
positionalScore = evaluatePieceSquareTables(board, playerColor)
return materialScore + positionalScoreConcept: Narrow alpha-beta window around expected score from previous iteration
Benefit: ~15% speedup — more cutoffs in stable positions
Implementation: Implemented in src/ai/Search.ts in the iterative deepening loop. Uses ±25cp window for depths ≥ 4, with exponential widening (delta doubles) on fail-high/fail-low. Falls back to full window when delta exceeds 400cp. Search-equivalent — produces identical moves to a full-width search.
Concept: Search first move with full window, rest with null window (zero-window)
Benefit: Faster search if the first move is best (good move ordering)
Implementation: Implemented in src/ai/Search.ts in the negamax() inner loop (and at root when not collecting per-move analysis scores)
Concept: After the search completes, collect all root moves scoring within randomness centipawns of the best move and randomly pick one from that set.
Benefit: The engine occasionally prefers moves with nearly equal scores, making it less predictable across repeated games without degrading tactical accuracy. The maximum loss per move is bounded by the randomness value.
Default: 0 (disabled). Set to a positive value to enable.
Reference values:
| Value | Effect |
|---|---|
| 0 | Fully deterministic — always plays the same move (default) |
| 10 | Very subtle — only nearly-identical moves ever swap |
| 30 | Slight variety — moves within ~½ pawn of best may vary |
| 80 | Noticeable — fun for casual play |
| 200 | Chaotic — may play obviously weaker moves (not recommended) |
Implementation detail:
// Applied in Search.ts at the root level only — never inside the search tree
const threshold = bestScore - randomness;
const candidates = scoredMoves.filter(e => e.score >= threshold);
bestMove = candidates[Math.floor(Math.random() * candidates.length)].move;- Zero search overhead — filtering is applied post-search on already-computed root scores
- PVS disabled at root for the final iteration when randomness > 0 to ensure accurate scores
- Blunders impossible — moves far below the best score are never candidates
- Tactical moves are unaffected — mating moves score thousands of centipawns above alternatives
Concept: If position is good even after skipping a move, prune Benefit: Aggressive pruning in non-zugzwang positions Caution: Must verify not in zugzwang situations
Concept: Search late moves (after ordering) with reduced depth Benefit: Focus search on promising moves Future Enhancement: Reduce depth for moves beyond 4th move
Location: src/types/board.types.ts
Structure:
interface InternalBoard {
// Piece representation
mailbox: Int8Array; // 64-element array, piece per square
// Bitboards for efficient position queries
whitePieces: Bitboard; // All white pieces
blackPieces: Bitboard; // All black pieces
allPieces: Bitboard; // All pieces
whitePawns: Bitboard; // White pawns
// ... one bitboard per piece type per color
// Game state
turn: InternalColor; // WHITE or BLACK
castlingRights: {
whiteShort: boolean;
whiteLong: boolean;
blackShort: boolean;
blackLong: boolean;
};
enPassantSquare: SquareIndex | null;
halfMoveClock: number;
fullMoveNumber: number;
// Cached information
zobristHash: bigint;
isCheck: boolean;
isCheckmate: boolean;
isStalemate: boolean;
}Design Rationale:
- Mailbox + Bitboards: Hybrid approach for flexibility
- Cached Status: Avoid repeated check detection
- Zobrist Hash: Always up-to-date for TT lookups
Location: src/types/move.types.ts
Structure:
interface InternalMove {
from: SquareIndex; // 0-63
to: SquareIndex; // 0-63
piece: Piece; // Moving piece
capturedPiece: Piece; // EMPTY or captured piece
flags: MoveFlag; // Bitfield for move type
promotionPiece?: Piece; // For pawn promotions
}
enum MoveFlag {
NONE = 0,
CAPTURE = 1 << 0, // 0001
CASTLING = 1 << 1, // 0010
EN_PASSANT = 1 << 2, // 0100
PROMOTION = 1 << 3, // 1000
PAWN_DOUBLE_PUSH = 1 << 4, // 10000
}Benefits:
- Compact: Single integer for move type
- Fast Queries: Bitwise operations
- Complete: All information for unmake/remake
Location: src/ai/AIEngine.ts
const LEVEL_CONFIG: Record<AILevel, LevelConfig> = {
1: { baseDepth: 1, extendedDepth: 0, checkExtension: false, qMaxDepth: 0 }, // Beginner
2: { baseDepth: 2, extendedDepth: 0, checkExtension: true, qMaxDepth: 0 }, // Easy
3: { baseDepth: 2, extendedDepth: 1, checkExtension: true, qMaxDepth: 1 }, // Intermediate (default)
4: { baseDepth: 3, extendedDepth: 2, checkExtension: true, qMaxDepth: 2 }, // Advanced
5: { baseDepth: 4, extendedDepth: 3, checkExtension: true, qMaxDepth: 4 }, // Expert
};Adaptive Depth:
The engine uses a simple position-dependent heuristic to pick an effective depth:
- Compute root legal move count (branching factor proxy)
- Count remaining pieces (simplification proxy)
- Start at
baseDepthand add small increments - Clamp the result to:
This allows deeper searches in endgames (where search is fast) while keeping opening/middlegame computation bounded.
Performance: Response time increases exponentially with search depth. Actual performance varies significantly by hardware (CPU, RAM), position complexity, and transposition table size. Use the benchmark script (npm run benchmark) to measure performance on your specific system.
| Optimization | Enabled | Test Time | Speedup |
|---|---|---|---|
| Baseline (none) | No | 16.3s | 1.0× |
| + Transposition Table | Yes | 8.5s | 1.9× |
| + Move Ordering | Yes | 6.2s | 2.6× |
| + Iterative Deepening | Yes | 5.6s | 2.9× |
| All Optimizations | Yes | 5.6s | 2.9× |
Overall Improvement: 65% faster (2.9× speedup)
| Configuration | Nodes | Time |
|---|---|---|
| No optimizations | ~160,000 | 2.1s |
| With optimizations | ~45,000 | 0.7s |
Node Reduction: 72% fewer nodes evaluated
Typical Values (Depth 4 search with default settings):
- Total lookups: ~50,000
- Cache hits: ~35,000 (70% hit rate)
- Stored entries: ~12,000 unique positions
- Memory usage: ~480KB (of 8MB allocated in Node.js, or ~480KB of 4MB in browser)
-
Opening Book
- Pre-computed opening moves
- Format: JSON or binary format
- Location:
src/ai/OpeningBook.ts - Benefit: Instant move in opening phase
-
Endgame Tablebases
- Perfect play for ≤5 pieces
- Syzygy format compatibility
- Location:
src/ai/Tablebase.ts - Benefit: Guaranteed wins/draws in endgames
-
Parallel Search
- Multi-threaded search with Web Workers
- Lazy SMP (Shared Memory Parallelism)
- Location:
src/ai/ParallelSearch.ts - Benefit: Utilize multi-core processors
-
Principal Variation Search (PVS) — Implemented
- Search PV with full window, rest with null window
- Location:
src/ai/Search.ts
-
Null Move Pruning
- Skip move and verify position still good
- Zugzwang detection required
- Location:
Search.tsenhancement - Benefit: 20-30% speedup in middlegame
-
Late Move Reductions (LMR)
- Reduce depth for unlikely moves
- Re-search if promising
- Location:
Search.tsenhancement - Benefit: 15-25% deeper search
-
Aspiration Windows— DONE (~15% speedup) -
Singular Extensions
- Extend search if one move clearly best
- Location:
Search.tsenhancement - Benefit: Better tactical depth
Step 1: Plan
- Identify bottleneck (profiling)
- Research technique
- Design API
Step 2: Implement
// Create new file in src/ai/
export class NewOptimization {
// Implementation
}
// Integrate in Search.ts
import { NewOptimization } from './NewOptimization';
class Search {
private newOpt: NewOptimization;
constructor() {
this.newOpt = new NewOptimization();
}
// Use in search
}Step 3: Test
// Create test in test/unit/ or test/integration/
describe('NewOptimization', () => {
it('should improve performance', () => {
// Test implementation
});
});Step 4: Benchmark
// Add to test/performance/search-benchmark.test.ts
it('should show NewOptimization effectiveness', () => {
// Compare with/without optimization
});Step 5: Document
- Add section to this file
- Update README.md if user-facing
- Add inline code comments
Unit Tests:
npm test -- test/unit/Integration Tests:
npm test -- test/integration/ai.test.tsPerformance Benchmarks:
npm test -- test/performance/search-benchmark.test.tsManual Testing:
import { Game } from './src';
const game = new Game();
console.time('AI Move');
const move = game.ai({ level: 3 });
console.timeEnd('AI Move');
console.log('Move:', move);Node.js Built-in Profiler:
node --prof test-script.js
node --prof-process isolate-*-v8.log > processed.txtChrome DevTools:
node --inspect-brk test-script.js
# Open chrome://inspectEnable Debug Logging:
// In Search.ts, add logging
private alphaBeta(...) {
console.log(`Depth: ${depth}, Alpha: ${alpha}, Beta: ${beta}`);
// ... rest of function
}Visualize Search Tree:
// Track nodes visited
private searchTree: any[] = [];
private alphaBeta(...) {
this.searchTree.push({ depth, alpha, beta, moves });
// ... search
}
// After search
console.log(JSON.stringify(this.searchTree, null, 2));This AI implementation represents a modern, efficient chess engine suitable for web applications and Node.js environments. The combination of classical algorithms (minimax, alpha-beta) with contemporary optimizations (transposition table, move ordering, iterative deepening) provides strong play at reasonable computational cost.
Key Achievements:
- ✅ 65% performance improvement
- ✅ Competitive play at all difficulty levels
- ✅ Clean, maintainable architecture
- ✅ Comprehensive test coverage
- ✅ Full TypeScript type safety
For questions or contributions, see the main project repository.