Skip to content
Tutorials Center
My learning

Topics

Lesson 35 of 37 ยท Projects and Practice

Project: Tic-Tac-Toe by Self-Play

Build a tic-tac-toe agent that learns purely by playing against itself: afterstate values, temporal-difference learning, exploration, and an evaluation against random play and a perfect minimax opponent.

In this project you will build an agent that learns to play tic-tac-toe with no knowledge of strategy. All it gets is the rules and the final result (win, draw, loss). It improves by playing thousands of games against itself and learning the value of each board position. Two things make it a good first project: the game is small enough to verify the result completely, and the same recipe (self-play plus value learning) is the idea behind systems that master chess and Go.

You will use ideas from earlier lessons: temporal-difference learning, epsilon-greedy exploration and Q-learning.

Plan

  1. Represent the board and the rules.
  2. Learn a value table V(board): the estimated chance that X eventually wins from that position.
  3. Play games in which both sides use the same table: X picks the move that maximizes V, O picks the move that minimizes it.
  4. After each game, update the values with TD learning.
  5. Evaluate against a random player and against a perfect minimax player, which gives us a ground truth: against perfect play the best possible result is a draw.

Afterstates

Instead of learning Q(state, action), we learn the value of the afterstate: the board after a move is made. Many different (board, move) pairs lead to the same afterstate, so the table is smaller and it learns faster. The agent chooses a move by looking at all afterstates reachable from the current board and picking the best one. This only works because the game is deterministic and we know the rules.

flowchart LR
    B["Current board"] --> M1["Afterstate 1: V = 0.52"]
    B --> M2["Afterstate 2: V = 0.71"]
    B --> M3["Afterstate 3: V = 0.40"]
    M2 -->|"X maximizes"| P["Play move 2"]

X picks the move whose resulting board has the highest value for X.

The learning rule

Values start at 0.5 (unknown) except for finished games: 1.0 if X has won, 0.0 if O has won and 0.5 for a draw. After a game of positions s_0, s_1, ..., s_T, we sweep backwards and move each value toward the one that followed it:

TEXT
V(s_t) <- V(s_t) + alpha * (V(s_(t+1)) - V(s_t))

This is TD(0) without discounting. The final position already holds the true result, so the information flows backwards, one step further every time a position is revisited. During training both players explore: with probability epsilon they pick a random move.

The code

Python Train a self-play tic-tac-toe agent

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

How good is it?

A learned table is only meaningful if we measure it. We test against two opponents with the exploration switched off:

  • A random player. A good agent should win most games and almost never lose.
  • A minimax player that searches the whole game tree and never errs. The best possible outcome against it is a draw, so the number to watch is how often the learner loses.
Python Evaluate against random play and perfect play

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Against random play the learner should win the large majority of games. Against the perfect player it should lose rarely or never; a draw is the best possible result. If you see losses as O, increase games further. The second player has less margin for error, and some rarely visited lines need more experience. Because the code uses the exact rules, it will fully solve the game if given enough games; the point is to see learning do it.

Experiments to try

  • Change eps to 0 during training. What happens to the number of positions with a learned value? Without exploration some positions are never visited.
  • Change alpha to 0.05 and 0.5. Which one learns faster? Which one ends up more stable?
  • Train X and O with two different tables so they cannot share what they learn.
  • Initialize unseen positions optimistically (for X, 1.0) and compare with 0.5.
  • Replace the table by a small neural network over the 9 cells. This is the first step toward the function approximation of deep Q-networks.
  • Add symmetry: rotate and reflect boards so equivalent positions share one value.

What you practiced

  • Modeling a two-player game as an RL environment and using afterstates.
  • Self-play: the agent is its own opponent, so the opponent improves as the learner does.
  • TD learning with a backward sweep over a finished game.
  • Using an exact solver (minimax) as ground truth to evaluate learning, a technique worth copying whenever it is feasible.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is an afterstate?

    Learning values of afterstates is efficient because many (state, action) pairs lead to the same resulting position.
  2. 2. Why do we sweep backwards through the game when updating values?

    Each position is moved toward the value of the position that followed it, starting from the one that holds the true outcome.
  3. 3. Against a perfect minimax opponent, what is the best possible result for the learner in tic-tac-toe?

    Tic-tac-toe is a draw with perfect play from both sides, so the number to watch is how often the learner loses.
  4. 4. Why does X maximize V while O minimizes it in this setup?

    One value table from X's perspective serves both sides in a zero-sum game.

Summary

  • Self-play lets an agent learn a game with nothing but the rules and the final outcomes.
  • Learning afterstate values with backward TD sweeps is simple and efficient for deterministic games.
  • Exploration is essential; without it many positions are never evaluated.
  • An exact solver provides a trustworthy benchmark for the learned policy.
  • The same idea, with a neural network instead of a table and tree search on top, scales to chess and Go.

Next: Project: Balancing CartPole from Scratch