Three players and no answer

The two-player restriction is usually presented as a simplification, as though three-player games were the same subject with more bookkeeping. They are not, and the reason is worth stating before any computation.

With two players the game is zero-sum. What is bad for one is good for the other, so “play well” needs no further explanation: a player maximises, the opponent minimises, and backward induction has exactly one answer at every position. Every theorem on this site rests on that, all the way down to the fact that a position has a single outcome class.

Add a third player and it disappears. A player who cannot win still has moves, and nothing in the rules of the game says which of the other two should get the win instead.

What the conventions are #

Backward induction still works up to a point. At a position with no moves, the player before the mover took the last counter and has won; that much is the rule. At a position where the mover can move to something they win, they do; that much is rational.

The difficulty is the remaining case: the mover cannot win, and has to choose between two moves that hand the win to different opponents. Two natural rules:

• Downstream. Prefer the next player to lose, so the win goes to the player after them.
• Upstream. Prefer the previous player to win.

Both have a story. Downstream says a player punishes the opponent about to move against them. Upstream says a player rewards the one who has just given them the position. Neither is derivable from the rules of Nim, because the rules of Nim say only who wins and say nothing about how a losing player should feel about the two winners.

The sweep runs both over the same 71 positions — every three-heap position up to five counters a heap, and every two-heap position up to eight — and the two agree on 15 of them.

There is no third rule waiting to be found that both would accept. Any convention has to answer the same question, and the question is which of two opponents a losing player prefers to see win; the answer is a fact about the players and not about the board. A theory that wanted to avoid the choice would have to avoid the case, and the case is 56 positions in 71.

What agreement and disagreement mean here #

Fifteen agreements is not fifteen positions the conventions have settled, and the obvious explanation for them is wrong in a way worth recording.

The obvious explanation is that the choice never came up: the mover could win outright, so the tie-breaking clause never fired and both readings returned the same answer. That is checkable, and it fails. The mover wins outright in nine of the fifteen agreements — and in forty-six of the fifty-six disagreements, where it is therefore commoner rather than rarer. A root position at which the convention is never consulted still inherits its answer from sub-positions at which it was, so “the clause never fired here” says nothing about whether the two columns will match.

What does explain six of the fifteen is the one thing on this page that owes nothing to a convention.

So the fifteen are six theorems and nine coincidences, which is a much less comfortable reading than fifteen settled positions.

The 56 disagreements are the whole content. A position on which two defensible readings of “play well” name different winners is a position with no winner — not an unsolved one, an ill-posed one. And 56 of 71 is not an edge case.

The question that survives #

There is one question about a three-player position that no convention touches, and it is worth isolating because it is the only thing here with an unambiguous answer.

Can a named player force a win against the other two acting together?

That is zero-sum again — one player against a coalition — so backward induction applies with two labels instead of three, and there is exactly one answer.

The answer is nobody in 65 of 71. The six exceptions are all positions where two heaps of one counter make the arithmetic trivial — a player can count the parity of the remaining moves and be certain — and every other position in the sweep is what Li called queer: a position with no player able to guarantee anything.

Those six are exactly the six explained agreements above, and the coincidence is not one. A forced win is a statement about every way the other two could play, including every way a tie-break could make them play, so a convention has nothing left to decide. Where the six positions live is therefore the only part of the three-player table that a two-player reader would recognise: a position, an answer, and no parameter.

That is the honest state of the subject. Two-player theory answers “who wins” for every position; three-player theory answers it for a handful and reports the rest as depending on the players.

The generalisation that does not generalise #

The nim-sum adds the binary digits of the heap sizes modulo two, and a position is a loss for the mover exactly when every column comes out zero. The natural three-player version adds the same digits modulo three.

It is a beautiful guess. It is not a theorem.

Fifty-four out of 71 is the shape of a rule that captures something and is not the answer. Li’s 1978 analysis shows what the base-three condition really does capture — it identifies positions from which a particular coalition structure holds — and it is not the outcome of the game under either convention above.

Notice also that the rule is being measured against one of the two conventions. Measured against the other it gets a different score, and there is no principled reason to prefer either measurement, which is the whole problem restated as a difficulty about testing.

What breaks first #

It is worth tracing which of the site’s standing facts survive a third player and which do not, because the damage is not uniform.

The game still ends. Termination is a property of the position graph and does not care how many players are walking it. Three-player Nim finishes, always, in at most as many moves as there are counters.

Backward induction still runs. Every position can be labelled, bottom up, with a winner — for each convention. What has gone is the uniqueness of the label, not the ability to compute one.

The sum theory has gone entirely. Two heaps of three-player Nim added together is not a sum of anything: a move in one component changes whose turn it is in the other, and with two players that is harmless because turn parity is the same everywhere. With three it is not — the component a player returns to has advanced by two turns, not one — and there is no disjunctive sum to speak of.

That third one is the deepest damage, and it is the least visible. The whole of this subject is the arithmetic of sums; three-player play removes the arithmetic and leaves a game tree.

Why two is the special number #

It is tempting to read all of this as a gap in the theory: nobody has yet worked out the right convention. That is not the situation.

The two-player case is special because “the opponent plays to win” and “the opponent plays to make me lose” are the same sentence. With three players they come apart, and so do half a dozen other sentences that read as one: playing to win, playing to stop somebody else winning, playing to come second if second existed, playing to be the one who did not lose last.

A game with a scoring rule would settle this — every player maximises their own score and the sentences separate cleanly — but scoring is a different subject, and counting at the end changes everything. Normal play has no score. It has a winner and two losers, and no way to rank the losers — which is the same shortage of information that makes misère play’s outcome pair insufficient, arriving from a different direction.

Who found it, and when #

Straffin’s 1985 note is the usual reference for the convention problem, and its argument is the one above: three-player games do not have well-defined outcomes without an assumption that is not in the rules, and different assumptions give different answers.

Li’s 1978 paper on three-player Nim is the source of the base-three rule and of the word queer for the positions nobody can force. Both papers are short, and neither claims to have solved anything — they are careful accounts of what goes wrong, which is the appropriate genre for the subject.

The interesting later development is the one that avoids the problem rather than solving it. Multiplayer games with scores have a well-developed theory, and so do games where coalitions are declared in advance. What has no theory is the case this page is about: three players, normal play, and no assumptions.

Two positions a reader can check at the table #

The smallest positions settle the question by hand, and the smallest pair of them settles it in opposite directions.

Three heaps of one. Nobody has a choice: every move takes one counter, and after three moves the counters are gone. The first player takes one, the second takes one, and the third takes the last and wins. No convention is consulted because no player is ever offered two moves that differ, and both columns of the table say the third player.

Heaps of one, two and two. Now the first player has choices, and so does everybody after them. Downstream says the first player wins; upstream says the second. Nobody can force a win against the other two together, so there is no third answer to appeal to — the position is queer, and the two columns are two readings rather than one right answer and one wrong one.

Those two positions are the first and the sixth of the whole sweep, and the five before the sixth all agree. So the ill-posedness is not a property of large or complicated positions: it arrives at the sixth-smallest position anybody could write down, and it arrives as soon as somebody has a choice they cannot win with.

The whole game tree of that position fits on a page, so the difficulty is not that it is hard to compute. It is that the computation needs an input the rules do not supply.

The queer positions, and what is left to say about them #

Sixty-five positions of 71 are queer, and it would be easy to treat that as the end of the discussion. It is not quite.

A queer position still supports statements. It may be that one player can force at least a draw in a sense — never being the one who loses — or that a pair of players has a joint strategy guaranteeing the third does not win. Both are well-posed questions with unambiguous answers, because both are coalition questions in disguise, and both are computable by the same two-outcome search used above.

What does not exist is a single label. The two-player theory’s central object is the outcome class: one symbol per position, computed once, and everything else read off it. The queer positions have no such symbol, and the honest replacement is a small table of coalition facts — which is not an outcome class and does not compose.

The absence of composition is the loss that matters. An outcome class is useful because the sum of two positions has one too, even when it is not determined by the parts’. A table of coalition facts about a sum is not a table of coalition facts about anything smaller.

What the solver computed, and how #

Nim positions are heap lists; the moves are the ordinary ones; the player before the mover wins at a position with no moves.

Each convention is a separate backward induction over positions labelled with whose turn it is. At a position the mover wins if any move leads to a position they win; otherwise the convention chooses between the two remaining winners, and the two conventions differ only in that line.

The coalition question is a third, independent search. For each of the three players, a two-outcome backward induction in which that player maximises and both opponents minimise — which is a completely different computation from either convention and shares no state with them.

The base-three rule is evaluated from the heap sizes directly and compared against the downstream convention’s verdict. The comparison is reported as a count with the convention named, because the score is a fact about a pair — a rule and a convention — and quoting it without the second half would be quoting a number about nothing.

What the two conventions are really about #

The names are convenient and they hide the actual disagreement, which is not about kindness or spite.

Downstream and upstream differ over what a losing player thinks the game is. Under downstream, a player who cannot win treats the game as a contest they have already lost and plays to make the next opponent lose too — a local, immediate preference. Under upstream, they treat the sequence of turns as a chain of obligations and repay the player who handed them the position.

Neither reading is more mathematical than the other, and neither is available from the rules of Nim, which say only that the player taking the last counter wins. The rules are silent because two-player games never needed the answer: with two players, a losing player has nowhere to direct a preference.

That is the point worth carrying past this page. The three-player problem is not a harder version of a two-player problem. It is a different question with an extra parameter, and the parameter is not in the game.

Why two players is the special case rather than the small one #

It is natural to read three-player theory as the two-player theory with an extra player bolted on, and the failures then look like difficulties of scale. They are not: two is the number at which several separate things coincide, and adding a third player breaks each of them independently.

Two is where the outcome is a bit. With two players and no draws, Left wins and Right wins are complementary, so one number settles the position and negation exchanges the two answers. With three, the outcome is a choice among three and there is nothing for negation to be.

Two is where a coalition is not a decision. A player who is not the mover has exactly one thing to do: play as well as possible against the mover. With three, the two non-movers may or may not cooperate, and optimal play stops naming a unique behaviour before any game has been analysed. That is not an unsolved problem — it is a missing hypothesis, and the two conventions on this page are two ways of supplying one.

And two is where a difference is a game. $G - H$ is $G$ plus the position with the players exchanged, which needs exactly the exchange that three players do not admit. Without it there is no comparison, no equality, no canonical form and no arithmetic — the same collapse misère play produces by a different route, arriving here from the number of players rather than from the ending condition.

So the honest summary is not that three-player games are harder. It is that the two-player theory is built on a coincidence of small numbers, and the objects it studies — values, sums, comparisons — do not have three-player analogues waiting to be found. What replaces them has to be a different theory rather than a generalisation, which is why the literature on this is thin and mostly about conventions.

Where the model stops #

Seventy-one positions: three heaps to five counters, two heaps to eight. That is a small sweep and it is enough, because the finding is a disagreement rather than an agreement — 56 counterexamples to the idea that the winner is a property of the position, where one would have done.

Two conventions is also a choice. There are others — a losing player might move at random, or prefer whichever opponent has been winning less — and each would give a third column. Adding them would strengthen the finding and would not change it.

And nothing here says three-player games are uninteresting. They are studied, under assumptions, and the assumptions are where the content is. What the sweep says is that the assumptions cannot be avoided, and that a page of theorems about three-player positions with no assumption stated is a page about nothing in particular.

Where the ladder goes next #

This rung establishes why the whole site is about two players. The rung above is the version with an assumption: fix a coalition structure or a scoring rule, and ask what of the two-player theory survives — which is a real subject and a different one.

Two neighbours are worth the trip. The first theorem, and the winner it declines to name is the two-player result that guarantees an answer exists, and reading it beside this page shows exactly which hypothesis is doing the work. And an outcome with no value behind it is the other place on this site where a position has no answer — for a completely different reason, and with the same consequence.