tic-tac-toe-rl

Applying reinforcement learning and search theory to the game of Tic-Tac-Toe.

The board is represented as a pair of 9-bit bitboards (one per player), with game rules, state generation, and the play loop handled by the Environment class. Players — human or agent — are pluggable, so any combination of human-vs-human, human-vs-agent, or agent-vs-agent play is possible. See How to Run below.

Agents

• Value Iteration / Policy Iteration — classical dynamic-programming solutions over the full Tic-Tac-Toe state space, used as a baseline for optimal play.
• Minimax (with alpha-beta pruning) — exact adversarial search, assuming an opponent who also plays optimally.
• Q-Learning — model-free tabular learning of state-action values through self-play.
• Monte Carlo Tree Search (MCTS) — evaluates moves via simulated rollouts rather than a precomputed table or a full search of the tree.

Tic-Tac-Toe's small, fully-enumerable state space makes it a good testbed for comparing these approaches side by side before applying similar methods to larger games.

Project Description

Environment

The state of the game is a tuple of three pieces of data - two integers and one character(34, 65, 'X'). The first integer is a 9-bit bitboard of the cross's placements, the second is the nought's, and the character records whose turn it is to move next.

Each integer is the base-10 representation of a 9-bit bitboard over the 9 cells of the board (indexed 0–8). So 34 is 000100010 for the cross, and 65 is 001000001 for the nought:

$$ 34_{10} = \texttt{000100010}_2 \qquad 65_{10} = \texttt{001000001}_2 $$

Taking the bitwise OR of the two boards gives the full set of occupied cells:

$$ \texttt{000100010}_2 \lor \texttt{001000001}_2 = \texttt{001100011}_2 $$

so the state (34, 65, 'X') represents that board configuration with X to move next.

Markov Decision Process Model

Each agent below is built on top of a shared MDP interface, defined by the tuple $(\mathcal{S}, \mathcal{A}, P, R, \gamma)$:

State space, $\mathcal{S}$, is all reachable $(X\text{-}mask, O\text{-}mask, turn)$ triples, generated by traversing the game tree from the empty board with players alternating turns. Terminal states — a completed three-in-a-row for either player, or a full board — are included in $\mathcal{S}$ but have no outgoing actions.

Action space $\mathcal{A}(s)$. For a non-terminal state $s$ where it is the learning agent's turn, $\mathcal{A}(s)$ is the set of empty cells, encoded as single-bit masks:

$$ \mathcal{A}(s) = { 2^i \mid \text{cell } i \text{ is empty in } s } $$

Transition function $P(s' \mid s, a)$. The agent's own move is deterministic. To keep the problem a single-agent MDP (rather than a two-player game tree), the opponent's reply is folded directly into the transition: after the agent plays $a$, the opponent is modeled as choosing uniformly at random among the remaining empty cells. If $k$ cells remain open after the agent's move, each resulting state occurs with probability

$$ P(s' \mid s, a) = \frac{1}{k} $$

If the agent's own move already ends the game (win or draw), the transition is deterministic to that terminal state.

Reward function $R(s, a, s')$. Reward is zero except on transitions into a terminal state, from the learning agent's perspective:

$$ R(s, a, s') = \begin{cases} +1 & \text{agent wins at } s' \\ -1 & \text{opponent wins at } s' \\ 0 & \text{draw, or } s' \text{ non-terminal} \end{cases} $$

Discount factor $\gamma$. Since every game terminates within 9 plies, $\gamma = 1$ is used by default (no need to discount for convergence), though it is configurable per agent.

Bellman optimality equation. Value Iteration and Minimax both build on

$$ V^{\ast}(s) = \max_{a \in \mathcal{A}(s)} \sum_{s'} P(s' \mid s, a)\Big[R(s,a,s') + \gamma V^{\ast}(s')\Big] $$

with the optimal policy read off as $\pi^{\ast}(s) = \arg\max_a Q^{\ast}(s, a)$.

---

Agents

Value Iteration

Iteratively applies the Bellman backup above to every state until values converge within a tolerance $\varepsilon$:

$$ V_{k+1}(s) \leftarrow \max_{a} \sum_{s'} P(s'\mid s,a)\big[R(s,a,s') + \gamma V_k(s')\big] $$

stopping when $\max_s |V_{k+1}(s) - V_k(s)| < \varepsilon$. The greedy policy is extracted once, after convergence, by taking the $\arg\max$ over actions using the final value function.

The algorithm can be described with the following pseudocode [3]:

• Initialize $\epsilon > 0$ to determine convergence condition
• Initialize $V(s)$, for all $s \in S^{+}$ to be 0
• Loop
  • $\Delta \leftarrow 0 $
  • Loop for each $s \in S^+$
    • $v \leftarrow V(s)$
    • $V(s) \leftarrow \max_a \sum_{s'} P(s'|s,a) \times (R(s') + \gamma V(s'))$
    • $\Delta \leftarrow max(\Delta, \lvert v - V(s) \rvert) $
• Until $\Delta < \epsilon$

Then once we find an accurate estimate for the value function, we can extract the optimal policy.

Policy Iteration

This one is a two step process where the algorithm alternates between policy evaluation and improvement until the policy stops changing:

1. Policy evaluation — solve $V^{\pi}$ for the current fixed policy $\pi$, by repeated application of

$$ V^{\pi}_{k+1}(s) \leftarrow \sum_{s'} P(s' \mid s, \pi(s))\big[R(s,\pi(s),s') + \gamma V^{\pi}_k(s')\big] $$

2. Policy improvement — given the converged $V^{\pi}$, greedily update the policy:

$$ \pi(s) \leftarrow \arg\max_a \sum_{s'} P(s'\mid s,a)\big[R(s,a,s') + \gamma V^{\pi}(s')\big] $$

Convergence is guaranteed once step 2 leaves $\pi$ unchanged for every state.

The algorithm for both steps is as follows [3]:

Policy Iteration

Initialize $V(s) \in \mathbb{R}$ and $\pi(s) \in A(s)$ arbitrarily for all $s \in S$

Policy Evaluation

• Loop
  • $\Delta \leftarrow 0 $
  • Loop for each $s \in S^+$
    • $v \leftarrow V(s)$
    • $V(s) \leftarrow \sum_{s'} P(s'|s,\pi(s)) \times (R(s') + \gamma V(s'))$
    • $\Delta \leftarrow max(\Delta, \lvert v - V(s) \rvert) $
• Until $\Delta < \epsilon$

Policy Improvement

• $\text{policy-stable} \leftarrow true $
• For each $s \in S$
  • $\text{old-action} \leftarrow \pi(s)$
  • $V(s) \leftarrow \underset{a}{\text{argmax}} \sum_{s'} P(s'|s,a) \times (R(s') + \gamma V(s'))$
  • if $\text{old-action} \neq \pi(s)$, then $\text{policy-stable} \leftarrow false$
• If policy-stable then stop and return $\text{V} \approx v_* $, and $\pi \approx \pi_* $; else go to policy evaluation

Minimax (with $\alpha$–$\beta$ pruning)

Unlike VI/PI, Minimax treats Tic-Tac-Toe as the two-player adversarial game it actually is, rather than folding the opponent into a stochastic transition. Each ply alternates between maximizing (the agent's turn) and minimizing (the opponent's turn):

$$ \text{minimax}(s) = \begin{cases} \text{evaluate}(s) & \text{if } s \text{ is terminal} \\ \max_{a \in \mathcal{A}(s)} \text{minimax}(\text{apply}(s,a)) & \text{agent's turn} \\ \min_{a \in \mathcal{A}(s)} \text{minimax}(\text{apply}(s,a)) & \text{opponent's turn} \end{cases} $$

The minimax formulation and its $\alpha$–$\beta$ pruning optimization follow the standard treatment in [2]: pruning cuts off branches that cannot influence the final decision, without changing the result. Since Tic-Tac-Toe is small and fully solved, this search is exact — a Minimax agent never loses.

Q-Learning

A model-free method — it never uses $P$ or $R$ directly, only samples gathered by actually playing games. States and actions are updated via the tabular Q-learning update rule [3]:

$$ Q(s,a) \leftarrow Q(s,a) + \alpha\Big[r + \gamma \max_{a'} Q(s',a') - Q(s,a)\Big] $$

Training is done via self-play: the same agent plays both sides, and because the game is zero-sum, a state that is good for the player about to move is exactly as bad for their opponent. This means the bootstrapped estimate from the next state must be negated before it is folded into the update:

$$ Q(s,a) \leftarrow Q(s,a) + \alpha\Big[r - \gamma \max_{a'} Q(s',a') - Q(s,a)\Big] $$

Action selection during training follows an $\varepsilon$-greedy policy, with $\varepsilon$ decayed (with a floor) across episodes to shift from exploration toward exploitation as the table fills in.

Monte Carlo Tree Search (MCTS)

Rather than solving the whole state space up front, MCTS builds a search tree incrementally, one move at a time, using four phases repeated for a fixed budget [2]:

1. Selection — descend the tree from the root using the UCB1 formula, balancing exploitation of known-good moves against exploration of under-visited ones:

$$ \text{UCB1}(s,a) = \frac{w_a}{n_a} + c\sqrt{\frac{\ln N}{n_a}} $$

where $w_a$/$n_a$ are the accumulated reward and visit count for child $a$, and $N$ is the parent's visit count.

2. Expansion — add a new child node for an untried action.
3. Simulation — play out a random rollout to a terminal state.
4. Backpropagation — propagate the rollout's result back up the tree, incrementing visit counts and flipping the sign of the result at every level (since, as in self-play Q-learning, turns alternate and a result good for one player is bad for the other).

After the search budget is spent, the root's child with the most visits is selected as the move — visit count rather than raw value, since it is a more robust signal under partial exploration.

How to Run

git clone https://github.com/<your-username>/tic-tac-toe-rl.git
cd tic-tac-toe-rl

Train an agent (Value Iteration, Policy Iteration, or Q-Learning) and save its policy/Q-table to disk:

python3 -m src.utils.trainer

Play a game, choosing which algorithm controls each side (human, Value/Policy Iteration, Minimax, Q-Learning, or MCTS):

python3 main.py

You'll be prompted to choose an algorithm for cross and for nought; pre-trained policies are loaded automatically from policies/.

Sources

[1] https://github.com/bsamseth/tic-tac-toe/blob/master/tictactoe.py

[2] Russell, S. J., and Peter Norvig. Artificial Intelligence: A Modern Approach. 4th ed., Pearson, 2020.

[3] Sutton, Richard S., and Andrew G. Barto. Reinforcement Learning: An Introduction. 2nd ed., The MIT Press, 2018.

[4] https://huggingface.co/learn/deep-rl-course

[5] https://paulinamoskwa.github.io/blog/2025-08-31/rl-pt1

[6] https://github.com/sonnysideupp/RL-MDP-TicTacToe/tree/main