A game where nobody can be ahead in moves

Stones of two colours on a board. A move takes one of the mover’s own stones onto an orthogonally adjacent enemy stone, which comes off; the moving stone ends up on the square it cleared. The player who cannot move loses.

Nothing in that rule mentions symmetry, and yet the rule is symmetric in a way that decides everything about the values: a blue stone beside a red one is a move for Left and a move for Right at the same time.

All-small by construction #

A game is all-small when, in it and in every position reachable from it, one player has a move exactly when the other does. The class matters because a player who can never gain a spare move can never be ahead by a whole move — so no all-small position is worth a positive number, and every value in the class is an infinitesimal.

Most games are shown to be all-small by checking. Clobber is all-small by reading the rule.

Adjacency is symmetric: if a blue stone is next to a red one, then that red one is next to a blue one. The first fact is a move for Left and the second is the same fact, read as a move for Right. So Left has a move exactly when some blue-red adjacency exists, which is exactly when Right has one — in every position, at every stage, without exception.

The figures here check it anyway, over every position reachable from each board drawn, and refuse to draw if any position gives one player a move and not the other. An argument that clean is worth a test that could fail it.

The values that come out #

Small boards produce the small infinitesimals, and there are fewer of them than the number of boards would suggest.

A single blue stone beside a single red one is $\ast$: whoever moves takes the other stone and the opponent has nothing. Four stones in a row, alternating, is $\{\ast, \uparrow \mid \ast, \downarrow\}$ — not a nimber, and not one of the standard infinitesimals either, which is the first sign that this game generates its own vocabulary.

The 2×3 board with alternating colours is worth 0: whoever moves loses, on a board of six stones with no visible symmetry to explain it.

Playing a board that is worth nothing #

A position worth 0 is a second-player win, which makes it the right board to hand a reader: the value is stated before anything is touched, the reader moves first, and the reader loses.

The demonstration is worth more here than in most games, because worth zero in a game of infinitesimals is not a comfortable draw. It means the second player has an answer to every one of the first player’s moves, on a board where every position is a knife-edge and no amount of material advantage exists to fall back on. There is nothing to be ahead by except the move itself.

Following one board to the end #

The 2×3 board is small enough to walk through, and walking through it is the fastest way to feel why a game with no material can still be decided.

Six stones, alternating, three blue and three red. Left moves first and every move available takes one red stone off and slides a blue stone into its place. Whatever Left plays, the board afterwards has five stones on it and — this is the part worth watching — Right has a reply that leaves a position worth zero again.

That is what a value of 0 means operationally: the second player can restore the balance after every move, for as many moves as the first player cares to make. It is not that the position is symmetric, because after two moves it usually is not. It is that the second player’s answer exists at every branch, which is a claim about all 117 positions reachable from the board and not about the four or five a game actually visits.

The count is worth keeping in mind while playing. A reader clicking through the figure above sees perhaps four positions; the table behind it holds every position any sequence of clicks could produce, and each entry was checked to leave the opponent in a lost position. The claim on the page is small — worth 0 — and the object standing behind it is not.

A fragment vocabulary #

Because Clobber positions break into pieces, most of the analysis is a matter of recognising fragments, and the smallest ones are worth naming.

A lone pair. One blue stone adjacent to one red one, with nothing else nearby: worth $\ast$. Whoever moves takes the opponent’s stone and leaves an empty region.

A stone with no enemy neighbour. Worth 0, whichever colour it is, since it can never move and can never be taken. Isolated stones are furniture.

A line of four, alternating. Worth $\{\ast, \uparrow \mid \ast, \downarrow\}$ — a genuinely partizan object, not a nimber, and not reducible to anything with a shorter name.

Two facts follow from that list. Since $\ast + \ast = 0$, a board splitting into an even number of lone pairs is a second-player win and an odd number is a first-player win: the whole analysis is a parity count. And since isolated stones are worth nothing, a position’s material — how many stones each player has — is entirely uninformative. A player with six stones to the opponent’s two may be losing badly.

That last point is the one that makes Clobber feel unlike other board games on first contact. There is no material advantage, no territory and no score. What there is instead is the atomic weight, and it is invisible without computing it.

Where the fight actually is #

If no Clobber position is worth a whole move, what are the players competing over?

Atomic weight, mostly. The measure of how many ups a position is worth is the right currency for all-small games: it is to infinitesimals what the mean value is to hot games, and it decides sums of all-small components the way ordinary numbers decide sums of cold ones.

And star, which is what a great many small Clobber positions come out as. A pair of adjacent opposite stones is $\ast$; so is a 3×3 board of alternating colours; so are many awkward fragments. Since $\ast + \ast = 0$, a board that decomposes into an even number of star-valued pieces is a second-player win, and counting them is the whole analysis.

Both currencies are visible on four boards drawn together, and neither is visible on any one of them.

Two values across four boards is the collapse this game is made of, and it is what makes the star arithmetic worth learning: two $\ast$ boards on one table are a second-player win and three of them are a first-player win, whatever the boards look like.

Decomposition, and why it matters more here #

A Clobber board falls apart quickly and permanently. Every move removes a stone, so the board only ever thins, and isolated groups — a blue stone with no red neighbour, a cluster cut off by empty squares — stop interacting entirely.

That makes the disjunctive sum the working method rather than a theoretical nicety. A mid-game Clobber position is a handful of small fragments, each worth an infinitesimal, and the total is their sum. Since evaluating components separately turns a product into a sum, it is also the only affordable way to handle a board of any size.

The fragments recur, too. A two-stone pair is worth $\ast$ wherever it appears; a three-in-a-row is worth what it is worth on every board that contains one. So a table of small fragment values, computed once, does most of the work of analysing a large position.

An empty square is where a board comes apart, and the arithmetic it hands over is a parity count and nothing more.

No move crosses an empty square in either direction, because a move needs a stone standing beside an enemy stone and a gap breaks the adjacency the rule is built out of. So a row with gaps in it was already a sum before anybody was asked to evaluate it, and eight squares of Clobber can be settled by counting to two.

The one-line argument, written out #

The all-small claim deserves a proof rather than a gesture, because it is the reason this game is in the collection and because it is short enough to give in full.

Let $P$ be any Clobber position. Left has a move in $P$ exactly when there exist adjacent squares holding a blue stone and a red stone. Right has a move in $P$ exactly when there exist adjacent squares holding a red stone and a blue stone. Adjacency is a symmetric relation, so those two conditions are the same condition. Therefore Left has a move if and only if Right does.

Now let $Q$ be any position reachable from $P$. A Clobber move produces another Clobber position — stones on a board, the same rules — so the argument above applies to $Q$ unchanged. Therefore $P$ is all-small.

Two things are worth noticing about that proof. It never mentions how many stones each player has, which is why material is irrelevant here. And it never mentions the board’s shape, so it holds on a strip, a square, a hexagonal board or an arbitrary graph — the property comes from the move rule, and any game whose move rule is symmetric in this way inherits it.

Contrast Domineering, where Left places vertically and Right horizontally. Those are different conditions on the same board, and a Domineering position routinely offers a move to one player and none to the other — which is why its values include whole numbers, and why a player there really can be a move ahead.

What makes it hard anyway #

Clobber is all-small, decomposes readily, and has tiny values. It is still, as a family, out of reach.

The number of positions on an $m \times n$ board is exponential in the squares, and the fragments that appear in real play are not always small: a large connected tangle of alternating stones does not decompose until quite late, and a solver must evaluate it whole. The 3×3 board here needs 91 positions and 128,313 routes; a 5×5 board is far past what these figures compute.

There is also no closed form. Nobody has a rule that reads a Clobber position and returns its value, and the family has been studied since 2001 without one emerging — the same situation as Domineering, and for the same reason: a short rule whose moves interact.

So the game sits in an interesting position. Its class is settled by a one-line argument — every value is infinitesimal, always. Its values are as hard to compute as anything else on this site.

Two boards that look alike and are not #

A useful exercise, and one that makes the point that these values must be computed rather than judged.

A row of three, blue-red-blue, is worth $\ast$. A row of three, blue-red-red, is worth $\downarrow$ — a position Right wins outright, whoever moves.

The two differ by the colour of one stone at the end of a line, and their values are not merely different numbers but different kinds of object: a nimber, which neither player prefers, against a negative infinitesimal, which Right prefers in every sum it ever appears in. Adding the two together gives $\ast + \downarrow$, which is neither of them and is a third thing again.

All four rows of three that have a move in them make the point better than the pair does, because two of them share a value and two do not.

There is a practical lesson in the pair, and it is the reason a Clobber player cannot work by eye. In a game with numbers, a position that looks slightly better usually is slightly better, and small misjudgements cost small amounts. Here the values are not ordered by anything visible: a fragment is worth $\ast$ or $\uparrow$ or $\downarrow$ according to a computation, and the difference between them is the difference between a position either player is happy to take and one only Right wants. There is no gradual scale to be approximately right on.

That is what the site’s standing caution about notation is for. $\ast$ and $\downarrow$ are compact and completely opaque; the two rows of three stones are legible and say nothing about their values. Neither picture is sufficient alone, which is why both appear.

What the pictures cannot show #

Three limits.

A board drawn here is small enough to solve, and that is the selection. Every value on this page was computed by exhaustive evaluation. Nothing here says what happens at the sizes people actually play, which is 5×6 and larger, and where the published analysis relies on decomposition and atomic weight rather than on complete search.

All-small does not mean equal. A game where both players always have a move is not thereby balanced: the values are infinitesimals, and infinitesimals are strictly ordered among themselves, so one player can be enormously better off in the only currency the game has. Tiny and miny are the standing demonstration that “smaller than every positive number” describes a scale rather than a size.

The colour convention is this site’s, not the game’s. Blue for Left and red for Right is Conway’s mnemonic and the convention throughout these essays; Clobber is usually published with black and white stones. Nothing about the values depends on it.

A value is not a plan. The 2×3 board is worth zero, and knowing that does not tell the second player what to answer with — only that an answer exists. Turning the value into play means consulting the table, which is what the figure does, and a value being small is no guarantee that the strategy behind it is.

Who invented it, and when #

Clobber is recent by the standards of this subject: Albert, Grossman and Nowakowski introduced it in 2001, and it was designed rather than inherited — a game built to be all-small, to decompose, and to have interesting infinitesimal values, which is an unusual set of design goals and produced an unusually clean example.

It became a standard test bed almost immediately. Computer Olympiad tournaments run Clobber; the analysis of it drove work on atomic weight and on the practical use of decomposition; and it is now one of the games people reach for when they want a partizan family whose whole difficulty is in the infinitesimals rather than in temperature.

The name, incidentally, is exactly what it sounds like: a stone clobbers the enemy stone it lands on. It is the rare case in this subject of a game whose name describes its move, and the plainness is of a piece with the design — one rule, no exceptions, and everything interesting arriving as a consequence rather than as a feature.

Which is the argument for its place here. Most of this collection’s games are cold enough that the fight is about numbers, and the infinitesimals are a refinement at the end. Clobber has no numbers at all. Everything it does happens in the part of the theory that other games treat as the small print.

Where the ladder goes next #

clobber opens here with the game and the observation that it has no numbers in it at all. The two rungs above measure what it does have instead.

One row of Clobber sweeps every string of blue, red and empty squares up to eight long — 9,840 rows — and finds them carrying only 111 values, every one of them infinitesimal, with a third of the rows worth exactly nought. The interesting half is what happens as the row grows: six alternating stones are worth nought and eight are worth a form that takes four lines to print, so the values do not settle down as the row lengthens. They explode, while the row itself stays trivial to describe.

That is the practical problem this game presents, and when the bracket decides is the answer to it. A Clobber row’s value is an all-small game nobody can hold in their head, so what a player or a solver carries is the up-bracket: a pair of integers between which the atomic weight must lie. As an approximation it is worth exactly what it settles — 1,585 of 7,875 pairs of rows are ordered by it, every one of those orders is right, and of the 6,290 pairs it declines, 4,222 have no answer to decline.

Read together they say why this game belongs in a collection about values. Most games here are cold enough that the fight is about numbers and the infinitesimals are small print at the end. Clobber has nothing but small print, and it is the game where the theory’s least familiar apparatus is the only apparatus there is.