[5/6] Add Late Move Reductions (LMR) and Principal Variation Search (PVS)

[luccabb]

Summary

• Add Late Move Reductions (LMR) to reduce search depth for late quiet moves
• Add Principal Variation Search (PVS) for faster searches with good move ordering

Details

Late Move Reductions (LMR)

Reduce search depth for moves that are unlikely to be the best:

Conditions:

• Depth >= 3 (need sufficient depth to reduce)
• Move index >= 3 (first few moves get full depth)
• Not in check (check positions are critical)
• Quiet move (no capture, no check, no promotion)

Implementation:

reduction = 1  # Reduce by 1 ply
board_score = negamax(depth - 1 - reduction, ...)
if board_score > alpha:
    board_score = negamax(depth - 1, ...)  # Re-search at full depth

Principal Variation Search (PVS)

Optimize search based on the assumption that the first move is best:

Implementation:

• First move: full alpha-beta window search
• Later moves: zero window search first (faster)
• If zero window beats alpha, re-search with full window

if move_index == 0:
    score = negamax(alpha=-beta, beta=-alpha)  # Full window
else:
    score = negamax(alpha=-alpha-1, beta=-alpha)  # Zero window
    if score > alpha:
        score = negamax(alpha=-beta, beta=-alpha)  # Re-search

Test plan

• All 64 unit tests pass
• Verified LMR only applies to late quiet moves
• Verified PVS re-searches when needed

---

🤖 Generated with Claude Code

[github-actions]

🔬 Stockfish Benchmark Results

vs Stockfish Skill Level 3

Metric	Wins	Losses	Draws	Total	Win %
Overall	0	100	0	100	0%
As White	0	50	0	50	0%
As Black	0	50	0	50	0%

vs Stockfish Skill Level 4

Metric	Wins	Losses	Draws	Total	Win %
Overall	0	100	0	100	0%
As White	0	50	0	50	0%
As Black	0	50	0	50	0%

vs Stockfish Skill Level 5

Metric	Wins	Losses	Draws	Total	Win %
Overall	0	100	0	100	0%
As White	0	50	0	50	0%
As Black	0	50	0	50	0%

Configuration

• 5 chunks × 20 rounds × 3 skill levels = 300 total games
• Each opening played with colors reversed (-repeat) for fairness
• Moonfish: 60s per move
• Stockfish: 60+5 time control

[luccabb]

/run-nps-benchmark

[github-actions]

⚡ NPS Benchmark Results

Metric	Value
Depth	5
Positions	48
Total nodes	8113081
Total time	955.93s
Nodes/second	8487

Node count is the primary signal — it's deterministic and catches search behavior changes. If the node count changes, the PR changed search behavior. NPS is informational only (CI runner performance varies).

Per-position breakdown

Position  1/48: nodes=21527      time=2.68s  nps=8036
Position  2/48: nodes=276259     time=32.86s  nps=8408
Position  3/48: nodes=25672      time=2.16s  nps=11898
Position  4/48: nodes=265962     time=28.94s  nps=9189
Position  5/48: nodes=134738     time=16.02s  nps=8408
Position  6/48: nodes=40826      time=4.86s  nps=8401
Position  7/48: nodes=90294      time=13.31s  nps=6784
Position  8/48: nodes=186695     time=22.37s  nps=8346
Position  9/48: nodes=266054     time=33.97s  nps=7831
Position 10/48: nodes=387416     time=47.62s  nps=8135
Position 11/48: nodes=89774      time=10.50s  nps=8546
Position 12/48: nodes=157450     time=20.82s  nps=7562
Position 13/48: nodes=197050     time=23.31s  nps=8454
Position 14/48: nodes=70904      time=9.67s  nps=7334
Position 15/48: nodes=79628      time=9.23s  nps=8629
Position 16/48: nodes=83357      time=9.33s  nps=8937
Position 17/48: nodes=3745       time=0.30s  nps=12458
Position 18/48: nodes=2160       time=0.16s  nps=13440
Position 19/48: nodes=9617       time=0.88s  nps=10952
Position 20/48: nodes=46285      time=3.76s  nps=12301
Position 21/48: nodes=12882      time=1.14s  nps=11256
Position 22/48: nodes=2051       time=0.13s  nps=16223
Position 23/48: nodes=983        time=0.06s  nps=15638
Position 24/48: nodes=4482       time=0.39s  nps=11537
Position 25/48: nodes=9388       time=0.76s  nps=12307
Position 26/48: nodes=21963      time=1.71s  nps=12823
Position 27/48: nodes=27647      time=2.58s  nps=10731
Position 28/48: nodes=181271     time=17.91s  nps=10119
Position 29/48: nodes=55216      time=4.92s  nps=11224
Position 30/48: nodes=3281       time=0.23s  nps=14582
Position 31/48: nodes=138838     time=15.13s  nps=9174
Position 32/48: nodes=779054     time=92.29s  nps=8441
Position 33/48: nodes=396217     time=56.85s  nps=6969
Position 34/48: nodes=205228     time=21.12s  nps=9717
Position 35/48: nodes=435863     time=44.90s  nps=9706
Position 36/48: nodes=1760166    time=209.58s  nps=8398
Position 37/48: nodes=1247314    time=155.75s  nps=8008
Position 38/48: nodes=1558       time=0.09s  nps=17319
Position 39/48: nodes=2433       time=0.17s  nps=14544
Position 40/48: nodes=2950       time=0.10s  nps=31045
Position 41/48: nodes=5493       time=0.40s  nps=13778
Position 42/48: nodes=18868      time=1.64s  nps=11495
Position 43/48: nodes=1473       time=0.10s  nps=15358
Position 44/48: nodes=16998      time=1.55s  nps=10995
Position 45/48: nodes=18524      time=1.80s  nps=10294
Position 46/48: nodes=327527     time=31.90s  nps=10268
Position 47/48: nodes=0          time=0.00s  nps=0  (terminal)
Position 48/48: nodes=0          time=0.00s  nps=0  (terminal)