state_search_common.H File Reference

Common infrastructure for implicit state-space search. More...

#include <chrono>
#include <concepts>
#include <cstddef>
#include <limits>
#include <optional>
#include <type_traits>
#include <utility>
#include <ah-concepts.H>
#include <ah-errors.H>
#include <htlist.H>
#include <search_move_ordering.H>
#include <tpl_array.H>
#include <tpl_hash.H>

Include dependency graph for state_search_common.H:

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

Go to the source code of this file.

Classes
struct	Aleph::SearchStats
	Counters collected during a search run. More...
struct	Aleph::SearchLimits
	Hard bounds applied by the search engine. More...
struct	Aleph::ExplorationPolicy
	Exploration controls shared across engines. More...
struct	Aleph::SearchSolution< State, Move >
	Snapshot of a concrete solution encountered during the traversal. More...
struct	Aleph::KeepFirstSolution< Solution >
	Comparison policy that keeps the first solution seen. More...
struct	Aleph::ContinueSearch
	Default solution visitor that always continues the search. More...
class	Aleph::SearchSolutionCollector< Solution >
	Collector that stores accepted solutions in an Aleph list. More...
class	Aleph::BestSolution< Solution, Compare >
	Tracks the best solution seen so far according to a comparator. More...
struct	Aleph::SearchResult< Solution, Compare >
	Aggregates the outcome of one search execution. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.
namespace	Aleph::search_engine_detail
	Shared helper utilities used internally by all search engines.

Concepts
concept	Aleph::SearchState
	Minimal requirement for mutable search states.
concept	Aleph::SearchMove
	Minimal requirement for search moves.
concept	Aleph::VisitedStateSet
	Concept for a set suitable for tracking globally visited states.
concept	Aleph::VisitedBoundMap
	Concept for a map tracking the best bound seen per visited state.
concept	Aleph::IncrementalBoundProvider
	Concept for domains that can estimate a move's bound without modifying state (incremental bound for Branch-and-Bound ordering).
concept	Aleph::IncrementalEvaluator
	Concept for adversarial-search domains that can estimate a child score without modifying state (incremental evaluator for Alpha_Beta Estimated_Score move ordering).
concept	Aleph::SupportsBestFirst
	Concept that checks whether a search engine supports the Best_First exploration strategy at compile time.
concept	Aleph::SearchSolutionVisitor
	Concept for callbacks invoked on each accepted solution.
concept	Aleph::SuccessorGenerator
	Concept for lazy successor generation.
concept	Aleph::GoalPredicate
	Concept for domains that can recognize goal states.
concept	Aleph::TerminalPredicate
	Optional concept for explicit non-solution terminal states.
concept	Aleph::DomainPruner
	Optional concept for domain-side pruning hooks.
concept	Aleph::MoveKeyProvider
	Optional concept for domains that can key moves for history heuristics.
concept	Aleph::SearchStateKeyProvider
	Generic concept for domains that can expose a stable state key.
concept	Aleph::HeuristicEvaluator
	Concept for domains that provide an admissible heuristic.
concept	Aleph::ActionCostProvider
	Concept for domains that provide the cost of applying a move.
concept	Aleph::BacktrackingDomain
	Minimal contract for DFS/backtracking domains.

Typedefs
template<SearchMove Move>
using	Aleph::SearchPath = Array< Move >
	Default Aleph container used to store a move path.
using	Aleph::SearchClock = std::chrono::steady_clock
	Monotonic clock used for search timings.
template<typename Key , typename Data , template< typename, typename, class > class HashMapTable = MapOLhash, class Cmp = Aleph::equal_to<Key>>
using	Aleph::SearchStorageMap = DynHashMap< Key, Data, HashMapTable, Cmp >
	Aleph hash map alias for memoization/transposition storage.
template<typename Key , template< typename, class > class HashSetTable = OLhashTable, class Cmp = Aleph::equal_to<Key>>
using	Aleph::SearchStorageSet = DynHashSet< Key, HashSetTable, Cmp >
	Aleph hash set alias for visited-state storage.
template<typename Solution , typename Compare = KeepFirstSolution<Solution>>
using	Aleph::Incumbent = BestSolution< Solution, Compare >
	Alias used by optimization/search engines for their current best.

Enumerations
enum class	Aleph::SearchStatus { Aleph::NotStarted , Aleph::Exhausted , Aleph::StoppedOnSolution , Aleph::LimitReached }
	Final state of a search execution. More...

Functions
double	Aleph::search_elapsed_ms (const SearchClock::duration &duration) noexcept
template<SearchMove Move>
void	Aleph::reserve_search_path (SearchPath< Move > &path, const SearchLimits &limits)
template<typename Domain >
bool	Aleph::search_engine_detail::is_terminal_state (const Domain &domain, const typename Domain::State &state)
	Dispatch helper for the optional is_terminal hook.
template<typename Domain >
bool	Aleph::search_engine_detail::should_prune_state (Domain &domain, const typename Domain::State &state, const size_t depth)
	Dispatch helper for the optional should_prune hook.
template<typename Result >
void	Aleph::search_engine_detail::register_visit (const size_t depth, Result &result)
	Update visit counters and max-depth statistic.
template<typename Result >
bool	Aleph::search_engine_detail::expansion_limit_reached (Result &result, const SearchLimits &limits)
	Check whether the expansion limit has been reached.
template<typename Result >
bool	Aleph::search_engine_detail::stop_after_solution (Result &result, const ExplorationPolicy &policy, const SearchLimits &limits)
	Decide whether to stop the search after a solution was accepted.

Variables
constexpr size_t	Aleph::Search_Unlimited = std::numeric_limits<size_t>::max()
	Sentinel used by SearchLimits to mean "no bound".

Detailed Description

Common infrastructure for implicit state-space search.

This module defines the small set of reusable types needed by the first generation of search engines over implicit trees and DAGs:

• search status, limits and statistics,
• incumbent/best-solution tracking,
• path and storage aliases based on Aleph containers,
• minimal concepts for states, moves and lazy successor generation.

The design intentionally starts with a small contract centered on State + Move + make/unmake, leaving room for later phases to add branch-and-bound, negamax and memoization on top of the same base.

Author

Leandro Rabindranath León

Definition in file state_search_common.H.