The colour swap pays through a mirror

Pieces that can only come apart counted what a Clobber solver stores when it values pieces rather than boards: every live piece that turns up anywhere in the search, shifted to its corner so that the same piece in two places is stored once. On a four-by-four board that is 395,947 pieces. It ended by naming two identifications the shift does not make. A piece and its mirror image are the same game, since a Clobber capture looks the same in all four directions. And a piece with its colours swapped is the negative of the original — every move handed to the other player — so a solver could store one of the pair and read the other’s value off by turning it over.

The second promised a halving for nothing, unless a large share of pieces turned out to be their own negatives. Neither half of that prediction survives the count. The halving does not come from the colours. It comes, when it comes at all, from a mirror — and the reason is a fact about the checkerboard that also settles who can win the opening.

Two identifications, and the ceiling they share #

Symmetry and colour are both rearrangements a solver can make without valuing anything. Symmetry is the group of eight: four rotations of the square, and a reflection of each. Colour is the group of two: leave the piece alone, or swap blue for red. Together they make a group of sixteen, and an orbit under a group can be no larger than the group, so no combination of the two can make a table more than sixteen times smaller. What counts as the same position met the same ceiling for Domineering’s symmetries — four there, since a quarter turn exchanges the players — and found the measured fold a little under it. The ceiling is a promise about the worst case for the solver and the best case for the fold; what the fold actually reaches depends on how many orbits are full.

The colour swap has one more property that matters for a solver. A symmetric copy has the same value and can share an entry outright. A colour-swapped copy has the negative value, so it shares an entry with a sign: the solver stores one and negates on the way out. That is the same arrangement the Domineering essay recommends for its quarter turns — four symmetries that shrink the table, four that populate it cheaply — and it costs one pass over a small object instead of a search.

Colour alone folds a tenth #

The census is the one the earlier essay made: every live piece reachable from the checkerboard start on four boards, 3 × 4, 2 × 6, 3 × 5 and 4 × 4, each shifted to its corner with its colours kept. Each table is then folded three ways.

By colour alone the tables fold by 1.08 to 1.16. The prediction of a halving assumed that a piece’s colour swap would be in the table alongside it, waiting to be identified. It mostly is not. On 3 × 4 the colour swap of a piece turns up as another piece in the table 22 per cent of the time; on 3 × 5 and 4 × 4, 16 and 17 per cent. A piece whose negative never occurs in the search has nothing to be identified with, and storing it with a sign saves nothing.

By symmetry alone the tables fold by 2.3 to 4.4, which is the familiar shape: below the ceiling of eight, nearer to it on the larger boards, where more pieces are small enough to be rotated freely inside the bounding box. And by both together the fold is 4.71 on 3 × 4, 4.44 on 2 × 6 and 8.67 on 4 × 4 — in each case almost exactly twice the symmetry fold. Colour, worth a tenth on its own, is worth a factor of two beside symmetry. On 3 × 5 it is worth a twelfth either way.

Something about three of the boards and not the fourth makes a piece’s negative turn up, provided it may be rotated or reflected first.

A mirror that changes colours #

The something is the checkerboard. Clobber starts with the stones alternating, blue on the squares of one colour and red on the other, so the start position is the board’s colouring. A symmetry of the board either keeps every square on its own colour or sends every square to the other one.

The arithmetic is short. Reflecting a board of $C$ columns left to right sends column $c$ to column $C - 1 - c$, which changes the colour of a square exactly when $C - 1$ is odd — when $C$ is even. Top to bottom is the same with the number of rows. A half turn changes colour when the two sides add to an odd number. So on 3 × 4 the left–right mirror and the half turn both change colours; on 2 × 6 both mirrors do; on 4 × 4 both mirrors and the quarter turns do; and on 3 × 5, where both sides are odd, nothing does.

A colour-changing symmetry carries the starting position to its own colour swap. Every position reachable from the start is reached by some sequence of captures. The mirror image of that sequence is a legal sequence from the mirror image of the start, which is the start with its colours swapped; swap the colours back and it becomes a legal sequence from the start itself, ending at the colour swap of the mirror image. So every reachable position’s mirror image is the colour swap of another reachable position. So on such a board the table contains, for every piece, a rotated or reflected copy of its negative. Identification by colour alone cannot see it, because the negative is lying on its side. Identification by colour and symmetry together finds it every time, and the fold doubles.

On 3 × 5 no symmetry changes colours, the start is not carried to its swap, and a piece’s negative turns up only when a small piece happens to be reachable on squares of the other parity. That accounts for the twelfth.

The surprising part is which rearrangement is doing the work. For Domineering, the essay on identification found that a quarter turn of the board is a negation, because it exchanges the two directions a domino can lie. For Clobber the quarter turn is an ordinary symmetry, and negation is a recolouring — but on a board with an even side, an ordinary mirror carries the whole collection of positions to its negative. The same three objects, in a different arrangement, and the solver that knows the board’s shape gets the negation for free.

Almost nothing is its own negative by shape #

The earlier essay’s caveat was that the halving would fail if many pieces were their own negatives, since a piece equal to its colour swap folds no further under colour. That fear turns out to be the least of it.

No piece on any of the four boards is its own colour swap where it stands, and none could be: that would need every occupied square to hold a blue stone and a red stone at once. A piece can be its own negative up to symmetry — its colour swap is one of its rotations or reflections — and those are 159 of 11,191 pieces on 3 × 4, 109 of 4,999 on 2 × 6, 268 of 126,811 on 3 × 5 and 935 of 395,947 on 4 × 4. Between 0.2 and 2.2 per cent. The pieces with a symmetry of their own, which are what keeps the symmetry fold under eight, are similarly rare: five per cent on 3 × 4, under one per cent on 4 × 4.

So the orbits under the group of sixteen are nearly all full where the group acts, and the fold is limited not by self-negative pieces but by the colour swap’s absence on boards without a colour-changing mirror. That is a structural answer to the earlier question and a different one from the one it expected.

What only a solve can fold #

There is a third identification the solver can make, and it is not a rearrangement. Two pieces with the same value are interchangeable in every sum, whatever they look like. The values that are their own negatives counted thirty such values among the 1,474 born by day three; a piece can be worth one of them without its shape having any symmetry at all.

On 3 × 4 every one of the 11,191 pieces can be valued in a few seconds, and the values are what the rearrangements promised: every mirrored copy in the table agrees with the original, 22,784 checks, and every colour-swapped copy is worth the negative, 2,470 checks, with no exception. The theory is not in doubt; the check is there because a table that leaned on it without looking would be trusting a sign convention in code.

And the values fold much further. The 11,191 pieces take 632 distinct values — a fold of 17.7, past the ceiling of sixteen that no arrangement of squares and colours can exceed. On 2 × 6 it is 4,999 pieces and 286 values, 17.5. More than a third of the pieces on both boards are worth their own negative: 4,195 of 11,191 on 3 × 4, against 159 that are self-negative by shape. Nearly a fifth are worth nought, 2,079 of them, which is the commonest value by far and the one a region-valuing solver drops without storing.

Why the values crowd together so much more than the shapes do has a reason particular to this game. Clobber is all-small: adjacency is symmetric, so whenever Blue has a capture Red has one too, in every position and every subposition, and every value is an infinitesimal — nought, stars, ups and downs and their tangles, never a number other than nought and never anything hot. A small piece has few ways to be small. The 632 values on 3 × 4 are drawn from a narrow band near nought, and the band is narrower than the variety of shapes that land in it, which is what lets a value table fold past the arithmetic ceiling of any rearrangement.

The commonest value deserves its own sentence. A live piece worth nought has captures in it and is worth nothing to either player in any sum: whoever moves in it can be answered there, and it can be dropped from the position as completely as a dead piece. Pieces that can only come apart found that deleting dead stones saved a solver more than splitting the board did. The 2,079 live pieces worth nought on 3 × 4 are the same saving one level up — stones that are not dead, have moves, and still contribute nothing — and a solver learns which they are only by solving them.

Those numbers describe what an identification costs as much as what it saves. The symmetry and colour folds are free: they need the piece and nothing else. The value fold needs the value, and the value is what the table is for. What it costs to notice a repetition priced the symmetry fold on Domineering and found the mapping alone seventeen and a half times the whole cost of not folding, because sending every entry to its canonical orientation is work. A value-keyed table pays nothing of the kind at lookup, and everything at construction. On a board where values are computed anyway — which, in this subject, they always are — it is the identification worth having, and it is the one that comes last.

A key that carries a sign #

A solver that wants the colour swap’s saving needs a key that can tell it which way round a piece is stored. The natural one takes all sixteen images of a piece — eight symmetric copies of the piece and eight of its colour swap — writes each down, and keys the piece by whichever comes first in some fixed order, remembering whether the winner was a swapped image. A lookup returns the stored value, negated when the flag is set. Two pieces related by any of the sixteen land on one entry, and the flag reconciles the signs.

That key is twice the work of the symmetry key alone, and on 3 × 5 it buys a twelfth. On the even boards it buys a factor of two, because there the negative is in the table and lying on its side. A solver that knew the board’s parity in advance could choose: the sixteen-image key on a board with a colour-changing mirror, the eight-image key on a board with two odd sides. A key shorter than the position is a reminder that a key is a design decision with its own failure modes; this one has none of the hashing kind, since it keys by the piece itself, but it has a price that depends on a fact about the board the solver may not have thought to check.

There is a quieter cost too. The sixteen-image key identifies pieces whose values are negatives, and a solver that forgets to apply the sign stores the wrong value for half of every pair it meets — silently, since every stored value is a legitimate value of some piece. The checks above, every colour swap found worth exactly the negative, are the guard against that, and a production solver would want the same guard in its own code. How often a board falls apart measured how often a solver gets pieces to look up in the first place; the identifications here only matter on the positions where it does.

An even board opens at its own negative #

The mirror argument has one consequence worth more than a factor of two, because it is about a single position rather than a table. Apply it to the start itself.

On a board with an even side, the mirror across that side changes every square’s colour, so it carries the opening to its colour swap. A mirror image of a Clobber position is the same game. A colour swap is its negative. So the opening of every board with an even side equals its own negative, whatever the board’s size — and a game equal to its own negative cannot be a win for one player whoever starts, since $G \ge 0$ would give $-G \ge 0$ and then $G = 0$. The opening is a second-player win or a first-player win, and that is settled by the mirror without a single position searched.

The solved boards agree. The openings of 2 × 3, 1 × 6, 2 × 6 and 3 × 4 are worth nought, second-player wins; those of 1 × 4, 2 × 4, 1 × 8 and 2 × 5 are first-player wins, worth a star or a longer all-small value equal to its own negative. Nothing in the argument decides between the two, and the boards split.

On a board whose sides are both odd the argument says nothing, and the rows show it saying nothing. The row of five opens at $\{∗ \mid ↓\}$, a win for Right whoever starts. Seven opens at a value Right also wins outright; nine at $↓∗$, which a first player wins but which is not its own negative. Three by three happens to open at a star, self-negative by accident rather than by a mirror. In each odd row Blue has one stone more than Red, and on the rows of five and seven the extra stone is a liability.

This is a mirror strategy without the strategy. The strategy that is a symmetry found Cram’s mirror winning outright for the second player, exactly on boards with both sides even. Clobber’s mirror cannot be played the same way — a capture across the axis removes the very stone the copy would have had to move — and so it does not hand the second player a win. What it hands over is the value’s symmetry: the opening is its own negative, and which of the two possible outcomes it has still needs a search.

The convention named #

Normal play: the player with no capture loses. A piece is an orthogonally connected set of stones with at least one capture available; pieces with none are dead and worth nought, and are not stored. The tables are the reachable pieces on each board from the checkerboard start with Blue on the corner square, by any sequence of moves by either player, each shifted to its corner. “Symmetry” is the eight rotations and reflections of a piece, applied to the piece and not to the board, since a rotated piece is the same game wherever it sits; “colour” swaps blue and red. Values are canonical forms computed by the recursion, and two pieces are identified by value when their canonical forms are the same.

What the counts cannot show #

What the larger boards do under the value fold. The values were computed on the two boards whose pieces can be valued in seconds; on 4 × 4 the pieces number 395,947 and each is a search of its own. The fold of 17.7 past a ceiling of sixteen is measured on small pieces, many of them worth nought, and nothing here says whether the fold grows or shrinks as pieces get larger and their values more varied.

Which outcome an even opening has. The mirror settles that an even board’s opening is its own negative. It does not settle whether that is nought or not, and the twelve boards split four to four with no visible rule — 2 × 3 and 2 × 6 are nought, 2 × 4 and 2 × 5 are not.

And how much the colour-changing mirror saves a real solver. The fold counts orbits, which is the most an identification could save. A solver pays to find each piece’s canonical orientation, and on Domineering that price was larger than the saving; here the colour swap adds one more transformation to the eight, and whether that tips the account is a timing question this does not answer.

Still open: whether a value table grows like the values #

The value fold on 3 × 4 is 17.7 and on 2 × 6 17.5, two numbers close enough to suggest a pattern and too few to be one. A solver for larger boards would want to know whether the number of distinct values of Clobber pieces grows like the number of pieces, like its square root, or like something set by the depth of the values rather than by the size of the board. A self-negative value costs a day found self-negative values expensive in birthday; the 4,195 self-negative pieces here are cheap in size. The measurement is the value census on 3 × 5, where the pieces are ten times as many and the solve is a question of hours rather than seconds, set against the same census on the two boards already counted.