AlphaZero-inspired Dots & Boxes agent
A self-play reinforcement learning agent that combines neural network evaluation with Monte Carlo Tree Search to learn strategic play without human gameplay data.
Traditional Dots and Boxes bots can rely heavily on handcrafted heuristics. I wanted to investigate whether an AlphaZero-inspired agent could discover useful strategic principles through self-play rather than being explicitly programmed with them.
Overview
In 2017, DeepMind's AlphaZero learned chess, shogi and Go from scratch. It never saw a human game. It just played itself millions of times and became the strongest player in the world at all three. That result raised a question I couldn't shake: when an agent learns purely from experience, does it end up thinking the way experts do, or does it find something else entirely?
Dots and Boxes is the perfect place to ask. Most people know it as a doodle game from the back of a school copybook, but at a high level it has a surprisingly deep theory. Strong players rely on named techniques like the double-cross and the long chain rule, worked out by mathematicians and enthusiasts over decades. Because that theory is so well documented, you can actually check whether an AI has found it.
For my final-year thesis at Munster Technological University, I designed and built an AlphaZero-inspired agent for a 4×4 Dots and Boxes board, trained it entirely through self-play on a distributed cloud cluster, and built an evaluation suite to test whether it had independently discovered those human strategies.
The infrastructure worked: a full 1,000-iteration training run completed on Google Kubernetes Engine in 8.4 hours for under $50. The research answer is still open, and the reasons why taught me more about distributed systems and ML training than anything that went right. This page covers both.
Why Dots and Boxes?
The rules are simple. Players take turns drawing a line between two dots. Complete the fourth side of a box and you claim it and move again. Most boxes wins.
The strategy is not simple. Late in the game the board breaks into chains and loops of boxes, and whoever is forced to open the first long chain usually loses. Expert players fight over that control using techniques that look like mistakes to a beginner:
- Forced capture: take a free box when it's there. The basic tactical baseline.
- Double-cross: decline the last two boxes of a chain so your opponent has to open the next one.
- Parity sacrifice: give away a small chain early to flip who ends up in control of the long ones.
- Loop control: treat closed loops differently from open chains, because they cost more to decline.
That gave me two concrete research questions. First, does a neural-guided MCTS agent actually beat a range of baseline opponents on win rate and score margin? Second, does its learned behaviour match those four human principles when tested on positions where the correct move is known?
I chose a 4×4 board (40 possible lines) over the 6×6 in my original design. It still contains all four strategic patterns, but each game is about half the length, which meant far more training games for the same compute.
From a laptop script to a distributed training system
The first version was a modular monolith: game engine, search, network, training and evaluation all in one process on my laptop. That was the right call for proving the core loop worked, and the wrong one the moment I tried to train. Self-play is brutally CPU-hungry. Every move runs 200 tree-search simulations, each one calling the neural network, and a single machine couldn't generate games fast enough to feed training.
So I rebuilt it as three independent services on Google Kubernetes Engine, each scaled to its own workload:
- Self-play service (6 replicas): plays the current best model against itself and writes every game to Bigtable. Inside each pod, game threads share a batched inference queue that groups up to 64 board states into one forward pass.
- Training service (1 replica): samples positions from a replay buffer, applies 8-way symmetry augmentation, trains a challenger network, and gates it against the current best over 20 games. A challenger needs a 55% win rate to be promoted.
- Evaluation service (1 replica): benchmarks checkpoints against five baseline agents and a suite of strategic probe positions, and tracks Elo ratings over time.
The services never call each other directly. Game records and training metrics live in Bigtable; model weights, checkpoints and evaluation requests live in Cloud Storage. When a challenger is promoted, the training service updates a sentinel file, and self-play pods poll it and hot-swap to the new weights without restarting.
Everything is defined as code. Terraform provisions the cluster, buckets and Bigtable instance, and Helm charts hold each service's replicas, resource limits and environment. I could tear the whole thing down after a run and bring it back identically, which mattered on a student budget.
One small win I'm proud of: I developed all three services locally against mocked interfaces for Cloud Storage and Bigtable. When it came time to deploy, switching to the real services needed credentials and endpoints, not code changes.
Five sprints, two rewrites, one cluster
I built the system in five two-week agile sprints starting in January, each ending with a short retrospective on what shipped, what slipped and what needed reworking. The plan changed a lot. Two of the five sprints ended up being restructures I hadn't planned for at all, and in hindsight they were some of the most valuable engineering in the project.
Slide 1 — Sprint 1: Game engine and baselines
Image: Figure 6, class diagram (Board, GameState, Move)
I built the game engine around immutability. Every move returns a new GameState, so the tree search can explore thousands of hypothetical futures without corrupting the real game. Move is a frozen dataclass for the same reason. I also wrote five baseline opponents to measure against: random, defensive, greedy, heuristic and pure MCTS. The sprint's main snag was a tangle of circular imports, fixed by enforcing a strict one-way dependency order.
Slide 2 — Sprint 2: Neural network and self-play
Image: Figure 5, DotZeroNet architecture
I connected a residual neural network to the search and built the self-play loop, replay buffer and model gating. Two choices made each game count for more: encoding the board from the current player's perspective so one network learns for both sides, and rotating and flipping every position into its eight symmetric versions at training time. The hardest bug was mismatched tensor shapes between the board encoder and the network input.
Slide 3 — Sprint 3: Evaluation framework
Image: a probe position rendered on the board, or the EndgameSpec code
I built a tournament runner and a suite of 17 endgame probe positions across the four strategic categories. Rather than hand-drawing each board, I described positions abstractly (chains, loops, whose turn) and had a builder generate them from templates. An exact minimax solver labelled the correct move and outcome for each one, so there was no subjective judgement in the ground truth.
Slide 4 — Sprint 4: Modularisation
Image: before/after repo structure diagram
The monorepo was buckling, so I split it into three services and two shared packages: game (board, rules, search) and model (network, inference). I realised the tree search code had been living in the model package when it really belonged with the game, and moving it broke imports across every service. I also migrated from PyTorch to TensorFlow for a smoother container deployment, and reconciled version conflicts between TensorFlow, NumPy and the Google Cloud libraries.
Slide 5 — Sprint 5: GKE deployment
Image: Figure 3, iterative training cycle, or a GKE console screenshot
I containerised all three services with Docker, provisioned the cloud resources with Terraform, and deployed with Helm. When no T4 GPUs were available in my target zones, I moved training to CPU, and it turned out not to matter: self-play was always the bottleneck. The full run completed in 8.4 hours with two pod crashes, both restarted automatically by Kubernetes without any meaningful hit to throughput.
How DotZero thinks
The agent has two parts that work together: a neural network that gives intuition, and a tree search that checks that intuition by looking ahead.
The network (DotZeroNet). Each board goes in as a 5×5 grid with four layers: horizontal lines drawn, vertical lines drawn, boxes I own, boxes my opponent owns. It passes through a convolutional layer and six residual blocks of 64 channels, then splits into two heads. The policy head outputs a probability for each of the 40 possible lines, with illegal moves masked out. The value head outputs a single number between −1 and 1: how likely the current player is to win from here.
The search (PUCT Monte Carlo Tree Search). Before every move, the agent runs 200 simulations. Each one walks down the tree, balancing moves the network likes against moves it hasn't tried much, using the PUCT formula with an exploration constant of 1.5. When it reaches a new position, it asks the network for a value instead of playing a random game to the end. That single change, swapping random rollouts for a learned evaluation, is the core idea behind AlphaZero.
Learning from itself. During self-play, I add Dirichlet noise to the root of the search so the agent occasionally tries moves it would normally dismiss, and sample moves in proportion to how often the search visited them. After each game, every position is labelled with the search's move distribution and the final result. The network then trains to predict both, so its intuition gradually catches up with what the search discovered. In evaluation, the noise is switched off and the agent plays its best move.
The search tree is also reused between moves: after a move is played, the subtree under it becomes the new root, so work from the previous turn isn't thrown away.
What the Policy Loss curve revealed
It learned, then it stopped. Policy loss fell from about 2.95 to 2.68 over the first 200 iterations. For context, an agent picking uniformly at random among 40 moves would sit around 3.69, so the network was clearly learning to separate sensible moves from bad ones. Model gating was busy too: challengers regularly beat the incumbent, some by 70–80%, and were promoted to become the new self-play model. Then the curve flattens and drifts back up to 2.7–2.85 for the rest of the run. After iteration 228 no challenger was ever promoted again, and the challenger's win rate against the best model sat at exactly 50%. The two models had become effectively identical.
Here's the Value Loss Data
The value head got worse, not better. Value loss dropped from 0.55 to around 0.1 in the first 50 iterations, so early on the network was learning to predict who would win. From iteration 200 it climbed steadily to nearly 1.0, the opposite of what a healthy run looks like. Once the best model froze, self-play kept producing games of the same quality. The value head was being asked to fit a noisy target that never improved, and its predictions drifted further from the real outcomes.
The diagnosis: Learning Rate
The learning rate schedule explains the timing. Cosine annealing took it from 1×10⁻³ to effectively zero by iteration 200, exactly where policy loss plateaued and value loss started rising. For the last 80% of the run the network could barely change its weights, so every new challenger was a near-copy of the last. A second issue made it worse. The replay buffer was sized for 100,000 games but the run never came close to filling it, so early near-random games stayed in the training data the whole time instead of being pushed out by stronger ones. Fixing either issue on its own would likely have kept the run improving for longer, and working this out from the metrics alone was one of the most useful parts of the project.
Gallery
A closer look at the system design and the full set of training metrics from the 1,000-iteration run.
What went wrong, and what I learned
The evaluation bottleneck
The evaluation service was supposed to answer both research questions: win rates against the baselines, and accuracy on the strategic probe positions at each checkpoint. It couldn't keep up, and it's the main reason the research question is still open.
Three design problems stacked on top of each other:
- Everything ran on one thread. Each checkpoint's games against every baseline ran one after another. That took around 50 minutes per checkpoint. With a checkpoint every 5 iterations, a full run would have needed roughly 167 hours of evaluation to match an 8.4-hour training run.
- Scaling out made it worse, not better. Replicas polled Cloud Storage for evaluation requests with no way to claim one. Every replica picked up the same request and did identical work. I tried adding replicas mid-run and had to abandon it.
- Elo ratings overwrote each other. Each replica read the ratings, updated them from its own games, and wrote them back. With several running at once, the last write won and the ratings stopped meaning anything.
The frustrating part is that I'd already solved this exact problem elsewhere. The self-play service claimed work atomically, ran games across multiple processes, and scaled cleanly across six pods. Evaluation is the same kind of workload, a pool of independent games, but I didn't carry the pattern over. I'd only ever tested it at local scale, where the bottleneck never showed up.
What the loss curves can still tell us
Without probe results, I can only infer what the agent learned, and I want to be careful not to overclaim. The early drop in policy loss suggests it learned basic tactics like taking free boxes, and possibly the beginnings of the double-cross, which is a local pattern that shows up often in self-play. The rising value loss is evidence against deeper understanding: an agent that had grasped parity or loop control should get better at predicting who wins, not worse. So my best reading is tactical awareness yes, global strategy not yet, but that's a hypothesis, not a result.
Takeaways
- Test at production load before you depend on it. Every serious bug here was invisible at local scale.
- Apply proven patterns consistently. The fix for evaluation already existed in my own codebase.
- Size configuration to reality, not hope. Buffer size and learning rate schedule should follow the throughput you actually get.
- The constraint was design, not money. The run used about a fifth of the budget. More compute wouldn't have fixed any of this.
- Honest negative results are still results. Pinning down exactly why a system failed to converge is useful for anyone building something similar.
Closing Thoughts
I set out to ask whether an AI could teach itself the strategies humans spent decades discovering. I haven't answered that yet, and I've made peace with that. What I did build is a complete, distributed AlphaZero-style training system, from game engine to Kubernetes cluster, that ran end to end for 8.4 hours on less than $50 of cloud compute.
The biggest lesson wasn't about reinforcement learning. It was about engineering discipline. Every serious problem in this project was invisible on my laptop and obvious at scale, and the fix for the worst of them already existed in my own codebase. I'd solved distributed game execution properly once, in self-play, and then didn't apply it a second time. That's a mistake I won't make again, and it's changed how I approach testing and design reviews.
I'm also proud of how I handled the result. It would have been easy to dress up the loss curves as evidence the agent learned the double-cross. Instead I traced exactly why training stalled, separated what the data shows from what I can only infer, and left a clear path to the answer: rebuild evaluation to mirror self-play, shrink the replay buffer, and soften the learning rate schedule. A second run fits comfortably in the remaining budget.
So the question is still open, but it's no longer hard. It's just next.