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!
Red, Yellow, and Green Hats
4 weeks ago
I think you've spotted the issue yourself in the paragraph beginning "This is unfortunate ..."
ReplyDeleteThe point is that the traditional sum operation for games (disjunctive sum) is not about the winning/losing rules at all -- it's about the tree of moves in the sum and how it's related to the tree for the summands. As it happens under "normal play" this leads to a rich theory, but "normal play" is imposed afterwards.
Even in the traditional case why does normal play in the sum proceed until there's no move available in either component? Why doesn't it end when there's no move available in one component?
I think that the non-mathy logic here is that both types of play here really revolve around "losing" and not "winning". Instead of phrasing things as "the last player to move wins", we can explain that the loser is a player who needs to make a move, but can't. This sort of solidifies the field a bit.
ReplyDeleteI do like this idea of sums where the game ends once there's no move in one of the components. This actually feels a lot more like some games such as Hex. A Hex game doesn't end because all the places to play are full, it ends because one of the players has completed their chain and fulfilled their goal. Is there any study of the theory of this sort of game?
Ah - it seems I should have read this post first in that it answers the question I posed over in part 3.
ReplyDeleteSome answers then:
From a technical standpoint, the end of a combinatorial game is not defined in terms of winning or losing but instead by the existence of a legal move. The usual form used in the analysis tends to be: If there are no legal moves available on your turn you lose (normal play) or win (misere play).
The game your are inadvertently playing here is the short disjunctive sum of nim heaps. As far as I'm aware, I'm the only person to have studied them and published any results. My thesis does extend to games like Hex, but I haven't studied it directly (in fact, I've left it as an open problem). Games like Hex have been studied from a very different angle under the heading of maker-breaker games.