fn run_internal<const ROOT: bool, const PV: bool>(
context: &mut SearchContext,
depth: i8,
ply: u16,
alpha: i16,
beta: i16,
allow_null_move: bool,
friendly_king_checked: bool,
previous_move: Move
) -> i16
Expand description
Entry point of the regular search, with generic ROOT
parameter indicating if this is the root node where the moves filterigh might happen, and PV
parameter
determining if the current node is a PV (principal variation) node in the PVS framework. The implementation contains a typical alpha-beta approach, together with
a bunch of reductions and prunings to optimize search. The most important parameter here, context
, contains the current state of the search, board state,
statistics, and is passed by reference to all nodes. Besides obvious parameters like depth
, ply
, alpha
and beta
, there’s also allow_null_move
which prevents two null move checks in a row, and friendly_king_checked
which is used to share friendly king check status between nodes (it’s always
calculated one depth earlier, as it’s used as one of the LMR constraints).
Search steps for PV node:
- test of abort flag
- test of initial constraints: abort flag, forced depth
- test if the enemy king is checked
- test if there’s threefold repetition draw, fifty move rule draw or insufficient material draw
- check extensions (https://www.chessprogramming.org/Check_Extensions)
- switch to the quiescence search if the depth is equal to zero
- read from the transposition table, return score if possible or update alpha/beta (https://www.chessprogramming.org/Transposition_Table)
- internal iterative reduction (https://chessprogrammingwiki.netlify.app/internal_iterative_reductions/)
- main loop:
- filter moves (if
ROOT
is set) - late move reduction (https://www.chessprogramming.org/Late_Move_Reductions)
- PVS framework (https://www.chessprogramming.org/Principal_Variation_Search)
- filter moves (if
- test if stalemate draw is detected
- update transposition table
Search steps for non-PV node:
- test of abort flag
- test of initial constraints: abort flag, forced depth, max nodes count
- test if the enemy king is checked
- test if there’s threefold repetition draw, fifty move rule draw or insufficient material draw
- check extensions (https://www.chessprogramming.org/Check_Extensions)
- switch to the quiescence search if the depth is equal to zero
- read from the transposition table, return score if possible or update alpha/beta (https://www.chessprogramming.org/Transposition_Table)
- internal iterative reduction (https://chessprogrammingwiki.netlify.app/internal_iterative_reductions/)
- razoring (https://www.chessprogramming.org/Razoring)
- static null move pruning (https://www.chessprogramming.org/Reverse_Futility_Pruning)
- null move pruning (https://www.chessprogramming.org/Null_Move_Pruning)
- main loop:
- filter moves (if
ROOT
is set) - late move pruning (https://www.chessprogramming.org/Futility_Pruning#MoveCountBasedPruning)
- late move reduction (https://www.chessprogramming.org/Late_Move_Reductions)
- PVS framework (https://www.chessprogramming.org/Principal_Variation_Search)
- filter moves (if
- test if stalemate draw is detected
- update transposition table