Implementation of the main Alpha-Beta search algorithm. More...

#include <Negamax.h>

Inheritance diagram for Negamax:

Collaboration diagram for Negamax:

[legend]

Public Member Functions
	Negamax (IEvaluator &eval, TranspositionTable &table, std::shared_ptr< SearchSharedData > shared, bool isMainThread, int threadId=0)
	Constructs a new Negamax search instance.
Move	startSearch (Board &root, const SearchParams &params) override
	Starts the search process on the given root board.
void	stop () override
	Asynchronously signals the search to stop immediately.
bool	isSearching () const override
	Checks if the search algorithm is currently running.
void	setInfoCallback (InfoCallback callback) override
	Sets the callback function for periodic information updates.
uint64_t	getNodes () const override
	Retrieves the total number of nodes evaluated by the search algorithm.
Public Member Functions inherited from ISearch
virtual	~ISearch ()=default

Private Member Functions
uint64_t	getPawnKey (const Board &board) const
	Computes a hash key based on the pawn structure.
uint64_t	getNonPawnKey (const Board &board, Color c) const
	Computes a hash key based on non-pawn pieces of a given color.
int	alphaBeta (Board &board, int depth, int alpha, int beta, int ply, bool allowNull, int extensions, bool prevWasCapture=false, bool cutnode=false, Move excludedMove=Move(0))
	The core recursive Alpha-Beta search function.
int	quiescence (Board &board, int alpha, int beta, int ply)
	Quiescence search to resolve tactical sequences before static evaluation.
bool	canLazySkip (const Board &board, int depth, int alpha, int beta, int ply, int fastScore, Bound &outBound, bool prevWasCapture, bool pvNode)
	Determines if the position can bypass a full neural network evaluation.
int	scoreMoveFast (const Move &move, const Board &board, Move ttMove, int ply, bool isCapture)
	Scores a move rapidly for sorting during move generation.
void	updateKillers (Move move, int ply)
	Updates killer move heuristics when a quiet move causes a beta cutoff.
void	updateHistory (const Board &board, Move move, int bonus, int ply)
	Updates history and continuation history heuristics based on search results.
int	see (const Board &board, Move move) const
	Static Exchange Evaluation (SEE) for a move.
int	pieceValue (PieceType pt) const
	Returns the base material value of a piece type for SEE calculations.
int	applyCorrHist (int rawEval, const Board &board, int ply) const
	Applies historical corrections to the raw neural network evaluation.
bool	isPassedPawn (const Board &board, Square sq, Color side) const
	Determines if the pawn on the given square is a passed pawn.
bool	isPawnPush7th (const Board &board, Move move) const
	Determines if the move pushes a pawn to the 7th rank (or 2nd for black).
void	syncTimeToShared ()
	Syncs the thread-local elapsed time to the shared data for the main thread.
bool	shouldStop () const
	Checks if the search should be aborted due to time limits or external stop signals.
int64_t	elapsedMs () const
	Calculates the elapsed time since the search started.
bool	shouldStopIteration (int depth, int score, Move bestMove) const
	Decides whether to stop the search early at the end of an Iterative Deepening iteration.
bool	isCapture (const Board &board, Move move) const
	Returns true if the move is a capture.
bool	isDraw (const Board &board) const
	Returns true if the position is a theoretical draw (e.g. 50-move rule, 3-fold repetition, insufficient material).
int	mateScore (int ply) const
	Returns the mate score adjusted for the current ply (so closer mates score higher).
bool	isMateScore (int score) const
	Checks if the given score is within the checkmate score range.
void	clearState ()
	Resets transient state arrays and variables before starting a new search.
void	flushLocalSearchStats ()
	Flushes local statistics (nodes, hits) to the global shared atomic counters.

Private Attributes
IEvaluator &	evalCtx_
	Reference to the thread-local evaluator.
TranspositionTable &	tt_
	Reference to the global transposition table.
std::shared_ptr< SearchSharedData >	shared_
	Shared state for thread coordination.
bool	isMainThread_
	True if this is the primary search thread.
int	threadId_
	Unique ID for this thread (used for move ordering diversity).
uint64_t	localNodes_ = 0
	Nodes searched by this thread.
uint64_t	localTbHits_ = 0
	Tablebase hits by this thread.
uint64_t	localTtHits_ = 0
	TT hits by this thread.
int	localSelDepth_ = 0
	Maximum selective depth reached by this thread.
TimeManager	timeManager_
	Manages time limits and soft/hard stops.
TimeManager::TimeAllocation	timeAlloc_ {}
	Pre-calculated time allocation constraints.
float	lastEvalCp_ = 0.0f
	Last evaluation score in centipawns (used for time decisions).
Move	lastBestMove_
	Best move found in the previous iterative deepening iteration.
int	lastScore_ = 0
	Score returned in the previous iteration.
int	bestMoveChanges_ = 0
	Count of how many times the best move changed at root.
int	scoreDrops_ = 0
	Count of significant evaluation drops at root.
std::array< uint64_t, 4096 >	rootNodeCounts_ {}
	Number of nodes spent evaluating each root move.
uint64_t	searchNodes_ = 0
	Total nodes searched during the current search session.
std::unique_ptr< SearchHeuristics >	h_
	Heap-allocated structure containing large arrays for search heuristics.
std::array< Move, SearchConstants::MAX_PLY >	prevMove_
	Records the move made at each ply to reach the current state.
std::array< Piece, SearchConstants::MAX_PLY >	prevPiece_ {}
	Records the piece that moved at each ply.
std::array< int, SearchConstants::MAX_PLY >	pvLength_
	Tracks the length of the principal variation at each ply.
std::array< int, SearchConstants::MAX_PLY >	evalHistory_ {}
	Tracks static evaluation history for pruning thresholds.
int	currentIter_ = 0
	The current depth iteration in Iterative Deepening.
std::vector< Move >	searchMoves_
	Restricts the search to only these root moves (used for 'searchmoves' command).
InfoCallback	infoCallback_
	Callback function to output search progress to the UCI protocol.
SimpleEvalContext	simpleEval_
	A fast, simple evaluator used for pre-NN filtering or lazy evaluation.

Static Private Attributes
static constexpr uint64_t	NODE_FLUSH_INTERVAL = 1024
	How often to flush local stats to the shared global counters.

Friends
class	MovePicker
	MovePicker requires access to scoreMoveFast and heuristics.

Detailed Description

Implementation of the main Alpha-Beta search algorithm.

This class encapsulates the search state for a single thread, including local transposition table statistics, move ordering heuristics, and time management. It coordinates with other search threads through SearchSharedData.

Constructor & Destructor Documentation

◆ Negamax()

Negamax::Negamax	(	IEvaluator &	eval,
		TranspositionTable &	table,
		std::shared_ptr< SearchSharedData >	shared,
		bool	isMainThread,
		int	threadId = 0 )

Constructs a new Negamax search instance.

Parameters

eval	Thread-local evaluator instance.
table	Global transposition table.
shared	Shared state for Lazy SMP coordination.
isMainThread	True if this instance is the primary search thread.
threadId	Unique identifier for this thread.

Here is the call graph for this function:

Member Function Documentation

◆ alphaBeta()

int Negamax::alphaBeta	(	Board &	board,
		int	depth,
		int	alpha,
		int	beta,
		int	ply,
		bool	allowNull,
		int	extensions,
		bool	prevWasCapture = false,
		bool	cutnode = false,
		Move	excludedMove = Move(0) )

private

The core recursive Alpha-Beta search function.

Parameters

board	The current board state.
depth	The remaining search depth.
alpha	The lower bound of the current search window.
beta	The upper bound of the current search window.
ply	The current distance from the root.
allowNull	True if Null Move Pruning is permitted at this node.
extensions	The number of depth extensions applied so far along this path.
prevWasCapture	True if the move that led to this node was a capture.
cutnode	True if we expect this node to fail high (used for LMR scaling).
excludedMove	A move to ignore during search (used for Singular Extensions).

Returns: The backed-up minimax score for the node.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ applyCorrHist()

int Negamax::applyCorrHist	(	int	rawEval,
		const Board &	board,
		int	ply ) const

private

Applies historical corrections to the raw neural network evaluation.

Corrects systematic evaluation errors based on pawn structures and piece configurations.

Parameters

rawEval	The raw static evaluation.
board	The board state.
ply	The distance from root.

Returns: The history-corrected evaluation.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ canLazySkip()

bool Negamax::canLazySkip	(	const Board &	board,
		int	depth,
		int	alpha,
		int	beta,
		int	ply,
		int	fastScore,
		Bound &	outBound,
		bool	prevWasCapture,
		bool	pvNode )

private

Determines if the position can bypass a full neural network evaluation.

Parameters

board	The board state.
depth	Remaining depth.
alpha	Alpha bound.
beta	Beta bound.
ply	Distance from root.
fastScore	Score from the fast/simple evaluator.
outBound	Output bound (Upper or Lower) if skipping is permitted.
prevWasCapture	True if previous move was a capture.
pvNode	True if this is a Principal Variation node.

Returns: True if the evaluation can be skipped.

Here is the call graph for this function:

◆ clearState()

void Negamax::clearState ( )

private

Resets transient state arrays and variables before starting a new search.

Here is the caller graph for this function:

◆ elapsedMs()

int64_t Negamax::elapsedMs ( ) const

private

Calculates the elapsed time since the search started.

Returns: Elapsed time in milliseconds.

Here is the caller graph for this function:

◆ flushLocalSearchStats()

void Negamax::flushLocalSearchStats ( )

private

Flushes local statistics (nodes, hits) to the global shared atomic counters.

Here is the caller graph for this function:

◆ getNodes()

uint64_t Negamax::getNodes ( ) const

inlineoverridevirtual

Retrieves the total number of nodes evaluated by the search algorithm.

Returns: The node count.

Implements ISearch.

◆ getNonPawnKey()

uint64_t Negamax::getNonPawnKey	(	const Board &	board,
		chess::Color	c ) const

private

Computes a hash key based on non-pawn pieces of a given color.

Parameters

board	The current board state.
c	The color of the pieces to hash.

Returns: The 64-bit non-pawn Zobrist key.

Here is the caller graph for this function:

◆ getPawnKey()

uint64_t Negamax::getPawnKey ( const Board & board ) const

private

Computes a hash key based on the pawn structure.

Parameters

board The current board state.

Returns: The 64-bit Zobrist key for pawns only.

Here is the caller graph for this function:

◆ isCapture()

bool Negamax::isCapture	(	const Board &	board,
		Move	move ) const

private

Returns true if the move is a capture.

Here is the caller graph for this function:

◆ isDraw()

bool Negamax::isDraw ( const Board & board ) const

private

Returns true if the position is a theoretical draw (e.g. 50-move rule, 3-fold repetition, insufficient material).

Here is the caller graph for this function:

◆ isMateScore()

bool Negamax::isMateScore ( int score ) const

inlineprivate

Checks if the given score is within the checkmate score range.

Here is the caller graph for this function:

◆ isPassedPawn()

bool Negamax::isPassedPawn	(	const Board &	board,
		Square	sq,
		Color	side ) const

private

Determines if the pawn on the given square is a passed pawn.

Parameters

board	The current board state.
sq	The square of the pawn.
side	The color of the pawn.

Returns: True if the pawn has no opposing pawns blocking its path to promotion.

◆ isPawnPush7th()

bool Negamax::isPawnPush7th	(	const Board &	board,
		Move	move ) const

private

Determines if the move pushes a pawn to the 7th rank (or 2nd for black).

Parameters

board	The current board state.
move	The move to evaluate.

Returns: True if it is a 7th rank pawn push.

◆ isSearching()

bool Negamax::isSearching ( ) const

inlineoverridevirtual

Checks if the search algorithm is currently running.

Returns: True if a search is in progress.

Implements ISearch.

◆ mateScore()

int Negamax::mateScore ( int ply ) const

private

Returns the mate score adjusted for the current ply (so closer mates score higher).

Here is the caller graph for this function:

◆ pieceValue()

int Negamax::pieceValue ( PieceType pt ) const

private

Returns the base material value of a piece type for SEE calculations.

◆ quiescence()

int Negamax::quiescence	(	Board &	board,
		int	alpha,
		int	beta,
		int	ply )

private

Quiescence search to resolve tactical sequences before static evaluation.

Searches only captures and promotions to ensure the evaluation is stable.

Parameters

board	The current board state.
alpha	The lower bound.
beta	The upper bound.
ply	The distance from the root.

Returns: The resolved stable score.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ scoreMoveFast()

int Negamax::scoreMoveFast	(	const Move &	move,
		const Board &	board,
		Move	ttMove,
		int	ply,
		bool	isCapture )

private

Scores a move rapidly for sorting during move generation.

Parameters

move	The move to score.
board	The current board state.
ttMove	The best move retrieved from the Transposition Table.
ply	The current distance from the root.
isCapture	True if the move is a capture.

Returns: The heuristic sorting score.

Here is the call graph for this function:

◆ see()

int Negamax::see	(	const Board &	board,
		Move	move ) const

private

Static Exchange Evaluation (SEE) for a move.

Evaluates the material consequence of a sequence of captures on a single square.

Parameters

board	The board state.
move	The capture move to evaluate.

Returns: The material gain/loss score.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ setInfoCallback()

void Negamax::setInfoCallback ( InfoCallback callback )

inlineoverridevirtual

Sets the callback function for periodic information updates.

Parameters

callback The function to call with depth, score, node count, NPS, and PV.

Implements ISearch.

◆ shouldStop()

bool Negamax::shouldStop ( ) const

private

Checks if the search should be aborted due to time limits or external stop signals.

Returns: True if the search must stop immediately.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ shouldStopIteration()

bool Negamax::shouldStopIteration	(	int	depth,
		int	score,
		Move	bestMove ) const

private

Decides whether to stop the search early at the end of an Iterative Deepening iteration.

Triggers soft time limits early if the best move seems stable and no score drops have occurred.

Parameters

depth	The completed search depth.
score	The best score achieved at this depth.
bestMove	The best move found.

Returns: True if the search should be terminated.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ startSearch()

Move Negamax::startSearch	(	Board &	root,
		const SearchParams &	params )

overridevirtual

Starts the search process on the given root board.

This is a blocking call that will execute the search algorithm until the stopping conditions in params (or stop()) are met.

Parameters

root	The starting board position.
params	The time and depth constraints for the search.

Returns: The best move found.

Implements ISearch.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ stop()

void Negamax::stop ( )

inlineoverridevirtual

Asynchronously signals the search to stop immediately.

This method must be thread-safe.

Implements ISearch.

◆ syncTimeToShared()

void Negamax::syncTimeToShared ( )

private

Syncs the thread-local elapsed time to the shared data for the main thread.

Here is the caller graph for this function:

◆ updateHistory()

void Negamax::updateHistory	(	const Board &	board,
		Move	move,
		int	bonus,
		int	ply )

private

Updates history and continuation history heuristics based on search results.

Parameters

board	The board state before the move.
move	The move executed.
bonus	The bonus/penalty to apply (based on search depth).
ply	The current distance from root.

Here is the caller graph for this function:

◆ updateKillers()

void Negamax::updateKillers	(	Move	move,
		int	ply )

private

Updates killer move heuristics when a quiet move causes a beta cutoff.

Parameters

move	The move that caused the cutoff.
ply	The distance from root where the cutoff occurred.

Here is the caller graph for this function:

◆ MovePicker

MovePicker

friend

MovePicker requires access to scoreMoveFast and heuristics.

Member Data Documentation

◆ bestMoveChanges_

int Negamax::bestMoveChanges_ = 0

private

Count of how many times the best move changed at root.

◆ currentIter_

int Negamax::currentIter_ = 0

private

The current depth iteration in Iterative Deepening.

◆ evalCtx_

IEvaluator& Negamax::evalCtx_

private

Reference to the thread-local evaluator.

◆ evalHistory_

std::array<int, SearchConstants::MAX_PLY> Negamax::evalHistory_ {}

private

Tracks static evaluation history for pruning thresholds.

◆ h_

std::unique_ptr<SearchHeuristics> Negamax::h_

private

Heap-allocated structure containing large arrays for search heuristics.

◆ infoCallback_

InfoCallback Negamax::infoCallback_

private

Callback function to output search progress to the UCI protocol.

◆ isMainThread_

bool Negamax::isMainThread_

private

True if this is the primary search thread.

◆ lastBestMove_

Move Negamax::lastBestMove_

private

Best move found in the previous iterative deepening iteration.

◆ lastEvalCp_

float Negamax::lastEvalCp_ = 0.0f

private

Last evaluation score in centipawns (used for time decisions).

◆ lastScore_

int Negamax::lastScore_ = 0

private

Score returned in the previous iteration.

◆ localNodes_

uint64_t Negamax::localNodes_ = 0

private

Nodes searched by this thread.

◆ localSelDepth_

int Negamax::localSelDepth_ = 0

private

Maximum selective depth reached by this thread.

◆ localTbHits_

uint64_t Negamax::localTbHits_ = 0

private

Tablebase hits by this thread.

◆ localTtHits_

uint64_t Negamax::localTtHits_ = 0

private

TT hits by this thread.

◆ NODE_FLUSH_INTERVAL

uint64_t Negamax::NODE_FLUSH_INTERVAL = 1024

staticconstexprprivate

How often to flush local stats to the shared global counters.

◆ prevMove_

std::array<Move, SearchConstants::MAX_PLY> Negamax::prevMove_

private

Records the move made at each ply to reach the current state.

◆ prevPiece_

std::array<Piece, SearchConstants::MAX_PLY> Negamax::prevPiece_ {}

private

Records the piece that moved at each ply.

◆ pvLength_

std::array<int, SearchConstants::MAX_PLY> Negamax::pvLength_

private

Tracks the length of the principal variation at each ply.

◆ rootNodeCounts_

std::array<uint64_t, 4096> Negamax::rootNodeCounts_ {}

private

Number of nodes spent evaluating each root move.

◆ scoreDrops_

int Negamax::scoreDrops_ = 0

private

Count of significant evaluation drops at root.

◆ searchMoves_

std::vector<Move> Negamax::searchMoves_

private

Restricts the search to only these root moves (used for 'searchmoves' command).

◆ searchNodes_

uint64_t Negamax::searchNodes_ = 0

private

Total nodes searched during the current search session.

◆ shared_

std::shared_ptr<SearchSharedData> Negamax::shared_

private

Shared state for thread coordination.

◆ simpleEval_

SimpleEvalContext Negamax::simpleEval_

private

A fast, simple evaluator used for pre-NN filtering or lazy evaluation.

◆ threadId_

int Negamax::threadId_

private

Unique ID for this thread (used for move ordering diversity).

◆ timeAlloc_

TimeManager::TimeAllocation Negamax::timeAlloc_ {}

private

Pre-calculated time allocation constraints.

◆ timeManager_

TimeManager Negamax::timeManager_

private

Manages time limits and soft/hard stops.

◆ tt_

TranspositionTable& Negamax::tt_

private

Reference to the global transposition table.

The documentation for this class was generated from the following files:

engine/src/search/Negamax.h
engine/src/search/Negamax.cpp

Public Member Functions

Private Member Functions

Private Attributes

Static Private Attributes

Friends

Detailed Description

Constructor & Destructor Documentation

◆ Negamax()

Member Function Documentation

◆ alphaBeta()

◆ applyCorrHist()

◆ canLazySkip()

◆ clearState()

◆ elapsedMs()

◆ flushLocalSearchStats()

◆ getNodes()

◆ getNonPawnKey()

◆ getPawnKey()

◆ isCapture()

◆ isDraw()

◆ isMateScore()

◆ isPassedPawn()

◆ isPawnPush7th()

◆ isSearching()

◆ mateScore()

◆ pieceValue()

◆ quiescence()

◆ scoreMoveFast()

◆ see()

◆ setInfoCallback()

◆ shouldStop()

◆ shouldStopIteration()

◆ startSearch()

◆ stop()

◆ syncTimeToShared()

◆ updateHistory()

◆ updateKillers()

Friends And Related Symbol Documentation

◆ MovePicker

Member Data Documentation

◆ bestMoveChanges_

◆ currentIter_

◆ evalCtx_

◆ evalHistory_

◆ h_

◆ infoCallback_

◆ isMainThread_

◆ lastBestMove_

◆ lastEvalCp_

◆ lastScore_

◆ localNodes_

◆ localSelDepth_

◆ localTbHits_

◆ localTtHits_

◆ NODE_FLUSH_INTERVAL

◆ prevMove_

◆ prevPiece_

◆ pvLength_

◆ rootNodeCounts_

◆ scoreDrops_

◆ searchMoves_

◆ searchNodes_

◆ shared_

◆ simpleEval_

◆ threadId_

◆ timeAlloc_

◆ timeManager_

◆ tt_