Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
Public Types | Public Member Functions | Static Public Member Functions | Static Public Attributes | Private Member Functions | Static Private Member Functions | Private Attributes | List of all members
Aleph::Alpha_Beta< Domain > Class Template Reference

Adversarial search engine with Alpha-Beta pruning. More...

#include <Alpha_Beta.H>

Collaboration diagram for Aleph::Alpha_Beta< Domain >:
[legend]

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 Alpha-Beta search execution.
 
using Killer_Table = Killer_Move_Table< Move >
 Two-slot killer heuristic table for this move type.
 
using History_Table = typename adversarial_search_detail::History_Table_Selector< Domain >::Type
 History heuristic table type (sparse or no-op depending on domain).
 

Public Member Functions

 Alpha_Beta (Domain domain, ExplorationPolicy policy=default_policy(), const SearchLimits &limits={})
 Build an Alpha-Beta 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 Alpha-Beta from initial_state.
 
template<typename Tracer >
requires AdversarialSearchTracer<Tracer, Move, Score>
Result search (State initial_state, Tracer &tracer)
 Execute Alpha-Beta from initial_state while emitting trace events.
 
Result search_with_window (State initial_state, const Score alpha, const Score beta)
 Execute Alpha-Beta with an explicit root window.
 
template<typename Tracer >
requires AdversarialSearchTracer<Tracer, Move, Score>
Result search_with_window (State initial_state, const Score alpha, const Score beta, Tracer &tracer)
 Execute Alpha-Beta with an explicit root window and tracing.
 
template<typename Table , typename Keyer >
requires AdversarialSearchKeyer<Table, Keyer, State, Move, Score>
Result search (State initial_state, Table &table, Keyer keyer)
 Execute Alpha-Beta 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 Alpha-Beta with TT/keyer and tracing.
 
template<typename Table , typename Keyer >
requires AdversarialSearchKeyer<Table, Keyer, State, Move, Score>
Result search_with_window (State initial_state, Table &table, Keyer keyer, const Score alpha, const Score beta)
 Execute Alpha-Beta with TT/keyer and an explicit root window.
 
template<typename Table , typename Keyer , typename Tracer >
requires AdversarialSearchKeyer<Table, Keyer, State, Move, Score>
and AdversarialSearchTracer< Tracer, Move, Score > Result search_with_window (State initial_state, Table &table, Keyer keyer, const Score alpha, const Score beta, Tracer &tracer)
 Execute Alpha-Beta with TT/keyer, root window and tracing.
 
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 Alpha-Beta 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 Alpha-Beta with domain-provided key and tracing.
 
template<typename Table , typename D_ = Domain>
requires SearchStateKeyProvider<D_>
and AdversarialTranspositionMemo< Table, typename D_::State_Key, Move, Score > Result search_with_window (State initial_state, Table &table, const Score alpha, const Score beta)
 Execute Alpha-Beta with domain-provided key and explicit root window.
 
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_with_window (State initial_state, Table &table, const Score alpha, const Score beta, Tracer &tracer)
 Execute Alpha-Beta with domain-provided key, root window and tracing.
 

Static Public Member Functions

static ExplorationPolicy default_policy () noexcept
 Return the default exploration policy for Alpha-Beta.
 

Static Public Attributes

static constexpr bool supports_best_first = false
 Compile-time marker: Alpha_Beta only supports Depth_First strategy.
 

Private Member Functions

bool ordering_active () const noexcept
 
void validate_ordering_configuration () const
 
void clear_ordering_heuristics ()
 
size_t move_history_score (const Move &move) const noexcept
 
void record_cutoff_move (const size_t depth, const size_t remaining, const Move &move)
 
Array< RankedMove< Move, Score > > collect_ordered_moves (State &state, const size_t depth, Result &result)
 
template<typename Table , typename Keyer , typename Tracer >
requires AdversarialSearchTracer<Tracer, Move, Score>
Result search_impl (State initial_state, Table &table, Keyer &keyer, Tracer &tracer, const Score alpha, const Score beta)
 
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, Score &alpha, Score &beta, 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, const Score alpha, const Score beta)
 

Static Private Member Functions

static size_t history_bonus (const size_t depth, const size_t remaining) noexcept
 

Private Attributes

Domain domain_
 
ExplorationPolicy policy_
 
SearchLimits limits_
 
bool stop_ = false
 
Killer_Table killer_moves_
 
History_Table history_moves_
 

Detailed Description

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

Adversarial search engine with Alpha-Beta pruning.

Alpha-Beta improves upon pure Negamax by pruning branches that are guaranteed to be worse than a previously discovered line of play.

The domain contract and score semantics are identical to Negamax: evaluate(state) must always be expressed from the side-to-move perspective, while apply() / undo() alternate turns through the state.

If policy.move_ordering == MoveOrderingMode::Estimated_Score, the engine materializes each successor batch, scores children by a one-ply estimate, and reorders them before search. Optional killer/history hooks can further bias that ordering when explicitly enabled.

Template Parameters
Domaingame adapter exposing adversarial-search hooks.

Definition at line 70 of file Alpha_Beta.H.

Member Typedef Documentation

◆ Domain_Type

template<AdversarialGameDomain Domain>
using Aleph::Alpha_Beta< Domain >::Domain_Type = Domain

Type of the problem domain.

Definition at line 74 of file Alpha_Beta.H.

◆ History_Table

template<AdversarialGameDomain Domain>
using Aleph::Alpha_Beta< Domain >::History_Table = typename adversarial_search_detail::History_Table_Selector<Domain>::Type

History heuristic table type (sparse or no-op depending on domain).

Definition at line 86 of file Alpha_Beta.H.

◆ Killer_Table

template<AdversarialGameDomain Domain>
using Aleph::Alpha_Beta< Domain >::Killer_Table = Killer_Move_Table<Move>

Two-slot killer heuristic table for this move type.

Definition at line 84 of file Alpha_Beta.H.

◆ Move

template<AdversarialGameDomain Domain>
using Aleph::Alpha_Beta< Domain >::Move = typename Domain::Move

Move type.

Definition at line 78 of file Alpha_Beta.H.

◆ Result

template<AdversarialGameDomain Domain>
using Aleph::Alpha_Beta< Domain >::Result = AdversarialSearchResult<Move, Score>

Outcome of an Alpha-Beta search execution.

Definition at line 82 of file Alpha_Beta.H.

◆ Score

template<AdversarialGameDomain Domain>
using Aleph::Alpha_Beta< Domain >::Score = typename Domain::Score

Score type used for board evaluation.

Definition at line 80 of file Alpha_Beta.H.

◆ State

template<AdversarialGameDomain Domain>
using Aleph::Alpha_Beta< Domain >::State = typename Domain::State

Concrete search state type.

Definition at line 76 of file Alpha_Beta.H.

Constructor & Destructor Documentation

◆ Alpha_Beta()

template<AdversarialGameDomain Domain>
Aleph::Alpha_Beta< Domain >::Alpha_Beta ( Domain  domain,
ExplorationPolicy  policy = default_policy(),
const SearchLimits &  limits = {} 
)
inlineexplicit

Build an Alpha-Beta engine bound to one game domain.

Definition at line 103 of file Alpha_Beta.H.

Member Function Documentation

◆ clear_ordering_heuristics()

template<AdversarialGameDomain Domain>
void Aleph::Alpha_Beta< Domain >::clear_ordering_heuristics ( )
inlineprivate

Definition at line 345 of file Alpha_Beta.H.

References Aleph::Alpha_Beta< Domain >::history_moves_, and Aleph::Alpha_Beta< Domain >::killer_moves_.

Referenced by Aleph::Alpha_Beta< Domain >::search_impl().

◆ collect_ordered_moves()

template<AdversarialGameDomain Domain>
Array< RankedMove< Move, Score > > Aleph::Alpha_Beta< Domain >::collect_ordered_moves ( State &  state,
const size_t  depth,
Result &  result 
)
inlineprivate

Definition at line 376 of file Alpha_Beta.H.

References Aleph::Array< T >::append(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Alpha_Beta< Domain >::domain_, Aleph::Estimated_Score, Aleph::AdversarialSearchStats::heuristic_evaluations, Aleph::MoveOrderingStats::history_hits, Aleph::Array< T >::is_empty(), Aleph::MoveOrderingStats::killer_hits, Aleph::Alpha_Beta< Domain >::killer_moves_, Aleph::RankedMove< Move, Priority >::move, Aleph::Alpha_Beta< Domain >::move_history_score(), Aleph::SearchStats::move_ordering, Aleph::ExplorationPolicy::move_ordering, Aleph::MoveOrderingStats::ordered_batches, Aleph::MoveOrderingStats::ordered_moves, Aleph::Alpha_Beta< Domain >::policy_, Aleph::MoveOrderingStats::priority_estimates, Aleph::Array< T >::size(), Aleph::sort_ranked_moves(), Aleph::AdversarialSearchResult< Move, Score >::stats, Aleph::ExplorationPolicy::use_history_heuristic, and Aleph::ExplorationPolicy::use_killer_moves.

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

◆ default_policy()

template<AdversarialGameDomain Domain>
static ExplorationPolicy Aleph::Alpha_Beta< Domain >::default_policy ( )
inlinestaticnoexcept

Return the default exploration policy for Alpha-Beta.

Definition at line 97 of file Alpha_Beta.H.

References Aleph::Negamax< Domain >::default_policy().

Referenced by main(), TEST(), and TEST().

◆ domain() [1/2]

template<AdversarialGameDomain Domain>
const Domain & Aleph::Alpha_Beta< Domain >::domain ( ) const
inlinenoexcept

Read-only access to the bound game domain.

Definition at line 112 of file Alpha_Beta.H.

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

◆ domain() [2/2]

template<AdversarialGameDomain Domain>
Domain & Aleph::Alpha_Beta< Domain >::domain ( )
inlinenoexcept

Mutable access to the bound game domain.

Definition at line 118 of file Alpha_Beta.H.

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

◆ expansion_limit_reached()

template<AdversarialGameDomain Domain>
bool Aleph::Alpha_Beta< Domain >::expansion_limit_reached ( Result &  result)
inlineprivate

Definition at line 487 of file Alpha_Beta.H.

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

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

◆ history_bonus()

template<AdversarialGameDomain Domain>
static size_t Aleph::Alpha_Beta< Domain >::history_bonus ( const size_t  depth,
const size_t  remaining 
)
inlinestaticprivatenoexcept

Definition at line 351 of file Alpha_Beta.H.

References Aleph::Search_Unlimited.

Referenced by Aleph::Alpha_Beta< Domain >::record_cutoff_move().

◆ limits()

template<AdversarialGameDomain Domain>
const SearchLimits & Aleph::Alpha_Beta< Domain >::limits ( ) const
inlinenoexcept

Current hard limits.

Definition at line 130 of file Alpha_Beta.H.

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

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

◆ move_history_score()

template<AdversarialGameDomain Domain>
size_t Aleph::Alpha_Beta< Domain >::move_history_score ( const Move &  move) const
inlineprivatenoexcept

Definition at line 357 of file Alpha_Beta.H.

References Aleph::Alpha_Beta< Domain >::domain_, Aleph::Alpha_Beta< Domain >::history_moves_, Aleph::Alpha_Beta< Domain >::policy_, and Aleph::ExplorationPolicy::use_history_heuristic.

Referenced by Aleph::Alpha_Beta< Domain >::collect_ordered_moves().

◆ ordering_active()

template<AdversarialGameDomain Domain>
bool Aleph::Alpha_Beta< Domain >::ordering_active ( ) const
inlineprivatenoexcept

Definition at line 325 of file Alpha_Beta.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Domain, Aleph::ExplorationPolicy::move_ordering, Aleph::Alpha_Beta< Domain >::policy_, Aleph::ExplorationPolicy::use_history_heuristic, and Aleph::ExplorationPolicy::use_killer_moves.

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

◆ policy()

template<AdversarialGameDomain Domain>
const ExplorationPolicy & Aleph::Alpha_Beta< Domain >::policy ( ) const
inlinenoexcept

Current exploration policy.

Definition at line 124 of file Alpha_Beta.H.

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

Referenced by Aleph::Alpha_Beta< Domain >::set_policy().

◆ probe_transposition()

template<AdversarialGameDomain Domain>
template<typename Table , typename Keyer >
bool Aleph::Alpha_Beta< Domain >::probe_transposition ( State &  state,
const size_t  remaining,
Result &  result,
Table &  table,
Keyer &  keyer,
Score &  alpha,
Score &  beta,
adversarial_search_detail::NodeEvaluation< Move, Score > &  out 
)
inlineprivate

Definition at line 512 of file Alpha_Beta.H.

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

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

◆ record_cutoff_move()

template<AdversarialGameDomain Domain>
void Aleph::Alpha_Beta< Domain >::record_cutoff_move ( const size_t  depth,
const size_t  remaining,
const Move &  move 
)
inlineprivate

Definition at line 366 of file Alpha_Beta.H.

References Aleph::Alpha_Beta< Domain >::domain_, Aleph::Alpha_Beta< Domain >::history_bonus(), Aleph::Alpha_Beta< Domain >::history_moves_, Aleph::Alpha_Beta< Domain >::killer_moves_, Aleph::Alpha_Beta< Domain >::policy_, Aleph::ExplorationPolicy::use_history_heuristic, and Aleph::ExplorationPolicy::use_killer_moves.

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

◆ search() [1/6]

template<AdversarialGameDomain Domain>
Result Aleph::Alpha_Beta< Domain >::search ( State  initial_state)
inline

Execute Alpha-Beta from initial_state.

Parameters
[in]initial_stateRoot position.
Returns
Root score and one principal variation.
Exceptions
std::invalid_argumentif unsupported common-policy values are requested.

Definition at line 155 of file Alpha_Beta.H.

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

Referenced by Aleph::Alpha_Beta< Domain >::search(), Aleph::Alpha_Beta< Domain >::search(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), 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::Alpha_Beta< Domain >::search ( State  initial_state,
Table &  table 
)
inline

Execute Alpha-Beta with a transposition table using domain().state_key().

Definition at line 247 of file Alpha_Beta.H.

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

◆ search() [3/6]

template<AdversarialGameDomain Domain>
template<typename Table , typename Keyer >
requires AdversarialSearchKeyer<Table, Keyer, State, Move, Score>
Result Aleph::Alpha_Beta< Domain >::search ( State  initial_state,
Table &  table,
Keyer  keyer 
)
inline

Execute Alpha-Beta with a transposition table and explicit keyer.

Definition at line 199 of file Alpha_Beta.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Alpha_Beta< 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::Alpha_Beta< Domain >::search ( State  initial_state,
Table &  table,
Keyer  keyer,
Tracer &  tracer 
)
inline

Execute Alpha-Beta with TT/keyer and tracing.

Definition at line 209 of file Alpha_Beta.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Alpha_Beta< 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::Alpha_Beta< Domain >::search ( State  initial_state,
Table &  table,
Tracer &  tracer 
)
inline

Execute Alpha-Beta with domain-provided key and tracing.

Definition at line 268 of file Alpha_Beta.H.

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

◆ search() [6/6]

template<AdversarialGameDomain Domain>
template<typename Tracer >
requires AdversarialSearchTracer<Tracer, Move, Score>
Result Aleph::Alpha_Beta< Domain >::search ( State  initial_state,
Tracer &  tracer 
)
inline

Execute Alpha-Beta from initial_state while emitting trace events.

Definition at line 164 of file Alpha_Beta.H.

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

◆ search_impl()

template<AdversarialGameDomain Domain>
template<typename Table , typename Keyer , typename Tracer >
requires AdversarialSearchTracer<Tracer, Move, Score>
Result Aleph::Alpha_Beta< Domain >::search_impl ( State  initial_state,
Table &  table,
Keyer &  keyer,
Tracer &  tracer,
const Score  alpha,
const Score  beta 
)
inlineprivate

Definition at line 455 of file Alpha_Beta.H.

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

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

◆ search_node()

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

Definition at line 559 of file Alpha_Beta.H.

References Aleph::Alpha_Beta_Cutoff, Aleph::AdversarialSearchStats::alpha_beta_cutoffs, Aleph::blossom_maximum_cardinality_matching(), Aleph::Alpha_Beta< Domain >::collect_ordered_moves(), Aleph::Depth_Cutoff, Aleph::Alpha_Beta< 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::Alpha_Beta< Domain >::expansion_limit_reached(), Aleph::adversarial_search_detail::first_move_of(), Aleph::SearchStats::generated_successors, Aleph::Alpha_Beta< Domain >::limits_, Aleph::Lower_Bound, Aleph::SearchLimits::max_depth, Aleph::Alpha_Beta< Domain >::ordering_active(), Aleph::adversarial_search_detail::prepend_move(), Aleph::adversarial_search_detail::NodeEvaluation< Move, Score >::principal_variation, Aleph::Alpha_Beta< Domain >::probe_transposition(), Aleph::SearchStats::pruned_by_depth, Aleph::SearchStats::pruned_by_domain, Aleph::Alpha_Beta< Domain >::record_cutoff_move(), Aleph::search_engine_detail::register_visit(), Aleph::adversarial_search_detail::remaining_depth(), Aleph::Alpha_Beta< Domain >::search_node(), Aleph::search_engine_detail::should_prune_state(), Aleph::AdversarialSearchResult< Move, Score >::stats, Aleph::Alpha_Beta< Domain >::stop_, Aleph::Alpha_Beta< Domain >::store_transposition(), Aleph::Terminal_Node, Aleph::SearchStats::terminal_states, Aleph::Transposition_Hit, Aleph::Upper_Bound, and Aleph::adversarial_search_detail::NodeEvaluation< Move, Score >::value.

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

◆ search_with_window() [1/6]

template<AdversarialGameDomain Domain>
Result Aleph::Alpha_Beta< Domain >::search_with_window ( State  initial_state,
const Score  alpha,
const Score  beta 
)
inline

Execute Alpha-Beta with an explicit root window.

Definition at line 177 of file Alpha_Beta.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Alpha_Beta< Domain >::search_with_window().

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

◆ search_with_window() [2/6]

template<AdversarialGameDomain Domain>
template<typename Tracer >
requires AdversarialSearchTracer<Tracer, Move, Score>
Result Aleph::Alpha_Beta< Domain >::search_with_window ( State  initial_state,
const Score  alpha,
const Score  beta,
Tracer &  tracer 
)
inline

Execute Alpha-Beta with an explicit root window and tracing.

Definition at line 186 of file Alpha_Beta.H.

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

◆ search_with_window() [3/6]

template<AdversarialGameDomain Domain>
template<typename Table , typename D_ = Domain>
requires SearchStateKeyProvider<D_>
and AdversarialTranspositionMemo< Table, typename D_::State_Key, Move, Score > Result Aleph::Alpha_Beta< Domain >::search_with_window ( State  initial_state,
Table &  table,
const Score  alpha,
const Score  beta 
)
inline

Execute Alpha-Beta with domain-provided key and explicit root window.

Definition at line 287 of file Alpha_Beta.H.

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

◆ search_with_window() [4/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::Alpha_Beta< Domain >::search_with_window ( State  initial_state,
Table &  table,
const Score  alpha,
const Score  beta,
Tracer &  tracer 
)
inline

Execute Alpha-Beta with domain-provided key, root window and tracing.

Definition at line 306 of file Alpha_Beta.H.

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

◆ search_with_window() [5/6]

template<AdversarialGameDomain Domain>
template<typename Table , typename Keyer >
requires AdversarialSearchKeyer<Table, Keyer, State, Move, Score>
Result Aleph::Alpha_Beta< Domain >::search_with_window ( State  initial_state,
Table &  table,
Keyer  keyer,
const Score  alpha,
const Score  beta 
)
inline

Execute Alpha-Beta with TT/keyer and an explicit root window.

Definition at line 222 of file Alpha_Beta.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Alpha_Beta< Domain >::search_with_window().

◆ search_with_window() [6/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::Alpha_Beta< Domain >::search_with_window ( State  initial_state,
Table &  table,
Keyer  keyer,
const Score  alpha,
const Score  beta,
Tracer &  tracer 
)
inline

Execute Alpha-Beta with TT/keyer, root window and tracing.

Definition at line 233 of file Alpha_Beta.H.

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

◆ set_limits()

template<AdversarialGameDomain Domain>
void Aleph::Alpha_Beta< Domain >::set_limits ( const SearchLimits &  limits)
inlinenoexcept

Replace the hard limits for future runs.

Definition at line 142 of file Alpha_Beta.H.

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

◆ set_policy()

template<AdversarialGameDomain Domain>
void Aleph::Alpha_Beta< Domain >::set_policy ( const ExplorationPolicy &  policy)
inlinenoexcept

Replace the exploration policy for future runs.

Definition at line 136 of file Alpha_Beta.H.

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

◆ store_transposition()

template<AdversarialGameDomain Domain>
template<typename Table , typename Keyer >
void Aleph::Alpha_Beta< 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 499 of file Alpha_Beta.H.

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

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

◆ validate_ordering_configuration()

template<AdversarialGameDomain Domain>
void Aleph::Alpha_Beta< Domain >::validate_ordering_configuration ( ) const
inlineprivate

Definition at line 331 of file Alpha_Beta.H.

References ah_invalid_argument_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::Estimated_Bound, Aleph::ExplorationPolicy::move_ordering, Aleph::Alpha_Beta< Domain >::policy_, Aleph::ExplorationPolicy::use_history_heuristic, and Aleph::ExplorationPolicy::use_killer_moves.

Referenced by Aleph::Alpha_Beta< Domain >::search_impl().

Member Data Documentation

◆ domain_

template<AdversarialGameDomain Domain>
Domain Aleph::Alpha_Beta< Domain >::domain_
private

Definition at line 318 of file Alpha_Beta.H.

Referenced by Aleph::Alpha_Beta< Domain >::collect_ordered_moves(), Aleph::Alpha_Beta< Domain >::domain(), Aleph::Alpha_Beta< Domain >::domain(), Aleph::Alpha_Beta< Domain >::move_history_score(), Aleph::Alpha_Beta< Domain >::record_cutoff_move(), Aleph::Alpha_Beta< Domain >::search(), Aleph::Alpha_Beta< Domain >::search(), Aleph::Alpha_Beta< Domain >::search_node(), Aleph::Alpha_Beta< Domain >::search_with_window(), and Aleph::Alpha_Beta< Domain >::search_with_window().

◆ history_moves_

template<AdversarialGameDomain Domain>
History_Table Aleph::Alpha_Beta< Domain >::history_moves_
private

Definition at line 323 of file Alpha_Beta.H.

Referenced by Aleph::Alpha_Beta< Domain >::clear_ordering_heuristics(), Aleph::Alpha_Beta< Domain >::move_history_score(), and Aleph::Alpha_Beta< Domain >::record_cutoff_move().

◆ killer_moves_

template<AdversarialGameDomain Domain>
Killer_Table Aleph::Alpha_Beta< Domain >::killer_moves_
private

Definition at line 322 of file Alpha_Beta.H.

Referenced by Aleph::Alpha_Beta< Domain >::clear_ordering_heuristics(), Aleph::Alpha_Beta< Domain >::collect_ordered_moves(), and Aleph::Alpha_Beta< Domain >::record_cutoff_move().

◆ limits_

template<AdversarialGameDomain Domain>
SearchLimits Aleph::Alpha_Beta< Domain >::limits_
private

Definition at line 320 of file Alpha_Beta.H.

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

◆ policy_

template<AdversarialGameDomain Domain>
ExplorationPolicy Aleph::Alpha_Beta< Domain >::policy_
private

Definition at line 319 of file Alpha_Beta.H.

Referenced by Aleph::Alpha_Beta< Domain >::collect_ordered_moves(), Aleph::Alpha_Beta< Domain >::move_history_score(), Aleph::Alpha_Beta< Domain >::ordering_active(), Aleph::Alpha_Beta< Domain >::policy(), Aleph::Alpha_Beta< Domain >::record_cutoff_move(), Aleph::Alpha_Beta< Domain >::search_impl(), Aleph::Alpha_Beta< Domain >::set_policy(), and Aleph::Alpha_Beta< Domain >::validate_ordering_configuration().

◆ stop_

template<AdversarialGameDomain Domain>
bool Aleph::Alpha_Beta< Domain >::stop_ = false
private

Definition at line 321 of file Alpha_Beta.H.

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

◆ supports_best_first

template<AdversarialGameDomain Domain>
constexpr bool Aleph::Alpha_Beta< Domain >::supports_best_first = false
staticconstexpr

Compile-time marker: Alpha_Beta 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 94 of file Alpha_Beta.H.

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