from typing import Callable, List, Optional, Tuple, Any


def alphabeta(
    state: Any,
    depth: int,
    alpha: float,
    beta: float,
    maximizing: bool,
    get_actions: Callable[[Any], List[Any]],
    apply_action: Callable[[Any, Any], Any],
    is_terminal: Callable[[Any], bool],
    evaluate: Callable[[Any], float],
) -> float:
    if is_terminal(state) or depth == 0:
        return evaluate(state)

    actions = get_actions(state)
    if maximizing:
        value = float("-inf")
        for a in actions:
            child = apply_action(state, a)
            value = max(
                value,
                alphabeta(
                    child, depth - 1, alpha, beta, False,
                    get_actions, apply_action, is_terminal, evaluate,
                ),
            )
            alpha = max(alpha, value)
            if alpha >= beta:
                break  # beta cutoff
        return value
    else:
        value = float("inf")
        for a in actions:
            child = apply_action(state, a)
            value = min(
                value,
                alphabeta(
                    child, depth - 1, alpha, beta, True,
                    get_actions, apply_action, is_terminal, evaluate,
                ),
            )
            beta = min(beta, value)
            if alpha >= beta:
                break  # alpha cutoff
        return value


def best_move(
    state, get_actions, apply_action, is_terminal, evaluate, depth=9
):
    best_val, best_a = float("-inf"), None
    alpha, beta = float("-inf"), float("inf")
    for a in get_actions(state):
        child = apply_action(state, a)
        val = alphabeta(
            child, depth - 1, alpha, beta, False,
            get_actions, apply_action, is_terminal, evaluate,
        )
        if val > best_val:
            best_val, best_a = val, a
        alpha = max(alpha, best_val)
    return best_a, best_val
