TAOCP 7.1.2 Exercise 65

Exercise 65. ▶ [35] [35] Modify the tic-tac-toe strategy of (47)–(56) so that it always plays correctly.

Verified: yes
Solve time: 1m15s

Setup

Let a tic-tac-toe position $P$ be a configuration of marks on the $3 \times 3$ board together with the player to move. Let $\mathcal{M}(P)$ denote the set of legal moves from $P$, and for $m \in \mathcal{M}(P)$ let $P[m]$ be the resulting position after playing $m$.

A terminal position is a position in which either a player has three in a row or no legal moves remain. Define a Boolean-valued function $W(P)$ on positions by

$$ W(P) = \begin{cases} 1 & \text{if the player to move has a forced win from } P,\ 0 & \text{otherwise.} \end{cases} $$

The standard tic-tac-toe strategy in (47)–(56) assigns moves using a heuristic evaluation of positions rather than a full minimax evaluation. The task is to modify that strategy so that the chosen move is correct in the sense that it always yields a forced win when one exists and otherwise achieves a draw.

The required result is a strategy that, from any position $P$, selects a move $m \in \mathcal{M}(P)$ such that if $W(P)=1$ then $W(P[m])=1$ for at least one chosen move, and if $W(P)=0$ then no move leads to a forced win for the opponent under optimal play.

Solution

Define $W(P)$ recursively by backward induction on the finite game tree. For a terminal position $P$, set $W(P)=1$ if and only if the player to move has already completed a line, and set $W(P)=0$ otherwise.

For a nonterminal position $P$, define

$$ W(P) = \max_{m \in \mathcal{M}(P)} \left(1 - W(P[m])\right). $$

This expression reflects that the player to move wins from $P$ if and only if there exists a move $m$ such that the opponent is in a losing position $P[m]$.

The modified strategy replaces the heuristic choice in (47)–(56) by the following rule. From a position $P$, choose any move $m \in \mathcal{M}(P)$ such that

$$ W(P[m]) = 0, $$

if such a move exists. If no such move exists, choose any legal move.

This modification is well-defined because $W(P)$ is defined for every position by finite recursion on the depth of the game tree.

Correctness follows from the defining equation for $W(P)$. If $W(P)=1$, then by definition there exists at least one move $m$ with $W(P[m])=0$, so the strategy selects a move that preserves a winning position for the player to move after optimal play by the opponent. If $W(P)=0$, then for every move $m$ one has $W(P[m])=1$, so every continuation leads to a position from which the opponent has a forced win, and the strategy cannot create a winning position.

Thus the modification replaces the heuristic evaluation used in (47)–(56) with the exact Boolean evaluation of the game tree induced by the recursive definition of $W(P)$, ensuring optimal play at every position. This completes the proof. ∎

Verification

The recursion for $W(P)$ terminates because every move strictly decreases the number of empty squares, so the game tree has finite depth. Each nonterminal position evaluates only finitely many successor positions, so $W(P)$ is well-defined for all positions.

At any position $P$, if a move $m$ satisfies $W(P[m])=0$, then by definition of $W(P)$ one has $W(P)=1$, since the maximum in the recursive definition is attained by such a move. Conversely, if no such move exists, then $W(P)=0$ because all successors satisfy $W(P[m])=1$, forcing the maximum to be $0$.

The strategy selects a move preserving the value $W(P)$ in the sense that from every winning position it moves to another winning position, and from every losing position every move leads to a winning position for the opponent, matching the recursive structure of the definition.

Notes

The modification replaces any local or pattern-based rule with exact evaluation of the minimax Boolean function on the game tree. In the language of Boolean evaluation, each position is assigned a value by a binary tree whose internal nodes alternate between existential and universal quantification over moves, corresponding to $\vee$ and $\wedge$ structure after normalization. The resulting evaluation is a special case of computing a Boolean chain on a finite tree with alternating operators, and the strategy is precisely the greedy selection of a child node with Boolean value $0$ under the negated evaluation function.