Hexxagon: a greedy player checked against every reply¶

Hexxagon is the old hexagon game where you grow your pieces across a board and every piece you land next to changes to your colour. A player that simply grabs the most pieces each turn plays it badly in one specific, repeatable way: it jumps a piece out of a solid wall to convert two more, and leaves a hole the opponent clones into, taking back the whole neighbourhood. This page shows the library's grounded pattern (propose, check, then act or degrade) stopping exactly that mistake with checks that account for every possible reply, and states just as exactly what those checks do not stop.

This page is for anyone who wants to watch act-or-degrade on a quick, visual game, and for engineers who want a template for a gate whose checks are a short exhaustive look-ahead rather than a deep search. No knowledge of the game is assumed; the next section explains it.

Try it in your browser

The board below plays this game's recorded example with no download; Play live runs this package itself in your browser, in Pyodide (about 7 MB, downloaded once), and the play page has every setting.

Hexxagon runs here when JavaScript is on; the play page has it too, and the commands below run it in a terminal.

Run it¶

uv run grounded-decision examples games_hexxagon                 # the report below
uv run grounded-decision play hexxagon                           # watch gated vs search, live
uv run grounded-decision play hexxagon --start ring              # the ring trap: six pieces infected on move 1
uv run grounded-decision play hexxagon --agents you,gated        # play Ruby yourself
uv run grounded-decision play hexxagon --agents you,search --guarded   # the gate checks your moves

The same through make: make play-hexxagon, make watch-hexxagon, make history-hexxagon, make audit-hexxagon.

Source: src/grounded_decision/examples/games/hexxagon_rules.py (the rules, the bitboards, the drawing) and hexxagon.py (the players, the gate, the exact solver, the report). Tests: tests/test_games_hexxagon.py.

The game in four paragraphs¶

Two players, Ruby (moves first) and Pearl, play on a hexagon of hexagonal cells. The standard board, as in the 1992 original, has five cells along each edge (61 cells) with three cells near the centre removed, leaving 58. Each player starts with three pieces on alternate corners:

a     P . . . R
b    . . . . . .
c   . . . . . . .
d  . . . # . . . .
e R . . . . # . . P
f  . . . # . . . .
g   . . . . . . .
h    . . . . . .
i     P . . . R

R is Ruby, P Pearl, # a removed cell (a hole). Cells are named by row letter and place in the row, so the centre is e5 and the holes are d4, e6 and f4. That is the compact text the report and --view json print. On screen the board is drawn flat-topped, as in the original: the same board turned a quarter turn, so each row above becomes a column (a on the left) whose cells count up from the bottom. Pearl starts at the top, bottom left and bottom right, Ruby at the top left, top right and bottom; the holes sit directly above the centre and to its lower left and lower right. With --coords (on when you play) every empty cell shows its number and the columns their letters:

   a   b   c   d   e   f   g   h   i
 ┌────────────────────────────────────┐
 │                ╭▲╮                 │
 │            ╭8╮ ╰─╯ ╭8╮             │
 │        ╭7╮ ╰─╯ ╭8╮ ╰─╯ ╭7╮         │
 │    ╭6╮ ╰─╯ ╭7╮ ╰─╯ ╭7╮ ╰─╯ ╭6╮     │
 │╭●╮ ╰─╯ ╭6╮ ╰─╯ ╭7╮ ╰─╯ ╭6╮ ╰─╯ ╭●╮ │
 │╰─╯ ╭5╮ ╰─╯ ╭6╮ ╰─╯ ╭6╮ ╰─╯ ╭5╮ ╰─╯ │
 │╭4╮ ╰─╯ ╭5╮ ╰─╯ ███ ╰─╯ ╭5╮ ╰─╯ ╭4╮ │
 │╰─╯ ╭4╮ ╰─╯ ╭5╮ ███ ╭5╮ ╰─╯ ╭4╮ ╰─╯ │
 │╭3╮ ╰─╯ ╭4╮ ╰─╯ ╭5╮ ╰─╯ ╭4╮ ╰─╯ ╭3╮ │
 │╰─╯ ╭3╮ ╰─╯ ███ ╰─╯ ███ ╰─╯ ╭3╮ ╰─╯ │
 │╭2╮ ╰─╯ ╭3╮ ███ ╭4╮ ███ ╭3╮ ╰─╯ ╭2╮ │
 │╰─╯ ╭2╮ ╰─╯ ╭3╮ ╰─╯ ╭3╮ ╰─╯ ╭2╮ ╰─╯ │
 │╭▲╮ ╰─╯ ╭2╮ ╰─╯ ╭3╮ ╰─╯ ╭2╮ ╰─╯ ╭▲╮ │
 │╰─╯ ╭1╮ ╰─╯ ╭2╮ ╰─╯ ╭2╮ ╰─╯ ╭1╮ ╰─╯ │
 │    ╰─╯ ╭1╮ ╰─╯ ╭2╮ ╰─╯ ╭1╮ ╰─╯     │
 │        ╰─╯ ╭1╮ ╰─╯ ╭1╮ ╰─╯         │
 │            ╰─╯ ╭●╮ ╰─╯             │
 │                ╰─╯                 │
 └────────────────────────────────────┘

(This is the frame without colour, where Ruby is ● and Pearl ▲; with colour both are discs in their own colour.) --layout pointy draws the rows instead; the cell names are the same in both.

On your turn you pick one of your pieces and an empty cell one or two cells away. One cell away is a clone: a new piece appears and the old one stays. Two cells away is a jump: the piece moves and its old cell empties. Then every opponent piece next to the cell you landed on turns into yours. There are no other captures.

The game ends when one side has no pieces, when the board is full, when the player to move has no legal move (the other player then takes every empty cell, as in the original), or after 100 moves in a row without a clone (jumps alone never fill the board, so without this a game could go on for ever; pieces are then counted). Whoever has more cells wins.

How to type a move¶

A clone is written as its target, e2: every clone into the same cell gives the same position, whichever of your neighbouring pieces it grew from. A jump is written as its origin and target, e1-e3 (e1 e3 works too). Or type just one of your pieces, e1: the board is drawn again with its clone targets in green and its jump targets in yellow (1 and 2 without colour), and you type the target. With --agents you,... the board shows coordinates and, before each of your moves, the five moves that keep the most margin after the opponent's best reply.

The players¶

The margin is your pieces minus your opponent's. A clone that converts \(k\) pieces raises it by \(1 + 2k\); a jump that converts \(k\) raises it by \(2k\).

Agent	What it does	Information regime
`random`	A uniformly random legal move.	none
`noisy_greedy`	Greedy, but a random move one time in five: an opponent model, not a player to imitate.	none
`greedy`	The move that raises the margin the most right now; it never looks at the reply.	none
`gated`	Greedy proposes; four exact checks decide; if one fails, the certified fallback plays.	worst-case
`expectimax`	The move with the best expected margin after the reply, if the opponent is `noisy_greedy`, computed exactly.	probabilistic
`search`	Alpha-beta search on the margin, deepening until a budget of 3,000 positions per move runs out.	worst-case
`clairvoyant`	Is shown the opponent's actual reply to each of its moves and plays best against it. A benchmark, never a real player.	clairvoyant

grounded-decision play hexxagon --explain AGENT prints a paragraph on each.

The checks, and what they prove¶

For a move \(m\), let \(V(m)\) be your margin after \(m\) and the opponent's best reply (the reply that leaves you the smallest margin). If either move ends the game, \(V\) is the final margin plus 10,000 for a win or minus 10,000 for a loss, so every win outranks every unfinished line. Let \(M_0\) be your margin now. The gate computes \(V\) for every legal move exactly, accounting for every legal reply: nothing is estimated (Exact and fast on large boards below says how it does that without playing out every reply).

Check	Passes when
`legal`	The proposal is a legal move.
`takes_forced_win`	If some move wins within two moves whatever the reply (\(V \ge 10{,}000\)), the proposal is one of them.
`no_losing_reply`	If some move leaves the opponent no reply that wins at once, the proposal is one of them.
`holds_exchange`	\(V(m) \ge M_0\): the best reply takes back no more than the proposal gained. If no move achieves that, the proposal must have the largest \(V\).

The fallback plays the move with the largest \(V\) (then the largest immediate gain, then a draw seeded by the position). Each check's "if no move…" clause names exactly the moves with the largest \(V\), so the fallback passes all four checks by construction.

What is proved. Every move the gated player makes is legal and:

wins within two moves whenever any move forces that;
never allows a reply that wins the game at once when some move avoids one;
never lets the opponent's best reply take back more than the move gained when some move avoids that, and otherwise loses the least possible over the two moves.

The tests check all three on hundreds of positions from random games on three board sizes, against a separate brute-force computation of \(V\) through the game's public interface.

What is not proved. Two moves are not the game. The gated player can still lose, and against search, which looks further ahead, it usually does (the table below). The guarantee is local and exact; strength is measured.

Exact and fast on large boards¶

Playing out every reply to every move costs (moves × replies) per decision. On a side-20 board (1,141 cells, up to about 700 moves a turn) a full gated-against-greedy game took 21 minutes, about one move a second. The gate now computes exactly the same numbers in time about linear in the moves, from two facts proved in the TwoPlyTable docstring of hexxagon.py:

Locality. A reply to an empty cell \(t\) is summed up by three numbers: how many of your pieces it converts (your pieces next to \(t\)), whether the opponent can clone there and how many of its pieces can jump there. A clone converting \(k\) gains \(2k + 1\), a jump \(2k\), so every reply value, the best reply and the greedy replies' values follow from counts over \(k = 0, \dots, 6\). A move changes only its target, the pieces it converts (next to the target) and a jump's origin, so it changes those numbers only for cells within distance 3 of its target or 2 of its origin. The gate counts the replies of the position once, then corrects at most 37 cells per target and 7 per jump origin.
When a reply can end the game. A piece of yours with an empty cell within distance 2 (a witness) means you have a piece, a move and a board that is not full, so the reply cannot end the game by the first three end rules. A reply kills a witness only by landing within distance 2 of it, and your move only by vacating its piece or filling its cell, so with witnesses more than 4 cells apart a move kills at most two and a reply at most one. When two survive the move, no reply ends the game (the 100-move rule is a plain count); when one survives, only replies to its seven nearby cells are played out; when none does, every reply is. The opponent's witnesses settle in the same way whether the move itself ends the game.

The tests compare the table with the full enumeration (and with a separate brute force through the game's public interface) on hundreds of positions of sides 3 to 8, every board variant and both layouts, including the last positions of games where replies wipe a player out, fill the board or leave a player stuck; replay recorded games and check every move, check and note is unchanged; and time the large board. On the machine these numbers come from, the side-20 game (play hexxagon --size 20x20 --agents gated,greedy --view none --seed 1, 1,475 moves, the same moves as before) takes about 4 seconds instead of 1,248, and gated against greedy on the standard board runs at about 6,000 moves a second instead of 1,250. The search agent produces its moves one gain level at a time instead of generating and sorting them all, visiting the same positions in the same order under the same node budget: the same side-20 game against greedy takes about 20 seconds instead of 74.

Here is the gate catching greedy's mistake on the second move of a game (uv run grounded-decision play hexxagon --agents greedy,gated --view history --style ascii --layout pointy --seed 0 --max-steps 2 --frame-every 2; the pointy layout keeps the plain text compact):

──────── after move 2 ────────
hexxagon  greedy vs gated [worst-case]  move 2/2
    P . . . R      move    2  ▲ Pearl (gated · worst-case): clone to e8
   . . . . . .       OVERRIDE  proposed clone to a2 -> played clone to e8
  . . . . . . .        why: wins 1, but the reply a5-a3 wins back 2; e8 is safer (piece lead -1)
 . . . # . . . .       ✓ legal                  a legal move
R R . . . # . p P      ✓ takes_forced_win       no move forces a win in two plies
 . . . # . . . .       ✓ no_losing_reply        no reply wins the game for Ruby
  . . . . . . .        ✗ holds_exchange         wins 1, but the reply a5-a3 wins back 2; e8 is safer (piece lead -1)
   . . . . . .         note: fallback: best margin after the best reply (-1)
    P . . . R

                       two_ply_margin=-1
                     moves    2 · acts    0 · overrides    1 · margin    0 · Ruby    4 · Pearl    4 · empty   50 · converted    0…
                     ● Ruby  ▊░░░░░░░░░ 4 pieces · 33 moves available  ▁▁
                     ▲ Pearl ▊░░░░░░░░░ 4 pieces · 32 moves available  ▁█
                     · 2. Pearl clones to e8
                     · 1. Ruby clones to e2

                     since the last frame: 2 moves, 1 overrides

Greedy wanted to clone next to Ruby's corner at a5. Ruby would jump a5-a3 and convert the new piece, so Pearl would end the exchange one piece worse than it started. The fallback's clone to e8 costs nothing. In the terminal the board is drawn with coloured pieces: the move's origin and target are highlighted (the target green for a clone, yellow for a jump, as in the original), a jump leaves a hollow ring where the piece was (a clone keeps its piece there), and the pieces a move converted flash in their new colour (lower case r/p in plain ASCII). The next section shows that flash.

What you see when a ring is infected¶

The famous Hexxagon move: six of your opponent's pieces surround an empty cell, you jump into the middle, and all six turn. Strong players rarely leave such a ring, so in self-play it is rare (about 17 times in 4,400 moves). --start ring sets it up on move 1: Pearl's six round c5, and a Ruby piece on a3, one jump away (uv run grounded-decision play hexxagon --start ring --view history --style unicode --color never --seed 0 --max-steps 2):

┌────────────────────────────────────┐  move    1  ● Ruby (gated · worst-case): jump a3-c5, converts 6
│                ╭▲╮                 │    ACT  the proposal passed the 4 checks that ran
│            ╭─╮ ╰─╯ ╭─╮             │
│        ╭─╮ ╰─╯ ╭─╮ ╰─╯ ╭─╮         │      ✓ legal                  a legal move
│    ╭─╮ ╰─╯ ╭─╮ ╰─╯ ╭─╮ ╰─╯ ╭─╮     │      ✓ takes_forced_win       no move forces a win in two plies
│╭●╮ ╰─╯ ╔◉╗ ╰─╯ ╭─╮ ╰─╯ ╭─╮ ╰─╯ ╭●╮ │      ✓ no_losing_reply        no reply wins the game for Pearl
│╰─╯ ╔◉╗ ╚═╝ ╔◉╗ ╰─╯ ╭─╮ ╰─╯ ╭─╮ ╰─╯ │      ✓ holds_exchange         wins 12; the best reply wins back 4 (piece lead +3…
│╭─╮ ╚═╝ ┏●┓ ╚═╝ ███ ╰─╯ ╭─╮ ╰─╯ ╭─╮ │      note: greedy: gains 12 now (2 tied)
│╰─╯ ╔◉╗ ┗╍┛ ╔◉╗ ███ ╭─╮ ╰─╯ ╭─╮ ╰─╯ │
│┌∘┐ ╚═╝ ╔◉╗ ╚═╝ ╭─╮ ╰─╯ ╭─╮ ╰─╯ ╭─╮ │
│└┄┘ ╭─╮ ╚═╝ ███ ╰─╯ ███ ╰─╯ ╭─╮ ╰─╯ │      gain=12
│╭─╮ ╰─╯ ╭─╮ ███ ╭─╮ ███ ╭─╮ ╰─╯ ╭─╮ │    moves    1 · acts    1 · overrides    0 · margin    7 · Ruby   10 ·…
│╰─╯ ╭─╮ ╰─╯ ╭─╮ ╰─╯ ╭─╮ ╰─╯ ╭─╮ ╰─╯ │    ● Ruby  █▊░░░░░░░░ 10 pieces · 72 moves available
│╭▲╮ ╰─╯ ╭─╮ ╰─╯ ╭─╮ ╰─╯ ╭─╮ ╰─╯ ╭▲╮ │    ▲ Pearl ▌░░░░░░░░░ 3 pieces · 24 moves available
│╰─╯ ╭─╮ ╰─╯ ╭─╮ ╰─╯ ╭─╮ ╰─╯ ╭─╮ ╰─╯ │    ✦ 1. Ruby jumps a3→c5 · infects 6: b4 b5 c4 c6 d5 d6
│    ╰─╯ ╭─╮ ╰─╯ ╭─╮ ╰─╯ ╭─╮ ╰─╯     │
│        ╰─╯ ╭─╮ ╰─╯ ╭─╮ ╰─╯         │
│            ╰─╯ ╭●╮ ╰─╯             │
│                ╰─╯                 │
└────────────────────────────────────┘

The six converted pieces are drawn double-outlined with a marked glyph (╔◉╗): with colour, each is a solid block of its new owner's colour, brightened, with a dark ◉. In blocks and braille they show the new colour brightened; in plain ASCII they are #r#.
The landing cell is outlined heavy (┏●┓), with a dashed lower edge for a jump (yellow with colour; a clone's target is solid, green).
The rest of the ring and the cell the jump left are outlined lightly (┌∘┐).
The panel keeps an event line for the last three moves, big ones bold: ✦ 1. Ruby jumps a3→c5 · infects 6: b4 b5 c4 c6 d5 d6.

In the live view (play hexxagon, which waits 0.6 s per move) the move is also animated: the piece lands with its ring outlined, the six pieces flash amber in their old colour, then flip to the new one. The animation uses the time the view waits anyway, so it costs nothing; with --delay 0, --fps max or --view none there is none, and matches run exactly as fast as before. The history view shows the final picture of each move only.

On a terminal, --zoom auto (the default) draws each cell as big as the board fits: on a 100 × 40 terminal the standard board takes 38 columns by 20 rows, with the panel beside it. --zoom 2 or 3 makes the cells bigger still.

Measured: who beats whom¶

Every pair, from both seats, four seeds each, on the standard board (uv run grounded-decision compare hexxagon --agents random,greedy,gated,expectimax,search --seeds 4). The start position is the same for every seed, so compare plays the first two moves of each game at random, drawn by the seed and the same for every seating (the openings are printed under the table); without them the deterministic players would replay one game per pairing.

  agent                    games  won drawn lost  cut  points    moves    score overrides  win rate (95% interval)
  search                      32   29     2    1    0    30.0     70.1     41.2         0  0.91 [0.75, 0.98]
  gated                       32   19     3   10    0    20.5     68.3     36.9       446  0.59 [0.41, 0.76]
  expectimax                  32   19     3   10    0    20.5     69.1     37.3         0  0.59 [0.41, 0.76]
  greedy                      32    9     0   23    0     9.0     65.3     29.5         0  0.28 [0.14, 0.47]
  random                      32    0     0   32    0     0.0     13.4      0.0         0  0.00 [0.00, 0.11]

The gate turns greedy (9 of 32 games won) into a player that wins 19, by overriding 446 proposals in 32 games, about two moves in five; each override is a proposal that failed one of the exact checks above. expectimax, which looks exactly as far ahead but bets on a model of the reply instead of the worst one, does as well here; search, which looks several moves ahead, wins 29 of 32. The intervals are exact (Clopper–Pearson) and wide: these are 32 games per row, not a rating.

The exact solution of a tiny board¶

On the side-2 board (seven cells) the whole game can be solved. The solver is a memoised search over (Ruby's pieces, Pearl's pieces, moves since the last clone); the 100-move rule makes that graph finite and loop-free. From the report (uv run grounded-decision examples games_hexxagon):

Exact solution, side-2 board, one piece each on opposite corners (10,101 positions): Ruby's final margin under perfect play is +7.
  Ruby's first moves: b2 +7, a2-c2 +7, a2-b1 +7, b3 -7, a1 -7
Side-2 board, standard corners: Ruby's margin +7 (the first clone to the centre converts all three Pearls).

The tests check the solver against plain minimax with no memory and no pruning on random positions, and check that the alpha-beta search, given unlimited depth, returns the same values. The report also counts the positions reachable from the standard start (24 after one move, 570 after two, 16,548 after three); the tests recount the first two with an independent move generator that works from coordinates and hex distances only.

The side-3 board already has 16 playable cells, roughly \(3^{16}\), or 43 million, colourings before counting the 100-move counter: out of reach for this pure-Python solver. On larger boards the audit's oracle is a depth-limited search and says so.

Audit and information regimes¶

uv run grounded-decision audit hexxagon (or make audit-hexxagon) replays one game of the gated player against search and judges every gated move against an alpha-beta search three moves deep:

Decisions audited: 53
  total regret 27, mean 0.5094 per decision
  agreed with the oracle: 36/53 (P(agrees with the oracle) ∈ [0.54, 0.80] (95%, 53 trials))
  gate overrides: 11

Regret is in pieces of margin after the oracle's horizon. The oracle is not exact; --oracle exact is available on the side-2 board only (--size 2x2) and refuses larger boards with a clear message.

The audit then prints the regime table: four agents, each playing 20 seeds from both seats on the side-4 board (34 cells) against noisy_greedy. All four win almost every game, so the table measures how often each wins by converting every opponent piece:

  agent [regime]                           opponent         games       W/D/L  rate (95% interval)        mean final margin
  clairvoyant [clairvoyant (benchmark)]    noisy_greedy        40      40/0/0  wipe-out 0.450 [0.293, 0.615]         24.8
  expectimax [probabilistic]               noisy_greedy        40      40/0/0  wipe-out 0.350 [0.206, 0.517]         23.4
  gated [worst-case]                       noisy_greedy        40      39/0/1  wipe-out 0.425 [0.270, 0.591]         22.9
  search [worst-case]                      noisy_greedy        40      40/0/0  wipe-out 0.400 [0.249, 0.567]           25

Seeing the opponent's actual reply (clairvoyant) against modelling it exactly (expectimax) differs by +0.100, with a simultaneous 95% interval of [−0.265, +0.446]; insuring against the worst reply (gated) against betting on the model differs by −0.075 [−0.423, +0.287]. Neither difference is distinguishable from zero with 40 games a row: in this game, at this depth, against this opponent, the regime matters less than looking further ahead. What the gated player has that the others do not is the guarantee in the previous section, which holds against every opponent.

Options¶

Option	Effect
`--size NxN`	Board side, 2 or more, with no upper limit; rows after `z` are lettered `aa`, `ab`, … (`--size 4x4` is a quick 34-cell game). Holes are added from side 3.
`--coords`	Column (or row) letters and cell numbers on the board (on by default when you play).
`--board standard\\|open\\|donut\\|rectangle`	The board: the original (three holes), no holes (61 cells), a hexagon without its middle (54 cells), or 7 rows of 9 hexagons (63 cells).
`--holes e4,c2`	Remove exactly these cells instead of the standard holes (`--holes ""` removes none).
`--start corners\\|opposite\\|ring`	The opening: three pieces each on alternate corners (the original), one each on opposite corners, or the ring trap (Ruby infects six on move 1).
`--layout flat\\|pointy`	Flat-topped cells in columns, as the original (default), or pointy-topped rows.
`--zoom 1\\|2\\|3\\|auto`	Cell size; `auto` (default on a terminal) picks the largest that fits.
`--style ascii\\|unicode\\|blocks\\|braille`	How the board is drawn.

From Python, hexxagon.configure(side, side, holes=False, start="opposite", jump_limit=None) gives a board without holes, one piece each on opposite corners, or no 100-move rule (the exact solver needs the rule); board=, start=, layout= and holes="e4,c2" match the options above. play hexxagon --list describes every board, start and layout.

The boards are built on a small geometry layer (src/grounded_decision/examples/games/geometry.py): a set of hexagonal cells with holes, their distances and neighbours, their labels, and both screen layouts. The rules only ask it for cells at distance 1 (clones) and 2 (jumps), so any shape it can describe is playable.

Limits¶

The removed cells of the original are three alternate cells of the centre ring; which three, relative to the starting corners, we could not confirm from any source. We remove the three pointing towards Pearl's corners; the other choice is this board mirrored with the colours swapped.
A player with no legal move ends the game here (the original rule); some Ataxx rule sets let that player pass instead.
The 100-move rule is ours (it mirrors Ataxx engines' 50-move rule); the original has none.
The gate's guarantee covers two moves. It says nothing about the result of the game.
The clairvoyant benchmark asks the real opponent for its reply to every one of its moves, so against a gated or searching opponent it is still slow on large boards; it is meant for the small boards of the regime table.

Next¶

Checkers and Chinese checkers: the same pattern with a tactical search and with progress checks.
Seeing the future, assuming the worst, or betting on the odds: the information regimes in the table above.