I got some comments while I was gone, but I haven't even read them yet. No fear: they will be read! Currently I'd like to discuss another issue raised by my students as they continue to code up adding games together. I asked the following question in class:
If I add a misere game with a normal game, is the result misere?
Keep in mind that my students are not in a CGT course; they need to be able to process this information in order to elegantly determine who loses a game. They determined that, yes, the game is misere. When the game is over, that means that the last move from the misere subgame was made, and thus the last player should lose.
We then went about coding up the simple isMisere() function that each Game object should have. Someday I hope to talk more about programming this all up, but today is sadly not that day.
Instead, I realized there that there was still a problem. That sum is misere, but is very different than if it is a sum of normal play games, made to be misere. What do I mean with this?
Consider the sum of nim games (each of one heap) with values 1, 2 and 2, with the added property that the last game (one with 2 sticks) is a misere game. When determining whether the sum is misere, we find that it is. The last player to play will lose.
Now, however, consider the misere version of the sum of the same games, where none of those subgames is misere. Again, this is a misere game: the last player will lose. The games, however, are fundamentally different, causing strategies between the two to be unequal. In the first version, taking the non-misere pile of 2 results in a win; the opponent will soon be forced to take that last stick from the misere pile. In the second version---where the whole game is misere, but none of the subgames are---taking a pile of 2 is a losing move; the opponent will just take the other pile of 2 sticks.
They are both misere, but on a different level. On a final, programming note: depending on how your misereness is implemented, these levels can be represented differently, either as a public or private property.
Perhaps there will be more on this later!
Jokes from the Audience
1 week ago
What might further complicate things is if there are multiple components who are treated as misere individually. The end of such a sum may have many individual moves left over.
ReplyDeleteFor example: heaps of size 3, 4 and 5 where the 4 and 5 are "misere" components. The game will end with the position 0,1,1. This is not an end position of a normal or misere game since there are two possible moves left.
If you want to treat misere to be a property of a given component, then the sum is just a sum and cannot be labeled as normal or misere. This is what happens when you consider the short disjunctive sum as you've described it.
The typical view, on the other hand, is that being normal or misere is a property of the game taken as a whole (not as a property of each component).
Totally. It seems very unsatisfying, however, if we can't take the sum of two games just because one of them has been classified as "misere". I definitely wanted my students to be able to add them. Thus, their programming challenge is how to determine when the game is over and which player has won.
ReplyDeleteTo do this elegantly, they need to be able to determine whether the whole game is misere. They have to do this because they have to let misere losing turns play out.