Chess Programming Concepts Guide

This guide explains the core concepts used in ChessML and modern chess engines. Each document focuses on why the technique matters and how to implement it, with clear examples and practical advice.

Core Concepts (Foundational)

These are the building blocks every chess engine needs:

Bitboards

Elo Impact: ~100-200 Elo
64-bit integers representing chess board state. Enables parallel operations on all squares simultaneously using bitwise operations. Essential for fast move generation.

Magic Bitboards

Elo Impact: ~50-100 Elo
Pre-computed lookup tables for sliding piece (rook, bishop, queen) attack generation. Uses “magic numbers” to hash occupancy patterns into table indices for constant-time lookups.

Zobrist Hashing

Elo Impact: Enables transposition tables (~200-300 Elo)
Fast incremental position hashing using XOR operations. Required for transposition table implementation. Positions can be compared using 64-bit keys instead of full board comparison.

Search Techniques (Critical for Strength)

These determine how deeply and efficiently your engine can search:

Alpha-Beta Pruning

Elo Impact: ~1000+ Elo vs basic minimax
The foundation of modern chess search. Prunes branches that provably can’t affect the final decision, typically reducing nodes searched by 50-90%. Works best with good move ordering.

Transposition Tables

Elo Impact: ~200-300 Elo
Cache position evaluations to avoid re-searching identical positions reached through different move orders. Requires Zobrist hashing for fast position keys. Typically saves 30-40% of search effort at depth 6+.

Elo Impact: ~150-250 Elo
Extends search beyond fixed depth to resolve tactical sequences (captures, checks). Prevents the “horizon effect” where the engine stops searching mid-tactics and misjudges positions. Uses SEE to prune losing captures.

Null Move Pruning

Elo Impact: ~100-150 Elo
Aggressive pruning by giving the opponent a free move. If they still can’t beat beta, the position is too good and can be pruned. Reduces search tree by 40-60% with minimal accuracy loss.

Late Move Reductions (LMR)

Elo Impact: ~100-200 Elo
Search later moves (likely weaker) at reduced depth. If one looks promising at shallow search, re-search at full depth. Relies heavily on good move ordering. Effectively increases search depth by 1-2 plies.

Move Ordering (Force Multiplier)

Good move ordering is critical for alpha-beta efficiency:

Move Ordering

Elo Impact: ~100-200 Elo
The art of trying promising moves first. Combines hash moves, capture ordering, killer moves, history heuristic, and countermoves. Good ordering can effectively double alpha-beta search depth.

Static Exchange Evaluation (SEE)

Elo Impact: ~30-80 Elo
Calculates material outcome of capture sequences without search. Essential for ordering captures in move ordering and pruning bad captures in quiescence search.

Evaluation (Understanding Positions)

How the engine judges who’s winning:

Evaluation Function

Elo Impact: ~200-400 Elo
Assigns numerical scores to positions. Includes material counting, piece-square tables, pawn structure, king safety, and positional factors. The “eyes” of the engine.

Opening Knowledge

Pre-computed opening theory:

Opening Books

Elo Impact: ~50-150 Elo
Database of pre-analyzed opening positions. Saves time in known positions and ensures solid opening play. Typically uses Polyglot format for compatibility.

Learning Path

Beginner (Build a Basic Engine)

  1. Bitboards - Represent the board efficiently
  2. Alpha-Beta Pruning - Basic search
  3. Evaluation Function - Material + piece-square tables

Result: ~1500-1800 Elo engine

Intermediate (Add Intelligence)

  1. Zobrist Hashing - Position keys
  2. Transposition Tables - Cache results
  3. Move Ordering - Basic ordering (hash + MVV-LVA)
  4. Quiescence Search - Tactical stability

Result: ~2000-2200 Elo engine

Advanced (Optimize Performance)

  1. Magic Bitboards - Fast attack generation
  2. Null Move Pruning - Aggressive pruning
  3. Late Move Reductions - Deeper search
  4. Static Exchange Evaluation - Better capture evaluation
  5. Opening Books - Opening knowledge

Result: ~2400+ Elo engine

Quick Reference

Elo Gains Summary

Technique Elo Gain Complexity Priority
Alpha-Beta Pruning ~1000 Medium Critical
Transposition Tables ~200-300 Medium Critical
Evaluation Function ~200-400 Medium Critical
Quiescence Search ~150-250 Medium High
Move Ordering ~100-200 Medium High
Null Move Pruning ~100-150 Low High
Late Move Reductions ~100-200 High High
Bitboards ~100-200 High Medium
Opening Books ~50-150 Low Medium
Magic Bitboards ~50-100 High Medium
SEE ~30-80 Medium Medium
Zobrist Hashing Enables TT Low Critical

Implementation Order

Phase 1 - Basic Functionality:

  • Bitboards (board representation)
  • Alpha-Beta (search)
  • Basic Evaluation (material + PST)

Phase 2 - Core Improvements:

  • Zobrist Hashing
  • Transposition Tables
  • Quiescence Search
  • Basic Move Ordering

Phase 3 - Optimizations:

  • Null Move Pruning
  • Late Move Reductions
  • Advanced Move Ordering (killers, history, countermoves)
  • SEE

Phase 4 - Polish:

  • Magic Bitboards
  • Opening Books
  • Evaluation Tuning

Additional Resources

Contributing

Found an error or want to improve these docs? See CONTRIBUTING.md.

These documents are written for newcomers to chess programming. The goal is understanding over completeness — enough detail to implement effectively, not exhaustively.

Table of contents