def ttt_actions(board):
    return [i for i, v in enumerate(board) if v == 0]


def ttt_apply(board, action, player=None):
    board = list(board)
    player = player or (1 if board.count(1) == board.count(-1) else -1)
    board[action] = player
    return tuple(board)


LINES = [
    (0, 1, 2), (3, 4, 5), (6, 7, 8),
    (0, 3, 6), (1, 4, 7), (2, 5, 8),
    (0, 4, 8), (2, 4, 6),
]


def ttt_winner(board):
    for a, b, c in LINES:
        s = board[a] + board[b] + board[c]
        if s == 3:
            return 1
        if s == -3:
            return -1
    return 0


def ttt_terminal(board):
    return ttt_winner(board) != 0 or 0 not in board


def ttt_evaluate(board):
    return ttt_winner(board)  # +1 win for X, -1 win for O, 0 draw/ongoing


def ttt_apply_alternating(board, action):
    # infer whose turn it is from piece counts, so best_move's
    # single-argument apply_action signature stays generic
    x_count = board.count(1)
    o_count = board.count(-1)
    player = 1 if x_count == o_count else -1
    return ttt_apply(board, action, player)


if __name__ == "__main__":
    empty = tuple([0] * 9)
    move, value = best_move(
        empty, ttt_actions, ttt_apply_alternating,
        ttt_terminal, ttt_evaluate, depth=9,
    )
    print(f"Best opening move: {move}, minimax value: {value}")
    # Tic-tac-toe is a solved game: perfect play from an empty
    # board always evaluates to 0 (a draw).
