Pure Negamax search over an implicit game tree. More...

#include <Negamax.H>

Collaboration diagram for Aleph::Negamax< Domain >:

Public Types
using	Domain_Type = Domain
	Type of the problem domain.

using	State = typename Domain::State
	Concrete search state type.

using	Move = typename Domain::Move
	Move type.

using	Score = typename Domain::Score
	Score type used for board evaluation.

using	Result = AdversarialSearchResult< Move, Score >
	Outcome of an adversarial search execution.

Public Member Functions
	Negamax (Domain domain, ExplorationPolicy policy=default_policy(), const SearchLimits &limits={})
	Build a Negamax engine bound to one game domain.

const Domain &	domain () const noexcept
	Read-only access to the bound game domain.

Domain &	domain () noexcept
	Mutable access to the bound game domain.

const ExplorationPolicy &	policy () const noexcept
	Current exploration policy.

const SearchLimits &	limits () const noexcept
	Current hard limits.

void	set_policy (const ExplorationPolicy &policy) noexcept
	Replace the exploration policy for future runs.

void	set_limits (const SearchLimits &limits) noexcept
	Replace the hard limits for future runs.

Result	search (State initial_state)
	Execute Negamax from `initial_state`.

template<typename Tracer > requires AdversarialSearchTracer<Tracer, Move, Score>
Result	search (State initial_state, Tracer &tracer)
	Execute Negamax from `initial_state` while emitting trace events.

template<typename Table , typename Keyer > requires AdversarialSearchKeyer<Table, Keyer, State, Move, Score>
Result	search (State initial_state, Table &table, Keyer keyer)
	Execute Negamax with a transposition table and explicit keyer.

template<typename Table , typename Keyer , typename Tracer > requires AdversarialSearchKeyer<Table, Keyer, State, Move, Score>
and AdversarialSearchTracer< Tracer, Move, Score > Result	search (State initial_state, Table &table, Keyer keyer, Tracer &tracer)
	Execute Negamax with TT/keyer and a trace sink.

template<typename Table , typename D_ = Domain> requires SearchStateKeyProvider<D_>
and AdversarialTranspositionMemo< Table, typename D_::State_Key, Move, Score > Result	search (State initial_state, Table &table)
	Execute Negamax with a transposition table using `domain().state_key()`.

template<typename Table , typename Tracer , typename D_ = Domain> requires SearchStateKeyProvider<D_>
and AdversarialTranspositionMemo< Table, typename D_::State_Key, Move, Score > and AdversarialSearchTracer< Tracer, Move, Score > Result	search (State initial_state, Table &table, Tracer &tracer)
	Execute Negamax with domain-provided key and a trace sink.

Static Public Member Functions
static ExplorationPolicy	default_policy () noexcept
	Return the default exploration policy for adversarial search.

Static Public Attributes
static constexpr bool	supports_best_first = false
	Compile-time marker: Negamax only supports Depth_First strategy.

Private Member Functions
template<typename Table , typename Keyer , typename Tracer > requires AdversarialSearchTracer<Tracer, Move, Score>
Result	search_impl (State initial_state, Table &table, Keyer &keyer, Tracer &tracer)

bool	expansion_limit_reached (Result &result)

template<typename Table , typename Keyer >
void	store_transposition (State &state, const size_t remaining, Result &result, Table &table, Keyer &keyer, const adversarial_search_detail::NodeEvaluation< Move, Score > &value, const TranspositionBound bound)

template<typename Table , typename Keyer >
bool	probe_transposition (State &state, const size_t remaining, Result &result, Table &table, Keyer &keyer, adversarial_search_detail::NodeEvaluation< Move, Score > &out)

template<typename Table , typename Keyer , typename Tracer > requires AdversarialSearchTracer<Tracer, Move, Score>
adversarial_search_detail::NodeEvaluation< Move, Score >	search_node (State &state, const size_t depth, Result &result, Table &table, Keyer &keyer, Tracer &tracer)

Private Attributes
Domain	domain_

ExplorationPolicy	policy_

SearchLimits	limits_

bool	stop_ = false

Detailed Description

template<AdversarialGameDomain Domain>
class Aleph::Negamax< Domain >

Pure Negamax search over an implicit game tree.

Negamax is the canonical base for two-player zero-sum search because a single maximization recurrence is enough once evaluation is defined from the side-to-move perspective.

Template Parameters

Domain game adapter exposing adversarial-search hooks.

Definition at line 839 of file Negamax.H.

Member Typedef Documentation

◆ Domain_Type

template<AdversarialGameDomain Domain>

using Aleph::Negamax< Domain >::Domain_Type = Domain

Type of the problem domain.

Definition at line 843 of file Negamax.H.

◆ Move

template<AdversarialGameDomain Domain>

using Aleph::Negamax< Domain >::Move = typename Domain::Move

Move type.

Definition at line 847 of file Negamax.H.

◆ Result

template<AdversarialGameDomain Domain>

using Aleph::Negamax< Domain >::Result = AdversarialSearchResult<Move, Score>

Outcome of an adversarial search execution.

Definition at line 851 of file Negamax.H.

◆ Score

template<AdversarialGameDomain Domain>

using Aleph::Negamax< Domain >::Score = typename Domain::Score

Score type used for board evaluation.

Definition at line 849 of file Negamax.H.

◆ State

template<AdversarialGameDomain Domain>

using Aleph::Negamax< Domain >::State = typename Domain::State

Concrete search state type.

Definition at line 845 of file Negamax.H.

Constructor & Destructor Documentation

◆ Negamax()

template<AdversarialGameDomain Domain>

Aleph::Negamax< Domain >::Negamax	(	Domain	domain,
		ExplorationPolicy	policy = `default_policy()`,
		const SearchLimits &	limits = `{}`
	)

inlineexplicit

Build a Negamax engine bound to one game domain.

Definition at line 871 of file Negamax.H.

Member Function Documentation

◆ default_policy()

template<AdversarialGameDomain Domain>

static ExplorationPolicy Aleph::Negamax< Domain >::default_policy ( )

inlinestaticnoexcept

Return the default exploration policy for adversarial search.

Definition at line 862 of file Negamax.H.

References Aleph::ExplorationPolicy::Depth_First, Aleph::Negamax< Domain >::policy(), Aleph::ExplorationPolicy::stop_at_first_solution, and Aleph::ExplorationPolicy::strategy.

Referenced by Aleph::Alpha_Beta< Domain >::default_policy(), and TEST().

◆ domain() [1/2]

template<AdversarialGameDomain Domain>

const Domain & Aleph::Negamax< Domain >::domain ( ) const

inlinenoexcept

Read-only access to the bound game domain.

Definition at line 879 of file Negamax.H.

References Aleph::Negamax< Domain >::domain_.

◆ domain() [2/2]

template<AdversarialGameDomain Domain>

Domain & Aleph::Negamax< Domain >::domain ( )

inlinenoexcept

Mutable access to the bound game domain.

Definition at line 885 of file Negamax.H.

References Aleph::Negamax< Domain >::domain_.

◆ expansion_limit_reached()

template<AdversarialGameDomain Domain>

bool Aleph::Negamax< Domain >::expansion_limit_reached ( Result & result )

inlineprivate

Definition at line 1034 of file Negamax.H.

References Aleph::search_engine_detail::expansion_limit_reached(), Aleph::Negamax< Domain >::limits_, and Aleph::Negamax< Domain >::stop_.

Referenced by Aleph::Negamax< Domain >::search_node().

◆ limits()

template<AdversarialGameDomain Domain>

const SearchLimits & Aleph::Negamax< Domain >::limits ( ) const

inlinenoexcept

Current hard limits.

Definition at line 897 of file Negamax.H.

References Aleph::Negamax< Domain >::limits_.

Referenced by Aleph::Negamax< Domain >::set_limits().

◆ policy()

template<AdversarialGameDomain Domain>

const ExplorationPolicy & Aleph::Negamax< Domain >::policy ( ) const

inlinenoexcept

Current exploration policy.

Definition at line 891 of file Negamax.H.

References Aleph::Negamax< Domain >::policy_.

Referenced by Aleph::Negamax< Domain >::default_policy(), and Aleph::Negamax< Domain >::set_policy().

◆ probe_transposition()

template<AdversarialGameDomain Domain>

template<typename Table , typename Keyer >

bool Aleph::Negamax< Domain >::probe_transposition	(	State &	state,
		const size_t	remaining,
		Result &	result,
		Table &	table,
		Keyer &	keyer,
		adversarial_search_detail::NodeEvaluation< Move, Score > &	out
	)

inlineprivate

Definition at line 1059 of file Negamax.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), Aleph::TranspositionStats::cutoffs, Aleph::Exact, out, Aleph::AdversarialSearchResult< Move, Score >::stats, and Aleph::AdversarialSearchStats::transpositions.

Referenced by Aleph::Negamax< Domain >::search_node().

◆ search() [1/6]

template<AdversarialGameDomain Domain>

Result Aleph::Negamax< Domain >::search ( State initial_state )

inline

Execute Negamax from initial_state.

Parameters

[in] initial_state Root position. Its side to move defines the perspective of the returned score.

Returns: One principal variation and its root score.

Precondition: domain().evaluate(state) returns values in [score_floor<Score>(), score_ceiling<Score>()]. The engine keeps std::numeric_limits<Score>::lowest() as an internal sentinel and remaps it to std::numeric_limits<Score>::max() when a negation would otherwise overflow.

Exceptions

std::invalid_argument if a non-depth-first exploration strategy is requested or common limits are malformed.

Definition at line 928 of file Negamax.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Negamax< Domain >::search().

Referenced by Aleph::Negamax< Domain >::search(), Aleph::Negamax< Domain >::search(), and TEST().

◆ search() [2/6]

template<AdversarialGameDomain Domain>

template<typename Table , typename D_ = Domain>
requires SearchStateKeyProvider<D_>

and AdversarialTranspositionMemo< Table, typename D_::State_Key, Move, Score > Result Aleph::Negamax< Domain >::search	(	State	initial_state,
		Table &	table
	)

inline

Execute Negamax with a transposition table using domain().state_key().

Definition at line 971 of file Negamax.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Negamax< Domain >::domain_, and Aleph::Negamax< Domain >::search_impl().

◆ search() [3/6]

template<AdversarialGameDomain Domain>

template<typename Table , typename Keyer >
requires AdversarialSearchKeyer<Table, Keyer, State, Move, Score>

Result Aleph::Negamax< Domain >::search	(	State	initial_state,
		Table &	table,
		Keyer	keyer
	)

inline

Execute Negamax with a transposition table and explicit keyer.

keyer(state) must return a stable key that identifies search-equivalent states. The engine internally combines it with remaining depth to keep the cache consistent with the configured horizon.

Definition at line 952 of file Negamax.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Negamax< Domain >::search().

◆ search() [4/6]

template<AdversarialGameDomain Domain>

template<typename Table , typename Keyer , typename Tracer >
requires AdversarialSearchKeyer<Table, Keyer, State, Move, Score>

and AdversarialSearchTracer< Tracer, Move, Score > Result Aleph::Negamax< Domain >::search	(	State	initial_state,
		Table &	table,
		Keyer	keyer,
		Tracer &	tracer
	)

inline

Execute Negamax with TT/keyer and a trace sink.

Definition at line 962 of file Negamax.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Negamax< Domain >::search_impl().

◆ search() [5/6]

template<AdversarialGameDomain Domain>

template<typename Table , typename Tracer , typename D_ = Domain>
requires SearchStateKeyProvider<D_>

and AdversarialTranspositionMemo< Table, typename D_::State_Key, Move, Score > and AdversarialSearchTracer< Tracer, Move, Score > Result Aleph::Negamax< Domain >::search	(	State	initial_state,
		Table &	table,
		Tracer &	tracer
	)

inline

Execute Negamax with domain-provided key and a trace sink.

Definition at line 987 of file Negamax.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Negamax< Domain >::domain_, and Aleph::Negamax< Domain >::search_impl().

◆ search() [6/6]

template<AdversarialGameDomain Domain>

template<typename Tracer >
requires AdversarialSearchTracer<Tracer, Move, Score>

Result Aleph::Negamax< Domain >::search	(	State	initial_state,
		Tracer &	tracer
	)

inline

Execute Negamax from initial_state while emitting trace events.

Definition at line 937 of file Negamax.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Negamax< Domain >::search_impl().

◆ search_impl()

template<AdversarialGameDomain Domain>

template<typename Table , typename Keyer , typename Tracer >
requires AdversarialSearchTracer<Tracer, Move, Score>

Result Aleph::Negamax< Domain >::search_impl	(	State	initial_state,
		Table &	table,
		Keyer &	keyer,
		Tracer &	tracer
	)

inlineprivate

Definition at line 1005 of file Negamax.H.

References ah_invalid_argument_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::ExplorationPolicy::Depth_First, Aleph::Domain, Aleph::SearchStats::elapsed_ms, Aleph::Exhausted, Aleph::AdversarialSearchResult< Move, Score >::limits, Aleph::Negamax< Domain >::limits_, Aleph::SearchLimits::max_solutions, Aleph::ExplorationPolicy::move_ordering, Aleph::NotStarted, Aleph::AdversarialSearchResult< Move, Score >::policy, Aleph::Negamax< Domain >::policy_, Aleph::AdversarialSearchResult< Move, Score >::principal_variation, root(), Aleph::search_elapsed_ms(), Aleph::Negamax< Domain >::search_node(), Aleph::AdversarialSearchResult< Move, Score >::stats, Aleph::AdversarialSearchResult< Move, Score >::status, Aleph::Negamax< Domain >::stop_, Aleph::ExplorationPolicy::strategy, Aleph::ExplorationPolicy::use_history_heuristic, Aleph::ExplorationPolicy::use_killer_moves, and Aleph::AdversarialSearchResult< Move, Score >::value.

Referenced by Aleph::Negamax< Domain >::search(), Aleph::Negamax< Domain >::search(), Aleph::Negamax< Domain >::search(), and Aleph::Negamax< Domain >::search().

◆ search_node()

template<AdversarialGameDomain Domain>

template<typename Table , typename Keyer , typename Tracer >
requires AdversarialSearchTracer<Tracer, Move, Score>

adversarial_search_detail::NodeEvaluation< Move, Score > Aleph::Negamax< Domain >::search_node	(	State &	state,
		const size_t	depth,
		Result &	result,
		Table &	table,
		Keyer &	keyer,
		Tracer &	tracer
	)

inlineprivate

Definition at line 1082 of file Negamax.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Depth_Cutoff, Aleph::Negamax< Domain >::domain_, Aleph::Domain_Prune, Aleph::adversarial_search_detail::emit_trace(), Aleph::Enter_Node, Aleph::adversarial_search_detail::evaluate_leaf(), Aleph::Exact, Aleph::Exit_Node, Aleph::SearchStats::expanded_states, Aleph::Expansion_Limit, Aleph::Negamax< Domain >::expansion_limit_reached(), Aleph::adversarial_search_detail::first_move_of(), Aleph::SearchStats::generated_successors, Aleph::Negamax< Domain >::limits_, Aleph::SearchLimits::max_depth, Aleph::adversarial_search_detail::prepend_move(), Aleph::adversarial_search_detail::NodeEvaluation< Move, Score >::principal_variation, Aleph::Negamax< Domain >::probe_transposition(), Aleph::SearchStats::pruned_by_depth, Aleph::SearchStats::pruned_by_domain, Aleph::search_engine_detail::register_visit(), Aleph::adversarial_search_detail::remaining_depth(), Aleph::Negamax< Domain >::search_node(), Aleph::search_engine_detail::should_prune_state(), Aleph::AdversarialSearchResult< Move, Score >::stats, Aleph::Negamax< Domain >::stop_, Aleph::Negamax< Domain >::store_transposition(), Aleph::Terminal_Node, Aleph::SearchStats::terminal_states, Aleph::Transposition_Hit, and Aleph::adversarial_search_detail::NodeEvaluation< Move, Score >::value.

Referenced by Aleph::Negamax< Domain >::search_impl(), and Aleph::Negamax< Domain >::search_node().

◆ set_limits()

template<AdversarialGameDomain Domain>

void Aleph::Negamax< Domain >::set_limits ( const SearchLimits & limits )

inlinenoexcept

Replace the hard limits for future runs.

Definition at line 909 of file Negamax.H.

References Aleph::Negamax< Domain >::limits(), and Aleph::Negamax< Domain >::limits_.

◆ set_policy()

template<AdversarialGameDomain Domain>

void Aleph::Negamax< Domain >::set_policy ( const ExplorationPolicy & policy )

inlinenoexcept

Replace the exploration policy for future runs.

Definition at line 903 of file Negamax.H.

References Aleph::Negamax< Domain >::policy(), and Aleph::Negamax< Domain >::policy_.

◆ store_transposition()

template<AdversarialGameDomain Domain>

template<typename Table , typename Keyer >

void Aleph::Negamax< Domain >::store_transposition	(	State &	state,
		const size_t	remaining,
		Result &	result,
		Table &	table,
		Keyer &	keyer,
		const adversarial_search_detail::NodeEvaluation< Move, Score > &	value,
		const TranspositionBound	bound
	)

inlineprivate

Definition at line 1046 of file Negamax.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Negamax< Domain >::stop_, and value.

Referenced by Aleph::Negamax< Domain >::search_node().

Member Data Documentation

◆ domain_

template<AdversarialGameDomain Domain>

Domain Aleph::Negamax< Domain >::domain_

private

Definition at line 998 of file Negamax.H.

Referenced by Aleph::Negamax< Domain >::domain(), Aleph::Negamax< Domain >::domain(), Aleph::Negamax< Domain >::search(), Aleph::Negamax< Domain >::search(), and Aleph::Negamax< Domain >::search_node().

◆ limits_

template<AdversarialGameDomain Domain>

SearchLimits Aleph::Negamax< Domain >::limits_

private

Definition at line 1000 of file Negamax.H.

Referenced by Aleph::Negamax< Domain >::expansion_limit_reached(), Aleph::Negamax< Domain >::limits(), Aleph::Negamax< Domain >::search_impl(), Aleph::Negamax< Domain >::search_node(), and Aleph::Negamax< Domain >::set_limits().

◆ policy_

template<AdversarialGameDomain Domain>

ExplorationPolicy Aleph::Negamax< Domain >::policy_

private

Definition at line 999 of file Negamax.H.

Referenced by Aleph::Negamax< Domain >::policy(), Aleph::Negamax< Domain >::search_impl(), and Aleph::Negamax< Domain >::set_policy().

◆ stop_

template<AdversarialGameDomain Domain>

bool Aleph::Negamax< Domain >::stop_ = false

private

Definition at line 1001 of file Negamax.H.

Referenced by Aleph::Negamax< Domain >::expansion_limit_reached(), Aleph::Negamax< Domain >::search_impl(), Aleph::Negamax< Domain >::search_node(), and Aleph::Negamax< Domain >::store_transposition().

◆ supports_best_first

template<AdversarialGameDomain Domain>

constexpr bool Aleph::Negamax< Domain >::supports_best_first = false

staticconstexpr

Compile-time marker: Negamax only supports Depth_First strategy.

Passing ExplorationPolicy::Strategy::Best_First to this engine raises std::invalid_argument at runtime. Check this constant before constructing a policy to detect the mismatch at compile time.

Definition at line 859 of file Negamax.H.

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

Negamax.H

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ Domain_Type

◆ Move

◆ Result

◆ Score

◆ State

Constructor & Destructor Documentation

◆ Negamax()

Member Function Documentation

◆ default_policy()

◆ domain() [1/2]

◆ domain() [2/2]

◆ expansion_limit_reached()

◆ limits()

◆ policy()

◆ probe_transposition()

◆ search() [1/6]

◆ search() [2/6]

◆ search() [3/6]

◆ search() [4/6]

◆ search() [5/6]

◆ search() [6/6]

◆ search_impl()

◆ search_node()

◆ set_limits()

◆ set_policy()

◆ store_transposition()

Member Data Documentation

◆ domain_

◆ limits_

◆ policy_

◆ stop_

◆ supports_best_first