Monday, January 18, 2010

Double Misere

Is Chomp actually a misere game? Naturally, it seems easy to describe it as such: there is a grid of cookies, and if you have to take the upper-left cookie (or just take it on a whim) then the game is over and you lose. That cookie is poisonous, after all!

When I first heard it, however, it was described using normal play: you just weren't allowed to take that last cookie.

Sometimes this is how misere games are described: that last losing move just isn't an option. Strategies for those games are then equivalent to the misere description. You can no longer make that last move, so the current final move wins the game.

If we consider more flipping between misere and normal play, this is a bit nicer. Before, if we consider Chomp to be a misere game with the poison cookie, then flipping to normal play makes the game extremely trivial: eat that upper-left cookie and win the game instantly! Great!

If instead we consider the normal-play version where we cannot take the upper-left cookie, and we toggle the misereness, the game might be slightly more interesting. Here, a player loses if they take the last-remaining non-upper-left-poison cookie. This game is not as trivial as the other (how trivial is it? I have no idea!).

We could then convert this misere game into an equivalent normal-play game by removing all moves that are leaves on the game tree. Now we have a game which ends when two cookies are left: the top-left cookie and either the one directly beneath or to the right of it.

This is different than just toggling the misereness twice: we are building a new game by twice rewriting the misere-version of a game as a normal-play game. Otherwise, we would be left with the original game.

No comments:

Post a Comment