The same rule on a star

Kōnane was played on carved boards in Hawai‘i long before anybody wrote down a theory of games, and its rule for losing — the player who cannot move loses — is the convention the whole theory is built on, arrived at some centuries early. Evaluate a row of it and out come halves, quarters, stars, switches and infinitesimals: the entire vocabulary, from a game nobody designed to display any of it. That is a striking fact and also, on its own, an anecdote. One game holding the vocabulary might be a coincidence of one game.

The test is a second game. It has to be old, it has to be something people played rather than something a mathematician built, it has to share the rule for losing, and it has to be small enough to be solved completely rather than sampled. Mū tōrere meets every condition. It is a Māori game, recorded from the East Coast of the North Island of New Zealand, played on a star of eight points with a centre, four counters a side — and it is lost by the player who cannot move.

Solved, it answers the question Kōnane raised, and the answer is not the one the anecdote suggested. The vocabulary is not in the rule for losing. Mū tōrere has that rule and almost none of the vocabulary, because it has neither of the two things Kōnane has that the theory actually needs.

A board with one empty place #

The board is an eight-pointed star. Its eight points lie on a circle, each joined by a line to the points either side of it and by a spoke to the centre. There are nine places and eight counters, so exactly one place is empty at every moment, and every move is a counter sliding along a line into that one empty place. A counter on the circle may move to a neighbouring point; a counter in the centre may move out to any point; and a counter on the circle may move into the centre only if it has an opponent’s counter beside it on the circle. Nothing is ever captured. A player whose counters have no legal move into the empty place loses.

Accounts of the rules differ in small details, and this essay uses the version usually given, with Black moving first. The clause about entering the centre is the one that matters, and the next section shows why it is there.

Two things about these rules separate Mū tōrere from Kōnane before anything is computed. In Kōnane every move after the opening is a capture: a stone hops over an opponent’s stone and removes it, so the number of stones on the board falls by one with every move and the game must end. In Mū tōrere nothing leaves the board, and almost every move can be undone — a counter that slid from one point to the next can slide back on the owner’s next turn, if the opponent’s move left the place empty. So a game of Mū tōrere need not end at all.

That alone puts the game outside the theory of values. Every value the theory assigns is defined by recursion on the options of a position, and the recursion rests on a condition: that play cannot go on for ever. In a game where positions recur, the definition of a position’s value mentions the value of a position that mentions it back, and nothing bottoms out. Loopy games is the whole of what happens then, and its instrument is not a recursion but retrograde analysis: label the positions where the mover is stuck as lost, propagate backwards — a position is won if some move leads to a loss for the opponent, lost once every move leads to a win for the opponent — and whatever the propagation never reaches is a draw, because from it play can go on for ever without either side being forced to lose.

The board is small enough that this can be done on every position there is. Nine places, one empty, four counters of each colour on the other eight: nine choices for the empty place and seventy ways to arrange the colours, 630 arrangements, each considered once with Black to move and once with White.

The clause that keeps the first move from winning #

Start with the clause about the centre, because it is the first thing the computation explains. Drop it — let any counter move into an empty centre — and the game is over after one move.

At the start the only empty place is the centre, and Black’s four counters sit on four neighbouring points. If Black slides one of the two middle counters inward, the point it leaves is flanked on both sides by Black’s own counters, and the only other line into it is the spoke from the centre, which Black now occupies. White cannot reach the empty place from anywhere. White cannot move, and loses. Without the clause, Mū tōrere is a game the first player wins in one move, which is to say it is not a game.

With the clause, only Black’s two end counters — each sitting beside a White counter — may enter the centre, and the start is drawn. Dropping the clause changes the outcome of 120 of the board’s 630 arrangements, not just the start, but the start is where the difference is absolute.

This is the first surprising connection between the two old games, and it was not looked for. The two moves that are not captures found that Kōnane also needs a special rule at the start: its board begins full, so no capture is possible, and the first two moves are removals that happen nowhere else in the game. Both games carry a clause whose job is to make the opening work — Kōnane’s because its ordinary moves cannot begin from a full board, Mū tōrere’s because its ordinary moves would end the game at once. Whoever settled these rules, in two oceans, met a problem at the start and fixed it with one sentence about the first moves, and in both cases the sentence is the part of the rules a computation shows to be load-bearing.

Every arrangement, both ways round #

The theory’s first vocabulary is not the values. It is the four outcome classes the normal-play rule produces: a position is won by Left whoever starts, won by Right whoever starts, won by whoever moves first, or won by whoever moves second — lost, that is, for whoever must move. Every Kōnane position falls into one of the four, because every Kōnane game ends. Mū tōrere has a fifth possibility, the draw, and two half-way cases, where one mover can force a win and the other can only avoid losing.

The census is mostly draws. Of the 630 arrangements, 294 are drawn whichever player is to move. Another 208 are won by one mover and drawn for the other, and 96 are lost by one mover and drawn for the other. Only 32 are decided whoever starts — sixteen for each side — and up to the star’s sixteen symmetries those sixteen are a single arrangement. And two of the theory’s four classes are empty. No arrangement is won by whoever moves first; no arrangement is lost by whoever must move.

The second of those is the one to stop on, because it is the class the whole of impartial theory begins with. A position in which having to move is a misfortune — chess’s zugzwang, Nim’s zero, the P-position — is the most characteristic object the normal-play rule produces. Kōnane’s row of eight has 3,493 of them, more than half its rows. Mū tōrere has none. That is an observation from the census, not a theorem with a proof here, though the shape of the game suggests why: a player is stuck only when every line into the empty place comes from an opponent’s counter, and then the opponent, to move, always has a counter on one of those lines. So no arrangement is lost on the spot for both movers; that none is lost for both with best play further on is what the census observes and does not explain.

Dropping the clause changes this — 72 arrangements become wins for whoever moves first, the bracketed figure in the corner — but even then nothing is lost for whoever must move.

How soon a game can be decided #

The census counts every arrangement, including ones no game ever reaches. The useful question is what happens in play from the start, and the board is small enough to follow every line.

From the start, play can reach 1,180 of the 1,260 position-and-mover pairs — 86 of them up to symmetry — and the last of them is first reached after twenty-four moves. Of those 1,180, 208 are won for the player to move and 128 lost for the player to move; the rest are drawn with best play from there. The first won position appears four moves in, so the game can be thrown away on White’s second move.

A position won for the player to move is not a position anyone wants to be the other player in. It is reached only when the opponent has just made a losing move — and losing moves are scarce. In every drawn position that play can reach, the player to move has at most one losing move. Of the 844 drawn positions reachable from the start, 716 have none at all and 128 have exactly one; across all of them, 128 of 1,424 legal moves lose, about one move in eleven. Mū tōrere, played well, is a game of knowing the one bad move in each of 128 positions and not making it.

Five moves deep and no deeper #

When a mistake is made, the punishment is quick.

Every won position on the board, reachable or not, is a win in one, three or five moves, and every lost position a loss in nothing, two or four. There is no longer combination anywhere in the game. The longest, drawn above, starts from a position four moves into a game in which White has just made the losing move: Black steps a counter round the circle, White’s best reply comes out of the centre, Black slips into the centre beside a White counter, White moves again with nothing that helps, and Black’s third move seals the empty point between two of Black’s own counters with Black in the centre. The shape of every finish is the same as the first-move win the clause forbids — a hole surrounded by one colour — reached legally rather than at once.

This is a second thing Kōnane has that Mū tōrere lacks, and it matters for the vocabulary as much as termination does. Kōnane’s values are not only who wins; they are how much: a position worth two is two spare moves, a half is a fraction of a move, an infinitesimal is a margin smaller than any number of moves. Those quantities exist because a Kōnane position can be the sum of separate regions, each holding moves in reserve that can be spent later, and the theory’s numbers count that reserve. Mū tōrere’s board never splits. There is one empty place and every move is about it, so there are no separate regions, no reserves, no sums — and every decision on the board is visible within five moves of being made.

A draw that has to be known #

The start is drawn, and the census says most positions are drawn. It would be easy to read that as a game in which nothing much can go wrong. The last measurement says the opposite.

Let one player choose uniformly at random among its legal moves, and let the other play perfectly — take its fastest win when it has one and otherwise any drawing move. Summing exactly over every branch, the random player is certain to lose. As Black, moving first, it has lost within ten of its own moves a quarter of the time, within fifty moves 92 per cent of the time, and within a hundred moves more than 99 per cent; on average it lasts 23.6 moves. As White it does worse, losing within ten moves more than half the time and lasting 16.6 moves on average.

So the draw is a property of knowledgeable play, not of the board. One move in eleven from a drawn position loses, and a player who does not know which will find one sooner or later; a game that is drawn with best play and lost by every player who guesses is a game with a great deal of skill in it. This is also a fair description of what the people who played it would have had to learn: not a theory, but the 128 positions in which one move loses.

Two old games, side by side #

The comparison the Kōnane essay wanted can now be drawn in one table.

Same rule for losing, opposite results. Kōnane’s row of eight has 6,561 arrangements, all of which end, falling into all four outcome classes and carrying between them 36 distinct values. Mū tōrere has 630 arrangements, of which 598 are drawn for at least one mover; it has two of the four classes empty and the other two nearly so; and the question “what is this position worth?” has no answer, because worth is defined by a recursion that a game which can loop never lets finish.

Even the part of the theory built for games that loop does not reach it. Some loopy games have values all the same — a stopper, a game in which no sequence of alternating moves can go on for ever, can be given one, and the theory of on, off and their relatives is built on stoppers. Mū tōrere is not a stopper: from positions that arise in ordinary play, Black and White can trade six moves round the circle and through the centre and arrive back exactly where they began, and repeat it as long as they like. Its draws are outcomes with no value behind them in the strictest sense.

What the vocabulary was made of #

So the answer to the question Kōnane posed — is the vocabulary something the theory found in games or something games turn out to have? — is now sharper than either alternative. The vocabulary is not a consequence of the rule for losing. Mū tōrere shows a game can have that rule exactly and produce no values, no numbers, no infinitesimals and not even a single position where having to move is bad.

What Kōnane has, and Mū tōrere lacks, is two structural facts about its moves. Every move takes a stone off the board, so the game ends and values can be defined at all. And positions split into regions that do not interact, so a position is a sum and the theory’s numbers have something to count — moves held in reserve in one region while play goes on in another. The values are what those two facts produce under the normal-play rule; the rule on its own produces only outcomes, and on a board where moves can be undone, mostly draws. The ko rule is the same lesson from a third old game: Go needed a clause forbidding repetition before any of this could apply to it, and Mū tōrere has no such clause.

Counting conventions #

A position is the contents of the nine places with one empty; the two players are Black, who is Left and moves first from the start, and White, who is Right. A move slides one of the mover’s counters along a line into the empty place — along the circle, out of the centre, or into the centre when one of that counter’s two neighbours on the circle holds an opponent’s counter. A player with no legal move loses. Verdicts are by retrograde analysis over all 630 arrangements with each player to move: stuck positions lost, a position won when some move reaches a loss for the opponent and lost when every move reaches a win, everything unreached drawn. The number of moves to the end is the round of the propagation at which a position was labelled — the fastest win for the winner, the slowest loss for the loser. Symmetry classes are under the sixteen rotations and reflections of the star. The random player chooses uniformly among its legal moves; its opponent takes the fastest win available, else a drawing move. The Kōnane row is every arrangement of eight squares each empty, black or white, valued by the ordinary recursion and reduced to canonical form.

What a solved board leaves out #

The history here is thin and taken from common knowledge rather than from sources examined for this essay: that the game is Māori, associated with the East Coast of the North Island, and recorded by ethnographers in the early twentieth century. The rules used are the commonly given ones, and some accounts add restrictions on the first moves which would change the analysis of the opening and not the census of the board. Nothing here says how the game was taught or played, how strong its players were, or whether they knew the start to be drawn.

The comparison uses Kōnane’s row of eight because it is the census the Kōnane essays already rest on; a two-dimensional Kōnane board has fewer values per square, not more, and would make the contrast starker rather than different. And the claim about what the vocabulary is made of rests on two games. Two is a pattern only in the weak sense that the second game breaks the first’s anecdote in a way that names a cause; it is not a survey of traditional games.

Still open: a game that ends and never splits #

The two causes named here — that moves are irreversible and that positions split — are confounded in Kōnane and both absent in Mū tōrere, so these two games cannot say which matters more. A third old game with one and not the other would separate them. A game whose every move is irreversible but whose board never falls apart would end, would have values defined, and would test whether those values are rich — halves, switches, infinitesimals — or collapse to a handful of integers and stars, as a single region with no reserve to count might be expected to. The opposite case, a game that splits into regions and lets moves be undone, is what the theory of sums of loopy games is about, and a traditional game of that shape solved whole would say whether the draws of each region add up to a draw of the board or interfere.