Autonomous Agent Gaming

"""
Chess Game Agent using python-chess

Complete implementation of a chess-playing agent with move evaluation,
position analysis, and game playing capabilities.

Requires: pip install python-chess
"""

import chess
from enum import Enum
from typing import Optional, Tuple


class ChessAgent:
    """Chess-playing agent using the python-chess library."""

    def __init__(self):
        """Initialize the chess agent with a new board."""
        self.board = chess.Board()
        self.move_count = 0

    def play_game(self, opponent_agent=None) -> Tuple[str, int]:
        """
        Play a complete chess game.

        Args:
            opponent_agent: Another agent to play against. If None, random moves.

        Returns:
            Tuple of (game_result, move_count)
            - game_result: "1-0" (white wins), "0-1" (black wins), "1/2-1/2" (draw)
            - move_count: Total number of half-moves
        """
        self.move_count = 0

        while not self.board.is_game_over():
            if self.board.turn:  # White's turn
                move = self.get_best_move()
            else:  # Black's turn
                if opponent_agent:
                    move = opponent_agent.get_best_move()
                else:
                    move = self.get_random_move()

            self.board.push(move)
            self.move_count += 1

        return self.board.result(), self.move_count

    def get_best_move(self) -> Optional[chess.Move]:
        """
        Find the best move in the current position using positional evaluation.

        Evaluates each legal move and returns the one with highest score.

        Returns:
            Best move in the current position
        """
        legal_moves = list(self.board.legal_moves)

        if not legal_moves:
            return None

        best_move = None
        best_score = float('-inf')

        for move in legal_moves:
            self.board.push(move)
            score = self.evaluate_position()
            self.board.pop()

            if score > best_score:
                best_score = score
                best_move = move

        return best_move

    def evaluate_position(self) -> int:
        """
        Evaluate the current position based on material count.

        Uses standard piece values:
        - Pawn: 1
        - Knight/Bishop: 3
        - Rook: 5
        - Queen: 9

        Args:
            None

        Returns:
            Score from white's perspective (positive = advantage)
        """
        piece_values = {
            chess.PAWN: 1,
            chess.KNIGHT: 3,
            chess.BISHOP: 3,
            chess.ROOK: 5,
            chess.QUEEN: 9
        }

        score = 0
        for piece_type, value in piece_values.items():
            white_count = len(self.board.pieces(piece_type, chess.WHITE))
            black_count = len(self.board.pieces(piece_type, chess.BLACK))
            score += (white_count - black_count) * value

        return score

    def get_random_move(self) -> Optional[chess.Move]:
        """
        Get a random legal move.

        Useful for baseline opponent or random playouts.

        Returns:
            Random legal move, or None if none available
        """
        legal_moves = list(self.board.legal_moves)
        if not legal_moves:
            return None
        return legal_moves[0]  # Should use random.choice() in practice

    def get_board_state(self) -> str:
        """
        Get string representation of the current board.

        Returns:
            ASCII representation of the board
        """
        return str(self.board)

    def get_fen(self) -> str:
        """
        Get FEN (Forsyth-Edwards Notation) of current position.

        Returns:
            FEN string
        """
        return self.board.fen()

    def set_fen(self, fen: str):
        """
        Set board position from FEN string.

        Args:
            fen: Forsyth-Edwards Notation string
        """
        self.board = chess.Board(fen)

    def is_game_over(self) -> bool:
        """
        Check if the game is over.

        Returns:
            True if game is finished (checkmate, stalemate, etc)
        """
        return self.board.is_game_over()

    def is_check(self) -> bool:
        """
        Check if current player is in check.

        Returns:
            True if in check
        """
        return self.board.is_check()

    def is_checkmate(self) -> bool:
        """
        Check if current position is checkmate.

        Returns:
            True if checkmate
        """
        return self.board.is_checkmate()

    def get_legal_moves(self):
        """
        Get all legal moves in current position.

        Returns:
            List of legal chess.Move objects
        """
        return list(self.board.legal_moves)

    def make_move(self, move: chess.Move):
        """
        Execute a move on the board.

        Args:
            move: chess.Move object to play

        Raises:
            ValueError: If move is not legal
        """
        if move not in self.board.legal_moves:
            raise ValueError(f"Illegal move: {move}")
        self.board.push(move)

    def undo_move(self) -> bool:
        """
        Undo the last move.

        Returns:
            True if a move was undone, False if no moves to undo
        """
        if len(self.board.move_stack) == 0:
            return False
        self.board.pop()
        return True

    def reset(self):
        """Reset the board to starting position."""
        self.board = chess.Board()
        self.move_count = 0

    def get_game_status(self) -> str:
        """
        Get human-readable game status.

        Returns:
            String describing game state
        """
        if self.board.is_checkmate():
            winner = "Black" if self.board.turn else "White"
            return f"Checkmate! {winner} wins."
        elif self.board.is_stalemate():
            return "Stalemate - Draw!"
        elif self.board.is_check():
            player = "White" if self.board.turn else "Black"
            return f"{player} is in check."
        elif self.board.is_game_over():
            return "Game over - Draw by rule."
        else:
            player = "White" if self.board.turn else "Black"
            return f"{player} to move."

"""
Custom Game Environment Implementation

Base classes and utilities for building custom game environments
compatible with game agents.
"""

from enum import Enum
from typing import Any, Tuple, Optional
from abc import ABC, abstractmethod


class GameState(Enum):
    """Enumeration of possible game states."""

    PLAYING = 1
    AGENT_THINKING = 2
    GAME_OVER = 3


class GameEnvironment(ABC):
    """
    Abstract base class for game environments.

    Provides interface for agents to interact with games.
    """

    def __init__(self, width=800, height=600):
        """
        Initialize the game environment.

        Args:
            width: Display width (if rendering)
            height: Display height (if rendering)
        """
        self.width = width
        self.height = height
        self.state = self.reset()

    def reset(self) -> Any:
        """
        Initialize or reset the game.

        Returns:
            Initial game state
        """
        return self.get_initial_state()

    def step(self, action) -> Tuple[Any, float, bool]:
        """
        Execute one action in the environment.

        Args:
            action: Action to execute

        Returns:
            Tuple of (next_state, reward, done)
            - next_state: Resulting game state
            - reward: Reward for the action
            - done: True if episode is finished
        """
        next_state = self.apply_action(self.state, action)
        reward = self.calculate_reward(self.state, action, next_state)
        done = self.is_terminal(next_state)
        self.state = next_state

        return next_state, reward, done

    def render(self):
        """
        Render the current game state (if graphics are available).

        Can be overridden to use pygame, matplotlib, or other rendering.
        """
        pass

    @abstractmethod
    def get_initial_state(self) -> Any:
        """
        Get the initial game state.

        Returns:
            Initial state
        """
        pass

    @abstractmethod
    def apply_action(self, state: Any, action: Any) -> Any:
        """
        Apply an action to a state.

        Args:
            state: Current game state
            action: Action to apply

        Returns:
            Resulting game state
        """
        pass

    @abstractmethod
    def calculate_reward(self, state: Any, action: Any, next_state: Any) -> float:
        """
        Calculate reward for an action.

        Args:
            state: State before action
            action: Action taken
            next_state: State after action

        Returns:
            Reward value
        """
        pass

    @abstractmethod
    def is_terminal(self, state: Any) -> bool:
        """
        Check if a state is terminal (game over).

        Args:
            state: Game state to check

        Returns:
            True if game is over
        """
        pass

    @abstractmethod
    def get_legal_actions(self, state: Any):
        """
        Get available actions from a state.

        Args:
            state: Current game state

        Returns:
            List of legal actions
        """
        pass


class PygameGameEnvironment(GameEnvironment):
    """
    Game environment with pygame rendering support.

    Extends GameEnvironment with pygame-based graphics.
    """

    def __init__(self, width=800, height=600, fps=60):
        """
        Initialize pygame environment.

        Args:
            width: Screen width
            height: Screen height
            fps: Frames per second for rendering
        """
        try:
            import pygame
            self.pygame = pygame
            self.has_pygame = True
        except ImportError:
            self.has_pygame = False
            print("Warning: pygame not installed. Graphics disabled.")

        self.fps = fps
        self.clock = None
        self.screen = None

        if self.has_pygame:
            self.pygame.init()
            self.screen = self.pygame.display.set_mode((width, height))
            self.clock = self.pygame.time.Clock()

        super().__init__(width, height)

    def render(self):
        """
        Render current game state with pygame.

        Fills screen white and calls draw_state for custom graphics.
        """
        if not self.has_pygame or not self.screen:
            return

        self.screen.fill((255, 255, 255))
        self.draw_state(self.state)
        self.pygame.display.flip()
        self.clock.tick(self.fps)

    def draw_state(self, state: Any):
        """
        Draw the game state on screen.

        Override this method to implement custom graphics.

        Args:
            state: Game state to render
        """
        pass

    def get_initial_state(self) -> Any:
        """Get initial state - must be implemented by subclass."""
        pass

    def apply_action(self, state: Any, action: Any) -> Any:
        """Apply action - must be implemented by subclass."""
        pass

    def calculate_reward(self, state: Any, action: Any, next_state: Any) -> float:
        """Calculate reward - must be implemented by subclass."""
        pass

    def is_terminal(self, state: Any) -> bool:
        """Check if terminal - must be implemented by subclass."""
        pass

    def get_legal_actions(self, state: Any):
        """Get legal actions - must be implemented by subclass."""
        pass

    def close(self):
        """Clean up pygame resources."""
        if self.has_pygame:
            self.pygame.quit()

"""
Monte Carlo Tree Search (MCTS) Implementation

Probabilistic game tree exploration algorithm.
Effective for games with high branching factors where full exploration is infeasible.
"""

import math
import random
from dataclasses import dataclass
from typing import Optional, List, Any


@dataclass
class MCTSNode:
    """Node in the Monte Carlo Tree Search tree."""

    game_state: Any  # 'GameState' type
    parent: Optional['MCTSNode'] = None
    children: Optional[List['MCTSNode']] = None
    visits: int = 0
    value: float = 0.0

    def __post_init__(self):
        """Initialize children list if not provided."""
        if self.children is None:
            self.children = []


class MCTSAgent:
    """Game agent using Monte Carlo Tree Search algorithm."""

    def __init__(self, iterations=1000, exploration_constant=1.414):
        """
        Initialize MCTS agent.

        Args:
            iterations: Number of MCTS iterations to run
            exploration_constant: Balance exploration vs exploitation (UCT constant)
        """
        self.iterations = iterations
        self.c = exploration_constant  # Exploration constant for UCT formula

    def get_best_move(self, game_state):
        """
        Get the best move using Monte Carlo Tree Search.

        Runs multiple simulations of the game tree, balancing exploration
        of new moves with exploitation of known good moves.

        Args:
            game_state: Current game state

        Returns:
            Best move based on MCTS simulations
        """
        root = MCTSNode(game_state)

        # Run MCTS iterations
        for _ in range(self.iterations):
            # Selection and expansion
            node = self.tree_policy(root)
            # Simulation and evaluation
            reward = self.default_policy(node.game_state)
            # Backpropagation
            self.backup(node, reward)

        # Return move with highest visit count
        best_child = max(
            root.children,
            key=lambda child: child.visits
        )
        return self.get_move(root.game_state, best_child.game_state)

    def tree_policy(self, node):
        """
        Select and expand nodes in the tree.

        Follows UCT (Upper Confidence bounds applied to Trees) formula
        to balance exploration and exploitation.

        Args:
            node: Starting node for tree traversal

        Returns:
            New node to simulate from
        """
        while not node.game_state.is_terminal():
            if not self.fully_expanded(node):
                # Expand tree with new node
                return self.expand(node)
            else:
                # Select best child using UCT
                node = self.best_uct(node)
        return node

    def expand(self, node):
        """
        Add a new child node to the tree.

        Selects an unexplored move and creates a new node for it.

        Args:
            node: Parent node to expand from

        Returns:
            New child node
        """
        legal_moves = node.game_state.get_legal_moves()
        explored_moves = {
            self.get_move(node.game_state, child.game_state)
            for child in node.children
        }

        unexplored_move = random.choice(
            [m for m in legal_moves if m not in explored_moves]
        )

        child_state = node.game_state.apply_move(unexplored_move)
        child = MCTSNode(child_state, parent=node)
        node.children.append(child)
        return child

    def default_policy(self, game_state):
        """
        Simulate game with random moves (playout).

        Runs a fast simulation from the given state to a terminal state
        using random moves.

        Args:
            game_state: Starting state for simulation

        Returns:
            Game result/reward from simulation
        """
        state = game_state.copy()

        while not state.is_terminal():
            move = random.choice(state.get_legal_moves())
            state = state.apply_move(move)

        return state.get_result()

    def backup(self, node, reward):
        """
        Backpropagate simulation results up the tree.

        Updates visit counts and value sums for all nodes from the
        simulated node back to the root.

        Args:
            node: Node to backpropagate from
            reward: Reward value from simulation
        """
        while node is not None:
            node.visits += 1
            node.value += reward
            node = node.parent

    def best_uct(self, node):
        """
        Select best child using Upper Confidence Bounds for Trees (UCT).

        Formula: UCT = exploitation + exploration
                     = (child_value / child_visits) + c * sqrt(ln(parent_visits) / child_visits)

        Args:
            node: Parent node

        Returns:
            Child node with highest UCT value
        """
        best_child = None
        best_uct = float('-inf')

        for child in node.children:
            uct = self.calculate_uct(child, node.visits)
            if uct > best_uct:
                best_uct = uct
                best_child = child

        return best_child

    def calculate_uct(self, node, parent_visits):
        """
        Calculate UCT value for a node.

        Balances exploitation (average reward) with exploration
        (uncertainty in estimates).

        Args:
            node: Child node to evaluate
            parent_visits: Number of visits to parent node

        Returns:
            UCT value for the node
        """
        exploitation = node.value / (node.visits + 1)
        exploration = self.c * math.sqrt(math.log(parent_visits) / (node.visits + 1))
        return exploitation + exploration

    def fully_expanded(self, node):
        """
        Check if all children of a node have been explored.

        Args:
            node: Node to check

        Returns:
            True if all legal moves have child nodes
        """
        return len(node.children) == len(node.game_state.get_legal_moves())

    def get_move(self, state1, state2):
        """
        Extract the move that transforms state1 into state2.

        Args:
            state1: Before state
            state2: After state

        Returns:
            The move made
        """
        pass

"""
Minimax with Alpha-Beta Pruning Implementation

Optimal decision-making algorithm for turn-based games.
Uses minimax tree search with alpha-beta pruning for efficiency.
"""


class MinimaxGameAgent:
    """Game agent using minimax algorithm with alpha-beta pruning."""

    def __init__(self, max_depth=4):
        """
        Initialize the minimax agent.

        Args:
            max_depth: Maximum search depth for the minimax tree
        """
        self.max_depth = max_depth
        self.nodes_evaluated = 0

    def get_best_move(self, game_state):
        """
        Find the best move using minimax with alpha-beta pruning.

        Args:
            game_state: Current game state

        Returns:
            Best move to play
        """
        _, best_move = self.minimax(
            game_state,
            self.max_depth,
            True,  # Maximizing player
            float('-inf'),
            float('inf')
        )
        return best_move

    def minimax(self, game_state, depth, maximizing, alpha, beta):
        """
        Minimax algorithm with alpha-beta pruning.

        Recursively evaluates the game tree, alternating between maximizing
        and minimizing player moves. Prunes branches that cannot affect the
        final decision.

        Args:
            game_state: Current game state
            depth: Remaining search depth
            maximizing: True if maximizing player's turn
            alpha: Best value for maximizer so far
            beta: Best value for minimizer so far

        Returns:
            Tuple of (evaluation_score, best_move)
        """
        self.nodes_evaluated += 1

        # Terminal node or max depth reached
        if depth == 0 or game_state.is_terminal():
            return self.evaluate(game_state), None

        if maximizing:
            max_eval = float('-inf')
            best_move = None

            for move in game_state.get_legal_moves():
                next_state = game_state.apply_move(move)
                eval_score, _ = self.minimax(
                    next_state, depth - 1, False, alpha, beta
                )

                if eval_score > max_eval:
                    max_eval = eval_score
                    best_move = move

                alpha = max(alpha, eval_score)
                if beta <= alpha:
                    break  # Beta cutoff - prune remaining branches

            return max_eval, best_move

        else:  # Minimizing player
            min_eval = float('inf')
            best_move = None

            for move in game_state.get_legal_moves():
                next_state = game_state.apply_move(move)
                eval_score, _ = self.minimax(
                    next_state, depth - 1, True, alpha, beta
                )

                if eval_score < min_eval:
                    min_eval = eval_score
                    best_move = move

                beta = min(beta, eval_score)
                if beta <= alpha:
                    break  # Alpha cutoff - prune remaining branches

            return min_eval, best_move

    def evaluate(self, game_state):
        """
        Static evaluation function for terminal or leaf nodes.

        Args:
            game_state: Game state to evaluate

        Returns:
            Numeric evaluation score
        """
        if game_state.is_checkmate():
            return float('-inf') if game_state.current_player else float('inf')
        if game_state.is_stalemate():
            return 0

        # Material count (can be extended with other evaluation factors)
        return game_state.evaluate_material()

    def reset_stats(self):
        """Reset evaluation statistics."""
        self.nodes_evaluated = 0

"""
Q-Learning Agent Implementation

Reinforcement learning agent that learns optimal policies through
interaction with the game environment using the Q-learning algorithm.
"""

import numpy as np
import random
from collections import defaultdict
from typing import Optional, List, Any


class QLearningAgent:
    """Reinforcement learning agent using Q-learning algorithm."""

    def __init__(self, learning_rate=0.1, discount_factor=0.99, epsilon=0.1):
        """
        Initialize the Q-learning agent.

        Args:
            learning_rate: Learning rate (alpha) for Q-value updates
            discount_factor: Discount factor (gamma) for future rewards
            epsilon: Exploration probability for epsilon-greedy action selection
        """
        self.alpha = learning_rate
        self.gamma = discount_factor
        self.epsilon = epsilon
        self.q_table = defaultdict(lambda: defaultdict(float))

    def get_action(self, state):
        """
        Select an action using epsilon-greedy strategy.

        With probability epsilon, explores a random action.
        With probability 1-epsilon, exploits the best known action.

        Args:
            state: Current game state

        Returns:
            Selected action
        """
        if np.random.random() < self.epsilon:
            # Explore: select random action
            return self.random_action(state)
        else:
            # Exploit: select best known action
            return self.best_action(state)

    def update_q_value(self, state, action, reward, next_state):
        """
        Update Q-value using Q-learning update rule.

        Q(s,a) := Q(s,a) + alpha * [r + gamma * max_a' Q(s',a') - Q(s,a)]

        Args:
            state: Current state
            action: Action taken
            reward: Reward received
            next_state: Resulting state
        """
        # Get best action for next state
        best_next_action = self.best_action(next_state)

        # Calculate TD target
        td_target = reward + self.gamma * self.q_table[next_state][best_next_action]

        # Calculate TD error
        td_error = td_target - self.q_table[state][action]

        # Update Q-value
        self.q_table[state][action] += self.alpha * td_error

    def best_action(self, state):
        """
        Get the action with highest Q-value for a state.

        Args:
            state: Current game state

        Returns:
            Best action, or None if no actions available
        """
        actions = self.get_legal_actions(state)
        if not actions:
            return None

        q_values = {a: self.q_table[state][a] for a in actions}
        return max(q_values, key=q_values.get)

    def random_action(self, state):
        """
        Select a random legal action.

        Args:
            state: Current game state

        Returns:
            Random legal action
        """
        return random.choice(self.get_legal_actions(state))

    def get_legal_actions(self, state):
        """
        Get available actions in the current state.

        Args:
            state: Current game state

        Returns:
            List of legal actions
        """
        pass

    def get_q_value(self, state, action):
        """
        Get Q-value for a state-action pair.

        Args:
            state: Game state
            action: Action to evaluate

        Returns:
            Stored Q-value
        """
        return self.q_table[state][action]

    def get_q_values(self, state):
        """
        Get all Q-values for a state.

        Args:
            state: Game state

        Returns:
            Dictionary of actions to Q-values
        """
        actions = self.get_legal_actions(state)
        return {a: self.q_table[state][a] for a in actions}

    def decay_epsilon(self, decay_rate=0.995):
        """
        Decay exploration probability over time.

        Gradually shift from exploration to exploitation as learning progresses.

        Args:
            decay_rate: Multiplicative decay rate per update
        """
        self.epsilon *= decay_rate
        self.epsilon = max(self.epsilon, 0.01)  # Maintain some exploration

    def save_q_table(self, filename):
        """
        Save Q-table to file for later use.

        Args:
            filename: Path to save file
        """
        import json
        # Convert defaultdict to regular dict for JSON serialization
        q_dict = {str(state): dict(actions) for state, actions in self.q_table.items()}
        with open(filename, 'w') as f:
            json.dump(q_dict, f)

    def load_q_table(self, filename):
        """
        Load Q-table from file.

        Args:
            filename: Path to load file
        """
        import json
        with open(filename, 'r') as f:
            q_dict = json.load(f)
        self.q_table = defaultdict(lambda: defaultdict(float))
        for state, actions in q_dict.items():
            for action, value in actions.items():
                self.q_table[state][action] = value

    def reset(self):
        """Clear all learned Q-values."""
        self.q_table.clear()

"""
Rule-Based Game Agent Implementation

A simple agent that uses predefined rules and heuristics to make decisions.
Best for games where domain knowledge can be encoded as rules.
"""


class RuleBasedGameAgent:
    """Game agent using predefined rules and heuristics for decision-making."""

    def __init__(self, difficulty="medium"):
        """
        Initialize the rule-based agent.

        Args:
            difficulty: Game difficulty level ("easy", "medium", "hard")
        """
        self.difficulty = difficulty
        self.rules = self.load_rules(difficulty)

    def decide_action(self, game_state):
        """
        Choose the best action based on game rules and heuristics.

        Args:
            game_state: Current state of the game

        Returns:
            Best action to take
        """
        best_action = None
        best_score = float('-inf')

        for action in self.get_legal_moves(game_state):
            next_state = self.simulate_move(game_state, action)
            score = self.evaluate_position(next_state)

            if score > best_score:
                best_score = score
                best_action = action

        return best_action

    def evaluate_position(self, game_state):
        """
        Heuristic evaluation of a game position.

        Combines multiple evaluation factors:
        - Material count (pieces/resources)
        - Positional advantages
        - Board/map control

        Args:
            game_state: State to evaluate

        Returns:
            Score representing position quality
        """
        score = 0

        # Material evaluation
        score += self.count_material(game_state)

        # Positional evaluation
        score += self.evaluate_position_factors(game_state)

        # Control evaluation
        score += self.evaluate_control(game_state)

        return score

    def get_legal_moves(self, game_state):
        """
        Get all valid moves from current state.

        Args:
            game_state: Current game state

        Returns:
            List of legal moves
        """
        pass

    def simulate_move(self, game_state, action):
        """
        Simulate the result of making a move.

        Args:
            game_state: Current game state
            action: Move to simulate

        Returns:
            Resulting game state
        """
        pass

    def load_rules(self, difficulty):
        """
        Load difficulty-adjusted rules.

        Args:
            difficulty: Game difficulty level

        Returns:
            Dictionary of rules for the difficulty level
        """
        pass

    def count_material(self, game_state):
        """
        Evaluate pieces/resources in the position.

        Args:
            game_state: Current game state

        Returns:
            Material score
        """
        pass

    def evaluate_position_factors(self, game_state):
        """
        Evaluate positional advantages (piece placement, control, etc).

        Args:
            game_state: Current game state

        Returns:
            Positional score
        """
        pass

    def evaluate_control(self, game_state):
        """
        Evaluate board/map control.

        Args:
            game_state: Current game state

        Returns:
            Control score
        """
        pass

"""
Game Strategy Modules

Advanced strategy implementations including opening books,
endgame tablebases, and adaptive multi-stage strategies.
"""

from enum import Enum
from typing import Optional, Dict, Any
from abc import ABC, abstractmethod


class GamePhase(Enum):
    """Phases of a game with different optimal strategies."""

    OPENING = 1
    MIDDLEGAME = 2
    ENDGAME = 3


class OpeningBook:
    """Pre-computed best moves for game openings."""

    def __init__(self):
        """Initialize opening book."""
        self.openings = self.load_opening_book()

    def get_opening_move(self, game_state: Any) -> Optional[Any]:
        """
        Get move from opening book if available.

        Args:
            game_state: Current game state

        Returns:
            Opening book move if found, None otherwise
        """
        position_hash = self.hash_position(game_state)
        if position_hash in self.openings:
            return self.openings[position_hash]
        return None

    def in_opening(self, game_state: Any) -> bool:
        """
        Check if current position is in opening book.

        Args:
            game_state: Current game state

        Returns:
            True if position is in opening book
        """
        position_hash = self.hash_position(game_state)
        return position_hash in self.openings

    def load_opening_book(self) -> Dict:
        """
        Load pre-computed opening moves.

        Would load from PGN files, opening databases, etc.

        Returns:
            Dictionary mapping position hashes to moves
        """
        # Load from PGN, databases, etc.
        return {}

    def hash_position(self, game_state: Any) -> int:
        """
        Create unique position identifier for lookup.

        Args:
            game_state: Game state to hash

        Returns:
            Hash value for position
        """
        pass


class EndgameTablebase:
    """Pre-computed endgame positions and optimal moves."""

    def __init__(self):
        """Initialize endgame tablebase."""
        self.tablebase = self.load_tablebase()

    def is_winning_move(self, game_state: Any) -> Optional[bool]:
        """
        Check if current position is winning for the player to move.

        Args:
            game_state: Current game state

        Returns:
            True if winning, False if losing, None if unknown
        """
        position_hash = self.hash_position(game_state)
        if position_hash in self.tablebase:
            return self.tablebase[position_hash].get("winning")
        return None

    def get_best_endgame_move(self, game_state: Any) -> Optional[Any]:
        """
        Get optimal move from tablebase if available.

        Args:
            game_state: Current game state

        Returns:
            Best move, or None if not in tablebase
        """
        position_hash = self.hash_position(game_state)
        if position_hash in self.tablebase:
            return self.tablebase[position_hash].get("best_move")
        return None

    def get_endgame_distance(self, game_state: Any) -> Optional[int]:
        """
        Get distance to mate (if known).

        Args:
            game_state: Current game state

        Returns:
            Number of moves to mate, or None if not known
        """
        position_hash = self.hash_position(game_state)
        if position_hash in self.tablebase:
            return self.tablebase[position_hash].get("dtm")  # Distance to mate
        return None

    def in_tablebase(self, game_state: Any) -> bool:
        """
        Check if position is in tablebase.

        Args:
            game_state: Current game state

        Returns:
            True if position is in tablebase
        """
        position_hash = self.hash_position(game_state)
        return position_hash in self.tablebase

    def load_tablebase(self) -> Dict:
        """
        Load endgame solutions.

        Would load from tablebase files, databases, etc.

        Returns:
            Dictionary of endgame positions
        """
        # Load from endgame files
        return {}

    def hash_position(self, game_state: Any) -> int:
        """
        Create position hash for tablebase lookup.

        Args:
            game_state: Game state to hash

        Returns:
            Hash value
        """
        pass


class AdaptiveGameAgent:
    """
    Agent that adapts strategy based on game phase.

    Uses opening book in opening, minimax in middlegame,
    and tablebase in endgame.
    """

    def __init__(self, opening_book=None, middlegame_engine=None, endgame_tablebase=None):
        """
        Initialize adaptive agent.

        Args:
            opening_book: Opening book instance
            middlegame_engine: Middlegame search engine (e.g., Minimax)
            endgame_tablebase: Endgame tablebase instance
        """
        self.opening_book = opening_book or OpeningBook()
        self.middlegame_engine = middlegame_engine
        self.endgame_tablebase = endgame_tablebase or EndgameTablebase()

    def decide_action(self, game_state: Any) -> Optional[Any]:
        """
        Choose strategy based on game phase.

        Args:
            game_state: Current game state

        Returns:
            Best move according to phase-appropriate strategy
        """
        phase = self.determine_game_phase(game_state)

        if phase == GamePhase.OPENING:
            move = self.opening_book.get_opening_move(game_state)
            if move:
                return move

        elif phase == GamePhase.ENDGAME:
            move = self.endgame_tablebase.get_best_endgame_move(game_state)
            if move:
                return move

        # Default to middlegame engine
        if self.middlegame_engine:
            return self.middlegame_engine.get_best_move(game_state)

        return None

    def determine_game_phase(self, game_state: Any) -> GamePhase:
        """
        Classify game phase based on material.

        Args:
            game_state: Current game state

        Returns:
            Current game phase
        """
        material_count = self.count_material(game_state)

        if material_count > 30:
            return GamePhase.OPENING
        elif material_count < 10:
            return GamePhase.ENDGAME
        else:
            return GamePhase.MIDDLEGAME

    def count_material(self, game_state: Any) -> int:
        """
        Count total material on the board.

        Args:
            game_state: Current game state

        Returns:
            Material count value
        """
        pass

    def get_phase_info(self, game_state: Any) -> Dict[str, Any]:
        """
        Get detailed information about game phase.

        Args:
            game_state: Current game state

        Returns:
            Dictionary with phase information
        """
        phase = self.determine_game_phase(game_state)
        material = self.count_material(game_state)

        return {
            'phase': phase.name,
            'material_count': material,
            'using_opening_book': phase == GamePhase.OPENING and self.opening_book.in_opening(game_state),
            'using_tablebase': phase == GamePhase.ENDGAME and self.endgame_tablebase.in_tablebase(game_state),
            'using_middlegame_engine': phase == GamePhase.MIDDLEGAME
        }


class StrategyModule(ABC):
    """Base class for pluggable strategy modules."""

    @abstractmethod
    def get_move(self, game_state: Any) -> Optional[Any]:
        """
        Get recommended move for position.

        Args:
            game_state: Current game state

        Returns:
            Recommended move
        """
        pass

    @abstractmethod
    def is_applicable(self, game_state: Any) -> bool:
        """
        Check if this strategy applies to the position.

        Args:
            game_state: Current game state

        Returns:
            True if strategy should be used
        """
        pass


class CompositeStrategy:
    """
    Composite strategy that combines multiple strategy modules.

    Tries strategies in order until one applies.
    """

    def __init__(self, strategies: list = None):
        """
        Initialize composite strategy.

        Args:
            strategies: List of strategy modules in priority order
        """
        self.strategies = strategies or []

    def add_strategy(self, strategy: StrategyModule):
        """
        Add a strategy module.

        Args:
            strategy: Strategy to add
        """
        self.strategies.append(strategy)

    def get_move(self, game_state: Any) -> Optional[Any]:
        """
        Get move from first applicable strategy.

        Args:
            game_state: Current game state

        Returns:
            Move from first applicable strategy, or None
        """
        for strategy in self.strategies:
            if strategy.is_applicable(game_state):
                move = strategy.get_move(game_state)
                if move:
                    return move
        return None

    def get_active_strategy(self, game_state: Any) -> Optional[StrategyModule]:
        """
        Identify which strategy is active.

        Args:
            game_state: Current game state

        Returns:
            Active strategy module, or None
        """
        for strategy in self.strategies:
            if strategy.is_applicable(game_state):
                return strategy
        return None

"""
Game Agent Benchmarking and Tournament Tools

Utilities for testing and evaluating game agents including
tournament play, rating systems, and performance metrics.
"""

import random
import math
from typing import List, Dict, Tuple, Optional
from dataclasses import dataclass, field
from collections import defaultdict


@dataclass
class AgentStats:
    """Statistics for an agent's performance."""

    name: str
    wins: int = 0
    losses: int = 0
    draws: int = 0
    elo_rating: float = 1600.0
    games_played: int = 0

    @property
    def win_rate(self) -> float:
        """Calculate win rate."""
        total = self.wins + self.losses + self.draws
        return self.wins / total if total > 0 else 0.0

    @property
    def score(self) -> float:
        """Calculate total score (wins + 0.5 * draws)."""
        return self.wins + 0.5 * self.draws


class GameAgentBenchmark:
    """Benchmark suite for game-playing agents."""

    def __init__(self):
        """Initialize benchmark."""
        self.agent_stats: Dict[str, AgentStats] = {}

    def run_tournament(self, agents: List, num_games: int = 100) -> Dict[str, int]:
        """
        Run round-robin tournament between agents.

        Each pair plays both as white and black (if applicable).

        Args:
            agents: List of agent objects to compete
            num_games: Total games to play

        Returns:
            Dictionary mapping agent names to win counts
        """
        results = {agent.name: 0 for agent in agents}

        games_per_matchup = num_games // (len(agents) * (len(agents) - 1))

        for _ in range(games_per_matchup):
            for i in range(len(agents)):
                for j in range(i + 1, len(agents)):
                    # Play agent i vs agent j
                    winner = self.play_game(agents[i], agents[j])
                    if winner:
                        results[winner.name] += 1

                    # Play agent j vs agent i
                    winner = self.play_game(agents[j], agents[i])
                    if winner:
                        results[winner.name] += 1

        return results

    def evaluate_elo_rating(self, agents: List, num_games: int = 100) -> Dict[str, float]:
        """
        Calculate Elo ratings for agents.

        Uses Elo rating system where rating changes depend on
        performance vs expected strength.

        Args:
            agents: List of agents to rate
            num_games: Number of games to play

        Returns:
            Dictionary mapping agent names to Elo ratings
        """
        # Initialize ratings
        elo_ratings = {agent.name: 1600.0 for agent in agents}

        for _ in range(num_games):
            agent1 = random.choice(agents)
            agent2 = random.choice([a for a in agents if a != agent1])

            winner = self.play_game(agent1, agent2)

            # Calculate expected outcome for each agent
            diff = elo_ratings[agent2.name] - elo_ratings[agent1.name]
            expected_1 = 1 / (1 + 10 ** (diff / 400))
            expected_2 = 1 - expected_1

            # Determine actual scores
            if winner == agent1:
                score_1 = 1.0
                score_2 = 0.0
            elif winner == agent2:
                score_1 = 0.0
                score_2 = 1.0
            else:  # Draw
                score_1 = 0.5
                score_2 = 0.5

            # Update ratings (K-factor = 32)
            elo_ratings[agent1.name] += 32 * (score_1 - expected_1)
            elo_ratings[agent2.name] += 32 * (score_2 - expected_2)

        return elo_ratings

    def glicko2_rating(self, agents: List, num_games: int = 100) -> Dict[str, float]:
        """
        Calculate Glicko-2 ratings (improved Elo system).

        Accounts for rating deviation (uncertainty).

        Args:
            agents: List of agents to rate
            num_games: Number of games to play

        Returns:
            Dictionary mapping agent names to Glicko-2 ratings
        """
        # Simplified Glicko-2 implementation
        ratings = {agent.name: 1600.0 for agent in agents}
        deviations = {agent.name: 350.0 for agent in agents}

        for _ in range(num_games):
            agent1 = random.choice(agents)
            agent2 = random.choice([a for a in agents if a != agent1])

            winner = self.play_game(agent1, agent2)

            # Calculate expected outcome
            diff = (ratings[agent2.name] - ratings[agent1.name]) / 173.7178
            expected = 1 / (1 + math.exp(-diff))

            # Determine actual score
            if winner == agent1:
                score = 1.0
            elif winner == agent2:
                score = 0.0
            else:
                score = 0.5

            # Update ratings with deviation factor
            d_squared = 1 / (0.0055 + 0.0001 * ((score - expected) ** 2))
            d = math.sqrt(d_squared)

            ratings[agent1.name] += (0.0055 / (1 / (deviations[agent1.name] ** 2) + 1 / d_squared)) * (score - expected)
            deviations[agent1.name] = math.sqrt(1 / (1 / (deviations[agent1.name] ** 2) + 1 / d_squared))

        return ratings

    def play_game(self, agent1, agent2) -> Optional:
        """
        Play a single game between two agents.

        Args:
            agent1: First agent
            agent2: Second agent

        Returns:
            Winning agent, or None for draw
        """
        pass

    def rate_agent_strength(self, agent, baseline_agents: List, num_games: int = 20) -> float:
        """
        Rate agent strength relative to baseline agents.

        Args:
            agent: Agent to rate
            baseline_agents: Baseline agents to compare against
            num_games: Games per baseline agent

        Returns:
            Strength score (higher = stronger)
        """
        wins = 0
        total = 0

        for baseline in baseline_agents:
            for _ in range(num_games):
                winner = self.play_game(agent, baseline)
                if winner == agent:
                    wins += 1
                total += 1

        return (wins / total * 100) if total > 0 else 0.0

    def performance_profile(self, agent, test_positions: List, time_limit: float = 1.0) -> Dict:
        """
        Get performance profile for an agent.

        Args:
            agent: Agent to test
            test_positions: Test positions to evaluate
            time_limit: Time limit per position in seconds

        Returns:
            Performance metrics dictionary
        """
        correct_moves = 0
        avg_time = 0
        move_quality_scores = []

        for position in test_positions:
            # Get agent's move
            move = agent.get_best_move()  # Would need timing implementation

            # Evaluate move quality
            quality = self.evaluate_move_quality(position, move)
            move_quality_scores.append(quality)

            if quality > 0.8:
                correct_moves += 1

        return {
            'accuracy': correct_moves / len(test_positions) if test_positions else 0.0,
            'avg_move_quality': sum(move_quality_scores) / len(move_quality_scores) if move_quality_scores else 0.0,
            'total_positions_tested': len(test_positions)
        }

    def evaluate_move_quality(self, position, move) -> float:
        """
        Evaluate quality of a move (0.0 to 1.0).

        Args:
            position: Game position
            move: Move to evaluate

        Returns:
            Quality score
        """
        pass

    def head_to_head_comparison(self, agent1, agent2, num_games: int = 50) -> Dict:
        """
        Detailed comparison between two agents.

        Args:
            agent1: First agent
            agent2: Second agent
            num_games: Number of games to play

        Returns:
            Comparison statistics
        """
        agent1_wins = 0
        agent2_wins = 0
        draws = 0

        for _ in range(num_games):
            winner = self.play_game(agent1, agent2)
            if winner == agent1:
                agent1_wins += 1
            elif winner == agent2:
                agent2_wins += 1
            else:
                draws += 1

        total = agent1_wins + agent2_wins + draws

        return {
            'agent1': agent1.name,
            'agent2': agent2.name,
            'agent1_wins': agent1_wins,
            'agent2_wins': agent2_wins,
            'draws': draws,
            'agent1_win_rate': agent1_wins / total if total > 0 else 0.0,
            'agent2_win_rate': agent2_wins / total if total > 0 else 0.0,
            'draw_rate': draws / total if total > 0 else 0.0
        }

"""
Game Theory Analysis Tools

Utilities for analyzing games from a game theory perspective,
including Nash equilibrium calculation and strategic analysis.
"""

import numpy as np
from typing import Tuple, List, Dict, Optional
from dataclasses import dataclass


@dataclass
class PayoffMatrix:
    """Represents a 2-player game payoff matrix."""

    player1_payoffs: np.ndarray
    player2_payoffs: np.ndarray
    row_labels: List[str]
    column_labels: List[str]

    def is_zero_sum(self) -> bool:
        """
        Check if this is a zero-sum game.

        In zero-sum games, one player's gain is another's loss.

        Returns:
            True if zero-sum (payoffs sum to zero)
        """
        return np.allclose(self.player1_payoffs + self.player2_payoffs, 0)

    def is_symmetric(self) -> bool:
        """
        Check if this is a symmetric game.

        Returns:
            True if both players have identical payoff structure
        """
        return np.allclose(self.player1_payoffs, self.player2_payoffs.T)


class GameTheoryAnalyzer:
    """Analyzer for game-theoretic properties and solutions."""

    @staticmethod
    def find_pure_strategy_nash_equilibria(payoff_matrix: PayoffMatrix) -> List[Tuple[int, int]]:
        """
        Find pure strategy Nash equilibria in a game.

        A Nash equilibrium is a strategy profile where no player can
        improve by unilaterally changing their strategy.

        Args:
            payoff_matrix: Game payoff matrix

        Returns:
            List of (row_index, column_index) tuples for Nash equilibria
        """
        equilibria = []
        p1_payoffs = payoff_matrix.player1_payoffs
        p2_payoffs = payoff_matrix.player2_payoffs

        # Check each cell
        for i in range(p1_payoffs.shape[0]):
            for j in range(p1_payoffs.shape[1]):
                # Check if best response for player 1
                if p1_payoffs[i, j] == np.max(p1_payoffs[:, j]):
                    # Check if best response for player 2
                    if p2_payoffs[i, j] == np.max(p2_payoffs[i, :]):
                        equilibria.append((i, j))

        return equilibria

    @staticmethod
    def calculate_mixed_strategy_2x2(payoff_matrix: PayoffMatrix) -> Tuple[np.ndarray, np.ndarray]:
        """
        Calculate mixed strategy Nash equilibrium for 2x2 game.

        For a 2x2 zero-sum game, finds the probability distribution
        over strategies that forms a Nash equilibrium.

        Args:
            payoff_matrix: 2x2 payoff matrix

        Returns:
            Tuple of (player1_strategy, player2_strategy)
            Strategies are probability distributions over actions
        """
        if payoff_matrix.player1_payoffs.shape != (2, 2):
            raise ValueError("This method only works for 2x2 games")

        p1 = payoff_matrix.player1_payoffs
        p2 = payoff_matrix.player2_payoffs

        # Use indifference conditions
        # Player 1: q * p1[0,0] + (1-q) * p1[1,0] = q * p1[0,1] + (1-q) * p1[1,1]
        numerator = p1[1, 1] - p1[1, 0]
        denominator = p1[0, 0] - p1[0, 1] - p1[1, 0] + p1[1, 1]

        if abs(denominator) < 1e-10:
            # Degenerate case
            q = 0.5
        else:
            q = numerator / denominator

        # Player 2 strategy calculation
        numerator = p2[1, 1] - p2[0, 1]
        denominator = p2[0, 0] - p2[0, 1] - p2[1, 0] + p2[1, 1]

        if abs(denominator) < 1e-10:
            p = 0.5
        else:
            p = numerator / denominator

        # Clamp to [0, 1]
        q = np.clip(q, 0, 1)
        p = np.clip(p, 0, 1)

        player1_strategy = np.array([q, 1 - q])
        player2_strategy = np.array([p, 1 - p])

        return player1_strategy, player2_strategy

    @staticmethod
    def calculate_expected_payoff(
        player1_strategy: np.ndarray,
        player2_strategy: np.ndarray,
        payoff_matrix: PayoffMatrix,
        player: int = 1
    ) -> float:
        """
        Calculate expected payoff for a strategy profile.

        Args:
            player1_strategy: Player 1's mixed strategy
            player2_strategy: Player 2's mixed strategy
            payoff_matrix: Game payoff matrix
            player: Which player (1 or 2) to calculate for

        Returns:
            Expected payoff value
        """
        if player == 1:
            payoffs = payoff_matrix.player1_payoffs
        else:
            payoffs = payoff_matrix.player2_payoffs

        return player1_strategy @ payoffs @ player2_strategy

    @staticmethod
    def minimax_value(payoff_matrix: PayoffMatrix) -> float:
        """
        Calculate minimax value for zero-sum game.

        Minimum guaranteed payoff for player 1 when playing optimally
        against an optimally-playing opponent.

        Args:
            payoff_matrix: Zero-sum game matrix

        Returns:
            Minimax value
        """
        if not payoff_matrix.is_zero_sum():
            raise ValueError("Minimax theorem only applies to zero-sum games")

        # For each row, find minimum (worst case for player 1)
        row_mins = np.min(payoff_matrix.player1_payoffs, axis=1)
        # Player 1 chooses row to maximize the minimum
        return float(np.max(row_mins))

    @staticmethod
    def maximin_value(payoff_matrix: PayoffMatrix) -> float:
        """
        Calculate maximin value for zero-sum game.

        Maximum loss player 2 is willing to accept when defending optimally.

        Args:
            payoff_matrix: Zero-sum game matrix

        Returns:
            Maximin value
        """
        if not payoff_matrix.is_zero_sum():
            raise ValueError("Maximin only applies to zero-sum games")

        # For each column, find maximum (best for player 1 from player 2's perspective)
        col_maxs = np.max(payoff_matrix.player1_payoffs, axis=0)
        # Player 2 chooses column to minimize player 1's maximum
        return float(np.min(col_maxs))


class CooperativeGameAnalyzer:
    """Analyzer for cooperative game theory concepts."""

    @staticmethod
    def calculate_shapley_value(payoff_function, players: List[str]) -> Dict[str, float]:
        """
        Calculate Shapley value for cooperative game.

        Indicates fair value of each player's contribution.

        Args:
            payoff_function: Function that takes coalition and returns payoff
            players: List of player names

        Returns:
            Dictionary mapping player names to Shapley values
        """
        n = len(players)
        shapley_values = {player: 0.0 for player in players}

        # This is a simplified implementation
        # Full implementation would enumerate all coalitions
        for player in players:
            # Calculate marginal contribution
            payoff_with = payoff_function(players)
            payoff_without = payoff_function([p for p in players if p != player])
            marginal = payoff_with - payoff_without
            shapley_values[player] = marginal / n

        return shapley_values

    @staticmethod
    def calculate_core(
        payoff_function,
        players: List[str]
    ) -> Optional[Dict[str, float]]:
        """
        Find core of cooperative game if it exists.

        The core is the set of outcomes where no coalition can
        improve by deviating.

        Args:
            payoff_function: Function that maps coalition to payoff
            players: List of player names

        Returns:
            A core allocation if it exists, None otherwise
        """
        # Simplified implementation
        # Full implementation would verify all coalition constraints
        n = len(players)
        total_payoff = payoff_function(players)

        # Check if equal division is in the core
        equal_share = total_payoff / n
        return {player: equal_share for player in players}

    @staticmethod
    def is_core_allocation(
        allocation: Dict[str, float],
        payoff_function,
        players: List[str],
        epsilon: float = 1e-6
    ) -> bool:
        """
        Check if an allocation is in the core.

        Args:
            allocation: Dictionary of player payoffs
            payoff_function: Function mapping coalitions to payoffs
            players: List of all players
            epsilon: Tolerance for floating point comparison

        Returns:
            True if allocation is in the core
        """
        # Check efficiency: total allocation equals grand coalition payoff
        total = sum(allocation.values())
        grand_payoff = payoff_function(players)
        if abs(total - grand_payoff) > epsilon:
            return False

        # Check stability: no coalition can improve
        for coalition in players:
            coalition_payoff = allocation[coalition]
            coalition_value = payoff_function([coalition])
            if coalition_payoff < coalition_value - epsilon:
                return False

        return True

"""
Performance Optimization Tools

Utilities for optimizing game agent performance including
transposition tables, killer heuristics, and parallel search.
"""

import threading
from concurrent.futures import ThreadPoolExecutor
from typing import Dict, Optional, List, Any, Callable
from dataclasses import dataclass, field


@dataclass
class TranspositionEntry:
    """Entry in a transposition table."""

    depth: int
    score: int
    flag: str  # 'exact', 'lower', 'upper'
    move: Optional[Any] = None


class TranspositionTable:
    """
    Cache for evaluated positions to avoid re-computation.

    Stores evaluation results indexed by position hash.
    """

    def __init__(self, max_size: int = 1000000):
        """
        Initialize transposition table.

        Args:
            max_size: Maximum number of entries to store
        """
        self.table: Dict[int, TranspositionEntry] = {}
        self.max_size = max_size
        self.hits = 0
        self.misses = 0
        self.lock = threading.Lock()

    def store(self, position_hash: int, depth: int, score: int, flag: str, move: Optional[Any] = None):
        """
        Store a position evaluation.

        Only stores if new evaluation is at greater depth.

        Args:
            position_hash: Hash of position
            depth: Search depth
            score: Evaluation score
            flag: Type of bound ('exact', 'lower', 'upper')
            move: Best move at this position
        """
        with self.lock:
            if position_hash not in self.table or self.table[position_hash].depth <= depth:
                self.table[position_hash] = TranspositionEntry(
                    depth=depth,
                    score=score,
                    flag=flag,
                    move=move
                )

    def lookup(self, position_hash: int, depth: int) -> Optional[int]:
        """
        Retrieve a stored evaluation.

        Args:
            position_hash: Hash of position
            depth: Required search depth

        Returns:
            Score if found at sufficient depth, None otherwise
        """
        with self.lock:
            if position_hash in self.table:
                entry = self.table[position_hash]
                if entry.depth >= depth:
                    self.hits += 1
                    return entry.score

            self.misses += 1
            return None

    def lookup_move(self, position_hash: int, depth: int) -> Optional[Any]:
        """
        Retrieve best move from transposition table.

        Args:
            position_hash: Hash of position
            depth: Required search depth

        Returns:
            Best move if available, None otherwise
        """
        with self.lock:
            if position_hash in self.table:
                entry = self.table[position_hash]
                if entry.depth >= depth:
                    return entry.move
            return None

    def hit_rate(self) -> float:
        """
        Calculate transposition table hit rate.

        Returns:
            Fraction of lookups that hit (0.0 to 1.0)
        """
        total = self.hits + self.misses
        return self.hits / total if total > 0 else 0.0

    def clear(self):
        """Clear all entries from table."""
        with self.lock:
            self.table.clear()
            self.hits = 0
            self.misses = 0

    def size(self) -> int:
        """
        Get current table size.

        Returns:
            Number of entries stored
        """
        return len(self.table)

    def efficiency(self) -> float:
        """
        Get table efficiency metric.

        Returns:
            Hit rate percentage (0-100)
        """
        return self.hit_rate() * 100


class KillerHeuristic:
    """
    Track moves that cause cutoffs at similar depths.

    Killer moves are moves at a given depth that have caused
    cutoffs at other nodes - likely to be good moves to try.
    """

    def __init__(self, max_depth: int = 20, num_killers: int = 2):
        """
        Initialize killer heuristic.

        Args:
            max_depth: Maximum search depth to track
            num_killers: Number of killer moves to track per depth
        """
        self.max_depth = max_depth
        self.num_killers = num_killers
        self.killers = [[None] * num_killers for _ in range(max_depth)]

    def record_killer(self, move: Any, depth: int):
        """
        Record a killer move at a depth.

        Args:
            move: Move that caused cutoff
            depth: Depth where move was played
        """
        if depth >= self.max_depth:
            return

        # Shift existing killers down
        if move != self.killers[depth][0]:
            for i in range(self.num_killers - 1, 0, -1):
                self.killers[depth][i] = self.killers[depth][i - 1]
            self.killers[depth][0] = move

    def get_killers(self, depth: int) -> List[Any]:
        """
        Get killer moves for a depth.

        Args:
            depth: Search depth

        Returns:
            List of killer moves for this depth
        """
        if depth >= self.max_depth:
            return []
        return [k for k in self.killers[depth] if k is not None]

    def is_killer(self, move: Any, depth: int) -> bool:
        """
        Check if a move is a killer at a depth.

        Args:
            move: Move to check
            depth: Search depth

        Returns:
            True if move is a killer at this depth
        """
        if depth >= self.max_depth:
            return False
        return move in self.killers[depth]

    def clear(self):
        """Clear all killer moves."""
        self.killers = [[None] * self.num_killers for _ in range(self.max_depth)]


class ParallelSearchCoordinator:
    """
    Coordinate parallel search over game tree.

    Distributes search work across multiple threads.
    """

    def __init__(self, num_threads: int = 4):
        """
        Initialize parallel search coordinator.

        Args:
            num_threads: Number of worker threads
        """
        self.num_threads = num_threads
        self.executor = ThreadPoolExecutor(max_workers=num_threads)

    def parallel_evaluate_moves(
        self,
        moves: List[Any],
        evaluate_func: Callable[[Any], int]
    ) -> Dict[Any, int]:
        """
        Evaluate multiple moves in parallel.

        Args:
            moves: List of moves to evaluate
            evaluate_func: Function that evaluates a move

        Returns:
            Dictionary mapping moves to scores
        """
        futures = {}
        for move in moves:
            future = self.executor.submit(evaluate_func, move)
            futures[move] = future

        results = {}
        for move, future in futures.items():
            results[move] = future.result()

        return results

    def parallel_minimax(
        self,
        moves: List[Any],
        minimax_func: Callable[[Any], int]
    ) -> tuple[Any, int]:
        """
        Run minimax search for multiple root moves in parallel.

        Args:
            moves: Root moves to explore
            minimax_func: Function that returns evaluation for a move

        Returns:
            Tuple of (best_move, best_score)
        """
        best_move = None
        best_score = float('-inf')

        futures = {}
        for move in moves:
            future = self.executor.submit(minimax_func, move)
            futures[move] = future

        for move, future in futures.items():
            score = future.result()
            if score > best_score:
                best_score = score
                best_move = move

        return best_move, best_score

    def shutdown(self):
        """Shutdown thread pool."""
        self.executor.shutdown(wait=True)


class SearchStatistics:
    """Track and report search statistics."""

    def __init__(self):
        """Initialize statistics tracker."""
        self.nodes_evaluated = 0
        self.nodes_cached = 0
        self.cutoffs = 0
        self.time_start = None
        self.time_end = None

    def record_node(self):
        """Record evaluation of one node."""
        self.nodes_evaluated += 1

    def record_cache_hit(self):
        """Record cache hit."""
        self.nodes_cached += 1

    def record_cutoff(self):
        """Record alpha-beta cutoff."""
        self.cutoffs += 1

    def branching_factor(self) -> float:
        """
        Calculate effective branching factor.

        Returns:
            Estimated branching factor
        """
        if self.nodes_evaluated == 0:
            return 0.0
        return self.nodes_evaluated / max(1, self.nodes_evaluated - self.cutoffs)

    def pruning_efficiency(self) -> float:
        """
        Calculate efficiency of pruning.

        Returns:
            Percentage of nodes pruned (0-100)
        """
        if self.nodes_evaluated == 0:
            return 0.0
        return (self.cutoffs / self.nodes_evaluated) * 100

    def cache_hit_rate(self) -> float:
        """
        Calculate cache hit rate.

        Returns:
            Percentage of cached vs evaluated (0-100)
        """
        total = self.nodes_cached + self.nodes_evaluated
        if total == 0:
            return 0.0
        return (self.nodes_cached / total) * 100

    def summary(self) -> str:
        """
        Get summary of search statistics.

        Returns:
            Formatted string with statistics
        """
        return (
            f"Nodes evaluated: {self.nodes_evaluated}\n"
            f"Nodes cached: {self.nodes_cached}\n"
            f"Alpha-beta cutoffs: {self.cutoffs}\n"
            f"Branching factor: {self.branching_factor():.2f}\n"
            f"Pruning efficiency: {self.pruning_efficiency():.2f}%\n"
            f"Cache hit rate: {self.cache_hit_rate():.2f}%"
        )