Tic-Tac-Toe with Minimax

1The same backup, a board instead of a club tree

Tic-tac-toe is a two-player, perfect-information, zero-sum game on nine cells. X writes first. A player who places three of their marks in a row, column or diagonal wins. A full board with no line is a draw. Game Playing and Minimax already said what 'optimal' means here: a move that maximises the worst-case utility against an opponent who minimises it. This lesson does not retell that backup. It implements it.

What changes is the object the recursion sees. The club tree had four printed leaves. A tic-tac-toe position has a set of empty cells, and each empty cell is a legal action. The leaves are positions where someone has three-in-a-row or the board is full. The numbers on those leaves are +1, 0 and −1, not the club's 3, 5, 2 and 9.

2Nine cells and a finished-line test

Store the board as a list of nine entries, row-major: indices 0, 1, 2 are the top row. Each entry is X, O, or empty. A legal move is an index whose entry is empty. The eight winning triples are the three rows, the three columns, and the two diagonals. `winner` returns X or O when one of those triples is uniform and non-empty, and None otherwise.

Call `winner` before you generate moves. A position that already contains a line is a leaf, even if empty cells remain. Generating a move from a finished board is the bug that lets a program 'play on' after the match is over and then back up a nonsense score.

Figure. The campus leftover, cells numbered 0 to 8. X holds 0 and 1; O holds 2 and 3. Cell 4 is sage because it is the move minimax will pick. Roles mark O's marks and that empty centre — they are not a strength scale.

3Plus one, zero, minus one

Utility is always written from X's point of view, the same convention as the club tree. An X line is +1. An O line is -1. A full board with no line is 0. Those three numbers are the only leaves. There is no 'X has two in a row' bonus inside this program — that would be an evaluation function, which Alpha-Beta Pruning named as a cutoff guess, and this board is small enough to finish.

The empty board's backed-up value is 0. Perfect play draws. That is a fact about tic-tac-toe, not a defect in the listing. The campus leftover is not empty: X already has two on the top row, O has blocked the third cell of that row, and the centre is still free. From there the backed-up value is +1 if both sides play the backup.

4Centre now, win on the next ply

On the campus leftover X is to move. Minimax tries every empty cell, lets O answer, and backs up. The unique first move with value +1 is cell 4, the centre. That mark does not win immediately — there is no X line yet. It creates two threats that O cannot kill together.

Whatever empty cell O takes next, X has a winning reply on the following ply: after O plays 5, 6 or 8, X completes the middle column at 7; after O plays 7, X completes the main diagonal at 8. That is the club-tree lesson in marks: MAX does not need the pretty cell if MIN would refuse it; here every MIN reply still leaves a MAX win, so the root value is +1.

5A function that returns a cell

The listing is the backup from Game Playing and Minimax with a board argument. `winner` is the line test. `minimax` returns a pair (score, move). MAX walks empty cells and keeps the child with the largest score; MIN keeps the smallest. A finished position returns (utility, None) because there is no move to publish. The caller at the root prints the move half of the pair.

On the campus leftover the printed move is 4 and the printed score is 1. On an empty board the score is 0 and the move is some legal first cell — often 0 in this left-to-right scan — because every opening draws against perfect play.

Figure. winner or a full board returns (utility, None) before any empty cell is tried. minimax returns the pair (score, move); a score alone cannot tell the caller which cell to mark. On the campus leftover the printed pair is (1, 4).

What the listing does

1. Leaf firstwinner or a full board returns (utility, None) before any empty cell is tried.
2. X max, O minEach empty cell is written, scored by the opponent's turn, then cleared.
3. Return bothThe pair is (score, move). A score alone cannot tell the caller which cell to mark.

Minimax on a 3×3

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):
    for i, j, k in LINES:
        if board[i] and board[i] == board[j] == board[k]:
            return board[i]
    return None

def minimax(board, player):
    w = winner(board)
    if w == 'X':
        return 1, None
    if w == 'O':
        return -1, None
    empties = [i for i, c in enumerate(board) if c is None]
    if not empties:
        return 0, None
    best_move = empties[0]
    if player == 'X':
        best = -2
        for i in empties:
            board[i] = 'X'
            val, _ = minimax(board, 'O')
            board[i] = None
            if val > best:
                best, best_move = val, i
        return best, best_move
    best = 2
    for i in empties:
        board[i] = 'O'
        val, _ = minimax(board, 'X')
        board[i] = None
        if val < best:
            best, best_move = val, i
    return best, best_move

Coding lab. Pick the centre on the leftover runs in the app, with checks on your output.

6What this program does not do

A playable loop is: show the board, if it is X's turn call minimax and mark that cell, if it is O's turn read a cell from a human, then repeat until `winner` or a full board. That loop is plumbing. It does not change the backup.

Three things this program refuses. It does not prune: Alpha-Beta Pruning cuts branches the backup will never need, and on 3×3 the extra code is optional. It does not evaluate unfinished positions: the tree fits in memory. It does not learn. A policy trained on self-play is the reinforcement-learning course, and it is a different object — a move distribution, not a backed-up leaf. Cross-link the theory lesson when you need the guarantee; stay here when you need a cell to mark.