DEV Community

Cover image for Quack-Mate: a chess engine in SQL
Roberto Cornacchia
Roberto Cornacchia

Posted on • Originally published at swingbit.github.io

Quack-Mate: a chess engine in SQL

#chess #duckdb #showdev #sql

We have all seen SQL pushed past its comfort zone to build things like 3D renderers or cellular automata. Naturally, I wondered about a classic computer science challenge: could you write a functional chess engine purely inside an analytical database using standard relational algebra?

The answer is yes. In fact, you can express the entire engine—generating moves, validating legality, scoring positions, and bubbling up the best strategy—inside a single WITH RECURSIVE query.

One grand recursive CTE

Recursive CTEs can handle a minimax tree search, just like the recursive minimax algorithm is implemented with imperative languages. By combining a top-down expansion of the board states with a bottom-up aggregation pass, DuckDB can execute a full minimax-based move search natively:

WITH RECURSIVE
    -- Expansion CTE: Top-down
    search_tree AS (
        -- Expansion base case: Root Node
        SELECT id, state, 0 as depth, is_white_turn FROM root

        UNION ALL

        -- Expansion step
        SELECT child.id, child.state, parent.depth + 1, child.is_white_turn
        FROM search_tree parent
        JOIN possible_moves child ON ...
        WHERE parent.depth < MAX_DEPTH
    ),

    -- Minimax CTE: Bottom-up
    minimax AS (
        -- Back-propagation base case:
        -- Target depth or terminal nodes
        SELECT id, parent_id, depth, static_eval(state) as score, 0 as step
        FROM search_tree s
        WHERE s.depth = MAX_DEPTH
           OR NOT EXISTS (SELECT 1 FROM search_tree child WHERE child.parent_id = s.id)

        UNION ALL

        -- Back-propagation step
        SELECT 
            parent.id, parent.parent_id, parent.depth,
            CASE WHEN parent.is_white_turn
                 THEN MAX(child.score) -- White maximises
                 ELSE MIN(child.score) -- Black minimises
            END as score,
            prev.step + 1 as step
        FROM (SELECT DISTINCT step FROM minimax) prev
        JOIN search_tree parent ON parent.depth = MAX_DEPTH - (prev.step + 1)
        JOIN recurring.minimax child ON child.parent_id = parent.id
        GROUP BY parent.id, parent.parent_id, parent.depth, parent.is_white_turn, prev.step
    )
SELECT score FROM minimax WHERE depth = 0;
Enter fullscreen mode Exit fullscreen mode

This query is obviously slightly simplified, but the structure is that of the actual production query. The production query, expanded with real move generations and all checks, is about 570 lines of SQL.

It actually works. It plays legal, sound chess completely inside a single database transaction.

But there is a massive catch. A recursive CTE query is inherently a Breadth-First Search (BFS). It has to hold every single board state of every single depth layer in memory simultaneously. Because it executes globally across rows, introducing classic Alpha-Beta pruning thresholds mid-query is practically impossible.

If you try to look ahead past 3 plies (one and a half full turns), the combinatorial explosion takes over, and the query will instantly eat all your RAM.

Batched Principal Variation Search (BPVS)

To make the engine actually playable with more than 3 plies without triggering an Out-Of-Memory crash, I had to transition from a single monolithic query to a hybrid architecture called Batched Principal Variation Search (BPVS).

All core calculations—board tracking, move validation, and position scoring—remain 100% encapsulated inside SQL queries executed by DuckDB. However, a thin external JavaScript loop acts as a coordinator to handle Iterative Deepening.

The "Batched" part is the secret sauce that makes this viable in SQL:

  • Pruning via Slices: Sequential Alpha-Beta pruning checks moves one by one, which is too slow for database round-trips. Conversely, processing 40 moves at once prevents updating pruning thresholds mid-query.
  • Progressive Chunking: BPVS solves this by grouping generated moves into small, prioritised horizontal slices (Batch sizes of 1, 3, 8, then 64) using SQL Window Functions.
  • Dynamic Thresholding: The database evaluates a small batch at full depth to quickly establish a baseline threshold (PVS). The JavaScript coordinator reads this bound and dynamically injects it as a hardcoded literal straight into the WHERE clause of the next SQL batch, allowing DuckDB to prune away thousands of hopeless branches before launching heavy relational joins.

The Optimisation Stack

To make this hybrid model performant enough for real-time play, I had to implement a complete stack of traditional chess engine heuristics adapted for relational tables:

  • Vectorised Bitboards: Storing the board state as a single row with 12 unsigned 64-bit integer columns (UBIGINT), reducing piece movement to instant binary operations.
  • Backwards Legality Probing: Skipping complex pin masks entirely by applying moves in bulk, then running an EXISTS subquery that traces enemy attacks backwards starting from the King's square.
  • Move Ordering Heuristics: Prioritising moves using custom weights for Transposition Table hits, MVV-LVA captures, Killer moves, and History tables.
  • Aggressive Selective Pruning: Injecting Reverse Futility Pruning, Forward Futility Pruning, Late Move Pruning, and Late Move Reductions straight into query scans to slice off entire sub-trees early.
  • Quiescence Search: Extending leaf nodes along active tactical capture lines to avoid the "horizon effect."

Reality Check: How Does It Perform?

Let's be clear: even with all these optimisations, it is significantly slower than a traditional imperative chess engine. A depth-4 search still takes a couple of seconds, and multi-threading offers little help because game-tree traversal is inherently sequential; adding more cores simply creates lock contention and thread coordination overhead inside DuckDB.

This comes down to the Granularity Paradox. In chess, pruning is far more important than raw throughput. The pruning requirement forces us to segment the search into many small queries, which is the opposite of what analytical databases like DuckDB are built for.

But defeating Stockfish was never the point. The project proves that with the right indexing, data schema, and batched orchestration, an analytical engine can be bent to execute highly complex, deep algorithmic tree structures.

Quack-Mate

Explore the Code and Play It

The entire project is open-source and open for inspection:

Top comments (0)