Chinese Checkers is a race across a six-pointed star. Move your marbles from one point to the opposite point. No captures, no material, just movement and blocking.

Chinese Checkers board
Photo by Wesley Fryer, CC BY 2.0, via Wikimedia Commons. Edited.

Nathan Sturtevant’s 2019 result is the two-player anchor. He strongly solved Chinese Checkers up to a 6×6 board with six pieces a side, covering 2,313,100,389,600 positions at the largest completed size. Every size he solved is a first-player win, and his stated open target is 7×7 with six pieces.

Three players change the object being solved. A player who can no longer win may still choose which opponent does. That player is a kingmaker.

I solved the two smallest three-player boards as a ladder: one marble each (1,245 reachable positions) and three marbles each (14,841,300,390 placement×turn states). A strong solution here means an exact tablebase over the full rule model, not a search from the opening.

From both openings, no player can force their own win, any two can force the third to lose, and every player can hand the win to either opponent. Draws first appear at three marbles, the same threshold Sturtevant found for two players, but no lone player can force one from the symmetric start.

You can explore the tablebase, read the solver and reproducibility package, or download the compressed tablebase artifacts.

The game

Three players sit at alternating points and race to the opposite point. The board is a central hexagon plus six triangular points. The one-marble version has 13 cells and shows the layout cleanly:

One-marble board layout

Colored disks are marbles; tinted outlined cells are goals. A starts at the top-right point and races to the red goal at lower left; B and C run their own diagonals across the same board. The three-marble board scales each point to three cells (37 in all) and gives each player three marbles.

A marble steps to an adjacent empty cell, or hops over any adjacent marble (yours or an opponent’s) into the empty cell beyond, chaining hops to cross the board in one turn. Nothing is captured. You win by filling your goal point.

That chained-hop rule is easy to underestimate. In the one-marble board below, C’s ordinary step creates a bridge. A can then hop over C and B into the goal in one turn.

Chained hop sequence

Why “who wins?” breaks with three players

Two players make a zero-sum game: every position is a win, a loss, or a draw, and “solved” is a single value. Three players break that. If A can no longer win, every move is equally bad for A’s own score. But the move can still choose whether B or C wins.

The object to compute is the control structure: which player, alone or with a partner, can force which result. I compute ordinary two-player forcing tables over the same graph:

  • Solo: can a player force their own win against the other two combined?
  • Enable: can players i and j together force j to win?
  • Pair-out: can two players force the third to lose?
  • Spoiler-draw: can a player force repetition rather than lose?

Kingmaker is derived from those tables. Player i is a kingmaker for player j when i can enable j’s win and j cannot force that win alone. The forcing questions are standard; the new part is reading an exact tablebase of a real three-player game this way.

How the algorithm changes

The retrograde primitive is still the classical one. In a two-player game, every position is one scalar: win, loss, or draw for the player to move. The backward rule is simple:

# Two-player retrograde, schematically.
if any(child is LOSS for child in moves(position)):
    position = WIN
elif all(child is WIN for child in moves(position)):
    position = LOSS
else:
    position = DRAW

With three players, “opponent win” is no longer one outcome. If A has lost, A may not care whether B or C wins, but the tablebase must. That choice is the kingmaker.

So I do not compute one three-player value. I compute a battery of two-player forcing questions over the same graph:

def can_force(position, max_side, objective):
    if terminal(position):
        return objective_holds(position)

    if position.turn in max_side:
        return any(can_force(child, max_side, objective)
                   for child in moves(position))
    else:
        return all(can_force(child, max_side, objective)
                   for child in moves(position))

The real solver implements that rule as loopy retrograde, not recursion: start from terminal states, walk backward through predecessors, mark a MAX state as won when any child is won, mark it as lost when every child is lost, and leave the unresolved states as draws.

can_force(s, {A}, "A wins") asks whether A can win against B and C. can_force(s, {A, B}, "B wins") asks whether A can help B win. can_force(s, {A, B}, "C loses") asks whether A and B can shut C out.

The draw question comes from the same solve. If A cannot force a win and the opposing coalition cannot force A into a terminal loss, the state is a draw for A under the repeated-state draw rule used by Sturtevant and adopted here.

A position’s solved value is the overlap of those answers:

entry = {
    "solo":   {A: A_can_force_A_win,
               B: B_can_force_B_win,
               C: C_can_force_C_win},
    "enable": {A_to_B: AB_can_force_B_win,
               A_to_C: AC_can_force_C_win,
               B_to_A: AB_can_force_A_win,
               B_to_C: BC_can_force_C_win,
               C_to_A: AC_can_force_A_win,
               C_to_B: BC_can_force_B_win},
    "pairout": {A: BC_can_force_A_out,
                 B: AC_can_force_B_out,
                 C: AB_can_force_C_out},
    "draw":   {A: A_can_force_draw,
               B: B_can_force_draw,
               C: C_can_force_draw},
}

That is the algorithmic difference. Two-player retrograde computes one value table. Three-player Chinese Checkers computes several ordinary retrograde tables, then reads their overlaps as control: solo wins, enabled wins, pair control, kingmakers, and spoiler draws.

Rung 1: one marble

The one-marble game has 1,245 reachable positions. One marble cannot wall off a goal, so there are no draws. Its job is calibration: small enough to solve two independent ways and check by hand.

Every reachable position sorts into one of four kinds:

Control type Positions
Terminal (someone has won) 171
Solo-win (a player forces their own win) 834
Kingmaker (a loser decides the winner) 240
Spoiler-draw 0
Total reachable 1,245

A fifth of the reachable board is already kingmaker territory. Here is one of those 240 positions, plus two legal choices from it:

Toy kingmaker position

B is to move and cannot win. One move hands A a forced win; another hands C a forced win. B has lost and still decides the game.

The solo forcing layer resolves by retrograde round 9. The ordered kingmaker questions run longer, to rounds 13 and 15, because they ask for a more specific result: not just “can this player win,” but “can this player help that other player win.” The opening verdict matches the three-marble game: no solo win, every pair can shut out the third, all six ordered kingmaker relations live.

Rung 2: three marbles

Three-marble opening

Result and scale

Three marbles each, 37 cells, 14,841,300,390 positions, counting placement and whose-turn. That count enumerates every placement the corner lanes allow, not just positions reachable from the start; the game is reversible enough that the two nearly coincide, and the solver labels all of them. This is the first exact strong solution of a three-player Chinese Checkers board I could find. That claim is intentionally scoped: the nearest prior work I found is analytic (three-player Nim), approximate and stochastic (multiplayer Can’t Stop), or a feasibility study of three-player Otrio.

Quantity Value
Positions 14,841,300,390
Solo win / loss / draw (per player) 950,015,894 / 13,890,307,418 / 956,384

The “per player” row is the same for A, B, and C by threefold rotation symmetry. Read it from one player’s perspective: in 6.4% of positions, that player can force their own win against the other two combined. In 93.6%, the other two can shut them out. A draw is rare but real. The rows do not quite sum to the position count: 20,694 enumerated placements have two goal points filled at once, which no legal game produces, and the solver marks them illegal rather than win, loss, or draw.

Compared with rung 1, three marbles change the scale but not the opening’s control structure:

  • Unchanged: the symmetric start is pure kingmaker on both rungs: no solo win, any two force the third out, all six kingmaker relations live.
  • New: draws. A lone player can force a perpetual block, impossible with one marble.
  • Deeper: the one-marble solo layer resolves in 9 rounds; the three-marble solo layer runs 53, with resolution peaking in rounds 10 to 13 instead of one ply from a terminal.

The opening stays kingmaker

The three-marble opening evaluates exactly like the one-marble opening. No player can force their own win. Any two players can force the third out. No lone player can force a draw. All six ordered kingmaker relations are live: A can hand the win to B or C, B can hand it to A or C, and C can hand it to A or B.

That balance persists for a while. A breadth-first search from the start finds that every reachable position through depth 8 is still in the kingmaker class. At depth 9, the first non-kingmaker positions appear: among 1,906,964 newly reached positions, 41 are solo-win and 1 is spoiler-draw. The other 1,906,922 remain kingmaker.

The widget below shows the two shortest witnesses. Don’t read them as good opening play. They are just the first reachable positions where the tablebase label changes.

Both lines start the same. The early B move differs, and nine plies later the labels split:

  • First solo-win for A: the position has become one where A can force their own win.
  • First spoiler-draw by A: the position has become one where A still cannot win, but can force repetition.

This is a reachability fact, not a claim about optimal opening play. It says the tablebase does not encounter a solo-win or spoiler-draw label until depth 9 from the symmetric start.

Draws and kingmakers

The one-marble board had zero drawn positions. The three-marble board has 956,384 solo-draw positions per player and 2,869,152 spoiler-draw positions overall, where one player can force repetition rather than lose. Sturtevant found the same threshold for two players.

Sorting all 14.8 billion positions by what their control structure says:

Control type Positions Share
Kingmaker (no one forces a win; someone picks) 11,988,362,862 80.8%
Solo-win (a player forces their own win) 2,814,699,759 19.0%
Terminal (someone has won) 35,368,617 0.24%
Spoiler-draw (a lone player forces a draw) 2,869,152 0.019%
Other 0 0%

The last row matters: the forcing questions classify the whole game, with no undecidable residue. Kingmaker territory dominates. In four of every five positions, the solved value is a question of who decides rather than who wins.

Two tablebase examples

The next two widgets are not meant to be puzzles. The board is there so the tablebase result has a concrete position attached to it. The status text and tabs are the important part.

A spoiler-draw, the kind that exists only at three marbles:

C is to move, but the label is about A’s defensive power. A has no forced win, and the other two players cannot force A into a terminal loss if A keeps the blocking cycle available. This is the option the symmetric opening never offers: a lone player with no win of their own, holding the draw.

Use this as a move-filter example. Under the A-vs-rest tablebase question, C has exactly one move that keeps A in the draw region. Most other C moves let A do better and force a solo win. After C’s draw-preserving move, A has a reply that keeps the blocking cycle available. The cycle tab gives the audit trail: after six more plies, the same board and same player to move return.

A decisive kingmaker:

A is to move and cannot win. There is no draw trick here. One tab gives C a forced win; the other gives B a forced win. A has lost, but A still chooses the winner.

This tablebase separates capability from behavior. It says what can be forced without assuming how indifferent players break ties. A separate policy pass could sit on top of the same state graph: normal self-interest, draw-preferring spoilers, or cyclic preferences like A wants B, B wants C, and C wants A. Those passes would collapse many kingmaker positions to a specific winner, but the answer would be preference-dependent rather than part of the strong solution.

Another extension changes the objective itself. This solve stops when the first player fills their goal. If players care about finishing second, the game needs a ranking objective, or a rule that continues after the first winner. That would measure a different thing: not just who can win, but how second-place incentives change blocking and kingmaking.

Rung 3: six marbles

The natural next rung is six marbles each, but the board convention matters. Sturtevant’s largest completed result is the two-player 6×6 / 6-piece gameplay rhombus. His stated open goal is 7×7 / 6-piece. For three players, the comparable six-piece target is the symmetric star geometry behind that 7×7 gameplay area: 73 cells, three players, six marbles each.

Six-marble target board

Reference Players Pieces Board model Status
Sturtevant 6×6 2 6 even gameplay rhombus solved
Sturtevant 7×7 2 6 odd, star-compatible gameplay area open
This rung 3 6 73-cell three-player star open

For that three-player star board, the setup is exact:

Quantity Value
Board 73 cells
Pieces 6 per player

The lane-restricted upper bound is computed exactly, then rounded here for display:

Quantity Rounded value
Lane-restricted placement×turn states ≈1.30×10²¹
C3-canonical states ≈4.33×10²⁰
Increase over rung 2 ≈87.6 billion×

The bounds come from the same lane-restricted enumerator used for rung 2, not a raw “marbles anywhere” count: each player’s six marbles are confined to that player’s two private corners plus the shared 37-cell center, and the count sums over how many marbles each player places in the shared center. The exact threefold rotational symmetry then divides placement×turn states by 3. Reachability will not save the problem by orders of magnitude. Chinese Checkers is capture-free and reversible, and on the smaller boards the reachable fraction quickly approaches the full lane-restricted space.

A naive scale-up of the current solve is out of reach. The rung-2 final tablebase is 14.84 GB; the same representation at six marbles would be about 1.3 zettabytes. The rung-2 compute run took 7.4 hours; multiplying only by canonical state count gives tens of millions of machine-years before accounting for larger branching, memory traffic, checkpointing, and I/O.

Six marbles is future work that starts with a new scoping phase, not a longer run: stronger compression, external-memory or distributed retrograde, reachability-aware indexing, better cost modeling, and likely funding or donated compute. The engineering question becomes as interesting as the game-theory question.

How the solver ran

The solve is a Rust retrograde over 14.8 billion positions. It ranks positions into dense array slots, generates moves on demand, solves four representative forcing layers, derives the other eight by rotation, and packs the result into a local tablebase. Four engineering choices mattered.

Indexing

A flat array of 14.8 billion values only works if a board can become its array slot and back with arithmetic. Each arrangement maps to a dense rank, and moves are generated on the fly: no hash map, no pointers, just index arithmetic into a slab of memory.

Wavefront

The counter-method floods outward from terminals across all 32 cores. Each position carries two atomic bytes: its value, and a count of unresolved moves. A move into a win resolves immediately. A move into a loss decrements the counter. A counter reaching zero means every move was bad. Reverse moves come for free because the game is capture-free and reversible.

Symmetry

The control structure is twelve forcing questions: each player’s solo, each ordered pair’s enable, each player’s pair-out. Spoiler-draw labels are the draw outcome of the solo layers. The board’s threefold rotational symmetry folds the twelve forcing questions to four representatives; the other eight follow by relabeling. I spent that fold on the question battery rather than the index: the solver keeps the full 14.8-billion-position array per layer and computes four layers instead of twelve, the same factor of three the canonical state count would give. Reflections are not valid symmetries because they reverse the fixed turn order A→B→C into A→C→B.

I caught that before the run by testing both folds on the one-marble board: sixfold symmetry, rotations plus reflections, broke the solved values; threefold rotation alone preserved them.

The compute run

Each forcing layer’s atomic arrays run about 30 GB while solving; a finished layer drops its counter and keeps the one-byte value array, so the four layers held together at the end take about 60 GB. The work is scattered atomic writes, so the right machine is a big CPU box, not a GPU. I rented a Hetzner CCX53: 32 vCPU, 128 GB RAM, enough memory headroom to keep the wavefront arrays resident instead of paging.

The run also needed operational plumbing: checkpoint each representative layer, resume cleanly if SSH died, and stream per-round progress so I could tell it was advancing rather than burning rented time. I built it locally, shipped the code to the box, ran it under tmux, watched memory with htop, and tore the machine down after copying back the packed tablebase. The final run finished in about 7.4 hours and cost a few euros; the final tablebase packs to 14.84 GB.

Validation

I trust the result because it passed the small checks before the large run and the large tablebase checks after it.

First, the counting model reproduces Sturtevant’s Table 1 positions column exactly, all eight rows, using 2*C(m²,k)*C(m²-k,k). That was the gate for understanding the two-player reference before trusting my star-board counts.

Second, the one-marble three-player game is small enough to solve exhaustively several ways. Two independent Python retrogrades and the Rust solver agree on every state. That comparison caught a real bug: the first Python move generator allowed a hop chain to return to its origin, which is a disguised pass. After forbidding it, the solvers agree on 335 wins, 910 losses, and 0 draws per player, with 240 reachable kingmaker positions.

Third, the symmetry fold is tested directly. Threefold rotation preserves the solved values; reflection does not, because it reverses the fixed A→B→C turn order. The n=2 ranker also round-trips positions and gives the expected 4,947,100,130 canonical placements.

Finally, the packed tablebase is read back for analysis. The control-type buckets sum exactly to 14,841,300,390 states, the per-player draw count matches the spoiler-draw bucket by symmetry, and the opening/depth-9 witnesses above come from tablebase queries rather than hand labels. The full 14.84 GB raw tablebase is served by the live explorer and published as a compressed release asset; the public repo contains the solver, validation harnesses, static witnesses, and explorer code.

Conclusion

Add a third player and “who wins” stops being a property of the position. A player who has lost can still decide the winner. What you can compute is the distribution of power: who can force their own win, who needs a partner, who is left choosing someone else’s victory.

The two solved openings agree despite being seven orders of magnitude apart. Draws enter at three marbles, but never from the symmetric start.

With three players, a solved game tells you who decides, not just who wins.

Resources: