Analysis of Misere Nim?

Question

My friend likes to impress people by playing 3-5-7 which has three piles of counters of sizes 3, 5 and 7. You can remove any number of coins from a single pile, the last player to move loses.

ooo
ooooo
ooooooo

This is a winning position for the first player, but With a solid understanding of the game tree she wins nearly every time playing second. She says, it reduces to knowing a few winning positions.

Two piles of the same size is second player win, in the jargon of Combinatorial Game Theory. Here is the pile (5,5).

ooooo
ooooo

If first player moves to (5,n) for n > 1, second player can imitate on the other pile, moving to (n,n). However, if first player moves to (5,1), second player moves to 1 and wins.

The other winning positions she remembers is (3,4,1) and (4,5,1). She can win once she recognizes these positions. Eventually (after losing many times) I told her that (n, n+1,1) is a losing position for any n...

---

If our game were played in normal play convention (player moving last wins), but real life Nim is played as a misere game. Probably the analysis is similar to normal-play Nim with some modification.

Recently there was a theory of Misere quotients where each game has a commutative monoid assoicated with it. What does that monoid looks like here? Is it finitely generated?

Answer 1

Let $\oplus$ denote the bitwise xor operation on natural numbers. It is both well-known and easy to verify that a Nim position $(n_1,\dots,n_k)$ is a second player win in misère Nim if and only if some $n_i>1$ and $n_1\oplus\cdots\oplus n_k=0$, or all $n_i\le1$ and $n_1\oplus\cdots\oplus n_k=1$.

If I understand it correctly, this translates to the following structure. Let $A=(\omega,\oplus,0)$ (in other words, $A$ is the direct sum of countably many copies of the two-element abelian group), let $A_0=\{0,1\}$ be its submonoid, and let $B=(\{0,1\},\lor,0)$ be the two-element semilattice. Then the underlying monoid of the misère quotient of Nim is the submonoid $Q=(A\times\{1\})\cup(A_0\times\{0\})$ of the product monoid $A\times B$, the misère quotient itself being $(Q,\{(0,1),(1,0)\})$. If $(n_1,\dots,n_k)$ is a Nim position, its value in $Q$ is $(n_1\oplus\cdots\oplus n_k,u)$, where $u=0$ if $n_i\in\{0,1\}$ for each $i$, and $u=1$ otherwise. $Q$ has (as a commutative monoid) the infinite presentation $\langle \{a_n:n\in\omega\},b\mid a_n+a_n=b+b=0,a_n+b=a_n+a_0\rangle$. Finitely generated submonoids of $Q$ are finite, hence $Q$ itself is not finitely generated.

(Note that the monoid corresponding to normal play Nim is just $A$.)