One row of Clobber

Clobber has the shortest rule of any partizan game on this site. Blue and red stones sit on a board; a move takes one of the mover’s own stones onto an orthogonally adjacent enemy stone, which is removed. Adjacency is symmetric, so a player has a move exactly when the opponent does — and every value the game produces is therefore smaller than every positive number.

On a full board the game is out of reach almost immediately. On one row it is not, and one row is not a watered-down version of the game so much as a different game with the same rule, small enough to solve completely.

Why every value is infinitesimal #

The rule guarantees it, and the argument is two sentences long, which is worth having before any census.

A Left move needs a blue stone with a red neighbour. A Right move needs a red stone with a blue neighbour. Adjacency is symmetric, so the two conditions are the same condition: if either player has a move, both do, and if either has none, neither has.

A position where the players run out together cannot be worth a whole move to anybody. More precisely, a game in which every follower gives both players a move or neither is all-small, and every all-small game is smaller in absolute value than every positive number. So no Clobber row is worth $\tfrac12$, or $1$, or any other number except zero.

That is a proof about the rule, and the census is the check that the code implementing the rule agrees with it. The two are different claims and this site runs both: the audit walks every position reachable from a row and asks the question directly, and a bug in the move generator would break the audit while leaving the argument true.

Every row up to eight #

The census is every string over three letters — blue, red, empty — up to eight squares long. That is 9,840 rows, each solved by the recursion.

Two things about that distribution are worth separating.

The values are few. A hundred and eleven values for ten thousand positions is a collapse of two orders of magnitude — a value is a class of positions and here the classes are enormous — and it is the opposite of what End-Nim does on a comparable census — 2,748 values for 5,460 positions, one for every other row. Clobber’s values compress; End-Nim’s do not.

And they are all infinitesimal. Zero, $\ast$, $\uparrow$, $\downarrow$, $\uparrow\!\ast$, $\downarrow\!\ast$, twice up-star and so on down the list. Not one row in the census is worth a number other than zero, which the rule guarantees: a player who runs out of moves has an opponent who has run out too, so no position can be worth a whole move to anybody.

A row is already a sum #

The census counts strings over three letters, and the third letter changes what is being counted more than it looks. An empty square is not a weak square — it is a wall. No move crosses it, in either direction, ever, because a move needs a stone standing next to an enemy stone and an empty square breaks the adjacency the rule is entirely built out of.

So a row is not one position. It is the disjunctive sum of the maximal runs of stones between its empties, and the sum has already been taken before the solver is asked anything. $\mathtt{xoxo.oxo}$ is a four-stone row plus a three-stone row, and its value is the sum of their two values, computable without ever looking at the eight-square position as a whole.

That is checkable rather than assertable, and it is worth checking on rows small enough to hold two parts in view at once.

That is most of the answer to why 9,840 rows carry only 111 values. The generating set is not the census. It is the set of connected rows — 510 of them over these lengths, against 9,840 with the walls put back — and every other value in the census is a sum of those. Values close under addition and the closure is small, because addition on infinitesimals collapses aggressively: $\uparrow$ plus $\uparrow$ is a value with its own short name, $\ast$ plus $\ast$ is nothing at all, and a hundred different arrangements of stones and gaps reduce to the same handful of totals.

End-Nim has no such wall and no such collapse, which is why the comparison two paragraphs above comes out so lopsided. Its 2,748 values over 5,460 positions is a game whose positions do not decompose and whose values are numbers rather than infinitesimals: numbers do not cancel, so nothing is lost on the way up and every position keeps its own answer.

Where the zeros come from #

A third of the census is worth exactly zero, and that figure has two quite different populations inside it that are worth separating before anybody concludes the game is mostly empty.

Two thousand three hundred and seventy-six of the 9,840 rows have no legal move at all. That is every string in which no blue stone is ever next to a red one — all the monochrome runs, all the rows of stones separated by gaps, the singletons, and the empty row itself. They are worth zero for the least interesting reason available: the game is already over, and it was over before it started. The count is arithmetic over the census’s own definition rather than a search — a string of length $n$ contributes when none of its $n-1$ adjacent pairs is a blue beside a red — and it comes to 24.1% of every row up to eight squares.

That leaves 1,192 rows that are worth zero and have moves in them, and those are the ones the claim is about. A row in that set has stones that touch, a move available to each player, a tree underneath it — and comes out worth nothing anyway, because every line the first player can start is answered. $\mathtt{xoxoxo}$ is in it and so is $\mathtt{xxoo}$, and the playable figure above is the invitation to disbelieve one of them.

The split matters for what a reader should take from the 36%. Read as one number, it says a third of Clobber rows are inert. Read properly, it says a quarter of them are inert and an eighth are live positions that a perfect opponent has already neutralised — which is a much stronger and much less obvious statement, and it is the one the recursion is actually being asked to certify.

It also sharpens the point about walls. Adding an empty square to a row can only remove moves, never create one, so gaps drive positions towards zero along the dullest possible route. The interesting question is the opposite one: how a row can be dense with adjacencies, full of moves for both players, and still be worth precisely nothing.

Two of each kind, drawn together, is the whole of the distinction.

The row that is worth nothing #

$\mathtt{xoxoxo}$ is worth zero exactly, and that is a stronger statement than “the second player wins”. It means the row can be added to any other game without changing its value at all — six stones on a board, and the board might as well be empty.

The mirror strategy is what is happening, and it is not obvious where the mirror is. The row has no symmetry a player could copy across — it is $\mathtt{xoxoxo}$, not a position beside its own reflection — so the second player’s answers are not reflections of the first player’s moves. They come out of the search, one reply per position, and the fact that they always exist is what worth zero means.

Why the census is worth having anyway #

An argument that every value is infinitesimal tells a reader almost nothing about which row beats which, and the census is where that information is.

Three thousand five hundred and sixty-eight rows are worth exactly zero. That is 36% of the census, and it means a third of all one-row Clobber positions can be deleted from any board they appear on without changing the answer.

Two thousand four hundred and fifty are worth $\ast$, and $\ast$ is not zero: a row worth $\ast$ is a first-player win on its own and cancels against another row worth $\ast$. Between them the two commonest values account for 61% of the census, and neither is visible from the picture.

The remaining 109 values are where the game lives. Up and down account for 1,398 rows; up-star and down-star for 756; twice up-star and twice down-star for 376; and the tail is long, with values like $\{\ast, \uparrow \mid \ast, \downarrow\}$ carrying 178 rows and a hundred more values carrying a few each.

Four of those values fit on four squares each, which is the shortest any of them can be written as a board.

A distribution that lopsided is the useful fact. A player who learns four values — zero, star, up and down — can name the value of three quarters of the positions this game produces on a short row.

The values grow while the rows do not #

Alternating rows are the natural family to follow, and they behave badly in an interesting way.

The row description grows by one character. The value goes from a single symbol to zero to something that fills a paragraph and back to $\downarrow\!\ast$. There is no monotone progression here at all, and the canonical form is not a summary of the row in any sense a reader would want — at eight stones it is longer than the exhaustive list of positions it was computed from.

What the two-dimensional game does with this #

One row is a game in its own right, and it is also the piece the real game is made of, so the relationship is worth stating.

A Clobber board breaks up as play goes on: stones disappear, and the surviving groups stop being adjacent to one another. Once a board has split into regions with no adjacency between them, it is a disjunctive sum of those regions, and each region is solved independently and the values added.

That is where a catalogue of one-row values earns its place. Many of the regions a real board decomposes into are rows — a strip of survivors along an edge, a line of three between two gaps — and a player who knows the row values reads those regions off instead of searching them.

What the catalogue does not do is solve the board. The regions are not always rows, the decomposition itself has to be found, and finding the parts of a board is a computation with its own cost. The 5×5 board Clobber tournaments are played on has never been solved by anybody, and nothing here changes that.

The economics of that are the reason the catalogue is worth having. A board in play breaks into independent regions and a sum of regions is solved region by region, so the cost of the whole is the cost of the parts plus the cost of noticing that they are parts — and on a game whose values are all infinitesimal, the parts have to be added rather than compared, because there is no ordering to compare them along.

What decides them #

If the values are unreadable, something else has to do the deciding, and for all-small games that something is atomic weight — roughly, how many ups a position is worth, computed as a bracket rather than a single number.

Atomic weight is what makes the census usable. A row’s exact value may be four lines long; its bracket is two integers, and two rows can be compared through their brackets whenever the brackets do not overlap. That is the difference between a value theory that computes and a value theory that helps.

The scale those brackets are read against runs finer than the ups do. Below every multiple of up sit the tinies and the minies, strictly ordered among themselves and all of them smaller than every positive number — so two Clobber rows can be incomparable while both are infinitesimal, and “smaller than every number” turns out to be a very weak statement about a position rather than a strong one.

What the solver computed, and how #

The recursion is four lines. A row is a string; a Left move is a blue stone with a red neighbour, the blue stone replacing the red one and leaving its own square empty; a Right move is the mirror. The game is game(leftOptions, rightOptions) built from those move lists, memoised on the string, and everything after that is the site’s ordinary machinery.

Three things are checked rather than assumed.

All-small is audited by walking every position reachable from a row and asking whether Left has a move exactly when Right does. That walk covers 2,742 positions across 120 of the longest rows, and the count of failures is zero. It is run rather than inferred because the argument is about a rule and the census is about positions, and a bug in the move generator would break the second while leaving the first true.

The values are named after canonicalisation, so the 111 is a count of values and not of forms. The playable figure’s reply table is verified exhaustively by valuecheck: every reply in the table is confirmed to leave the mover in a lost position, over the whole table rather than along one line.

The comparisons are decided by playing a difference and never by reading a name. Up is above nought; twice up-star is above up; down-star is below nought — and two of the census’s commonest relations come back confused rather than ordered, including $\{\ast, \uparrow \mid \ast, \downarrow\}$ against zero, which is the four-stone alternating row, and $\uparrow\!\ast$ against $\ast$. Confusion is why the outcome table has 3,816 first-player wins in it: a row confused with zero is one where whoever moves wins.

The value that is longer than the position #

The eight-stone alternating row is worth returning to, because it is the clearest case on this site of a canonical form failing to be a summary.

The row is eight characters. Its canonical form is four lines of nested braces, and the figure that would draw it refuses: the generator throws rather than produce a board with a label wider than the board. That refusal is the honest response — a picture whose caption is longer than its subject is not explaining anything — and the census reading exists to count such values instead.

What has gone wrong is not the reduction. The canonical form really is the smallest form of that value, and every option in it is doing work. What has gone wrong is the expectation: a value is a complete description, and a complete description of a complicated position is complicated. Compression is a property some games have and this one does not, at this length.

That is why atomic weight matters so much here. It is the deliberate throwing-away of most of the value in exchange for two integers, and on a game whose values run to four lines, two integers is the difference between a theory and a table.

Where the model stops #

Eight squares is the limit, and it is a limit on the census rather than on the solver: $3^n$ rows each solved over an exponential tree. Nine squares is affordable; twelve is not, and nothing here is a statement about long rows.

The one-row game is also not the game. Clobber is played on a rectangle, and a rectangle is not a sum of its rows — a stone can clobber upwards. Everything above is about the one-dimensional game, which shares the rule and not the difficulty: the 5×5 board that Clobber tournaments are played on has never been solved by anybody.

And the collapse to 111 values is a fact about small rows. A larger census would find more values; whether the ratio holds — whether values keep compressing as rows grow — is exactly the kind of extrapolation from four data points this site does not make.

Playing one, and what losing proves #

The playable figure is not decoration. It is the site’s standing argument in its strongest form: the winner is named before the reader moves, and the machine’s replies were computed in advance from the same recursion that produced the value.

Three things have to be true for that to mean anything, and all three are checked. The value is computed rather than quoted. The reply table is verified exhaustively — every reply in it leaves the mover in a lost position, over the whole table rather than along one line. And the page works without the script: the position, its value and the outcome are in the server-rendered picture, so a reader with no JavaScript keeps the argument and loses only the chance to test it.

A reader who beats the six-stone row has therefore found an error in the recursion — in game(), in canonical, in the move generator — and not in an opponent. That is a narrower claim than “the machine plays well” and a much stronger one.

Where the ladder goes next #

The obvious next rung is the one the atomic weight section gestures at: an all-small game with an unreadable value and a two-integer bracket is a game where the theory has been replaced by an approximation that works. How good that approximation is — how often two Clobber rows are ordered by their brackets, and how often the brackets overlap and decide nothing — is a measurement this census could support and does not make here.