"""Tic-tac-toe game logic (complete; you don't need to change this file).

A board is a tuple of 9 ints, row-major, cells numbered 0..8:

     0 | 1 | 2
    ---+---+---
     3 | 4 | 5
    ---+---+---
     6 | 7 | 8

1 = X, -1 = O, 0 = empty. X always moves first, so whose turn it is follows
from the number of marks on the board.

Results are always from X's point of view: +1 X won, -1 O won, 0 draw.
"""

from functools import lru_cache

EMPTY = (0,) * 9

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 winner(board):
    """+1 if X has three in a row, -1 if O has, 0 if the board is full (draw),
    None if the game is still going."""
    for i, j, k in LINES:
        v = board[i]
        if v != 0 and v == board[j] == board[k]:
            return v
    return None if 0 in board else 0


def to_move(board):
    """The player whose turn it is: +1 (X) or -1 (O)."""
    n = sum(1 for v in board if v != 0)
    return 1 if n % 2 == 0 else -1


def legal_moves(board):
    """List of empty cells, or [] if the game is over."""
    if winner(board) is not None:
        return []
    return [i for i in range(9) if board[i] == 0]


def play(board, move):
    """Return the new board after the player to move marks `move`."""
    assert board[move] == 0, f"cell {move} is not empty"
    b = list(board)
    b[move] = to_move(board)
    return tuple(b)


def render(board):
    """A printable picture of the board."""
    sym = {1: "X", -1: "O", 0: "."}
    rows = [" ".join(sym[board[3 * r + c]] for c in range(3)) for r in range(3)]
    return "\n".join(rows)


@lru_cache(maxsize=None)
def minimax_value(board):
    """Exact game value for the player to move under perfect play:
    +1 win, 0 draw, -1 loss."""
    w = winner(board)
    if w is not None:
        # If someone has won, it was the player who just moved.
        return 0 if w == 0 else -1
    return max(-minimax_value(play(board, m)) for m in legal_moves(board))


def optimal_moves(board):
    """All moves that achieve the minimax value (the 'perfect play' moves)."""
    vals = {m: -minimax_value(play(board, m)) for m in legal_moves(board)}
    best = max(vals.values())
    return [m for m, v in vals.items() if v == best]


def random_player(rng):
    """A player that picks a uniformly random legal move. `rng` is a random.Random."""
    def choose(board):
        return rng.choice(legal_moves(board))
    return choose


def play_game(x_player, o_player):
    """Play one game; each player is a function board -> move. Returns the result
    from X's point of view (+1, -1 or 0)."""
    board = EMPTY
    while winner(board) is None:
        mover = x_player if to_move(board) == 1 else o_player
        board = play(board, mover(board))
    return winner(board)


# Some positions used in the chapter, the tests and run.py.
WIN_IN_ONE = (1, 1, 0,
              -1, -1, 0,
              0, 0, 0)      # X to move: 2 wins at once
MUST_BLOCK = (1, 0, -1,
              0, 1, 0,
              0, 0, 0)      # O to move: only 8 avoids losing
FORK_TRAP = (1, 0, 0,
             0, -1, 0,
             0, 0, 1)       # O to move: corners 2 and 6 lose to a fork; edges draw