A game older than the theory

Kōnane is a Hawaiian game. It was played on boards carved into lava rock, one of which stands in a national historical park; it is recorded in the Kumulipo, and Cook’s crew saw it played on the third voyage.

Its rules take two sentences, and the second one is the whole reason it belongs here.

Stones of two colours fill the board in a checkerboard pattern. Every move is a capture: a stone hops over an adjacent enemy stone into the empty square beyond, taking it, and may keep hopping in the same direction. A player with no capture available loses.

That last clause is the normal-play convention — the player who cannot move loses — arrived at independently and a very long time before anybody wrote it down as a convention. It is the hypothesis every theorem on this site rests on, and it is sitting in the rules of a game nobody designed for the purpose.

What a row is worth #

This essay plays on a single row. That is not a toy version of the game; it is where the values are small enough to print and the positions short enough to draw, and even the one-dimensional game has not been solved in general.

Those are integers, which is unsurprising: a row where only one side can move is worth however many moves that side has, and integers are what the theory calls positions with a fixed number of free moves for one player.

The interesting part starts when both sides can move.

The census #

The right way to ask what a game holds is not to pick positions and evaluate them; it is to evaluate all of them.

Two squares longer and the picture changes size but not shape: 6,561 rows of eight squares carry 36 distinct values, of which 3,493 are zero. Collapsing thousands of arrangements onto dozens of values is the site’s standing claim about canonical form, and here it is made on a game chosen by somebody else.

The collapsing is worth seeing on the rows themselves rather than on the machinery that does it. Take one value out of the middle of the list and ask which rows carry it.

That is what canonical form buys, stated as a count rather than as a procedure: dominated and reversible options are stripped away until what is left is unique, and rows with nothing visible in common arrive at the same object. A row of seven squares has 2,187 arrangements and nineteen values between them; a row of eight has 6,561 and thirty-six. The arrangements multiply by three per square and the values do not, which is the whole reason a census of a game is a shorter document than a list of its positions.

It is worth being clear that nothing about the collapsing is a Kōnane fact. The evaluator does not know it is looking at stones, and the reduction it performs is the one it performs on a Hackenbush string or a Domineering board. What Kōnane supplies is the raw material — a few thousand arrangements that a person made up rules for without any of this in mind — and the collapsing happens to it in exactly the proportion the theory predicts for anything else.

What is in the list #

The values a row of eight can hold are worth naming, because the list is the argument.

There are integers, up to ±3 in this range: positions where one side has spare moves and the other has none.

There are halves and quarters. ...ox.x is worth ½ and .ox.x.x is worth ¼ — dyadic rationals, arising in a game about hopping stones for the same reason they arise in Hackenbush, which is that the simplest number between the options is what a position is worth.

There is star, and there are switches — .xo.xo. is worth {1 | −1}, a position both players want to move in and whose value is not a number at all.

Read down that column and the theory’s own table of contents is in it. A number, a finer number, a nimber, and a value with no number anywhere near it — and the five rows below each other differ by a stone or two.

The witnesses matter more than the values here, because they are what makes the claim checkable by hand. A reader who does not believe that ....xo. is worth ∗ has a seven-square position in front of them and two legal moves to try; a reader who does not believe that a game invented in Hawai‘i produces switches has .xo.xo. and can watch both players want to move in it. Every value in this essay comes with a position short enough to argue with, which is not something the theory’s own examples usually offer — a canonical form is a claim about a tree, and a row of stones is a claim about seven squares.

And there are infinitesimals, which is the part of the vocabulary a reader is entitled to be most suspicious of.

That is the strongest thing this essay has to say. The exotica of combinatorial game theory — the infinitesimals, the switches, the values that are not numbers — are routinely presented on games invented to display them, and it is fair to wonder how much of the vocabulary is an artefact of the examples. Kōnane is a control experiment nobody arranged. It produces the whole vocabulary.

What the thirty-six do not contain #

It produces the whole vocabulary is the essay’s strongest sentence and it deserves a qualification, because the census supports it in one sense and not in another.

Read the 36 values of the eight-square rows and every kind is there: integers to $\pm 3$, halves and quarters, numbers with a star on them, the nimbers $\ast$ and $\ast 2$, the infinitesimals $\uparrow$, $\downarrow$, $\uparrow\!\ast$, $\downarrow\!\ast$, $\Uparrow$ and $\Downarrow$, switches, and half a dozen forms with no short name at all — $\{0 \mid 0, \downarrow\!\ast\}$, $\{1 \mid 0, \{1 \mid 0\}\}$ and their relatives.

Read them for range and the list is narrow.

No denominator finer than a quarter. There are halves and quarters and no eighths, so the recursion is going two levels of the simplicity rule deep and no further.

No nimber above $\ast 2$. The impartial part of the vocabulary stops almost immediately.

And no temperature above one. The hottest values in the list are $\{2 \mid 0\}$, $\{2 \mid \ast\}$, $\{\ast \mid -2\}$ and $\{1 \mid -1\}$ — a gap of two, so a temperature of one, and nothing on the list is worth more than that to move in.

Which is the right shape for a control experiment #

That distinction is worth drawing carefully, because the two readings support the essay’s argument to very different degrees, and the weaker-sounding one is the one that matters.

The argument is that the vocabulary is not an artefact of the examples chosen to display it. What that needs is one of each kind — a number, a nimber, an infinitesimal, a switch, a nameless form — from a game nobody designed. The census supplies all five, and that is the claim standing.

What it does not need, and does not get, is depth in any of them. A row of eight squares supports a shallow game tree, so the values it can reach are shallow: two halvings of the simplicity rule, two nimbers, and fights worth a move rather than several. The narrowness is a fact about the board, not about Kōnane, and a longer row would supply eighths and hotter switches by exactly the mechanism that supplied quarters and cool ones.

So the honest form of the essay’s claim is this: Kōnane reaches every corner of the theory’s vocabulary and does not go far into any of them at this size. Every corner is what a control experiment needs; the distance is what a board of eight squares cannot pay for.

And the narrowness is itself worth having, because it is checkable. A game that produced infinitesimals and no numbers, or numbers and no switches, would be evidence that the vocabulary has corners nothing natural reaches. A game producing one of everything within a range its size explains is evidence of the opposite — and being able to say why the range stops where it does is the difference between a limitation and an unexplained absence.

Why the halves appear #

A quarter is a strange thing for a game about hopping stones to be worth, and where it comes from is worth following, because it is the same mechanism everywhere on this site rather than a Kōnane curiosity.

A value is the simplest number strictly between what Left can reach and what Right can reach. That rule — the simplicity rule — is what produces halves and quarters out of positions containing nothing fractional.

Take .ox.x.x, worth ¼. Left has one move and it leads to a position worth 0; Right has two, the better of which leads to a position worth ½. So the value is the simplest number strictly between 0 and ½, which is ¼. Nobody divided anything. The fraction is the name of a position that lies between two others in the ordering, and the ordering is a fact about who wins sums.

Those are three rows of the same game, so the arithmetic can be read off the picture rather than taken on trust.

A position worth a half is not half of anything: it is a position that behaves like a half when added to others, which is the only sense in which any of these values are numbers. That is worth saying plainly because the fractions look like the most artificial part of the theory and they are the most forced. Given the ordering, and given that positions are compared by adding them and asking who wins, the dyadic rationals are not a choice.

Play it #

The position worth zero above is a claim that can be tested rather than believed.

The reason to include it here rather than in an essay about play is that the claim is unusually specific. It is not “this game is hard” or “the machine is strong”; it is that a particular eleven-square position is worth exactly zero, and a value of zero has an operational meaning: the player who moves loses, whatever they do, however long they take.

The position was chosen by a search rather than by hand: every row of eleven squares was evaluated, the ones the reader cannot win were kept, and the one with the largest reply table won. That matters because a playable figure the reader loses in a single move demonstrates very little, and the difference between one move and three is the difference between being told and finding out.

The decomposition that is not there #

Every reader of this site will want to cut a long row into pieces and add up the values. It is the method the whole subject is built on and it is the first thing to try.

It does not work here, and the way it fails is instructive.

Checked over every row of seven squares: cutting at a single empty square gives the right answer 842 times out of 1,266. Widening the gap helps and never fixes it — a gap of three still fails 54 times out of 162. There is no width at which the equation becomes a theorem, because widening the gap does not stop a stone entering it.

That is a substantive fact about Kōnane and it is the reason its one-dimensional game is unsolved. The tool that makes Domineering, Hackenbush and Nim tractable is decomposition, and Kōnane resists it. Splitting a position is a claim about the position, and here the claim is false at every width anybody would try.

The values are the same values #

There is one more check worth making, and it is the check that turns a coincidence into a claim.

The values above are printed with the same names the rest of this site uses — ↑, ∗, ½ — and a sceptical reader is entitled to ask whether that is a naming convention or an identity. It is an identity, and the machinery says so: the evaluator interns positions by their canonical form, so a Kōnane row worth ↑ and a Hackenbush string worth ↑ are the same object in memory. There is no separate Kōnane arithmetic.

That is what makes the sums work. A Kōnane row and a Domineering board can be added together and the total evaluated, and the answer means what it means for either alone — because the value of a position is defined by how it behaves in sums and by nothing else, which is why comparing two positions is the same operation whatever games they came from.

Where the game actually stands #

Being exact about this matters, because a site that computes values for a game can easily be read as having solved it.

Kōnane is not solved. Chan and Tsai analysed the 1 × n game and did not finish it. Hearn proved the full two-dimensional game PSPACE-complete with respect to board size, by a reduction from nondeterministic constraint logic, so there is no prospect of a general answer of the kind Nim has. A 2008 result of dos Santos and Silva goes further and shows the game is universal in a strong sense — every combinatorial game appears inside it.

What this essay contains is a complete evaluation of every row up to eight squares, which is a statement about 6,561 positions and about nothing larger.

The gap between the two is worth measuring rather than gesturing at. A row of eight is 3⁸ arrangements; a row of twenty is 3²⁰, which is three and a half billion, and a row is the easy case. The full game on an 8 × 8 board starts from a filled checkerboard and its position count is past anything this machinery approaches. So the honest description of what has been done is: a small, complete census, at the bottom of an exponential, of a game whose general answer nobody has.

That is not a disappointing position to be in. It is the ordinary one for this subject, and the reason what “solved” means has to be said carefully every time — a complete answer for positions of a stated size is a different claim from a complete answer for the game, and only the first is ever on offer here.

The surprise: a game that resists its own theory #

Put the two halves of this essay side by side and there is something odd about them.

Kōnane produces every value the theory has a name for. It is, in the vocabulary sense, an ideal example — richer than Domineering, richer than Toads and Frogs, and about as rich as a game gets. And it is unsolved, in one dimension, on rows of a few dozen squares.

Those two facts are usually antagonists. A game with rich values is normally a game whose values can be computed and combined; that is what having values is for. Kōnane has the values and refuses the combining, and the refusal is not incidental — it is the same property that makes the values rich.

A hop can enter an empty region and leave it again, which is why no gap is a wall. It is also why a position’s options reach further than they do in a game where pieces stay put: a stone three squares away is a live option, so the option sets are larger, so the values are more varied. The mechanism producing the vocabulary is the mechanism blocking the decomposition.

That is a general shape worth naming, because it explains a pattern across this whole site. The games whose theory is cleanest — Nim, Hackenbush, Cutcake — are the ones whose positions fall apart most readily, and their values are correspondingly plain. Nim’s values are integers. Hackenbush’s are dyadic rationals and nothing else in the green case. The games with the interesting values are the ones that hold together, and holding together is exactly what makes them hard.

So Kōnane is not an unlucky game. It is an instance of a trade-off: richness of value and ease of decomposition pull against each other, and a game cannot be at both ends of it. The theory reaches furthest into games it can take apart, and the games it can take apart have the least to say.

What the picture cannot show #

The figures here are rows, and the game is played on a rectangle.

A two-dimensional board has hops in four directions rather than two, and the interaction between rows is exactly the thing that makes the game hard. Everything above about which values appear survives the restriction — a row is a legal position of the full game with everything else burnt away — but nothing about how often they appear does, and nothing about play on a real board does either.

The second thing not shown is the opening. Kōnane starts from a full checkerboard, and the first two moves are special: Black removes one of their own stones and White removes an adjacent one, which is the only non-capturing move either player ever makes. Nothing here models that, because a full board of any size is far past the evaluation, and every position drawn above is a middlegame or an ending arrived at by assumption rather than by play.

The convention, named #

Kōnane is normal play, and this is worth dwelling on because it is the essay’s opening claim.

The convention is not a modelling choice made here. It is in the rules of the game: a player who cannot capture loses. Nobody involved was choosing between normal and misère conventions, or knew there was a choice, and the one they have is the one under which almost every theorem in this subject holds.

The reason that is more than a coincidence is worth stating. Normal play is the convention that arises when a game is about running the opponent out of moves rather than about accumulating something, and games of that shape are common because they are easy to adjudicate — there is no counting at the end and no argument about the score. Games that keep score needed a different theory and got one much later.

Where the ladder goes next #

konane opens here with one rung and a clear direction for the next.

The obvious one is the two-dimensional game: the values of small rectangles, the point at which a board falls into independent regions, and whether the decomposition that fails in one dimension can be made to work in two. That is a real piece of work rather than a variation on this one, because the search grows by a factor of three per square and the positions stop being drawable.

The rung this essay would most like to see, though, is comparative. Kōnane is one old game that turns out to hold the whole vocabulary. Two would be a pattern.