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? C3RL compares tabular Q-learning and SARSA on Connect-3: the same board, rewards, training budget, and exploration schedule, with a different update target.

Q-learning is off-policy: its update target uses the greedy next action, even when the agent explores. SARSA is on-policy: its target uses the action actually taken. In practical terms, SARSA learns the value of the exploring policy it follows, mistakes included, while Q-learning learns about the greedy policy regardless of how it explores.

After 100,000 games each, both agents were strong against simple opponents. Against each other, the score was exactly 0.50. Interpreting that tie depends on accounting for the game’s first-move advantage.

SARSA is conservative; Q-learning is aggressive. Does that distinction produce a measurably different agent?

The sections below present the comparison, its results, and a mapped extension into deep Q-learning.

02 / The setup

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.

The smaller board makes repeated visits to state-action pairs realistic for tabular learning and keeps a full-depth solver practical as a reference. There is no external dataset: the training data is the sequence of state, action, and reward transitions produced by self-play.

A state is the flattened board 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 during both move selection and target calculation.

03 / Two learning rules

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

The distinction is entirely in $y$. Q-learning asks which legal next action looks best; SARSA uses the next action sampled by the same exploratory policy that generated the game.

Since s′ belongs to the opponent, its selected value enters the current player’s target with a minus sign.

The opponent changes the sign

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:

Here $\gamma$ discounts future value. Without the minus sign, an agent would learn to favor positions that are good for its opponent. Terminal targets use reward alone: a winning final move receives +1, the losing player’s final move receives −1, and a draw receives 0. Each method has its own table. Within a method, both sides share that table through the perspective convention.

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.

The exploration schedule is $\epsilon_g=\max\{0.02,\;0.30(1-g/G)\}$, where $G=100{,}000$. It reaches the floor before training ends. Evaluation is greedy, although equal-valued actions can still be broken randomly.

Three reference opponents provide 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 / Results

Both agents learn

Early performance improves quickly, then the learning curves spend much of the run in a similar band. They cross repeatedly, with neither method maintaining a clear learning-speed advantage.

Tournament results

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. Both agents genuinely learned. The heuristic gap is worth investigating. Establishing an algorithm-level advantage requires multiple training runs per method.

Why everything strong lands at 0.50

Connect-3 on this board is a first-player win under perfect play. All pairings among Q-learning, SARSA, and Perfect score 0.50. A separate 1,000-game evaluation against the solver gives 50% wins, no draws, and 50% losses for each learner.

First-move advantage dominates play among strong agents. Alternating who starts produces a statistical tie when each agent converts its games as the first player. The 0.50 score can therefore represent alternating wins across the two move orders.

A perfect solver maximizes the theoretical game outcome. From a lost position, it can treat several losing moves as equivalent, even when some would give a weaker opponent more chances to make a mistake.

06 / What the tie means

The head-to-head score is 0.500 ± 0.044, using an approximate 95% interval over 500 games. That interval describes finite evaluation sampling. Variation across independently trained agents requires multiple runs. The score statistic also allows half-points, so a binomial interval is only an approximation when draws occur.

These trained agents tied in this evaluation. Their performance against the solver supports strong play on the tested trajectories. Establishing optimal decisions in every reachable state requires a separate analysis.

Exploration never fully disappears. The learning rate stays constant. Self-play changes the opponent as learning progresses. A single seed also cannot reveal run-to-run variability. Sequential training gives the learners different random trajectories.

Multiple seeds, side-specific results, and checks against solver-labeled positions would make the comparison stronger. A larger board may also expose the conservative and aggressive tendencies that this solved game compresses into the same alternating-start score.

07 / Deep Q-learning

The extension asks whether a learned value function can generalize across board positions once a table becomes too sparse. It begins on the same 4 × 4 game, where the tabular agents and full-depth solver can catch implementation errors, then scales to a larger board.

Model and representation

Three binary input planes encode current-player pieces, opponent pieces, and empty cells. A starting model flattens the 3 × 4 × 4 input into two 64-unit ReLU layers with four outputs, one Q-value per column. A convolutional model becomes a later architectural comparison.

Replay entries contain state, action, reward, next state, terminal status, and the next legal-action mask. A replay buffer breaks temporal correlation; a separate target network slows movement in bootstrap values. Illegal columns are masked before every maximum or action selection.

Target and replay

The one-ply next-player perspective keeps the negative bootstrap. The plan compares standard DQN with Double DQN, which separates selecting the next action from evaluating it. With online parameters $\theta$ and target parameters $\bar\theta$:

Replay entries are created after each full game, preserving +1 for the winning final move and −1 for the losing final move. Terminal entries never bootstrap. Unit tests cover one-move wins, losing replies, draws, full columns, legal masks, and flipped player perspectives before any long run begins.

Experiment map

The initial configuration uses a 50,000-transition buffer, batch size 64, Adam at 0.001, 1,000 replay-warm-up transitions, and a hard target update every 1,000 optimizer steps. These are starting hypotheses to log and tune, while the tabular discount and exploration schedule anchor the first comparison.

Current-policy self-play is compared with a pool of frozen opponent snapshots while evaluation opponents remain fixed. Reports separate first- and second-player performance, wins, draws, losses, seed spread, environment moves, and wall-clock cost. On the small board, a held-out set of solver-labeled positions measures whether chosen moves preserve the best available outcome.

08 / References