Friday, December 3, 2010

Alleviating (some) Partiality Confusion

Perhaps it would be best for me to tell future classes: if at any place in a game, one player has a move that the other doesn't, then the game is not impartial. This seems like something very intuitive that one should be able to impart with a quick sentence, but there are many layers of confusion on this point. Perhaps one has to see many examples of impartial games first!

I often see an impartial game defined as one which has the same options for both players. Does that mean {1 | 1} is impartial? No... this is game is in Positive (L), and all impartial games should be in Fuzzy (N) or Zero (P).

In our text, impartial games are defined as follows (page 135 of Lessons in Play):
"If for a game and all its options, the left options equal the right options, then the game is dubbed impartial."

There could be some confusion here also. Is G = {{1|1} | {1|1}} an impartial game? Certainly the left options equal the right options. Additionally, of the options of G, the same is also true: the left options equal the right options. However, to see that it is not impartial, we have to go down one level further (the options of the options of the options). The necessary recursion of a definition of an impartial game may be implied, but it is probably important to note that the options must all also be impartial.

Is there some middle ground here? On Tuesday, I referred to the game {-1 | 2} being equal to 0, though not impartial. Being an element of either the class N (fuzzy) or P (zero) does not make a game impartial. Other games that aren't impartial:

G: {0 | 0, 1}. Even though G = * (0 dominates 1 for the right player) the options aren't strictly the same.

G: {0, 1 | 0, 1}. Even though the children are the same, those children are not impartial.

G: {X | -X} (where X is a set of games). Here, even though this game MUST be in either N or P, and any strategy for Left translates into a strategy for Right, the game is not impartial.

G: {* | *, *2}. G is in Zero, and all options are impartial, but Left does not have *2 as an option.

For one I'm not sure about, what about the Domineering game consisting of three open boxes in an L-shape? Both players can move to 0 as their only option (so the game is equal to *) but they move there in different ways. Is this game considered impartial?

I apologize above for not figuring out how to use nice and fancy letters for much of my notation!

Have a great weekend! Next week is our last week of classes here and will be my last week posting until next semester.

8 comments:

  1. The impartiality of a game depends on its form, not its value (and certainly not its outcome class). For example, your domineering position is not impartial, because the players have different moves (that each of those moves has the same value is not important). However, that same position played under the rules of cram is impartial.

    You could also give the definition as: a game is impartial if the Left options are identical to the Right options and every option is impartial.

    ReplyDelete
  2. Neil,

    your definition is in line with what I would have guessed, except that I would probably have used the word "equal" instead of "identical". I really expected that Domineering example to be considered impartial!

    Do you know of a good source for a definition of the form of a game? Have you seen a great version of the definition of impartial in some literature (besides your comment)?

    ReplyDelete
  3. I disagree with Neil: the domineering position should be considered impartial. The domineering position is just a way of visualizing {0|0}; the fact that it's played with such rules on such a board makes no difference at all to the game. To say that this domineering position is partizan is very analogous to saying that nim is partizan because different hands take away stones, but I don't think anyone would do that. But, to my mind, the confusion arises when we try to replace a game (meaning a pair of options, which are nested, and so forth) with some more concrete representation of the game, such as a domineering board or a Hackenbush figure.

    ReplyDelete
  4. abagoffruit,

    Do you agree with the rest of the examples? Is there somewhere these definitions are precisely nailed down?

    ReplyDelete
  5. Yes, I agree with you on the rest of them. I don't know if the definition is written down carefully enough to make it obvious whether the domineering example is impartial, but the definition in Lessons in Play (the left options and the right options in any position are the same) is probably the best one anywhere. It certainly solves the rest of them.

    Having said that, it might be beneficial at times to act as though moves that are really stupid are actually illegal; if that were the case, then {0|0,1} would suddenly become an impartial game, even though strictly speaking it's not, of course. Similarly, when we know how to play Northcott's game properly, we're likely to forget that it's strictly speaking a partizan game, since in every meaningful way, it's just like nim.

    ReplyDelete
  6. abagoffruit,

    I also like the definitions in Lessons in Play, except with Neil's addition that all those options must also be impartial. I think that would really solidify any questions.

    Perhaps we need a definition of "impartialish" for those games that act like impartial games, such as you mentioned above, under optimal play. It's a bit odd to have a notion that doesn't persist when adding dominated options, etc. Sadly, impartial games are equivalent to non-impartial games.

    ReplyDelete
  7. That any option must also be impartial follows from the Lessons in Play definition: by "position," we mean some game that can arise by playing the game to some depth.

    ReplyDelete
  8. abagoffruit,

    I think you are referencing a different version of the definition from the book, but one that seems better. Earlier, I quoted the "definition" on page 135, but the earlier definiton on page 41 is actually labelled as such:

    Definition 2.10: A game is impartial if both players have the same move options from any position.

    Using your explanation of the word "position", then I think this is the correct version. :)

    ReplyDelete