From Minimax to Reinforcement Learning : Why RL wins at Tic-Tac-Toe ?

An illustration of Tic-Tac-Toe game

This post captures my takeaways from Tic-tac-Toe game explained in the Chapter 1 of the book Reinforcement Learning: An Introduction by Sutton and Barto, the bible of RL.

What is Tic-Tac-Toe?

Tic-tac-toe is a two-player game where one player is plays Xs and the other is plays Os. The game is played on a 3x3 grid. The player who gets three of their marks in a row (horizontally, vertically, or diagonally) wins the game. If all the squares are filled and no player has three in a row, the game is a draw. In this blog we learn various classical techniques to solve Tic-Tac-Toe game and learn how RL is different from them.

Sample Tic-Tac-Toe Games - Left : Draw, Right : O Wins

Classical Techniques

Minimax

A minimax algorithm is a recursive algorithm used in decision making in-order to chose the best move in a two player game. Minimax assumes the opponent is always playing optimally. The algorithm builds a complete game tree, searching all possible future states to find a move that maximizes the player's minimum gain.

Key Components

1. Maximizer and Minimizer: Let X be the maximizer and O be the minimizer. X is the player who is trying to maximize the score of the game and O is the player who is trying to minimize the score of the game.

2. Terminal States: Terminal states are the states when the game is over. There are 3 different terminal states :

   • X wins, A value of +10 is assigned
   • O wins, A value of -10 is assigned
   • Draw, A value of 0 is assigned

Terminal states of Tic-Tac-Toe. Left : Draw, Middle : X Wins, Right : O Wins

3. Game Tree: Game tree is a tree that represents all possible future states of the game from the current state. Each node in the tree represents a state of the game and each edge represents a move. The game tree is built until all terminal states are reached.

Game tree of Tic-Tac-Toe

4. Propagation: Propagation is the process of assigning values to the nodes of the game tree. The values are assigned based on the terminal states and the values are propagated back to the root node.

   • If it's a maximizing player's turn, the value is assigned as the maximum of the values of the child nodes.
   • If it's a minimizing player's turn, the value is assigned as the minimum of the values of the child nodes.

5. Optimal Move: At the root of the game tree, the maximizing player selects the move that leads to the highest value.

function minimax(node, depth, maximizingPlayer):
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    if maximizingPlayer then
        value := -infinity
        for each child of node do
            value := max(value, minimax(child, depth − 1, FALSE))
        return value
    else (* minimizing player *)
        value := +infinity
        for each child of node do
            value := min(value, minimax(child, depth − 1, TRUE))
        return value

Minimax cannot model an imperfect opponent. If opponent doesn't play optimally, minimax will still play optimally and will end up playing defensively to ensure a draw, potentially missing a move that could lead to a win.

Dynamic Programming

Dynamic programming is a algorithm used to solve optimization problems by breaking them down into smaller subproblems and solving them recursively.

Key Components

1. Optimal Substructure: The solution to the main problem can be constructed from the optimal solutions of its subproblems.
2. Subproblems: The problem can be broken down into subproblems which are reused several times
3. Memoization: Memoization is the technique of storing the result of a subproblem so that it can be reused when the same subproblem is encountered again.

How it works for Tic-Tac-Toe

In the context of Tic-Tac-Toe, DP is used to calculate the "Value" of every possible game state. The "Value" represents the probability of winning from that specific position.

Step 1: Define the State Space Create a massive table that lists every possible legal configuration of Xs and Os on the board.

Step 2: Assign Values to Terminal States (The End) Fill in the values for the states where the game is already over, as these are known facts.

Step 3: Back up Values (Working Backwards) Compute the value of earlier states based on the values of the future states they lead to.

The core of DP is this step.

• YOUR turn: You assume you will play the best move. The value of the current state is the maximum value among the possible next states.

• OPPONENT turn:

  • Standard Minimax assumption: The opponent plays perfectly to minimize your score.
  • General DP assumption: Calculate the Expected Value based on the opponent's behavior.

By working backward from the end of the game to the empty board, fill the table. Once the table is full, "playing" simply means looking at the table and choosing the move with the highest value.

Limitations of DP

1. The Requirement of a Perfect Model (The "Opponent Problem") To calculate the values during the opponent's turn (Step 3 above), DP requires a complete specification of the opponent which is not possible in real life.

While Tic-Tac-Toe is small enough for DP (approx. 5,000 states), complex games such as Chess, Go, and Backgammon explode in size.

Evolutionary Algorithm

An Evolutionary Algorithm (EA) is a search algorithm that uses the principles of natural selection (that's why the name) to find the best solution to a problem. It works by maintaining a population of candidate solutions and iteratively improving them through a process of selection, crossover, and mutation. EA works by starting with population of solutions and iteratively improving the population by selecting the best solutions, creating new solutions by combining the best solutions and mutating (random variations) the solutions to explore new solutions until an optimal (or close to optimal) solution is found.

Key Components

How Evolutionary Algorithms Work for Tic-Tac-Toe

We use a policy to represent the solution. A policy is a giant list of rules that tells the player exactly what move to make for every possible configuration of Xs and Os on the board.

The Process (Hill-Climbing):

• Create a Policy: Start with a random rule set (e.g., "Always put an X in the top left if available").
• Evaluate: Hold this policy fixed and play many games against the opponent.
• Calculate Fitness: Count how many times this policy won. This win frequency is the estimate of the policy's quality.
• Mutate: Make a random change to the policy (e.g., change the rule for one specific board state).
• Re-Evaluate: Play many games with this new policy.
• Select: If the new policy wins more often than the old one, keep it. If not, revert to the old one.

Limitations of Evolutionary Algorithms

• Credit Assignment Problem: EA might select a policy that has a very less win frequency (False Positives).
• Data Requirement: EA requires a large amount of data to evaluate the fitness of a policy as it ignores move-by-move data. Hundreds of games are required to evaluate the fitness of a simple policy change.

Illustration of how EA works for Tic-Tac-Toe

Reinforcement Learning

Like I explained in my previous blog Intro to RL, the main objective of a RL algorithm is to obtain or learn a value function that decides the best action to take in a given state. In the context of Tic-Tac-Toe, the value function is a table that lists every possible legal configuration of Xs and Os on the board and assigns a value to each configuration.

How RL can be used for Tic-Tac-Toe

Here is a breakdown of the Reinforcement Learning (RL) algorithm for Tic-Tac-Toe as described in Chapter 1 of Sutton & Barto's book:

The Core Concept: Learning a "Value Function"

Unlike evolutionary methods (which search for a winning policy by looking only at the end result of a game), this RL approach learns by evaluating every single state (board configuration) encountered during the game.

Evaluating how we got to a state is as important as evaluating the state itself.

The goal is to learn a Value Function—a table of numbers where each number represents the probability of winning from that specific board position.

Step-by-Step Algorithm

1. Initialization

Before playing, the agent creates a table for every possible state of the game.

• Winning States (3 Xs): Value = 1.0 (We have already won).
• Losing/Draw States (3 Os or Full Board): Value = 0.0 (We cannot win).
• All Other States: Value = 0.5 (We assume a 50% chance of winning initially).

2. Playing Against the Opponent

The agent plays many games against an imperfect opponent. For every turn, the agent follows this decision process:

• Look Ahead: The agent looks at every empty spot on the board and determines what state would result from moving there.
• Check Values: It looks up the current value for each of those potential resulting states from the table.
• Select Move:
  • Greedy Move (Exploitation): Most of the time, the agent picks the move that leads to the state with the highest value.
  • Exploratory Move (Exploration): Occasionally, the agent picks a random move. This ensures it sees states it might otherwise miss, preventing it from getting stuck in a suboptimal strategy.

3. The Update Rule

This is the "magic" step where learning happens. Unlike methods that wait for the game to end to assign credit, this method updates values while the game is being played.

After making a greedy move, the agent updates the value of the previous state ($S_{t-1}$) to be closer to the value of the current state ($S_{t}$).

• $V(S_{t})$ : The estimated value of the state before the move.
• $V(S_{t+1})$ : The estimated value of the state after the move.
• $\alpha$ : The step-size parameter (learning rate). This is a small fraction that controls how fast the agent learns.

4. Convergence

As the agent plays more games:

• The values in the table drift away from the initial guess and converge toward the true probability of winning from each state.
• The agent effectively learns to plan without explicitly being programmed with rules, simply by maximizing the value function.

Interactive Demo

Try out the different algorithms yourself! Play against the AI and observe how each approach makes decisions (made with Google AI Studio).

• Minimax: Experiment with different tree depths to observe how the structure and evaluation of the game tree evolve.
• Dynamic Programming: Vary the opponent’s error rate to analyze how the DP algorithm performs, visualized as a heatmap of winning probability across moves.
• Evolutionary Algorithm: Test different mutation rates to evaluate EA performance, measured by win rate versus the number of games played.
• Reinforcement Learning: Explore different learning and exploration rates to examine how training performance changes over the number of games played.

References

1. Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction.
2. Tic-Tac-Toe playing online by Google
3. Minimax explanation by Sebastian Lague

Tools

• Image Generation: Gemini, ChatGPT
• Interactive Demo: Google AI Studio
• Editor: Antigravity