12
$\begingroup$

I'm interested in $5$-player nim (it will become clear why $5$). Individual players - which I'll identify with the numbers from $1$ to $5$ - make moves as usual, with the move order going $... \rightarrow 1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 5\rightarrow 1 \rightarrow ...$ (but the starting player is not determined ahead of time). A nonempty proper subset $S$ of $\{1,2,3,4,5\}$ is a winning coalition iff there is some choice of strategies for the players in $S$ such that, no matter who goes first and no matter what moves the players outside $S$ move, if the players in $S$ use their strategy then the first player to have no legal move will not be in $S$. (Note that there is no "winning player" as such, only a losing player. But "non-losing coalition" doesn't roll off the tongue as well.)

Say that a nim board (= initial setup of piles of stones) is strange if every $2$-element set of players is a winning coalition. (Obviously some $1$-element set of players must not be a winning coalition, and $5$ is the smallest set of players where $2$-element coalitions are strictly less than half of the total players.)

Question: do strange nim boards exist?

I've done a quick computer search that's turned up nothing, but that search was limited to boards with at most five piles and at most six stones per pile (and even then it only partially searched that gamespace).

Improve this question
$\endgroup$
14
  • 3
    $\begingroup$ @usul: if I understand correctly, there is no designated winner, just a designated loser. So if $\{1,2\}$ and $\{3,4\}$ are both winning and happen to play their respective strategies, then $5$ is bound to lose. $\endgroup$ Commented Dec 23, 2024 at 9:21
  • $\begingroup$ Maybe the title should reflect the intention by saying can every 2-player coalition avoid losing? $\endgroup$ Commented Dec 23, 2024 at 17:27
  • $\begingroup$ @AnthonyQuas Fair enough, updated! $\endgroup$ Commented Dec 23, 2024 at 20:50
  • 3
    $\begingroup$ Ok, I guess strange boards do not exist for 6 or any even number of players, because any nim board is either a win for the odd player or the even player, so a coalition that only plays on even rounds (respectively, odd rounds) cannot guarantee to win. $\endgroup$ Commented Dec 23, 2024 at 22:22
  • 2
    $\begingroup$ I think I can show (by an ugly case distinction) that every alliance of 3 non-consecutive players wins on every board with 7 piles of size $2$ and arbitrarily many piles of size 1. Since any three player-alliance can reduce a board with sufficiently many piles of size $\geq 2$ to such a board, this would mean that there is an upper bound on how many piles of size greater than $1$ a strange board can have. $\endgroup$ Commented Jan 1 at 9:48

2 Answers 2

Reset to default
3
+150
$\begingroup$

This is still a heavily computer-assisted argument, and also really long and annoying, but I think I have a complete proof that strange positions don't exist. I'm going to use the same notation as Mikhail's answer. Also, the "value" of a position is the set of $2$-player coalitions for which that position is winning, just because that concept is annoyingly long to express otherwise.

This Rust code checks the following properties for positions of the form $1^a2^b3^c4^d5^e$ with $(a,b,c,d,e) \leq (20,10,6,3,3)$:

  1. None of them are strange.
  2. If $2 \leq a \leq 15$, then the position has the same value as $1^{a+5}2^b3^c4^d5^e$. (It isn't particularly necessary to check this property until 15, but I didn't want to work out exactly how far was necessary and risk getting it wrong; the program only takes a few seconds to run, so it's not that important).
  3. If $b = 10$, or $c = 6$, or $d = 3$, or $e = 3$, the position is not winning for any 2-player coalition.
  4. If $e \geq 1$, it has the same value as $1^a2^b3^c4^d5^{e-1}6$.

Property 2 of the above list holds for all $a$, by a simple inductive argument, using the computer validation for $a \leq 15$ as the base case: any move from a position $1^{a+5}2^b3^c4^d5^e$ has a corresponding move from the position $1^a2^b3^c4^d5^e$ to the same position except with $5$ less piles of size $1$, which by the induction hypothesis has the same value; and so it has the same value as well, because the value of a position is determined by the values of each position that it can move to.

Property 3, combined with the above result extending it to all values of $a$, implies that any position with all stacks of height at most $5$ outside the range my code checked is not winning for any $2$-player coalition: play in such a position must eventually reach one of the "edges" of the range, which are all covered by property 3, and no $2$-player coalition can have a winning strategy once that happens. (This could also be framed as another inductive argument, but I find this approach easier).

A similar argument, combined with property 4, establishes the same thing for positions with one stack of height $6$ and otherwise all stacks of height at most $5$: either the stack of height $6$ is reduced, leaving the position in a situation covered by the above paragraph, or that never happens and it hits one of the edges (although note that in this case the edge is $e = 2$ rather than $e = 3$).

Now we extend this further: all positions with stacks of heights $> 5$ have the same value as the position where all of these stacks are reduced to 5, by induction. Call the position $P$, and the reduced position $Q$. By the induction hypothesis, each move from $P$ has the same value as the corresponding move from $Q$, so the only difference is that moves in $P$ like "reduce a stack of size $6$ to size $5$", which (by the induction hypothesis) lead to positions with the same value as $Q$, have been removed. But this means it has exactly the same set of move values as the position obtained by increasing one of the $5$s in $Q$ to a $6$, which by the previous paragraph has the same value as $Q$. So $P$ and $Q$ have the same value.

To summarize, here is a "complete" description of how to compute if a position is winning:

  • Reduce all stacks of size $> 5$ to stacks of size $5$.
  • Repeatedly remove $5$ stacks of size $1$, until there are at most $6$.
  • If there are (at least) $10$ stacks of size $2$, or $6$ stacks of size $3$, or $3$ stacks of size $4$, or $3$ stacks of size $5$, the position is not winning.
  • This leaves only finitely many cases.

For a set $S$ of two-player coalitions, here is a game in which $S$ is exactly the set of two-player winning coalitions. Each player declares the coalition that they are part of, which must be either an element of $S$, or a three-element set whose complement is not in $S$. The first player who is not in a valid coalition (meaning everyone in the coalition they selected also selected that coalition) loses. This is a generalisation of the construction in my comment, and demonstrates that all $1024$ possible sets of $2$-player coalitions are possible values for $5$-player games.

Only $55$ of these $1024$ values occur in $5$-player Nim. This is a pretty small number, so it seems plausible that in some sense the nonexistence of a strange position in particular is just a lack of an odd coincidence, rather than anything with a particularly deep explanation.

Improve this answer
$\endgroup$
3
  • $\begingroup$ This is quite nice! Tangentially, I'm not familiar with Rust - can you recommend a good introduction? $\endgroup$ Commented Jan 2 at 9:05
  • $\begingroup$ Chatgtp is good at explaining it. I got from 0 to working program for my research in a couple of hours by discussing code with it. $\endgroup$ Commented Jan 2 at 9:09
  • $\begingroup$ @NoahSchweber I think "The Rust Programming Language" is a pretty good introduction - it assumes that you already know about programming (in some other language), but in the question you said you did a computer search so I'm guessing that's probably fine. There are also various resources here. $\endgroup$ Commented Jan 2 at 9:46
5
$\begingroup$

Disclaimer: at the moment this is a partial answer since at least one key claim is unsubstantiated, despite being heavily suggested by computational evidence. Subject to updates if I manage to find a reasonable explanation.

Some notation points: we assume that between moves the players' indices are rotated such that the player $1$ is always next on the move (after the move $1$ becomes $5$, $5$ becomes $4$ and so on). We write $ab$ for player coalitions $\{a, b\}$, and $a^x b^y \ldots$ to denote boards "$x$ heaps of size $a$, $y$ heaps of size $b$, ..." I expect there to be no confusion between coalitions and nim boards.

Answer: I'm strongly convinced strange boards do not exist, and further, no board is simultaneously winning for coalitions $12, 23, 34, 45$. I was not able to find any kind of high-level strategic argument, and the perhaps the reasoning below is somewhat unspectacular (not to mention, incomplete at the time). For the computer evidence I have, I struggle to present it in a way that would be suitable in a human-readable explanation, and invite anyone interested to replicate my findings independently.

It is worth noting that, after generalizing to arbitrary DAG games, strange configurations do exist (see bottom of this answer), implying that the result is, at least to some extent, nim-specific, and abstract game-theoretic arguments are unlikely to exist.

Claim. No nim-board is winning simultaneously for coalitions $12, 23, 34, 45$.

We start by enumerating winning boards for the coalition $45$. Intuititevely, $45$'s actions are subtantially more limited than $123$'s, at least for boards with high degree of freedom. Running a computer analysis for boards of (up to) 10 heaps of size (up to) 10 yields the following:

Sub-claim 1. All boards winning for $45$ are of the form $1^{5k} + A$, where $A \in \{-, 1, 2, 1^2, 2^4, 2^33, 1^42, 1^43, 1^32^2, 1^32^5, 1^32^43, 1^22^6, 1^42^5\}$.

Limited to boards of the form $1^x2^y3^z$ with $y \leq 6, z \leq 1$, one can properly establish this by computer-assisted induction (again, I wasn't able to find any kind of nice argument). There should be general arguments for why boards containing $2^7$, $3^2$ or a heap $x \geq 4$ are always losing for $45$, although I believe those are likely to contain high amount of case analysis as well.

If we subscribe to believing Sub-claim 1, proving the rest amounts to finite amount of computation, which yields the following.

Sub-claim 2. All boards simultaneously winning for $34, 45$ are of the form $1^{5k} + A$, where $A \in \{-, 1, 2^4, 1^42, 1^32^5\}$.

Sub-claim 3. All boards simultaneously winning for $23, 34, 45$ are of the form $1^{5k}$.

Since $1^{5k}$ is losing for the coalition $12$, the main claim follows.

Strange DAG game. We argue that position $14$ of this DAG is winning for all 2-player coalitions.enter image description here

To change the mood of the answer a little bit, here's a strategic proof.

  • Starting at positions $1, 2, 3$, the losing player is forced.

  • Any 2-player coalition containing $1$ can win from any position among $4, 5, 6$. Indeed, $1$ is not in danger of being left with no moves. Choosing between two options of the remaining number of moves, he is able to save his partner from losing.

  • Position $7$ is winning exactly for those 2-player coalitions $C$ that contain either $1$ or $2$.

    • If $2 \in C$, he will win on the next move from any of $4, 5, 6$.
    • Otherwise, if $1 \in C$, he still can't be the one to lose in the end, so he can choose among $4, 5, 6$ to deprive the opposition of the only option that makes his partner lose.
    • Finally, if $1, 2 \not \in C$, the opposition forcibly wins by moving to position $1$ in 2 or 3 moves.

  • Any non-consecutive 2-player coalition wins from position $10$. The game will reach position $7$, and a non-consecutive coalition loses if it becomes $35$ by then. Depending on whether it takes 1 or 3 moves to get to position $7$, the potentially losing non-consecutive coalitions are $14$ and $13$, which can both avoid losing since they are on the move.

  • Still starting at position $10$, coalitions $12$ and $15$ win by choosing the correct route to $7$, and coalition $34$ will be happy to reach $7$ by any route to become either $23$ or $15$.

  • All 2-player coalitions except $45$ win starting at position $12$.

    • All non-consecutive coalitions will be happy to move through position $10$, and the only coalition unhappy to move through $7$ is $14$, who is luckily on the move.
    • All coalitions $12$, $23$, $34$ will by happy with the straight route to $7$, which $12$ is able to make happen. If the route goes to $10$ instead, $23$ and $34$ become $15$ and $12$ by then, and still win.
    • Coalition $15$ will prefer to go through $10$, becoming $34$ by then, which is a win.

  • Finally, all 2-player coalitions win starting from $14$. Coalitions in danger of becoming $45$ by the time position $12$ is reached are $15$ and $12$, which both can happily avoid it.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ Here's a simpler presentation of a strange DAG game ("simpler" in the sense of "less words", it probably has more nodes). Each player, on their turn, chooses some other player. After every player has chosen, the losing player is the first player who is not in a pair of two players who both chose each other; such a player must exist because the number of players is odd. Each 2-player coalition is winning by simply both choosing each other. (We can choose who the losing player is by having a chain of forced moves of appropriate length before the game ends.) $\endgroup$ Commented Dec 31, 2024 at 16:51
  • $\begingroup$ @pastebee Good point, that is indeed much simpler, thank you! Not sure what I was going for when trying to find the smallest graph example, but here we are. I'll still leave it in for now. $\endgroup$ Commented Dec 31, 2024 at 16:57
  • $\begingroup$ The "strange DAG game" was actually the motivation for this question (although my own construction was basically @pastebee's comment): if the answer to this question is that no strange nim games exist, then Sprague-Grundy fails for more players in a particularly strong way. $\endgroup$ Commented Dec 31, 2024 at 21:47

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.