adversarial_search_test.cc

Go to the documentation of this file.

/*
                          Aleph_w
 
  Data structures & Algorithms
  version 2.0.0b
  https://github.com/lrleon/Aleph-w
 
  This file is part of Aleph-w library
 
  Copyright (c) 2002-2026 Leandro Rabindranath Leon
 
  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:
 
  The above copyright notice and this permission notice shall be included in all
  copies or substantial portions of the Software.
 
  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  SOFTWARE.
*/
 
#include <cstdint>
#include <memory>
#include <stdexcept>
#include <string>
 
#include <gtest/gtest.h>
 
#include <ah-errors.H>
#include <State_Search.H>
 
using namespace Aleph;
 
namespace
{
 
struct ArtificialGameState
{
  size_t depth = 0;
  size_t code = 1;
  int player = 1;
};
 
struct ArtificialGameMove
{
  size_t next_code = 1;
  char label = 'A';
};
 
class ArtificialGameDomain
{
public:
  using State = ArtificialGameState;
  using Move = ArtificialGameMove;
  using Score = int;
  using State_Key = std::uint64_t;
 
  bool is_terminal(const State &state) const
  {
    return state.depth == 2;
  }
 
  Score evaluate(const State &state) const
  {
    return root_score(state.code)*state.player;
  }
 
  [[nodiscard]] State_Key state_key(const State &state) const noexcept
  {
    return (static_cast<State_Key>(state.code) << 1) |
           static_cast<State_Key>(state.player > 0 ? 1 : 0);
  }
 
  void apply(State &state, const Move &move) const
  {
    state.code = move.next_code;
    state.player = -state.player;
    ++state.depth;
  }
 
  void undo(State &state, const Move&) const
  {
    --state.depth;
    state.player = -state.player;
    state.code /= 2;
  }
 
  template <typename Visitor>
  bool for_each_successor(const State &state, Visitor visit) const
  {
    if (state.depth >= 2)
      return true;
 
    switch (state.code)
      {
      case 1:
        if (not visit(Move{2, 'A'}))
          return false;
        return visit(Move{3, 'B'});
 
      case 2:
        if (not visit(Move{4, 'a'}))
          return false;
        return visit(Move{5, 'b'});
 
      case 3:
        if (not visit(Move{6, 'a'}))
          return false;
        return visit(Move{7, 'b'});
 
      default:
        return true;
      }
  }
 
private:
  [[nodiscard]] static Score root_score(const size_t code) noexcept
  {
    switch (code)
      {
      case 2: return 6;
      case 3: return 1;
      case 4: return 3;
      case 5: return 5;
      case 6: return 2;
      case 7: return 4;
      default: return 0;
      }
  }
};
 
struct TicTacToeState
{
  Array<int> board;
  int player = 1;
  size_t moves_played = 0;
 
  TicTacToeState() : board(size_t(9), 0)
  {
    // empty
  }
};
 
class TicTacToeDomain
{
public:
  struct Move
  {
    size_t cell = 0;
 
    [[nodiscard]] bool operator == (const Move &) const noexcept = default;
  };
 
  using State = TicTacToeState;
  using Score = int;
  using State_Key = std::uint64_t;
  using Move_Key = size_t;
 
  bool is_terminal(const State &state) const
  {
    return winner(state) != 0 or state.moves_played == 9;
  }
 
  Score evaluate(const State &state) const
  {
    const int win = winner(state);
    if (win != 0)
      return win == state.player ? 100 : -100;
 
    if (state.moves_played == 9)
      return 0;
 
    return heuristic(state, state.player) - heuristic(state, -state.player);
  }
 
  [[nodiscard]] State_Key state_key(const State &state) const noexcept
  {
    State_Key key = static_cast<State_Key>(state.player > 0 ? 1 : 2);
    for (size_t i = 0; i < state.board.size(); ++i)
      {
        key *= 3;
        if (state.board[i] == 1)
          key += 1;
        else if (state.board[i] == -1)
          key += 2;
      }
 
    return key;
  }
 
  [[nodiscard]] Move_Key move_key(const Move &move) const noexcept
  {
    return move.cell;
  }
 
  void apply(State &state, const Move &move) const
  {
    state.board[move.cell] = state.player;
    state.player = -state.player;
    ++state.moves_played;
  }
 
  void undo(State &state, const Move &move) const
  {
    --state.moves_played;
    state.player = -state.player;
    state.board[move.cell] = 0;
  }
 
  template <typename Visitor>
  bool for_each_successor(const State &state, Visitor visit) const
  {
    static constexpr size_t order[] = {1, 3, 5, 7, 0, 2, 6, 8, 4};
 
    for (const size_t cell : order)
      if (state.board[cell] == 0 and not visit(Move{cell}))
        return false;
 
    return true;
  }
 
private:
  [[nodiscard]] static int winner(const State &state) noexcept
  {
    static constexpr size_t lines[8][3] = {
      {0, 1, 2}, {3, 4, 5}, {6, 7, 8},
      {0, 3, 6}, {1, 4, 7}, {2, 5, 8},
      {0, 4, 8}, {2, 4, 6}
    };
 
    for (const auto &line : lines)
      {
        const int a = state.board[line[0]];
        if (a != 0 and a == state.board[line[1]] and a == state.board[line[2]])
          return a;
      }
 
    return 0;
  }
 
  [[nodiscard]] static Score heuristic(const State &state, const int player) noexcept
  {
    static constexpr size_t lines[8][3] = {
      {0, 1, 2}, {3, 4, 5}, {6, 7, 8},
      {0, 3, 6}, {1, 4, 7}, {2, 5, 8},
      {0, 4, 8}, {2, 4, 6}
    };
 
    Score total = 0;
    for (const auto &line : lines)
      {
        size_t mine = 0;
        size_t empty = 0;
        bool blocked = false;
 
        for (const size_t cell : line)
          if (state.board[cell] == player)
            ++mine;
          else if (state.board[cell] == 0)
            ++empty;
          else
            {
              blocked = true;
              break;
            }
 
        if (blocked)
          continue;
 
        if (mine == 2 and empty == 1)
          total += 10;
        else if (mine == 1 and empty == 2)
          total += 1;
      }
 
    return total;
  }
};
 
static_assert(AdversarialGameDomain<ArtificialGameDomain>);
static_assert(AdversarialGameDomain<TicTacToeDomain>);
 
std::string path_signature(const SearchPath<ArtificialGameMove> &path)
{
  std::string out;
  for (const auto &move : path)
    out.push_back(move.label);
  return out;
}
 
template <typename Move, typename Score>
size_t count_trace_events(const AdversarialTraceCollector<Move, Score> &collector,
                          const AdversarialTraceEventKind kind)
{
  size_t count = 0;
  collector.events().for_each(
    [&](const AdversarialTraceEvent<Move, Score> &event)
    {
      if (event.kind == kind)
        ++count;
    });
  return count;
}
 
TicTacToeState make_tictactoe_state(const char *layout, const int player)
{
  TicTacToeState state;
  state.player = player;
 
  for (size_t i = 0; i < 9; ++i)
    switch (layout[i])
      {
      case 'X':
        state.board[i] = 1;
        ++state.moves_played;
        break;
 
      case 'O':
        state.board[i] = -1;
        ++state.moves_played;
        break;
 
      default:
        state.board[i] = 0;
      }
 
  return state;
}
 
template <typename Domain>
[[nodiscard]] typename Domain::Score
replay_pv(Domain &domain,
          typename Domain::State state,
          const SearchPath<typename Domain::Move> &pv)
{
  for (const auto &move : pv)
    domain.apply(state, move);
 
  const auto leaf_value = domain.evaluate(state);
  return (pv.size() % 2 == 0) ? leaf_value : -leaf_value;
}
 
} // end namespace
 
TEST(AdversarialSearchFramework, ArtificialGameNegamaxFindsKnownValueAndPath)
{
  auto result = negamax_search(ArtificialGameDomain{}, ArtificialGameState{});
 
  EXPECT_TRUE(result.exhausted());
  EXPECT_EQ(result.value, 3);
  EXPECT_EQ(path_signature(result.principal_variation), "Aa");
  EXPECT_EQ(result.stats.visited_states, 7u);
  EXPECT_EQ(result.stats.expanded_states, 3u);
}
 
TEST(AdversarialSearchFramework, ArtificialGameAlphaBetaMatchesNegamaxAndPrunes)
{
  auto negamax = negamax_search(ArtificialGameDomain{}, ArtificialGameState{});
  auto alpha_beta = alpha_beta_search(ArtificialGameDomain{}, ArtificialGameState{});
 
  EXPECT_EQ(alpha_beta.value, negamax.value);
  EXPECT_EQ(path_signature(alpha_beta.principal_variation), "Aa");
  EXPECT_LT(alpha_beta.stats.visited_states, negamax.stats.visited_states);
  EXPECT_GT(alpha_beta.stats.alpha_beta_cutoffs, 0u);
}
 
TEST(AdversarialSearchFramework, ArtificialGameDepthLimitUsesHeuristicEvaluation)
{
  SearchLimits limits;
  limits.max_depth = 1;
 
  auto result = negamax_search(ArtificialGameDomain{}, ArtificialGameState{}, {}, limits);
 
  EXPECT_TRUE(result.exhausted());
  EXPECT_EQ(result.value, 6);
  EXPECT_EQ(path_signature(result.principal_variation), "A");
  EXPECT_EQ(result.stats.pruned_by_depth, 2u);
}
 
TEST(AdversarialSearchFramework, TicTacToeFindsImmediateWinningMove)
{
  const TicTacToeState state = make_tictactoe_state("XX.OO....", 1);
 
  auto negamax = negamax_search(TicTacToeDomain{}, state);
  auto alpha_beta = alpha_beta_search(TicTacToeDomain{}, state);
 
  EXPECT_EQ(negamax.value, 100);
  EXPECT_EQ(alpha_beta.value, 100);
  ASSERT_TRUE(alpha_beta.has_principal_variation());
  EXPECT_EQ(alpha_beta.first_move().cell, 2u);
  EXPECT_EQ(negamax.first_move().cell, alpha_beta.first_move().cell);
}
 
TEST(AdversarialSearchFramework, TicTacToeAlphaBetaMatchesNegamaxAndVisitsFewerNodes)
{
  TicTacToeState state;
 
  auto negamax = negamax_search(TicTacToeDomain{}, state);
  auto alpha_beta = alpha_beta_search(TicTacToeDomain{}, state);
 
  EXPECT_EQ(negamax.value, 0);
  EXPECT_EQ(alpha_beta.value, negamax.value);
  ASSERT_TRUE(negamax.has_principal_variation());
  ASSERT_TRUE(alpha_beta.has_principal_variation());
  EXPECT_EQ(alpha_beta.first_move().cell, negamax.first_move().cell);
  EXPECT_LT(alpha_beta.stats.visited_states, negamax.stats.visited_states);
  EXPECT_GT(alpha_beta.stats.alpha_beta_cutoffs, 0u);
}
 
TEST(AdversarialSearchFramework, InvalidBestFirstPolicyIsRejected)
{
  ExplorationPolicy policy = Negamax<ArtificialGameDomain>::default_policy();
  policy.strategy = ExplorationPolicy::Strategy::Best_First;
 
  Negamax<ArtificialGameDomain> negamax(ArtificialGameDomain{}, policy);
  Alpha_Beta<ArtificialGameDomain> alpha_beta(ArtificialGameDomain{}, policy);
 
  EXPECT_THROW((void) negamax.search(ArtificialGameState{}), std::invalid_argument);
  EXPECT_THROW((void) alpha_beta.search(ArtificialGameState{}), std::invalid_argument);
}
 
TEST(AdversarialSearchFramework, AlphaBetaHeuristicMoveOrderingReducesNodes)
{
  TicTacToeState state;
 
  Alpha_Beta<TicTacToeDomain> plain_engine(TicTacToeDomain{});
  auto plain = plain_engine.search(state);
 
  ExplorationPolicy ordered_policy = Alpha_Beta<TicTacToeDomain>::default_policy();
  ordered_policy.move_ordering = MoveOrderingMode::Estimated_Score;
  ordered_policy.use_killer_moves = true;
  ordered_policy.use_history_heuristic = true;
 
  Alpha_Beta<TicTacToeDomain> ordered_engine(TicTacToeDomain{}, ordered_policy);
  auto ordered = ordered_engine.search(state);
 
  EXPECT_EQ(ordered.value, plain.value);
  ASSERT_TRUE(plain.has_principal_variation());
  ASSERT_TRUE(ordered.has_principal_variation());
  EXPECT_LT(ordered.stats.visited_states, plain.stats.visited_states);
  EXPECT_EQ(ordered.first_move().cell, 4u);
  EXPECT_GT(ordered.stats.alpha_beta_cutoffs, 0u);
  EXPECT_GT(ordered.stats.move_ordering.ordered_batches, 0u);
  EXPECT_GT(ordered.stats.move_ordering.ordered_moves, 0u);
  EXPECT_GT(ordered.stats.move_ordering.priority_estimates, 0u);
}
 
TEST(AdversarialSearchFramework, NegamaxTranspositionTablePreservesResultAndReducesNodes)
{
  TicTacToeState state;
  Negamax<TicTacToeDomain> engine(TicTacToeDomain{});
 
  auto without_tt = engine.search(state);
 
  using TT = AdversarialTranspositionTable<TicTacToeDomain::State_Key,
                                           TicTacToeDomain::Move,
                                           TicTacToeDomain::Score>;
  TT table;
  auto with_tt = engine.search(state, table);
 
  EXPECT_EQ(with_tt.value, without_tt.value);
  ASSERT_TRUE(with_tt.has_principal_variation());
  ASSERT_TRUE(without_tt.has_principal_variation());
  EXPECT_EQ(with_tt.first_move().cell, without_tt.first_move().cell);
  EXPECT_LT(with_tt.stats.visited_states, without_tt.stats.visited_states);
  EXPECT_GT(with_tt.stats.transpositions.hits, 0u);
  EXPECT_GT(with_tt.stats.transpositions.cutoffs, 0u);
  EXPECT_GT(table.stats().stores, 0u);
}
 
TEST(AdversarialSearchFramework, AlphaBetaTranspositionTablePreservesResultAndReducesNodes)
{
  TicTacToeState state;
  Alpha_Beta<TicTacToeDomain> engine(TicTacToeDomain{});
 
  auto without_tt = engine.search(state);
 
  using TT = AdversarialTranspositionTable<TicTacToeDomain::State_Key,
                                           TicTacToeDomain::Move,
                                           TicTacToeDomain::Score>;
  TT table;
  auto with_tt = engine.search(state, table);
 
  EXPECT_EQ(with_tt.value, without_tt.value);
  ASSERT_TRUE(with_tt.has_principal_variation());
  ASSERT_TRUE(without_tt.has_principal_variation());
  EXPECT_EQ(with_tt.first_move().cell, without_tt.first_move().cell);
  EXPECT_LT(with_tt.stats.visited_states, without_tt.stats.visited_states);
  EXPECT_GT(with_tt.stats.transpositions.hits, 0u);
  EXPECT_GT(with_tt.stats.transpositions.cutoffs, 0u);
  EXPECT_GT(table.stats().stores, 0u);
}
 
TEST(AdversarialSearchFramework, NegamaxIterativeDeepeningCollectsPerDepthPV)
{
  SearchLimits limits;
  limits.max_depth = 2;
 
  auto fixed = negamax_search(ArtificialGameDomain{}, ArtificialGameState{}, {}, limits);
  auto iterative = iterative_deepening_negamax_search(ArtificialGameDomain{},
                                                      ArtificialGameState{},
                                                      {},
                                                      limits);
 
  ASSERT_TRUE(iterative.has_iterations());
  ASSERT_EQ(iterative.iterations.size(), 2u);
  EXPECT_EQ(iterative.completed_iterations, 2u);
 
  EXPECT_EQ(iterative.iterations[0].depth, 1u);
  EXPECT_EQ(iterative.iterations[0].result.value, 6);
  EXPECT_EQ(path_signature(iterative.iterations[0].result.principal_variation), "A");
 
  EXPECT_EQ(iterative.iterations[1].depth, 2u);
  EXPECT_EQ(iterative.iterations[1].result.value, fixed.value);
  EXPECT_EQ(path_signature(iterative.iterations[1].result.principal_variation), "Aa");
 
  EXPECT_EQ(iterative.result.value, fixed.value);
  EXPECT_EQ(path_signature(iterative.result.principal_variation), "Aa");
  EXPECT_GT(iterative.total_stats.visited_states, fixed.stats.visited_states);
}
 
TEST(AdversarialSearchFramework, AlphaBetaIterativeDeepeningAspirationPreservesValue)
{
  SearchLimits limits;
  limits.max_depth = 2;
 
  AdversarialIterativeDeepeningOptions<int> options;
  options.initial_depth = 1;
  options.depth_step = 1;
  options.aspiration.half_window = 1;
  options.aspiration.growth = 1;
 
  auto fixed = alpha_beta_search(ArtificialGameDomain{}, ArtificialGameState{}, {}, limits);
  auto iterative = iterative_deepening_alpha_beta_search(ArtificialGameDomain{},
                                                         ArtificialGameState{},
                                                         {},
                                                         limits,
                                                         options);
 
  ASSERT_EQ(iterative.iterations.size(), 2u);
  EXPECT_EQ(iterative.result.value, fixed.value);
  EXPECT_EQ(path_signature(iterative.result.principal_variation), "Aa");
  EXPECT_TRUE(iterative.iterations[1].used_aspiration_window);
  EXPECT_GT(iterative.iterations[1].aspiration_researches, 0u);
  EXPECT_GT(iterative.aspiration_researches, 0u);
}
 
TEST(AdversarialSearchFramework, AlphaBetaTracingRecordsIterationsAndCutoffs)
{
  SearchLimits limits;
  limits.max_depth = 2;
 
  AdversarialIterativeDeepeningOptions<int> options;
  options.initial_depth = 1;
  options.depth_step = 1;
  options.aspiration.half_window = 1;
  options.aspiration.growth = 1;
 
  AdversarialTraceCollector<ArtificialGameMove, int> trace;
  auto iterative = iterative_deepening_alpha_beta_search(ArtificialGameDomain{},
                                                         ArtificialGameState{},
                                                         trace,
                                                         {},
                                                         limits,
                                                         options);
 
  EXPECT_EQ(iterative.result.value, 3);
  EXPECT_GT(trace.size(), 0u);
  EXPECT_EQ(count_trace_events(trace, AdversarialTraceEventKind::Iteration_Begin), 2u);
  EXPECT_EQ(count_trace_events(trace, AdversarialTraceEventKind::Iteration_End), 2u);
  EXPECT_GT(count_trace_events(trace, AdversarialTraceEventKind::Alpha_Beta_Cutoff), 0u);
  EXPECT_GT(count_trace_events(trace, AdversarialTraceEventKind::Aspiration_Retry), 0u);
}
 
TEST(AdversarialSearchFramework, AlphaBetaIterativeDeepeningTTPreservesValueAndReducesNodes)
{
  TicTacToeState state;
 
  SearchLimits limits;
  limits.max_depth = 9;
 
  ExplorationPolicy ordered_policy = Alpha_Beta<TicTacToeDomain>::default_policy();
  ordered_policy.move_ordering = MoveOrderingMode::Estimated_Score;
  ordered_policy.use_killer_moves = true;
  ordered_policy.use_history_heuristic = true;
 
  AdversarialIterativeDeepeningOptions<int> options;
  options.initial_depth = 1;
  options.depth_step = 1;
  options.aspiration.half_window = 4;
  options.aspiration.growth = 4;
 
  auto without_tt = iterative_deepening_alpha_beta_search(TicTacToeDomain{},
                                                          state,
                                                          ordered_policy,
                                                          limits,
                                                          options);
 
  using TT = AdversarialTranspositionTable<TicTacToeDomain::State_Key,
                                           TicTacToeDomain::Move,
                                           TicTacToeDomain::Score>;
  TT table;
  auto with_tt = iterative_deepening_alpha_beta_search(TicTacToeDomain{},
                                                       state,
                                                       table,
                                                       ordered_policy,
                                                       limits,
                                                       options);
 
  EXPECT_EQ(with_tt.result.value, without_tt.result.value);
  ASSERT_TRUE(with_tt.result.has_principal_variation());
  ASSERT_TRUE(without_tt.result.has_principal_variation());
  EXPECT_EQ(with_tt.result.first_move().cell, without_tt.result.first_move().cell);
  EXPECT_LT(with_tt.total_stats.visited_states, without_tt.total_stats.visited_states);
  EXPECT_GT(table.stats().stores, 0u);
}
 
// --- search_with_window tests ---
 
TEST(AdversarialSearchFramework, SearchWithWindowWideWindowMatchesFullSearch)
{
  Alpha_Beta<ArtificialGameDomain> engine(ArtificialGameDomain{});
 
  auto full = engine.search(ArtificialGameState{});
  auto windowed = engine.search_with_window(ArtificialGameState{}, -1000, 1000);
 
  EXPECT_EQ(windowed.value, full.value);
  EXPECT_EQ(path_signature(windowed.principal_variation),
            path_signature(full.principal_variation));
}
 
TEST(AdversarialSearchFramework, SearchWithWindowExactWindowReturnsCorrectValue)
{
  Alpha_Beta<ArtificialGameDomain> engine(ArtificialGameDomain{});
 
  auto full = engine.search(ArtificialGameState{});
  auto windowed = engine.search_with_window(ArtificialGameState{},
                                            full.value - 1, full.value + 1);
 
  EXPECT_EQ(windowed.value, full.value);
  ASSERT_TRUE(windowed.has_principal_variation());
}
 
TEST(AdversarialSearchFramework, SearchWithWindowFailLowReturnsUpperBound)
{
  Alpha_Beta<ArtificialGameDomain> engine(ArtificialGameDomain{});
 
  auto full = engine.search(ArtificialGameState{});
  auto windowed = engine.search_with_window(ArtificialGameState{},
                                            full.value + 5, full.value + 10);
 
  EXPECT_LE(windowed.value, full.value + 5);
}
 
TEST(AdversarialSearchFramework, SearchWithWindowFailHighReturnsLowerBound)
{
  Alpha_Beta<ArtificialGameDomain> engine(ArtificialGameDomain{});
 
  auto full = engine.search(ArtificialGameState{});
  auto windowed = engine.search_with_window(ArtificialGameState{},
                                            full.value - 10, full.value - 5);
 
  EXPECT_GE(windowed.value, full.value - 5);
}
 
TEST(AdversarialSearchFramework, SearchWithWindowTicTacToeMatchesFullSearch)
{
  const TicTacToeState state = make_tictactoe_state("XX.OO....", 1);
 
  Alpha_Beta<TicTacToeDomain> engine(TicTacToeDomain{});
  auto full = engine.search(state);
  auto windowed = engine.search_with_window(state, -200, 200);
 
  EXPECT_EQ(windowed.value, full.value);
  ASSERT_TRUE(windowed.has_principal_variation());
  EXPECT_EQ(windowed.first_move().cell, full.first_move().cell);
}
 
TEST(AdversarialSearchFramework, SearchWithWindowTTPreservesResult)
{
  const TicTacToeState state = make_tictactoe_state("XX.OO....", 1);
 
  Alpha_Beta<TicTacToeDomain> engine(TicTacToeDomain{});
  auto full = engine.search(state);
 
  using TT = AdversarialTranspositionTable<TicTacToeDomain::State_Key,
                                           TicTacToeDomain::Move,
                                           TicTacToeDomain::Score>;
  TT table;
  auto windowed = engine.search_with_window(state, table, -200, 200);
 
  EXPECT_EQ(windowed.value, full.value);
  ASSERT_TRUE(windowed.has_principal_variation());
  EXPECT_EQ(windowed.first_move().cell, full.first_move().cell);
  EXPECT_GT(table.stats().stores, 0u);
}
 
TEST(AdversarialSearchFramework, SearchWithWindowNarrowPrunesMoreNodes)
{
  TicTacToeState state;
 
  Alpha_Beta<TicTacToeDomain> engine(TicTacToeDomain{});
  auto wide = engine.search_with_window(state, -200, 200);
  auto narrow = engine.search_with_window(state, -1, 1);
 
  EXPECT_LE(narrow.stats.visited_states, wide.stats.visited_states);
}
 
// ---------------------------------------------------------------------------
// Principal Variation Replay Verification (Recommendation 6)
// ---------------------------------------------------------------------------
 
TEST(AdversarialSearchFramework, NegamaxPVReplayMatchesReportedValue)
{
  ArtificialGameDomain domain;
  auto result = negamax_search(domain, ArtificialGameState{});
 
  ASSERT_TRUE(result.has_principal_variation());
  const auto replayed = replay_pv(domain, ArtificialGameState{},
                                  result.principal_variation);
  EXPECT_EQ(replayed, result.value);
}
 
TEST(AdversarialSearchFramework, AlphaBetaPVReplayMatchesReportedValue)
{
  ArtificialGameDomain domain;
  auto result = alpha_beta_search(domain, ArtificialGameState{});
 
  ASSERT_TRUE(result.has_principal_variation());
  const auto replayed = replay_pv(domain, ArtificialGameState{},
                                  result.principal_variation);
  EXPECT_EQ(replayed, result.value);
}
 
TEST(AdversarialSearchFramework, DepthLimitedNegamaxPVReplayMatchesReportedValue)
{
  ArtificialGameDomain domain;
  SearchLimits limits;
  limits.max_depth = 1;
 
  auto result = negamax_search(domain, ArtificialGameState{}, {}, limits);
 
  ASSERT_TRUE(result.has_principal_variation());
  const auto replayed = replay_pv(domain, ArtificialGameState{},
                                  result.principal_variation);
  EXPECT_EQ(replayed, result.value);
}
 
TEST(AdversarialSearchFramework, TicTacToeNegamaxPVReplayMatchesValue)
{
  TicTacToeDomain domain;
  TicTacToeState state;
 
  auto result = negamax_search(domain, state);
 
  ASSERT_TRUE(result.has_principal_variation());
  const auto replayed = replay_pv(domain, state, result.principal_variation);
  EXPECT_EQ(replayed, result.value);
}
 
TEST(AdversarialSearchFramework, TicTacToeAlphaBetaPVReplayMatchesValue)
{
  TicTacToeDomain domain;
  TicTacToeState state;
 
  auto result = alpha_beta_search(domain, state);
 
  ASSERT_TRUE(result.has_principal_variation());
  const auto replayed = replay_pv(domain, state, result.principal_variation);
  EXPECT_EQ(replayed, result.value);
}
 
TEST(AdversarialSearchFramework, TicTacToeWinningPositionPVReplay)
{
  TicTacToeDomain domain;
  const TicTacToeState state = make_tictactoe_state("XX.OO....", 1);
 
  auto negamax = negamax_search(domain, state);
  auto alpha_beta = alpha_beta_search(domain, state);
 
  ASSERT_TRUE(negamax.has_principal_variation());
  ASSERT_TRUE(alpha_beta.has_principal_variation());
  EXPECT_EQ(replay_pv(domain, state, negamax.principal_variation), negamax.value);
  EXPECT_EQ(replay_pv(domain, state, alpha_beta.principal_variation), alpha_beta.value);
}
 
TEST(AdversarialSearchFramework, TicTacToeWithTTPVReplayMatchesValue)
{
  TicTacToeDomain domain;
  TicTacToeState state;
 
  using TT = AdversarialTranspositionTable<TicTacToeDomain::State_Key,
                                           TicTacToeDomain::Move,
                                           TicTacToeDomain::Score>;
  TT table;
  Negamax<TicTacToeDomain> engine(domain);
  auto result = engine.search(state, table);
 
  ASSERT_TRUE(result.has_principal_variation());
  const auto replayed = replay_pv(domain, state, result.principal_variation);
  EXPECT_EQ(replayed, result.value);
}
 
TEST(AdversarialSearchFramework, IterativeDeepeningPVReplayMatchesValueAtEachDepth)
{
  ArtificialGameDomain domain;
  SearchLimits limits;
  limits.max_depth = 2;
 
  auto iterative = iterative_deepening_negamax_search(domain,
                                                      ArtificialGameState{},
                                                      {},
                                                      limits);
 
  ASSERT_TRUE(iterative.has_iterations());
  for (size_t i = 0; i < iterative.iterations.size(); ++i)
    {
      const auto &iter = iterative.iterations[i];
      ASSERT_TRUE(iter.result.has_principal_variation())
        << "Iteration " << i << " has no PV";
      const auto replayed = replay_pv(domain, ArtificialGameState{},
                                      iter.result.principal_variation);
      EXPECT_EQ(replayed, iter.result.value)
        << "PV replay mismatch at iteration " << i
        << " (depth " << iter.depth << ")";
    }
 
  ASSERT_TRUE(iterative.result.has_principal_variation());
  const auto final_replayed = replay_pv(domain, ArtificialGameState{},
                                        iterative.result.principal_variation);
  EXPECT_EQ(final_replayed, iterative.result.value);
}
 
TEST(AdversarialSearchFramework, AlphaBetaIterativeDeepeningPVReplayMatchesValue)
{
  ArtificialGameDomain domain;
  SearchLimits limits;
  limits.max_depth = 2;
 
  AdversarialIterativeDeepeningOptions<int> options;
  options.initial_depth = 1;
  options.depth_step = 1;
  options.aspiration.half_window = 1;
  options.aspiration.growth = 1;
 
  auto iterative = iterative_deepening_alpha_beta_search(domain,
                                                         ArtificialGameState{},
                                                         {},
                                                         limits,
                                                         options);
 
  ASSERT_TRUE(iterative.result.has_principal_variation());
  const auto replayed = replay_pv(domain, ArtificialGameState{},
                                  iterative.result.principal_variation);
  EXPECT_EQ(replayed, iterative.result.value);
 
  for (size_t i = 0; i < iterative.iterations.size(); ++i)
    {
      const auto &iter = iterative.iterations[i];
      ASSERT_TRUE(iter.result.has_principal_variation())
        << "Iteration " << i << " has no PV";
      const auto r = replay_pv(domain, ArtificialGameState{},
                                iter.result.principal_variation);
      EXPECT_EQ(r, iter.result.value)
        << "PV replay mismatch at iteration " << i;
    }
}
 
TEST(AdversarialSearchFramework, SearchWithWindowPVReplayMatchesValue)
{
  TicTacToeDomain domain;
  const TicTacToeState state = make_tictactoe_state("XX.OO....", 1);
 
  Alpha_Beta<TicTacToeDomain> engine(domain);
  auto result = engine.search_with_window(state, -200, 200);
 
  ASSERT_TRUE(result.has_principal_variation());
  const auto replayed = replay_pv(domain, state, result.principal_variation);
  EXPECT_EQ(replayed, result.value);
}
 
// ===========================================================================
// H1: Exception-safety tests for Negamax and Alpha_Beta
// ===========================================================================
 
namespace
{
 
struct AdversarialThrowState
{
  std::shared_ptr<bool> undo_called;
  size_t node = 0;
};
 
struct AdversarialThrowMove
{
  bool throw_on_apply = false;
};
 
// Domain where apply() throws — undo must NOT be called.
struct ThrowingApplyGameDomain
{
  using State = AdversarialThrowState;
  using Move = AdversarialThrowMove;
  using Score = int;
 
  bool is_terminal(const State &state) const
  {
    return state.node >= 1;
  }
 
  Score evaluate(const State &) const
  {
    return 0;
  }
 
  void apply(State &state, const Move &move) const
  {
    if (move.throw_on_apply)
      ah_runtime_error() << "apply failed";
    state.node = 1;
  }
 
  void undo(State &state, const Move &) const
  {
    *state.undo_called = true;
    state.node = 0;
  }
 
  template <typename Visitor>
  bool for_each_successor(const State &state, Visitor visit) const
  {
    if (state.node != 0)
      return true;
    return visit(Move{true});
  }
};
 
// Domain where apply() succeeds but the child evaluation (is_terminal/evaluate)
// throws — undo must be called to restore state.
struct ThrowingPostApplyGameDomain
{
  using State = AdversarialThrowState;
  using Move = AdversarialThrowMove;
  using Score = int;
 
  bool is_terminal(const State &state) const
  {
    if (state.node == 1)
      ah_runtime_error() << "post-apply is_terminal failed";
    return false;
  }
 
  Score evaluate(const State &) const
  {
    return 0;
  }
 
  void apply(State &state, const Move &) const
  {
    state.node = 1;
  }
 
  void undo(State &state, const Move &) const
  {
    *state.undo_called = true;
    state.node = 0;
  }
 
  template <typename Visitor>
  bool for_each_successor(const State &state, Visitor visit) const
  {
    if (state.node != 0)
      return true;
    return visit(Move{false});
  }
};
 
// Domain that always evaluates to 0 (forced draw at every leaf).
struct ForcedDrawGameDomain
{
  using State = ArtificialGameState;
  using Move = ArtificialGameMove;
  using Score = int;
 
  bool is_terminal(const State &state) const
  {
    return state.depth == 2;
  }
 
  Score evaluate(const State &) const
  {
    return 0;
  }
 
  void apply(State &state, const Move &move) const
  {
    state.code = move.next_code;
    state.player = -state.player;
    ++state.depth;
  }
 
  void undo(State &state, const Move &) const
  {
    --state.depth;
    state.player = -state.player;
    state.code /= 2;
  }
 
  template <typename Visitor>
  bool for_each_successor(const State &state, Visitor visit) const
  {
    if (state.depth >= 2)
      return true;
    if (not visit(ArtificialGameMove{2, 'L'}))
      return false;
    return visit(ArtificialGameMove{3, 'R'});
  }
};
 
// Domain where a non-terminal node has no successors (for_each_successor is
// a no-op even though is_terminal returns false).  The engine must treat such
// a node as a de-facto terminal and evaluate it.
struct EmptySuccessorGameDomain
{
  using State = ArtificialGameState;
  using Move = ArtificialGameMove;
  using Score = int;
 
  bool is_terminal(const State &) const
  {
    return false;  // explicitly NOT terminal
  }
 
  Score evaluate(const State &) const
  {
    return 42;
  }
 
  void apply(State &, const Move &) const
  {
    // never called
  }
 
  void undo(State &, const Move &) const
  {
    // never called
  }
 
  template <typename Visitor>
  bool for_each_successor(const State &, Visitor) const
  {
    return true;  // no successors generated
  }
};
 
// Domain where evaluate() returns score_ceiling (the extreme positive value).
// Used to verify the engine handles boundary scores without overflow.
struct ExtremeScoreGameDomain
{
  using State = ArtificialGameState;
  using Move = ArtificialGameMove;
  using Score = int;
 
  bool is_terminal(const State &state) const
  {
    return state.depth >= 1;
  }
 
  Score evaluate(const State &state) const
  {
    // root-child evaluates to ceiling from root player's perspective
    return adversarial_search_detail::score_ceiling<Score>() * state.player;
  }
 
  void apply(State &state, const Move &move) const
  {
    state.code = move.next_code;
    state.player = -state.player;
    ++state.depth;
  }
 
  void undo(State &state, const Move &) const
  {
    --state.depth;
    state.player = -state.player;
    state.code /= 2;
  }
 
  template <typename Visitor>
  bool for_each_successor(const State &state, Visitor visit) const
  {
    if (state.depth >= 1)
      return true;
    return visit(ArtificialGameMove{2, 'A'});
  }
};
 
// ---------------------------------------------------------------------------
// Domain that satisfies IncrementalEvaluator (evaluate_after) so the fast
// path in Alpha_Beta::collect_ordered_moves is exercised.
// Reuses the ArtificialGameDomain tree shape and leaf values.
// ---------------------------------------------------------------------------
class IncrementalEvalGameDomain
{
public:
  using State = ArtificialGameState;
  using Move = ArtificialGameMove;
  using Score = int;
 
  mutable size_t evaluate_after_calls = 0;
 
  bool is_terminal(const State &state) const
  {
    return state.depth == 2;
  }
 
  Score evaluate(const State &state) const
  {
    return root_score(state.code) * state.player;
  }
 
  Score evaluate_after(const State &state, const Move &move) const
  {
    ++evaluate_after_calls;
    // Compute child score without mutating state: simulate apply then evaluate.
    const int child_player = -state.player;
    return root_score(move.next_code) * child_player;
  }
 
  void apply(State &state, const Move &move) const
  {
    state.code = move.next_code;
    state.player = -state.player;
    ++state.depth;
  }
 
  void undo(State &state, const Move &) const
  {
    --state.depth;
    state.player = -state.player;
    state.code /= 2;
  }
 
  template <typename Visitor>
  bool for_each_successor(const State &state, Visitor visit) const
  {
    if (state.depth >= 2)
      return true;
 
    switch (state.code)
      {
      case 1:
        if (not visit(Move{2, 'A'}))
          return false;
        return visit(Move{3, 'B'});
 
      case 2:
        if (not visit(Move{4, 'a'}))
          return false;
        return visit(Move{5, 'b'});
 
      case 3:
        if (not visit(Move{6, 'a'}))
          return false;
        return visit(Move{7, 'b'});
 
      default:
        return true;
      }
  }
 
private:
  [[nodiscard]] static Score root_score(const size_t code) noexcept
  {
    switch (code)
      {
      case 2: return 6;
      case 3: return 1;
      case 4: return 3;
      case 5: return 5;
      case 6: return 2;
      case 7: return 4;
      default: return 0;
      }
  }
};
 
} // end namespace
 
// ---------------------------------------------------------------------------
// H1: apply() throws — undo must not be called
// ---------------------------------------------------------------------------
 
TEST(AdversarialSearchFramework, NegamaxApplyExceptionDoesNotCallUndo)
{
  auto undo_called = std::make_shared<bool>(false);
  ThrowingApplyGameDomain domain;
  SearchLimits limits;
  limits.max_depth = 4;
 
  Negamax<ThrowingApplyGameDomain> engine(domain, {}, limits);
  EXPECT_THROW((void) engine.search(AdversarialThrowState{undo_called, 0}),
               std::runtime_error);
  EXPECT_FALSE(*undo_called);
}
 
TEST(AdversarialSearchFramework, AlphaBetaApplyExceptionDoesNotCallUndo)
{
  auto undo_called = std::make_shared<bool>(false);
  ThrowingApplyGameDomain domain;
  SearchLimits limits;
  limits.max_depth = 4;
 
  Alpha_Beta<ThrowingApplyGameDomain> engine(domain, {}, limits);
  EXPECT_THROW((void) engine.search(AdversarialThrowState{undo_called, 0}),
               std::runtime_error);
  EXPECT_FALSE(*undo_called);
}
 
// ---------------------------------------------------------------------------
// H1: post-apply exception — undo must be called
// ---------------------------------------------------------------------------
 
TEST(AdversarialSearchFramework, NegamaxPostApplyExceptionCallsUndo)
{
  auto undo_called = std::make_shared<bool>(false);
  ThrowingPostApplyGameDomain domain;
  SearchLimits limits;
  limits.max_depth = 4;
 
  Negamax<ThrowingPostApplyGameDomain> engine(domain, {}, limits);
  EXPECT_THROW((void) engine.search(AdversarialThrowState{undo_called, 0}),
               std::runtime_error);
  EXPECT_TRUE(*undo_called);
}
 
TEST(AdversarialSearchFramework, AlphaBetaPostApplyExceptionCallsUndo)
{
  auto undo_called = std::make_shared<bool>(false);
  ThrowingPostApplyGameDomain domain;
  SearchLimits limits;
  limits.max_depth = 4;
 
  Alpha_Beta<ThrowingPostApplyGameDomain> engine(domain, {}, limits);
  EXPECT_THROW((void) engine.search(AdversarialThrowState{undo_called, 0}),
               std::runtime_error);
  EXPECT_TRUE(*undo_called);
}
 
// ---------------------------------------------------------------------------
// H4: forced draw — both engines return value == 0
// ---------------------------------------------------------------------------
 
TEST(AdversarialSearchFramework, ForcedDrawReturnZeroScore)
{
  ForcedDrawGameDomain domain;
  SearchLimits limits;
  limits.max_depth = 2;
 
  auto negamax = negamax_search(domain, ArtificialGameState{}, {}, limits);
  auto ab = alpha_beta_search(domain, ArtificialGameState{}, {}, limits);
 
  EXPECT_EQ(negamax.value, 0);
  EXPECT_EQ(ab.value, 0);
  EXPECT_TRUE(negamax.exhausted());
  EXPECT_TRUE(ab.exhausted());
}
 
// ---------------------------------------------------------------------------
// H4: empty successor list in a non-terminal — treated as de-facto terminal
// ---------------------------------------------------------------------------
 
TEST(AdversarialSearchFramework, EmptySuccessorsInNonTerminalTreatedAsLeaf)
{
  EmptySuccessorGameDomain domain;
  SearchLimits limits;
  limits.max_depth = 4;
 
  auto negamax = negamax_search(domain, ArtificialGameState{}, {}, limits);
  auto ab = alpha_beta_search(domain, ArtificialGameState{}, {}, limits);
 
  // The root has no successors, so it is evaluated directly.
  // evaluate() returns 42 (from the side-to-move's perspective at depth 0,
  // player==1), so the root score should be 42.
  EXPECT_EQ(negamax.value, 42);
  EXPECT_EQ(ab.value, 42);
  EXPECT_GT(negamax.stats.terminal_states, 0u);
  EXPECT_GT(ab.stats.terminal_states, 0u);
}
 
// ---------------------------------------------------------------------------
// H4: extreme score (score_ceiling) — no overflow
// ---------------------------------------------------------------------------
 
TEST(AdversarialSearchFramework, ExtremePositiveScoreDoesNotOverflow)
{
  ExtremeScoreGameDomain domain;
  SearchLimits limits;
  limits.max_depth = 2;
 
  auto negamax = negamax_search(domain, ArtificialGameState{}, {}, limits);
  auto ab = alpha_beta_search(domain, ArtificialGameState{}, {}, limits);
 
  // score_ceiling is the max representable "normal" score; both engines
  // must return a finite, positive value.
  const int ceiling = adversarial_search_detail::score_ceiling<int>();
  EXPECT_GT(negamax.value, 0);
  EXPECT_LE(negamax.value, ceiling);
  EXPECT_EQ(ab.value, negamax.value);
  EXPECT_TRUE(negamax.has_principal_variation());
}
 
// ---------------------------------------------------------------------------
// H5: IncrementalEvaluator fast path — evaluate_after() is used for ordering
// ---------------------------------------------------------------------------
 
TEST(AdversarialSearchFramework, AlphaBetaIncrementalEvaluatorUsesEvaluateAfter)
{
  IncrementalEvalGameDomain domain;
  ExplorationPolicy policy;
  policy.move_ordering = MoveOrderingMode::Estimated_Score;
  SearchLimits limits;
  limits.max_depth = 2;
 
  Alpha_Beta<IncrementalEvalGameDomain> engine(domain, policy, limits);
  auto result = engine.search(ArtificialGameState{});
 
  // The tree has the same structure as ArtificialGameDomain, so the minimax
  // value must match: max(min(3,5), min(2,4)) = max(3,2) = 3.
  EXPECT_EQ(result.value, 3);
  EXPECT_TRUE(result.exhausted());
 
  // evaluate_after must have been called at least once (the fast path).
  EXPECT_GT(engine.domain().evaluate_after_calls, 0u);
 
  // Move ordering stats must show that priority estimates were computed.
  EXPECT_GT(result.stats.move_ordering.priority_estimates, 0u);
}
 
TEST(AdversarialSearchFramework, AlphaBetaIncrementalEvaluatorMatchesLegacy)
{
  // Verify that IncrementalEvaluator produces the same result as legacy
  // apply()/evaluate() ordering (ArtificialGameDomain).
  ArtificialGameDomain legacy_domain;
  IncrementalEvalGameDomain incr_domain;
 
  ExplorationPolicy policy;
  policy.move_ordering = MoveOrderingMode::Estimated_Score;
  SearchLimits limits;
  limits.max_depth = 2;
 
  auto legacy = alpha_beta_search(legacy_domain, ArtificialGameState{}, policy, limits);
  auto incr = alpha_beta_search(incr_domain, ArtificialGameState{}, policy, limits);
 
  EXPECT_EQ(legacy.value, incr.value);
  EXPECT_EQ(legacy.stats.terminal_states, incr.stats.terminal_states);
}