Solving Gobblet Gobblers
Gobblet Gobblers is a tic-tac-toe variant with a stacking mechanic, sold as a children’s game (ages 5+). I solved it exhaustively and built a web explorer for optimal play. Player 1 wins in 13 plies.
The solve is a retrograde analysis over every position reachable from the start, 531,557,711 of them. The output is a tablebase giving the exact outcome and distance-to-result for any position you can legally reach.
| Finding | Result |
|---|---|
| Result | Player 1 wins |
| Win distance from the start | 13 plies |
| Canonical reachable positions | 531,557,711 |
| Drawn positions | 208,563 (0.04%) |
| Deepest forced win | 23 plies |
Source: github.com/brianhliou/gobblet-gobblers
Each legal move is colored by its true outcome: green wins, red loses.
The game
A 3×3 board, two players. Each player has six pieces (two small, two medium, two large) and starts with all six in reserve. You win by showing three of your color in a line: any row, column, or diagonal.
Your turn
Each turn you do one of two things:
- Place a piece from your reserve onto the board, or
- Move one of your pieces already on the board to another square.
Either way the piece lands on an empty square or gobbles a strictly smaller one (yours or your opponent’s) by covering it. Only the top of a stack is visible: only the top piece counts toward a line, and only the top piece can be picked up and moved.
The reveal rule
Moving a piece off its square uncovers whatever sat under it, and that happens before your piece lands somewhere else. You can’t expose a finished line of your opponent’s color and leave it standing: if lifting a piece would reveal your opponent’s three-in-a-row, that piece has to come back down on one of those three squares and cover it. If it can’t reach any of them, the lift is illegal.
This is where the sharpest tactics come from. A piece can be pinned: it’s the only thing covering an opponent’s line, so it can’t move. A stack carries a history that constrains play many moves later. When the side to move has no legal move at all, it loses; when neither side can make progress, the game draws by repetition.
What you can’t see
The physical game hides covered pieces: you may not look under a gobbled piece, so you have to remember what’s there, and real play is partly a memory game. The solve assumes perfect information: both sides know every covered piece. The explorer shows the full stacks for the same reason, so you can see the exact position the tablebase evaluates.
Retrograde analysis
The repetition rule rules out the obvious approach. Forward minimax with a position → outcome cache assumes each position has a single value, but under threefold repetition a position’s value depends on the path that reached it: the same board is a draw where it’s the third occurrence and live where it’s the first. Caching one value per position is unsound. (This is the Graph History Interaction problem.)
Retrograde analysis solves the whole graph backward, with no path involved. Two phases:
- Enumerate every canonical position reachable from the start with a breadth-first sweep, keyed by position. Transpositions collapse to one node.
- Fill values by backward induction to a fixpoint. Seed the terminal positions, then repeat until nothing changes.
// one round over the still-unknown positions
for &pos in &unknown {
let mut win = false; // a move reaches a loss for the opponent
let mut all_children_decided_win = true;
for child in moves(pos) {
match value[child] {
Loss => { win = true; break; }
Unknown => all_children_decided_win = false,
Win => {}
}
}
if win { set(pos, Win) }
else if all_children_decided_win { set(pos, Loss) }
// else leave Unknown: it resolves in a later round, or it's a draw
}
Draws need no special handling. They’re the positions the fixpoint never resolves, stuck in cycles where neither side can force a result. No repetition counter appears anywhere in the solve. A position is drawn exactly when best play can avoid losing only by repeating forever, which is what the unresolved set is. This is the same method behind endgame tablebases for chess and checkers.
Results
531,557,711 canonical positions are reachable from the start, and the starting position is a win for Player 1 in 13 plies. Among the 370,974,636 non-terminal positions the outcome splits almost evenly: 185,455,752 are won for Player 1, 185,310,321 for Player 2, and just 208,563 are drawn (0.04%). Every reachable position is a forced win for one side or a draw; nothing is left undecided.
Notable findings
Most wins end at once, with a thin tail to 23 plies. In 83% of all positions the side to move already has a move that wins on the spot. Past that, won positions thin out fast as the distance grows, and they land on odd plies almost without exception. The tail narrows to a single forced win in 23 plies, the deepest in the game, reached by just 9 positions.
That deepest win is as sharp as it gets. From this position, Player 1 has 26 legal moves and exactly one holds the win (sliding the medium off the center stack) while the other 25 lose, and the win is still 23 plies away.
The opening is all-or-nothing by size, and not monotonically. Of the 27 first moves, every small and every large placement wins, but every medium placement loses: it hands Player 2 a forced win. A medium is the largest piece the opponent can still gobble. Answer it with your large, the only winning reply from the center, and you take its square with a piece that can never be uncovered, the medium buried beneath. A large can’t be gobbled at all; a small isn’t worth a bigger piece to cover. Only the middle size invites the capture.
Often only one move wins. In 12.7% of won positions a single move preserves the win and every other move throws it. The deepest win above is the extreme case, one saving move among 26.
Nearly a quarter of positions have a pinned piece. In 22.8% of positions, lifting some piece would expose the opponent’s three-in-a-row, so the reveal rule pins it in place.
Draws are an endgame thing. The 208,563 draws cluster late: 91% have at least 8 of the 12 pieces on the board, most often 10. They’re positions where both sides can shuffle without forcing a result.
Implementation
The full state fits in a u64: nine cells at six bits each (small, medium, large owner, two bits apiece) plus a turn bit. Moves are one byte, undo is two, and win detection is eight precomputed bitmasks.
Solving means holding all 370,974,636 non-terminal positions in memory at once. The position-to-id map is a custom open-addressing table to skip the per-entry pointer overhead a hash map would carry (about 6 GB at 0.74 load). The fixpoint runs in parallel across cores: each round reads the previous round’s values and writes the next, so every position resolves at its true distance and the win distances come out minimal. The whole solve takes about 30 minutes on a 14-core laptop, peaking under 12 GB.
Serving it is the second problem. The table won’t fit in a serverless function, so a minimal perfect hash maps the 370,974,636 canonical keys onto a dense range with no collisions and no stored keys (about 3.5 bits each), plus one byte of distance-to-result per position, totaling 531 MB held in RAM by a small Rust service.
Browser (game logic in WebAssembly)
│ POST /lookup/batch [canonical keys]
▼
Tablebase service (MPH in RAM)
│ outcome + distance per position
▼
Browser colors each move
The browser runs the game logic in WebAssembly and calls the service only for evaluations. Terminal positions it detects itself, so they never reach the tablebase.
What makes it deep
The reveal rule looks like the source of the depth: a piece pinned as the only cover over an opponent’s line, a lift that loses on the spot. But it isn’t. Re-solve with the rule removed, every lift allowed, and almost nothing changes: the same 370,974,636 positions, the same opening win in 13, the deepest win barely up from 23 plies to 25. The rule shapes a fifth of all move lists but rarely the verdict, because good play already avoids exposing a line.
The stacking is the source, and dropping it proves the point. Re-solve with covering disabled, every piece confined to an empty square, and the game collapses: 1,433,602 positions instead of 370,974,636, the deepest win down to 10 plies, not one draw. The reason is that nothing is ever captured. A gobble covers a piece; it doesn’t remove it. Material never thins the way captures simplify a chessboard toward its endgame, so a 3×3 grid never settles. Dōbutsu shōgi gets its depth from the same place by a different route: captured pieces come back as drops, so its material never drains either.
Player 1 wins in 13 plies. The explorer at gobblet.brianhliou.com plays from the tablebase, coloring every legal move by its true outcome and labeling it with the distance to the result. The solver is on GitHub.