Add MVV-LVA capture ordering, check extensions, and delta pruning

[luccabb]

Summary

Three search improvements that compound together:

1. MVV-LVA capture ordering in main search: Replace random shuffle of captures with Most Valuable Victim - Least Valuable Attacker sorting using fast integer lookups. Promotions are also prioritized.

2. Check extensions: When a move puts the opponent in check, extend the search by 1 ply to resolve tactical check sequences that would otherwise be cut off by the horizon effect.

3. Delta pruning in quiescence: If the stand-pat score plus the maximum possible capture gain (queen value + margin) is still below alpha, prune the entire quiescence node.

Benchmark results (depth 4)

Metric	Before	After	Change
Total nodes	4,760,507	3,382,748	−29.0%
NPS	22,634	24,444	+8.0%
Total time	210.32s	138.38s	−34.2%

Notable per-position improvements:

• Position 2: 136,937 → 29,205 (−78.7%)
• Position 37: 597,097 → 87,126 (−85.4%)
• Position 32: 435,139 → 196,560 (−54.8%)

Some positions show increased nodes due to check extensions — this is intentional, as the engine now searches deeper to find tactical solutions involving checks.

Local Stockfish Benchmark

Settings: 20 games, Stockfish skill 3, 10s/move, no opening book.

	W	L	D	Win Rate
Master (baseline)	19	1	0	95%
This PR	18	1	1	93%

Use /run-stockfish-benchmark for CI validation with opening book and longer time control.

Test plan

• All alpha_beta unit tests pass (16/16)
• /run-nps-benchmark
• /run-stockfish-benchmark

[github-actions]

Benchmarks

The following benchmarks are available for this PR:

Command	Description
/run-nps-benchmark	NPS speed benchmark (depth 5, 48 positions)
/run-stockfish-benchmark	Stockfish strength benchmark (300 games)

Post a comment with the command to trigger a benchmark run.

[greptile-apps]

Greptile Summary

This PR adds three search improvements to the alpha-beta engine: MVV-LVA capture ordering, check extensions, and delta pruning in quiescence search.

• MVV-LVA ordering (move_ordering.py): Replaces random capture shuffling with a fast integer-based Most Valuable Victim - Least Valuable Attacker sort. Promotions are correctly prioritized. Implementation is sound.
• Delta pruning (alpha_beta.py): Correctly prunes quiescence nodes where even the best possible capture can't raise the score above alpha. Uses the midgame queen value + 200 as the margin, which is reasonable.
• Check extensions (alpha_beta.py): Extends search by 1 ply when a move gives check. However, there is no guard against unbounded recursion — perpetual check sequences keep depth constant (depth - 1 + 1 = depth), and negamax has no repetition detection or maximum-ply cap. This could cause stack overflow in positions with long forced check sequences.

Confidence Score: 2/5

• Check extensions lack a recursion guard and could cause stack overflow on perpetual-check positions.
• The MVV-LVA ordering and delta pruning are correctly implemented. However, the check extension has no maximum depth or ply limit, and negamax lacks repetition detection. In positions with perpetual checks, the search depth never decreases, risking unbounded recursion. This is a functional correctness concern that could crash the engine on certain board positions.
• Pay close attention to moonfish/engines/alpha_beta.py — the check extension logic at lines 280-284 needs a depth/ply guard.

Important Files Changed

Filename	Overview
moonfish/engines/alpha_beta.py	Adds delta pruning (correct) and check extensions (missing depth/recursion guard for perpetual check positions).
moonfish/move_ordering.py	Adds MVV-LVA capture ordering with correct scoring logic; unused MG_PIECE_VALUES import.

Flowchart

flowchart TD
    A[negamax called with depth d] --> B[organize_moves with MVV-LVA ordering]
    B --> C{For each move}
    C --> D[board.push move]
    D --> E{board.is_check?}
    E -->|Yes| F["extension = 1\n(depth stays at d)"]
    E -->|No| G["extension = 0\n(depth decreases to d-1)"]
    F --> H["negamax(depth - 1 + 1 = d)"]
    G --> I["negamax(depth - 1)"]
    H --> J{depth <= 0?}
    I --> J
    J -->|Yes| K[quiescence_search]
    J -->|No| C
    K --> L{stand_pat + DELTA_MARGIN < alpha?}
    L -->|Yes| M[Delta prune: return alpha]
    L -->|No| N[Search tactical moves]
    N --> O[Return best score]

Loading

_{Last reviewed commit: a572196}

[greptile-apps]

_{2 files reviewed, 2 comments}

_{Edit Code Review Agent Settings | Greptile}

[greptile-apps]

Unbounded check extensions risk stack overflow

When a move gives check, the extension keeps depth at the same level (depth - 1 + 1 = depth). In positions with perpetual or long check sequences, this causes the search to never reduce depth, potentially recursing until Python's stack limit is hit.

There is no maximum-depth guard in negamax, and the repetition detection (is_repetition) only exists in quiescence search — not here. While the transposition table might catch some repeated positions, its cache key includes (alpha, beta) which vary across different branches, so there's no guarantee of termination.

A common safeguard is to limit total extensions (e.g., track cumulative ply from root and cap extensions once a maximum ply is reached):

# Example: cap total search depth at 2x the nominal depth
extension = 1 if board.is_check() and (current_ply < 2 * self.config.negamax_depth) else 0

Alternatively, adding board.is_repetition(2) as a draw-return early in negamax (similar to what quiescence already does) would prevent infinite check cycles.

[greptile-apps]

Unused import MG_PIECE_VALUES

MG_PIECE_VALUES is imported but never used in this file — the new MVV-LVA logic uses _MVV_LVA_VALUES instead.

Suggested change

MG_PIECE_VALUES,