Tic-Tac-Toe Against a Deterministic Automatic Opponent

Extend Tic-Tac-Toe with an automatic opponent. A human plays X, the computer plays O, and the board must be available for display after every human attempt and every actual computer move. Stop placing marks when either player wins or the board is a draw.

Implement play_against_ai(human_moves: int[][]) -> string[][]. Each input row is a human attempt [row, column]. For each attempt, first emit the resulting human event. If the attempt is accepted and leaves an unfinished game, choose and apply one automatic O move and emit its event. Return all events in order.

Each event contains eight strings:

[actor, accepted, board_row_0, board_row_1, board_row_2, status, next_player, move]

• actor is X or O; accepted is "1" or "0".
• Board rows contain X, O, and .. status is IN_PROGRESS, X_WON, O_WON, or DRAW.
• next_player is X or O while unfinished, otherwise -.
• move is the attempted coordinate as row,column, for example 1,2, with no spaces.

Automatic-player policy

The report requests an AI opponent but does not specify its strength. For this deterministic practice version, use perfect-play minimax with these exact rules:

• An O win has score +1, a draw score 0, and an X win score -1.
• On future O turns maximize this score; on future X turns minimize it.
• Choose the legal O move with the best resulting score. Among tied moves, choose the smallest row, then smallest column.
• Do not prefer faster wins or slower losses beyond that score and tie rule.

Constraints & Assumptions

• The board is initially empty, is 3 by 3, and X starts. There are at most 100 valid-coordinate human attempts.
• Occupied-cell human attempts are rejected; they do not trigger an AI move or consume the human's turn.
• Human attempts after a terminal result emit rejected X events with unchanged final state and do not trigger an AI move.
• Check for a win before a full-board draw after every accepted move, including the human move. A terminal human move must never be followed by a computer move.
• Search trial moves are internal only. Do not emit events for them, and undo them before applying the chosen move.
• All returned snapshots are independent. An empty input returns an empty event list.

Examples

human_moves = [[0,0]]
result = [
  ["X","1","X..","...","...","IN_PROGRESS","O","0,0"],
  ["O","1","X..",".O.","...","IN_PROGRESS","X","1,1"]
]

human_moves = [[1,1],[1,1]]
result = [
  ["X","1","...",".X.","...","IN_PROGRESS","O","1,1"],
  ["O","1","O..",".X.","...","IN_PROGRESS","X","0,0"],
  ["X","0","O..",".X.","...","IN_PROGRESS","X","1,1"]
]

Hint: Reuse one terminal-state definition

The live game and the search must agree about winning lines, draws, and whose turn follows a legal move. Evaluate terminal states before generating more moves.

Tic-Tac-Toe Against a Deterministic Perfect-Play Opponent

Approach

Use one terminal-state function for both real moves and search, checking the eight winning lines before checking fullness. Memoized minimax assigns terminal scores and recursively maximizes on O turns or minimizes on X turns. Real automatic selection scans empty cells in row-major order and changes the chosen move only for a strictly better score, implementing the exact tie rule without a depth preference. Search boards are immutable strings or copies, so search cannot leak marks into live snapshots. For every input attempt, update only if the game is unfinished and the square is empty, then emit one X event. Only an accepted unfinished attempt triggers the chosen O move and its event. Each event copies the three row strings; rejected and terminal attempts retain the current board and proper next-player field.

• Time complexity: O(H+9*S), where H is the number of attempts and S is the finite set of memoized reachable board/turn states; for the fixed 3 by 3 board this is O(H) with bounded search work.
• Space complexity: O(S+H) for memoized states and returned independent events; recursion depth is at most 9.