Negamax search for two-player zero-sum turn-based games. More...

#include <concepts>
#include <limits>
#include <type_traits>
#include <utility>
#include <ah-errors.H>
#include <state_search_common.H>
#include <Transposition_Table.H>

Include dependency graph for Negamax.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	Aleph::AdversarialSearchStats
	Statistics collected by adversarial search engines. More...

struct	Aleph::AdversarialTranspositionEntry< Move, Score >
	Cached adversarial-search entry stored in transposition tables. More...

struct	Aleph::Prefer_Exact_Adversarial_Entry< Move, Score >
	Replacement policy for adversarial transposition entries. More...

struct	Aleph::AdversarialTranspositionKey< StateKey >
	Convenience alias for adversarial transposition tables. More...

struct	Aleph::AdversarialSearchResult< Move, Score >
	Result of one adversarial search execution. More...

struct	Aleph::AdversarialTraceEvent< Move, Score >
	One trace event produced by an adversarial search. More...

struct	Aleph::Null_Adversarial_Search_Tracer
	Default no-op tracer used when the caller does not request tracing. More...

class	Aleph::AdversarialTraceCollector< Move, Score >
	Collector that stores trace events in an Aleph list. More...

struct	Aleph::AspirationWindow< Score >
	Aspiration-window configuration for iterative deepening. More...

struct	Aleph::AdversarialIterativeDeepeningOptions< Score >
	Controls for adversarial iterative deepening. More...

struct	Aleph::AdversarialIterativeDeepeningIteration< Move, Score >
	Result of one iterative-deepening iteration. More...

struct	Aleph::AdversarialIterativeDeepeningResult< Move, Score >
	Aggregate result of adversarial iterative deepening. More...

struct	Aleph::adversarial_search_detail::Null_Transposition_Table< Entry >

struct	Aleph::adversarial_search_detail::Dummy_State_Key

struct	Aleph::adversarial_search_detail::History_Table_Selector< Domain, Supported >

struct	Aleph::adversarial_search_detail::History_Table_Selector< Domain, true >

struct	Aleph::adversarial_search_detail::NodeEvaluation< Move, Score >

class	Aleph::Negamax< Domain >
	Pure Negamax search over an implicit game tree. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

namespace	Aleph::adversarial_search_detail

Concepts
concept	Aleph::AdversarialScore
	Score type accepted by adversarial search engines.

concept	Aleph::AdversarialTranspositionMemo
	Concept for memo tables storing adversarial-search entries.

concept	Aleph::AdversarialSearchTracer
	Concept for adversarial-search trace sinks.

concept	Aleph::AdversarialSearchKeyer
	Concept for explicit state-key providers used by adversarial TT overloads.

concept	Aleph::GameEvaluator
	Required evaluator contract for zero-sum games.

concept	Aleph::AdversarialGameDomain
	Minimal contract for alternating-turn zero-sum games.

Typedefs
template<typename StateKey , SearchMove Move, AdversarialScore Score, template< typename, typename, class > class HashMapTable = MapOLhash, class Cmp = Aleph::equal_to<AdversarialTranspositionKey<StateKey>>>
using	Aleph::AdversarialTranspositionTable = Transposition_Table< AdversarialTranspositionKey< StateKey >, AdversarialTranspositionEntry< Move, Score >, HashMapTable, Cmp, Prefer_Exact_Adversarial_Entry< Move, Score > >

Enumerations
enum class	Aleph::AdversarialTraceEventKind { Aleph::Enter_Node , Aleph::Exit_Node , Aleph::Terminal_Node , Aleph::Depth_Cutoff , Aleph::Domain_Prune , Aleph::Expansion_Limit , Aleph::Alpha_Beta_Cutoff , Aleph::Transposition_Hit , Aleph::Iteration_Begin , Aleph::Iteration_End , Aleph::Aspiration_Retry }
	Trace event kinds emitted by adversarial search engines. More...

Functions
template<typename StateKey >
size_t	Aleph::aleph_hash_value (const AdversarialTranspositionKey< StateKey > &key) noexcept

template<AdversarialScore Score>
constexpr Score	Aleph::adversarial_search_detail::score_floor () noexcept

template<AdversarialScore Score>
constexpr Score	Aleph::adversarial_search_detail::score_ceiling () noexcept

template<typename Result >
void	Aleph::adversarial_search_detail::mark_limit_reached (Result &result)

template<SearchMove Move>
SearchPath< Move >	Aleph::adversarial_search_detail::prepend_move (const Move &move, const SearchPath< Move > &tail)

template<typename Domain , typename Result >
auto	Aleph::adversarial_search_detail::evaluate_leaf (Domain &domain, const typename Domain::State &state, Result &result)

constexpr size_t	Aleph::adversarial_search_detail::remaining_depth (const SearchLimits &limits, const size_t depth) noexcept

void	Aleph::adversarial_search_detail::accumulate_move_ordering_stats (MoveOrderingStats &dst, const MoveOrderingStats &src) noexcept

void	Aleph::adversarial_search_detail::accumulate_transposition_stats (TranspositionStats &dst, const TranspositionStats &src) noexcept

void	Aleph::adversarial_search_detail::accumulate_search_stats (SearchStats &dst, const SearchStats &src) noexcept

void	Aleph::adversarial_search_detail::accumulate_adversarial_stats (AdversarialSearchStats &dst, const AdversarialSearchStats &src) noexcept

template<SearchMove Move, AdversarialScore Score, typename Tracer > requires AdversarialSearchTracer<Tracer, Move, Score>
void	Aleph::adversarial_search_detail::emit_trace (Tracer &tracer, const AdversarialTraceEventKind kind, const size_t depth, const size_t remaining, const size_t iteration=0, const size_t horizon=0, const size_t aspiration_retries=0, const Score value=Score{}, const Score alpha=Score{}, const Score beta=Score{}, const std::optional< Move > &move=std::nullopt, const SearchPath< Move > *principal_variation=nullptr)

template<SearchMove Move>
std::optional< Move >	Aleph::adversarial_search_detail::first_move_of (const SearchPath< Move > &path)

template<AdversarialScore Score>
constexpr Score	Aleph::adversarial_search_detail::saturating_subtract (const Score value, const Score delta) noexcept

template<AdversarialScore Score>
constexpr Score	Aleph::adversarial_search_detail::saturating_add (const Score value, const Score delta) noexcept

template<AdversarialScore Score>
constexpr Score	Aleph::adversarial_search_detail::grow_aspiration_half_window (const Score current, const AspirationWindow< Score > &window) noexcept

template<SearchMove Move, AdversarialScore Score, typename State , typename Table , typename Keyer , typename Result >
void	Aleph::adversarial_search_detail::store_adversarial_transposition (State &state, const size_t remaining, Result &result, Table &table, Keyer &keyer, const NodeEvaluation< Move, Score > &value, const TranspositionBound bound, const bool stop)
	Build an adversarial transposition-table entry and store it.

template<SearchMove Move, AdversarialScore Score, typename State , typename Table , typename Keyer , typename Result >
AdversarialTranspositionEntry< Move, Score > *	Aleph::adversarial_search_detail::probe_and_count_transposition (State &state, const size_t remaining, Result &result, Table &table, Keyer &keyer)
	Probe a transposition table and update probe/hit/miss statistics.

template<SearchMove Move, AdversarialScore Score, typename Engine , typename Tracer , typename RunOneIteration > requires AdversarialSearchTracer<Tracer, Move, Score>
AdversarialIterativeDeepeningResult< Move, Score >	Aleph::adversarial_search_detail::run_iterative_deepening (Engine &engine, const ExplorationPolicy &policy, const SearchLimits &limits, const AdversarialIterativeDeepeningOptions< Score > &options, Tracer &tracer, RunOneIteration &&run_one_iteration)
	Core iterative-deepening loop shared by Negamax and Alpha-Beta.

template<AdversarialGameDomain Domain>
auto	Aleph::negamax_search (Domain domain, typename Domain::State initial_state, ExplorationPolicy policy=Negamax< Domain >::default_policy(), SearchLimits limits={})
	Convenience wrapper for one-shot Negamax search.

template<AdversarialGameDomain Domain, typename Tracer > requires AdversarialSearchTracer<Tracer, typename Domain::Move, typename Domain::Score>
auto	Aleph::negamax_search (Domain domain, typename Domain::State initial_state, Tracer &tracer, ExplorationPolicy policy=Negamax< Domain >::default_policy(), SearchLimits limits={})
	Convenience wrapper for one-shot Negamax search with tracing.

template<AdversarialGameDomain Domain, typename Table , typename Keyer > requires AdversarialSearchKeyer<Table, Keyer, typename Domain::State, typename Domain::Move, typename Domain::Score>
auto	Aleph::negamax_search (Domain domain, typename Domain::State initial_state, Table &table, Keyer keyer, ExplorationPolicy policy=Negamax< Domain >::default_policy(), SearchLimits limits={})
	Convenience wrapper for Negamax search with transposition table.

template<AdversarialGameDomain Domain, typename Table , typename Keyer , typename Tracer > requires AdversarialSearchKeyer<Table, Keyer, typename Domain::State, typename Domain::Move, typename Domain::Score>
and AdversarialSearchTracer< Tracer, typename Domain::Move, typename Domain::Score > auto	Aleph::negamax_search (Domain domain, typename Domain::State initial_state, Table &table, Keyer keyer, Tracer &tracer, ExplorationPolicy policy=Negamax< Domain >::default_policy(), SearchLimits limits={})
	Convenience wrapper for Negamax search with TT/keyer and tracing.

template<AdversarialGameDomain Domain, typename Table > requires SearchStateKeyProvider<Domain>
and AdversarialTranspositionMemo< Table, typename Domain::State_Key, typename Domain::Move, typename Domain::Score > auto	Aleph::negamax_search (Domain domain, typename Domain::State initial_state, Table &table, ExplorationPolicy policy=Negamax< Domain >::default_policy(), SearchLimits limits={})
	Convenience wrapper for Negamax search with domain-provided state key.

template<AdversarialGameDomain Domain, typename Table , typename Tracer > requires SearchStateKeyProvider<Domain>
and AdversarialTranspositionMemo< Table, typename Domain::State_Key, typename Domain::Move, typename Domain::Score > and AdversarialSearchTracer< Tracer, typename Domain::Move, typename Domain::Score > auto	Aleph::negamax_search (Domain domain, typename Domain::State initial_state, Table &table, Tracer &tracer, ExplorationPolicy policy=Negamax< Domain >::default_policy(), SearchLimits limits={})
	Convenience wrapper for Negamax search with domain-provided key and tracing.

template<AdversarialGameDomain Domain>
auto	Aleph::iterative_deepening_negamax_search (Domain domain, typename Domain::State initial_state, ExplorationPolicy policy=Negamax< Domain >::default_policy(), SearchLimits limits={}, AdversarialIterativeDeepeningOptions< typename Domain::Score > options={})
	Iterative deepening over Negamax without transposition table.

template<AdversarialGameDomain Domain, typename Tracer > requires AdversarialSearchTracer<Tracer, typename Domain::Move, typename Domain::Score>
auto	Aleph::iterative_deepening_negamax_search (Domain domain, typename Domain::State initial_state, Tracer &tracer, ExplorationPolicy policy=Negamax< Domain >::default_policy(), SearchLimits limits={}, AdversarialIterativeDeepeningOptions< typename Domain::Score > options={})
	Iterative deepening over Negamax with tracing.

template<AdversarialGameDomain Domain, typename Table , typename Keyer > requires AdversarialSearchKeyer<Table, Keyer, typename Domain::State, typename Domain::Move, typename Domain::Score>
auto	Aleph::iterative_deepening_negamax_search (Domain domain, typename Domain::State initial_state, Table &table, Keyer keyer, ExplorationPolicy policy=Negamax< Domain >::default_policy(), SearchLimits limits={}, AdversarialIterativeDeepeningOptions< typename Domain::Score > options={})
	Iterative deepening over Negamax with TT/keyer reuse across iterations.

template<AdversarialGameDomain Domain, typename Table , typename Keyer , typename Tracer > requires AdversarialSearchKeyer<Table, Keyer, typename Domain::State, typename Domain::Move, typename Domain::Score>
and AdversarialSearchTracer< Tracer, typename Domain::Move, typename Domain::Score > auto	Aleph::iterative_deepening_negamax_search (Domain domain, typename Domain::State initial_state, Table &table, Keyer keyer, Tracer &tracer, ExplorationPolicy policy=Negamax< Domain >::default_policy(), SearchLimits limits={}, AdversarialIterativeDeepeningOptions< typename Domain::Score > options={})
	Iterative deepening over Negamax with TT/keyer reuse and tracing.

template<AdversarialGameDomain Domain, typename Table > requires SearchStateKeyProvider<Domain>
and AdversarialTranspositionMemo< Table, typename Domain::State_Key, typename Domain::Move, typename Domain::Score > auto	Aleph::iterative_deepening_negamax_search (Domain domain, typename Domain::State initial_state, Table &table, ExplorationPolicy policy=Negamax< Domain >::default_policy(), SearchLimits limits={}, AdversarialIterativeDeepeningOptions< typename Domain::Score > options={})
	Iterative deepening over Negamax using `domain.state_key()`.

template<AdversarialGameDomain Domain, typename Table , typename Tracer > requires SearchStateKeyProvider<Domain>
and AdversarialTranspositionMemo< Table, typename Domain::State_Key, typename Domain::Move, typename Domain::Score > and AdversarialSearchTracer< Tracer, typename Domain::Move, typename Domain::Score > auto	Aleph::iterative_deepening_negamax_search (Domain domain, typename Domain::State initial_state, Table &table, Tracer &tracer, ExplorationPolicy policy=Negamax< Domain >::default_policy(), SearchLimits limits={}, AdversarialIterativeDeepeningOptions< typename Domain::Score > options={})
	Iterative deepening over Negamax using `domain.state_key()` and tracing.

Detailed Description

Negamax search for two-player zero-sum turn-based games.

This module introduces the adversarial-search layer of the framework while keeping it separate from optimization search:

games are modeled as implicit state spaces with apply() / undo(),
evaluation is always interpreted from the side-to-move perspective,
results expose one principal variation instead of "solutions",
limits and baseline traversal statistics are reused from state_search_common.H.

The implementation targets deterministic, perfect-information, alternating- turn, zero-sum games. It is intentionally small so Alpha-Beta can reuse the same contract without pulling game-specific semantics into branch and bound.

Author: Leandro Rabindranath León

Definition in file Negamax.H.

Classes

Namespaces

Concepts

Typedefs

Enumerations

Functions

Detailed Description