C3RL: learning through self-play

01 / The question

If two agents learn the same game by playing against themselves, how much does the learning rule matter? That was the question behind C3RL, a self-play reinforcement learning project I built at the University of Waterloo. I compared tabular Q-learning and SARSA on Connect-3: the same board, rewards, training budget, and exploration schedule, with a different update target.

After 100,000 games each, both agents were strong against simple opponents. Against each other, the score was exactly 0.50. But the interesting part wasn’t picking a winner. It was figuring out what a tie actually tells us in a game where moving first matters so much.

A small game makes it easier to inspect what an agent learned—and harder to hide behind a single score.

This is a walkthrough of the original experiment, followed by a plan to extend it with deep Q-learning. The charts use the fixed-seed run’s raw data; the neural-network experiments haven’t been run yet.

02 / A smaller game

Connect-3 uses a 4 × 4 board with gravity. Players alternate dropping a piece into one of four columns. Three pieces in a horizontal, vertical, or diagonal line wins. A full board with no winner is a draw.

I used the smaller game because tabular learning needs to revisit states. A Q-table stores a value for each state–action pair; expanding the board quickly makes those repeated visits harder to get. Here, the game is also small enough to use a full-depth solver as a reference.

The state is the flattened board, always from the current player’s perspective: +1 for their pieces, −1 for their opponent’s, and 0 for empty cells. An action is a column index. Full columns are masked out both when selecting moves and when computing a target.

def key(self, player):
    return tuple((self.grid * player).flatten())

Both sides of a self-play game use the same table, but Q-learning and SARSA each have their own separate table. That perspective convention is what makes sharing between the two sides possible.

03 / Two learning rules

Both methods move an action value toward a target. The learning rate $\alpha$ controls the size of that correction.

Q-learning is off-policy: it bootstraps from the best available next action, even if the agent explored instead. SARSA is on-policy: it uses the next action actually sampled by the behavior policy.

The opponent changes the sign

In this implementation, the next state belongs to the other player. A valuable position for them is bad for the player who just moved. So the usual positive bootstrap becomes a negative one. For a nonterminal transition, the two targets are:

Here $\gamma$ discounts future value. The minus sign isn’t cosmetic: without it, an agent would learn to favor positions that are good for its opponent.

# Q-learning: best legal action for the next player
return r - self.gamma * max(next_q_row[c] for c in next_moves)

# SARSA: the action the next player actually took
return r - self.gamma * next_q_row[next_action]

Terminal targets don’t bootstrap. The winning final move gets +1; the losing player’s final move gets −1. Other moves, and the final move in a draw, have zero immediate reward. The code records the full game, then updates its transitions in forward order. That also means SARSA’s next action is available directly from the recorded trajectory.

04 / The experiment

The experiment keeps the main training choices fixed so the update rule is the intended difference. Values start at zero. Exploration chooses uniformly among legal moves; greedy play breaks value ties randomly.

More precisely, the code sets $\epsilon_g=\max\{0.02,\;0.30(1-g/G)\}$, where $G=100{,}000$. This reaches the floor before training ends, rather than decaying to zero. Evaluation is greedy: exploration is disabled, although ties can still be broken randomly.

Three reference opponents give the learned policies some context:

• Random: chooses a uniformly random legal column.
• Heuristic: takes an immediate win, otherwise blocks an immediate loss, otherwise plays randomly.
• Perfect: searches to the end of the game using memoized negamax.

The solver uses the same change of perspective. A winning move is worth +1, a board-filling draw is worth 0, and any other move is worth the negative of the resulting position’s value to the opponent.

05 / Reading the results

Both agents learn

Early performance improves quickly, then the learning curves spend much of the run in a similar band. They cross repeatedly. This run doesn’t show one method maintaining a clear learning-speed advantage.

The round-robin is a score matrix, not just win rate

The tournament gives a win 1 point, a draw 0.5, and a loss 0. This differs from the pure win rate plotted above. Each entry is the row player’s average score against the column player, with both move orders represented.

Q-learning scores 0.94 against Random and 0.85 against Heuristic. SARSA scores 0.96 and 0.92 respectively. Those are useful signs that both learned more than arbitrary moves. The heuristic gap is worth investigating, but one training run per method isn’t enough to call it a reliable algorithm-level advantage.

Why everything strong lands at 0.50

The paper reports that this game is a first-player win under perfect play. In the evaluation, all pairings among Q-learning, SARSA, and Perfect score 0.50. A separate 1,000-game evaluation against the solver reports 50% wins, no draws, and 50% losses for each learner.

That’s consistent with converting first-player games while losing from the disadvantaged side. It isn’t the same as drawing every game, and it doesn’t mean the agents learned nothing. Alternating who starts is essential to interpreting this result.

A perfect solver also need not maximize its score against a fallible opponent. From a theoretically lost position, it can treat several losing moves as equivalent, even when some would give a weaker opponent more chances to make a mistake. That helps explain why “Perfect” needn’t top every column of this matrix.

06 / What the tie means

The original paper reports a head-to-head score of 0.500 ± 0.044, using an approximate 95% interval over 500 games. That describes finite evaluation sampling under the paper’s approximation—not how results vary across independently trained agents. The score statistic also allows half-points, so a binomial interval is only an approximation when draws occur.

The conclusion I’d keep is narrower than “Q-learning and SARSA are equivalent”: these trained agents tied in this evaluation. Their performance against the solver supports strong play on the tested trajectories, not a proof of optimal decisions in every reachable state.

There are a few reasons to keep that distinction. Exploration never fully disappears. The learning rate stays constant. Self-play changes the opponent as learning progresses. And the single global seed is set once before training Q-learning and then SARSA, so they don’t receive identical random trajectories.

The two target formulas agree for a given table when SARSA’s sampled next action is greedy. But separately trained tables can differ, and fewer exploratory moves alone doesn’t prove convergence to an identical optimal policy. Multiple training seeds, side-specific results, and checks against solver-labeled positions would make the comparison much stronger.

07 / Next: deep Q-learning

Planned extension. Everything below is an experiment design, not a result from the original project.

The next question isn’t whether a neural network can beat perfect play. It’s whether a learned value function can generalize across board positions when a table becomes too sparse. I’d first make it work on the same 4 × 4 game, where the existing agents and solver give me a way to catch mistakes. Only then would I increase the board size.

Replace the table, keep the game

Start with three binary input planes: current-player pieces, opponent pieces, and empty cells. Flatten the 3 × 4 × 4 input into a small network with two 64-unit ReLU layers and four outputs—one Q-value per column. This is a proposed starting architecture, not a tuned configuration. A convolutional model can be a later comparison.

A replay buffer would store state, action, reward, next state, terminal status, and the next legal-action mask. A separate target network would provide slower-changing bootstrap values. These are standard ingredients in DQN; the network predicts action values rather than a probability distribution over moves. Mnih et al. (2015)

Keep the sign flip in the neural target

For one-ply, next-player-perspective transitions, the bootstrap is still negative. I’d implement standard DQN first, then compare Double DQN, which separates selecting the next action from evaluating it. Using online parameters $\theta$ and target parameters $\bar\theta$, the proposed Double DQN target is:

The online network selects the best legal action; the target network evaluates it. The separation follows van Hasselt, Guez, and Silver. The minus sign is the adaptation for this game’s state convention, not the standard single-agent formula.

I’d initially construct replay entries after each full game, preserving the existing winning-final-move +1 and losing-final-move −1 terminal labels. Those entries must not also bootstrap into the opponent’s terminal reward. Tests for one-move wins, losing replies, draws, full columns, and flipped player perspectives come before any long run.

A concrete experiment plan

For an initial configuration I’d try a 50,000-transition buffer, batch size 64, Adam at 0.001, 1,000 transitions of replay warm-up, and a hard target-network update every 1,000 optimizer steps. These are starting hypotheses to log and tune, not claims about what works best. The discount and exploration schedule can begin with the tabular settings to keep the comparison interpretable.

Self-play adds a moving opponent to an already changing value function. I’d compare current-policy self-play with a pool of frozen opponent snapshots, while keeping evaluation opponents fixed. Each report should separate first- and second-player performance, wins, draws, losses, training-seed spread, environment moves, and wall-clock cost. On the small board, a held-out set of solver-labeled positions can also test whether chosen moves preserve the best available outcome.

The extension succeeds if it tells me something about generalization or learning stability—not just if it produces another 0.50 on the same solved game. On larger boards, I’d report search limits explicitly instead of calling a depth-limited opponent “Perfect.”

08 / Notes & references

Adapted from my paper, A Self-Play Reinforcement Learning Comparison of Q-learning and SARSA for Connect-3, University of Waterloo, August 5, 2026. Implementation details were checked against the accompanying C3RL source. The interactive figures above read the raw JSON produced by a fixed-seed rerun of that experiment.

In the experiment repository, agents/training.py contains the shared self-play loop, analysis/evaluate.py defines the metrics, and run_experiment.py runs training and evaluation. The runner creates both the original image exports and the raw data used by the interactive charts above.

The runner fixes the training budget at 100,000 games and seeds Python and NumPy with 486. It exports chart-ready checkpoints to results/learning_curves.json and tournament scores to results/win_matrix.json. Exact reruns may depend on the runtime and dependency versions; recording those is part of the proposed reproducibility work.

1. Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction, second edition, 2018. Background on temporal-difference learning, Q-learning, and SARSA.
2. Volodymyr Mnih et al. Human-level control through deep reinforcement learning, 2015. DQN and the starting point for the proposed extension.
3. Hado van Hasselt, Arthur Guez, and David Silver. Deep Reinforcement Learning with Double Q-learning, 2015 preprint / AAAI 2016. Separating action selection from evaluation.