The third and final post on impartial games is out. Nothing to crazy, just some more in-depth examples of the Sprague-Grundy theorem in action.

· · Web · 2 · 0 · 1

@FreddyR I thought it was "break"? Like break a pile into two pieces?

If you haven't seen it already I have a paper on subtraction games that you might be interested in:

@FreddyR Also, here's a research question I don't know the answer to. Many two-player games are either PSPACE-complete or EXPTIME-complete, mostly depending on whether there is a polynomial bound on the number of moves. Is it possible to prove hardness of this type for a subtraction game with a single pile of stones? There's a result sort of like this at the end of but it's for a generalized kind of game "subtraction with hotspots" not a pure impartial subtraction game.

@11011110 It is break, apparently I can't spell. 🤦‍♂️ Will definelty give the paper a read!

Sign in to participate in the conversation

The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!