Tic-Tac-Toe Against a Deterministic Automatic Opponent
Company: Databricks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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:
```text
[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
```text
human_moves = [[0,0]]
result = [
["X","1","X..","...","...","IN_PROGRESS","O","0,0"],
["O","1","X..",".O.","...","IN_PROGRESS","X","1,1"]
]
```
```text
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.
```
Overview: Build an automated Tic-Tac-Toe opponent with perfect-play minimax, deterministic move ties, board events, invalid attempts, and terminal-state handling.
Read the full Databricks Software Engineer interview experience this question came from
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:
```text
[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
```text
human_moves = [[0,0]]
result = [
["X","1","X..","...","...","IN_PROGRESS","O","0,0"],
["O","1","X..",".O.","...","IN_PROGRESS","X","1,1"]
]
```
```text
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.
```
Constraints
- Initially empty 3 by 3 board with X starting; at most 100 human attempts with coordinates in 0 through 2.
- Emit an X event for each attempt; occupied-cell and post-terminal attempts are rejected without changing the board or triggering O.
- An accepted unfinished X move triggers one O move chosen by minimax: O win +1, draw 0, X win -1; future O maximizes and X minimizes.
- Tied O moves choose smallest row then column without preferring faster wins or slower losses.
- Check wins before full-board draws after every accepted move and stop placing marks once terminal.
- Events are independent eight-string snapshots [actor,accepted,row0,row1,row2,status,next_player,move], accepted 1/0, status IN_PROGRESS/X_WON/O_WON/DRAW, terminal next_player -, coordinate row,column.
Examples
Input: ([],)
Expected Output: []
Explanation: No attempts produce no events.
Input: ([[0, 0]],)
Expected Output: [['X', '1', 'X..', '...', '...', 'IN_PROGRESS', 'O', '0,0'], ['O', '1', 'X..', '.O.', '...', 'IN_PROGRESS', 'X', '1,1']]
Explanation: The first response uses perfect-play score and the earliest equally scoring coordinate.