Negamax Class Reference

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

#include <Negamax.h>

Inheritance diagram for Negamax:

Collaboration diagram for Negamax:

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
bool	isPawnPush7th (const Board &board, Move move) const
void	syncTimeToShared ()
bool	shouldStop () const
int64_t	elapsedMs () const
bool	shouldStopIteration (int depth, int score, Move bestMove) const
bool	isCapture (const Board &board, Move move) const
bool	isDraw (const Board &board) const
int	mateScore (int ply) const
bool	isMateScore (int score) const
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

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

Here is the caller graph for this function:

isDraw()

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

private

Here is the caller graph for this function:

isMateScore()

bool Negamax::isMateScore ( int score ) const

inlineprivate

Here is the caller graph for this function:

isPassedPawn()

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

private

isPawnPush7th()

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

private

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

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

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

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

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:

Friends And Related Symbol Documentation

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