Wednesday, September 2, 2009

Nimania and a Previous Question

Previously, I wrote about a question I didn't know the answer to:
Question: If you add two instances of a game together which creates a new instance of the same game, does this imply that the game is easy?
I received an email from Aviezri Fraenkel about a potential counterexample: the game Nimania.

I'd never heard about this game before, but I was so impressed by the simplicity of it's design, I have already included it as part of a new project assignment for my software design course.

Directly from that specification:
Nimania is a game somewhat like Nim. The game begins with a single pile of sticks, as in Nim, and on turn 1. On turn k, a player chooses a pile. If that pile has only one stick it is removed. Otherwise, that pile loses one stick and k new copies of that pile are added to the game (thus, there are now (k+1) piles of that size). A player wins if they take the last stick from the board.
The description of a game state looks a lot like Nim. Add a description of this and another game of Nimania and you get a new one: a bunch of piles. Except, however, the turn counters aren't necessarily the same, and they won't ever be synchronized (making a move in one of the games doesn't increment k for both games, just for that subgame).

My question above is far from clear; what does it mean to "create" a new instance of the same game? My intuition is that it does it automatically and that no transformations are required. This is true of Nim: the state of a Nim game is just a collection of piles. Add two Nim games together and you just union their piles together. Done.

Aviezri Fraenkel sent me a bunch of different potential counterexamples to the question; time to get back to the reading! In the meantime, any more thoughts on the same question are very welcome!

No comments:

Post a Comment