Again, I have assigned a new project to my software design class, and again I ran into a bit of a descriptive challenge. This time my class must redesign the project to include game sums. It's not too bad to describe the rules of adding two games together (each turn, a player moves on one of the two boards that were added together) and who wins (the player that makes the last move in all game boards).
...until you add in misere games. These games are phrased in terms of the loser, not the winner. The most simple way to "normalize" them, then, is to assume that players cannot make that final move in the game. Thus, misere nim can be rephrased as nim where you are not allowed to take the final "stick". Now this version acts as a normal play game.
So what happens when you have two games, one of which is misere, and you add them together? When, exactly, does one player lose or win? When is the game over?
We can state it as follows: the game ends either whenever a player makes the last play in one of the misere subgames (that player loses) or when a player makes the last play overall (only if none of the games were misere; that player wins).
The interesting point is that this is not equivalent to just counting that "misereness" towards the entire game. For summing a normal with a misere game, you cannot just add the two non-misere versions together and then state that the last person to play loses in the sum instead of wins. Instead, the misereness of each particular subgame must remain attached to that game.
This is unfortunate, because there is no way to construct every misere nim game (namely those with more than one pile) as a sum of single nim heaps, each of which might be misere. Instead you have to sum from normal piles then declare the whole thing to be misere. (This does put a good spin on the structure of the code my class has to come up with, though!)
Strangely, the definition of this adding takes a second seat to straight up analysis in textbook descriptions of misere games. This is my first natural question: how do we add misere games to other games? Instead, the analytical side seems to come up first: how do we evaluate sums with misere games? For gamesters, that is certainly the most pressing question, but for recreational players, this is a bit frustrating.
Unfortunately, I've run out of time! I hope to continue with this Friday, though!
A Domino-Covering Problem
2 months ago