Tic-Tac-Toe — Reinforcement Learning Agent

Sutton & Barto introduce tic-tac-toe as a motivating example for reinforcement learning. The classical approach to this game is minimax, which computes optimal play by assuming both players act perfectly. But minimax cannot exploit an imperfect opponent's mistakes — it plays the same way regardless of who it faces. An evolutionary method could search the space of policies directly, but it only uses the final outcome of each game, discarding the information available during play.

The RL approach instead learns a value function V(s) that estimates the probability of winning from each board state s. Specifically, the agent evaluates afterstates — the board positions that result after the agent places its mark but before the opponent responds. This is efficient because different actions from different prior states can lead to the same afterstate.

The agent uses an ε-greedy policy: with probability ε it makes a random exploratory move; otherwise it makes the greedy move — the one leading to the afterstate with the highest estimated value. After each greedy move (not exploratory ones), the value estimate is updated using temporal-difference (TD) learning:

Here S_t is the previous afterstate, S_t+1 is the current afterstate, and α is the step-size parameter controlling learning speed. The quantity V(S_t+1) − V(S_t) is the TD error: the difference between successive value estimates that drives learning. Over many games, these values converge to the true winning probabilities and the agent learns to play optimally against its training opponent.