← Back
Home › Systems › Games

chess-engine

chess engine: rules and move generation, search, evaluation, opening book, pondering, UCI

Stockfish, Leela

SystemTechniques · 6Primitives · 20 chess-engine Alpha-beta searchgame-ai · medium: Minimax that skips branches which cannot change the result; with iterative deepening, PVS and aspiration windows it is the core of classical adversarial search.›Parallel tree searchgame-ai · medium: Search one game tree on many threads: shared lossy transposition table (Lazy SMP), split points (YBWC), virtual loss for MCTSRetrograde analysisgame-ai · medium: Solve a finite game backwards from terminal states; compact state indexing and compressed win/draw/loss and distance tablesSequential probability ratio teststatistics · medium: Add up the log-likelihood ratio per observation and stop when it crosses a fixed bound; the least data of any test with the same error rates (for two point hypotheses).›Monte Carlo tree searchgame-ai · medium: Grows a search tree one simulation at a time, picking visits by a bandit rule (UCT or PUCT) and backing up averages; the search behind AlphaZero.›Multi-armed banditsmachine-learning · medium: Choose among K options repeatedly while learning their payoffs: epsilon-greedy, UCB1 and Thompson sampling keep total regret low where a fixed split or a fixed exploration rate pays forever.›Candidate ordering and pruninggame-ai · low: The heuristics that make alpha-beta and branch-and-bound fast: try likely-best candidates first (TT, captures, killers, history) and skip or reduce the rest (null move, LMR, futility).›Search time managementgame-ai · low: Allocate thinking time per move from clock, increment and search instabilityTransposition tablegame-ai · low: A fixed-size, lossy hash table of search results keyed by a state hash; gives ordering and cutoffs for repeated states, shared lock-free between threads.›Zobrist hashinggame-ai · low: A state's hash is the XOR of one random 64-bit key per (item, slot) fact that holds in it, updated in a few XORs per change.›Bitboardsgame-ai · low: One 64-bit word per set of up to 64 items, so set algebra becomes shifts, ANDs and table lookups; magic bitboards give ray queries in one multiply.›Evaluation functionsgame-ai · low: Score a game state without search: weighted features or lookup tables, interpolated by game phase; learned evaluators are variantsNNUE incremental evaluationgame-ai · low: Efficiently updatable neural network: a huge sparse first layer whose output (the accumulator) is patched per move, then tiny int8 layers; fast neural eval.›SIMD programminghardware-os · low: Process 4-16 lanes per instruction with AVX2, AVX-512 or NEON via Rust std::arch, with runtime dispatch and a portable fallback.›Virtual memory and the TLBhardware-os · low: How page tables and TLBs translate every address, what TLB reach means, and when 2 MiB or 1 GiB huge pages pay off on Linux.›Memory orderingconcurrency · low: What Relaxed, Acquire, Release and SeqCst atomics actually guarantee, what they cost on x86 and ARM, and which one each pattern needs.›Huffman codingcompression · low: Optimal prefix code with whole-bit codeword lengths; table-driven decoding at about one symbol per few cycles, the entropy stage of DEFLATE, JPEG and zstd literals.›Compact state encodingdata-structures · low: Pack a game position into a few fixed bytes (24 for chess: occupancy bitboard plus nibbles) for training data and dedupeBFS and DFSgraphs · low: The two basic graph traversals; BFS gives hop distances and levels, DFS gives discovery/finish order for cycles, components and topological order.›Loglikelihood scoringmachine-learning · low: Scoring choices by summed token log-probabilities, normalization by length, perplexity computationBayesian rate estimationstatistics · low: Estimate a conversion or event rate from few observations with a Beta-Binomial or Gamma-Poisson update: two counters, an honest interval, and P(B beats A) directly.›PRNGs (PCG, xoshiro)numerics · low: Small, fast, statistically strong non-cryptographic generators: PCG32 and xoshiro256**, with seeding, parallel streams and unbiased ranges.›+ 4 more primitives

Similar systems

Share the most building blocks with this one.

nnue-training 22 %go-engine 20 %fair-play 16 %