Friday, November 6, 2009

Summing with Misere Games (continued)

As I mentioned before, it's actually a bit difficult to find a good definition of how to take game sums when including misere games. The rule that a player loses if they make the last move in a misere game seems a bit "tacked on". Then the overall rule is very inelegant: a player loses when they can either no longer make a move or when they make the last move in a misere subgame. The first part needs to be in there in case there are no misere subparts.

This sort of inelegant construction reminds me of defining exponents back in grade school. I understood that 10^2 was 10*10 = 100 and that 10^1 was 10. 10^0, though? Why is that 1? Why not 0? Sure it fits the pattern, but the definition is still a bit skewed. I reasoned that there had to be a patch. 10^x was really 1*10*...*10 instead of just 10*...*10. Thus, 10^1 was 1*10 and 10^0 is just 1. That patch made things made sense. Excellent!

I think a similar patch could be used here. Notice that if we add to any game a one-move misere component (say, a misere nim game with a heap of size 1) the strategy of the game doesn't change at all; a player with a winning strategy should never choose to take the stick in that heap. Now, whenever we sum games together, we'll also add in that one-move misere game, just like we also multiplied by 1 above. With this, we can get rid of the dual rules for who loses a combinatorial game. The rule is now just: whoever makes the final move in a misere subgame loses. While it's true that the boardscape may be polluted with lots of these single misere games, neither of the players will pay them any attention until the final turn.

Yes, this logic may just be trading one patch for another, but this very strongly hints that misere should be the basic form of play instead of "normal" play.

It's hard to agree with this, however, when we are painting games in such a pessimistic light, basing results off the loser instead of winner!

Okay, I still have more to say... hang on until Monday. :)


  1. In his PhD, Paul Ottaway looked at the misere version of the `short disjunctive sum' (chose a component and make a move). In misere, if a component has no moves then the next player choses this component and declares that since he has no move, he wins. The partizan version is even more interesting. Paul shows that there is a large class of games--he calls them regular--which behave like normal play games.

  2. In normal play, the short disjunctive sum is equivalent to the "everyday" sum, correct?

    That there exist partisan misere games that behave like normal play games in these sums is amazing! Time for me to schedule in some more reading :)

  3. Yes - normal play components behave the same under both the short or long (traditional) disjunctive sum.

    The fact that we study partisan games does not necessarily mean we are not interested in impartial games. Usually, it just means we have results which apply to both since impartial games are a strict subset of partisan games. In particular, impartial games under a short sum are "trivial" in some sense since I am able to show that they are regular and therefore equivalent to some other impartial game.