Open
Conversation
Track 2 non-capture moves per ply that caused beta cutoffs (killer moves). These are tried after captures but before other quiet moves, improving move ordering and increasing cutoff rates. Benchmark (depth 4, 48 positions): - Nodes: 4,760,507 → 2,880,079 (−39.5%) - NPS: 22,634 → 24,985 (+10.4%) - Time: 210.32s → 115.27s (−45.2%)
Owner
Author
|
/run-nps-benchmark |
BenchmarksThe following benchmarks are available for this PR:
Post a comment with the command to trigger a benchmark run. |
Greptile SummaryAdds the killer move heuristic to the alpha-beta search engine, a well-known chess engine optimization that tracks non-capture moves causing beta cutoffs and prioritizes them in sibling nodes at the same ply. The implementation stores up to 2 killer moves per ply in a table initialized at the root, passes it through recursive
Confidence Score: 4/5
|
| Filename | Overview |
|---|---|
| moonfish/engines/alpha_beta.py | Adds killer move heuristic with ply tracking and killer table initialization. The NUM_KILLERS constant is defined but unused. Core logic is correct — killer moves are stored on beta-cutoff for non-captures and properly passed through recursive calls. |
| moonfish/move_ordering.py | Integrates killer moves into move ordering (captures → killers → quiet). Implementation is correct but has a redundant legality check — iterates legal moves then separately builds legal_moves_set to verify killers. |
Sequence Diagram
sequenceDiagram
participant SM as search_move
participant NM as negamax (ply=0)
participant NM1 as negamax (ply=1)
participant OM as organize_moves
participant KT as killers table
SM->>KT: Initialize [[None,None]] × (depth+20)
SM->>NM: negamax(board, depth, killers)
NM->>KT: Read killers[ply=0]
NM->>OM: organize_moves(board, killers=ply_killers)
OM-->>NM: captures + killer_moves + quiet_moves
loop For each move
NM->>NM1: negamax(board, depth-1, ply=1, killers)
NM1->>KT: Read killers[ply=1]
NM1->>OM: organize_moves(board, killers=ply_killers)
OM-->>NM1: ordered moves
NM1-->>NM: score
alt Beta cutoff on quiet move
NM->>KT: _store_killer(killers, ply=0, move)
Note over KT: Shift slot[1]=slot[0], slot[0]=move
end
end
NM-->>SM: best_score, best_move
Last reviewed commit: ba49e0a
![greptile-apps[bot]](https://avatars.githubusercontent.com/in/867647?s=60&v=4){kind=small}
| NULL_MOVE = Move.null() | ||
|
|
||
| # Number of killer moves to store per ply | ||
| NUM_KILLERS = 2 |
There was a problem hiding this comment.
Unused constant NUM_KILLERS
NUM_KILLERS is defined here but never referenced. The killer table initialization on line 347 hardcodes [None, None], and _store_killer uses literal indices [0] and [1]. Consider either using this constant in both places or removing it to avoid confusion.
Suggested change
| NUM_KILLERS = 2 |
Comment on lines
34
to
+53
| for move in board.legal_moves: | ||
| if board.is_capture(move): | ||
| captures.append(move) | ||
| elif move in killer_set: | ||
| # Skip killers from non_captures; we'll insert them after captures | ||
| continue | ||
| else: | ||
| non_captures.append(move) | ||
|
|
||
| random.shuffle(captures) | ||
| random.shuffle(non_captures) | ||
| return captures + non_captures | ||
|
|
||
| # Insert legal killer moves between captures and quiet moves | ||
| killer_moves = [] | ||
| if killers is not None: | ||
| legal_moves_set = set(board.legal_moves) | ||
| for k in killers: | ||
| if k is not None and k in legal_moves_set and not board.is_capture(k): | ||
| killer_moves.append(k) | ||
|
|
There was a problem hiding this comment.
Redundant legality check for killer moves
Killer moves are filtered from non_captures at line 37-39 using killer_set, but then a second pass at lines 48-52 re-validates them against legal_moves_set. Since the first loop already iterates all legal moves, any killer move that wasn't seen in the loop is guaranteed to be illegal (or a capture). You could track "seen legal killers" in the first loop and avoid constructing legal_moves_set entirely:
Suggested change
| for move in board.legal_moves: | |
| if board.is_capture(move): | |
| captures.append(move) | |
| elif move in killer_set: | |
| # Skip killers from non_captures; we'll insert them after captures | |
| continue | |
| else: | |
| non_captures.append(move) | |
| random.shuffle(captures) | |
| random.shuffle(non_captures) | |
| return captures + non_captures | |
| # Insert legal killer moves between captures and quiet moves | |
| killer_moves = [] | |
| if killers is not None: | |
| legal_moves_set = set(board.legal_moves) | |
| for k in killers: | |
| if k is not None and k in legal_moves_set and not board.is_capture(k): | |
| killer_moves.append(k) | |
| for move in board.legal_moves: | |
| if board.is_capture(move): | |
| captures.append(move) | |
| elif move in killer_set: | |
| # Skip killers from non_captures; we'll insert them after captures | |
| killer_set.discard(move) # mark as legal | |
| continue | |
| else: | |
| non_captures.append(move) | |
| random.shuffle(captures) | |
| random.shuffle(non_captures) | |
| # Insert legal killer moves between captures and quiet moves | |
| # Only include killers that were discarded above (i.e., legal and non-capture) | |
| killer_moves = [] | |
| if killers is not None: | |
| for k in killers: | |
| if k is not None and k not in killer_set and not board.is_capture(k): | |
| killer_moves.append(k) |
Note: If this suggestion doesn't match your team's coding style, reply to this and let me know. I'll remember it for next time!
⚡ NPS Benchmark Results
Per-position breakdown |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
1 participant
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Summary
plyparameter to negamax for proper killer table indexingThe killer move heuristic is one of the most effective chess engine improvements because quiet moves that cause a cutoff in one position often cause cutoffs in sibling positions at the same depth.
Benchmark (depth 4, 48 positions)
Local Stockfish Benchmark
Settings: 20 games, Stockfish skill 3, 10s/move, no opening book.
Use
/run-stockfish-benchmarkfor CI validation with opening book and longer time control.Test plan
/run-nps-benchmarkfor CI validation/run-stockfish-benchmarkfor strength validation