Follow me down the rabbit hole from trick-taking games to the Sprague–Grundy theorem. Nim, impartial games, perfect information, and Grundy values! Oh my!
Very much appreciate the breakdown of the game (Nim.) When I saw the word, I immediately flashed back to sixth grade (the last time I played it or heard the word out loud - and that was over 45 years ago.) Thanks also for defining terms - I got a lot of the article (even a potential idea for incorporating Nim at it's most basic into a real world puzzle for one of my projects :) )
Nim! Super nostalgic from me – it was ages ago that i took a game theory class, but i had a lot of fun ^^ i don't think we actually covered the Sprague–Grundy theorem, so that was cool to learn about :) and Sprouts, and lots of things in here :) game theory is such an interesting field ^^ when i was at a mathematical biology conference this summer, i went to a minisymposium about "Game theory in ecology and evolution" – here's a link to the details page, with further links to the individual speakers ^^ https://ecmtb2026.org/contributions/minisymposia/ms78
thank you for sharing, always interesting to think about <3
I thought you might enjoy this one! And "Game theory in ecology and evolution" sounds fascinating, though I must admit I barely understand all the complexities! :)
The closest I came to an impartial game in my collection is ZERTZ of the GIPF series. It has most of the required properties - the pieces are owned by neither player, but I think it's not an impartial game because of the win condition. The game involves capturing marbles of different colours, capture 4 whites and you win the game, 5 greys, 6 blacks, or 3 of each.
I believe that the fact that the game state must include how many marbles you currently have captured breaks the impartial nature of the game, because if there is a capture available that would win a white marble, and I have already captured 3 but you have only captured 2, then the game is won for me if it my turn but is not won for you if it your turn.
“That said, every two-player, normal-play, impartial game with perfect information can be theoretically reduced to the same behavior as a single-pile game of Nim.”
Even sticking with nim — not trying to generalise — this had me scratching my head. I was having trouble getting past all one-pile nim games being first player victory, which is not true of all nim games (e.g. 2 piles of 2 is 2nd player victory).
Am I right in thinking that the key to this is that a single-pile nim game can have *zero* stones (a losing position for the person to play and nim-sum = 0) or n stones, where n > 0 (a winning position for the person to play and nim-sum = n)? Then your non-carrying binary addition can get you non-empty multi-pile games that are equivalent to the zero-stone one-pile game, and we are off to the races. (Obvious link: <https://en.wikipedia.org/wiki/Nim>)
As a (non-maths, clearly) grad student in the days before the world wide web, I saw Last Year at Marienbad and covered sheets with scrawl trying to prove first player victory for the nim game played in the film. IIRC (and don’t put money on that), it worked. I stole an idea from an article I read about how the four-colour problem was tackled, having missed all this prior art.
Very much appreciate the breakdown of the game (Nim.) When I saw the word, I immediately flashed back to sixth grade (the last time I played it or heard the word out loud - and that was over 45 years ago.) Thanks also for defining terms - I got a lot of the article (even a potential idea for incorporating Nim at it's most basic into a real world puzzle for one of my projects :) )
That’s great! Thank you! 🙏
I recommend Quarto (by Gigamic) as a fairly fun and quick commercial impartial game!
I knew a reader would come through for me! Thanks! I’ll look that one up.
Nim! Super nostalgic from me – it was ages ago that i took a game theory class, but i had a lot of fun ^^ i don't think we actually covered the Sprague–Grundy theorem, so that was cool to learn about :) and Sprouts, and lots of things in here :) game theory is such an interesting field ^^ when i was at a mathematical biology conference this summer, i went to a minisymposium about "Game theory in ecology and evolution" – here's a link to the details page, with further links to the individual speakers ^^ https://ecmtb2026.org/contributions/minisymposia/ms78
thank you for sharing, always interesting to think about <3
I thought you might enjoy this one! And "Game theory in ecology and evolution" sounds fascinating, though I must admit I barely understand all the complexities! :)
Thanks!
The closest I came to an impartial game in my collection is ZERTZ of the GIPF series. It has most of the required properties - the pieces are owned by neither player, but I think it's not an impartial game because of the win condition. The game involves capturing marbles of different colours, capture 4 whites and you win the game, 5 greys, 6 blacks, or 3 of each.
I believe that the fact that the game state must include how many marbles you currently have captured breaks the impartial nature of the game, because if there is a capture available that would win a white marble, and I have already captured 3 but you have only captured 2, then the game is won for me if it my turn but is not won for you if it your turn.
“That said, every two-player, normal-play, impartial game with perfect information can be theoretically reduced to the same behavior as a single-pile game of Nim.”
Even sticking with nim — not trying to generalise — this had me scratching my head. I was having trouble getting past all one-pile nim games being first player victory, which is not true of all nim games (e.g. 2 piles of 2 is 2nd player victory).
Am I right in thinking that the key to this is that a single-pile nim game can have *zero* stones (a losing position for the person to play and nim-sum = 0) or n stones, where n > 0 (a winning position for the person to play and nim-sum = n)? Then your non-carrying binary addition can get you non-empty multi-pile games that are equivalent to the zero-stone one-pile game, and we are off to the races. (Obvious link: <https://en.wikipedia.org/wiki/Nim>)
As a (non-maths, clearly) grad student in the days before the world wide web, I saw Last Year at Marienbad and covered sheets with scrawl trying to prove first player victory for the nim game played in the film. IIRC (and don’t put money on that), it worked. I stole an idea from an article I read about how the four-colour problem was tackled, having missed all this prior art.
When it gets into the hardcore game theory math stuff, I'm as lost as anyone!
I noticed that Last Year at Marienbad caused Nim to have a resurgence in popularity for a while. Never saw the movie, but sounds interesting.
Thanks for your comment!
I loved Marienbad when I first saw it. I suspect that if I saw it again now, it might irritate, but it is definitely worth a look.