Here's the final version. Thanks to Dan Hoey and Jeff Peltier for their many suggestions and corrections.
OVERVIEW FIRM AND FICKLE GAMES
This is mostly from
Winning Ways, Vol I p 424,
with additional background material..
INFORMAL DEFINITION Roughly speaking, a component is "tame" if we can pretend it is a sum of nim-heaps. A tame component is either "fickle" or "firm". It is "fickle" if we can pretend it is a sum of nim-heaps of size 0 and 1. Otherwise, it is "firm" (that is, if it has a nim-heap of size two or greater).
To
formulate this definition precisely, it is convenient to first define a number of other concepts:
"ruleset", "position", "children", "nim", "game", "component",
"successor", "normal-play outcome class", "misere-play outcome class",
Grundy numbers, and nim-values. Let's take them in order.
RULESETS, POSITIONS, CHILDREN, & NIM
First
we need to discuss the interwoven concepts of "ruleset", "position",
and "children". A position is a state of the game for which the ruleset
allows us to determine the children of that position -- that is, allows
us to determine the set of positions that can be reached in one move
from the original position. So a "ruleset" is an algorithm for
determining the set of children of a given position. Each position must
be describable by
a finite ASCII string, and it must not be possible for a game to
continue forever. Formally, a ruleset is a function
P --> FiniteSubsets(
P) where
P is a countable set of positions (this must be the set of all possible positions in the game) and there is no infinite sequence
p_1,
p_2,
p_3,... such that each
p_(
i+1) is in Options(
p_i).
One very important ruleset is nim, which is defined by:
nim(*x) = {*(x-1), *(x-2), *(x-3), ..., *0}
Examples:
- nim(*5) = {*0,*1,*2,*3,*4}
- nim(*0) = {} (there are no children of the empty pile since no moves can be made
from it).
- sprouts(S2) = {A2,0L1}. (Let S2 be the sprouts position consisting only of a biosphere with two original spots)
- sprouts(S1) = {0L0}
- sprouts(0L0) = {0P0}
- sprouts(0P0) = {}
GAMES & COMPONENTSA "game" is a
multiset
of (position,ruleset) pairs; each pair is called a "component". We will denote the components in
a game by
G+
H+
I+...+
K, where Options(
G_1+
G_2+...+
G_n) =
H_1+
H_2+...+
H_n, such that exactly one
H_i is in Options(
G_i), and
H_
j=
G_
j for
j not equal to
i.
Examples:
- *1 is a game with just one component: the nim heap with one element
- *1+*1+*2+*3 is a game with four nim heaps: two of size 1, one of size 2, and one of size 3.
- S2 is a game with one sprouts component of two original spots
- S2+S3 is a game with two sprouts components of 2 and 3 original spots, respectively
- *2+S2 is a game with a nim component and a sprouts component
It is convenient to use a notation for positions that allows one to
unambiguously determine which ruleset governs that position. Then we can use the "Options" function as a universal ruleset. For
example, this document uses the convention of writing all Nim positions
as integers prefixed with an asterisk, and of not using an asterisk in
sprouts positions. Note that a single game may have components from
more than one ruleset (see example 5 above).
SUCCESSORSThe "successors" of a game
G, written
G', is the set of games that can be reached by making a move in one of the components. Equivalently,
G' is the set of games that can be obtained by replacing a component of
G with one of its children.
Examples:
- (*1+*2)' = { *0+*2, *1+*1, *1+*0 }
- (*1+S2)' = { *0+S2, *1+A2, *1+0L0 }
NEXT & PREVIOUS PLAYERIn any two player combinatorial game, the "next" player is defined to be the player whose turn it is
to move, and the "previous" player is defined to be the player who is not
the next player.
OUTCOME CLASSES
Every game falls into one of two disjoint "normal-play outcome classes", called
P+ and
N+ (for "previous player winning" and "next player winning", respectively).
- The normal-play outcome class P consists of those games which, with perfect play, can always be won by previous player in normal play.
- The normal-play outcome class N consists of those games which, with perfect play, can always be won by the next player to move in normal play.
Similarly, each game also falls into one of two disjoint "misere-play outcome classes", also called
P- and
N-.
When the context is clear, as in the context of the functions below, we will omit the trailing "+" or "-" and simply write
P or
N.
By o+(
G) we denote the normal-play outcome class of the game
G.
The "+" in "o+" should be thought of as being a superscript, not as the
"+" that separates components in a game, or as the plus that denotes
addition. Here, o+(
G) denotes the result of the function o+ with the argument
G, just
as sqrt(
x) denotes the result of the function sqrt with the argument
x.
More precisely, o+(
G) =
- N, if there exists H in G' such that o+(H) = P ("In normal play, a game is a win for the next player if one of its successors is a win for the previous player.")
- P, if there does not exist an H in G' such that o+(H) = P
("In normal play, a game is a win for the previous player if it does
not have a successor that is a win for the previous player.")
By o-(
G) we denote the misere-play outcome class of the game
G. Again, the notation can be misleading in plain ASCII. The minus should be thought of as being in a superscript font.
More precisely, o-(
G) =
- N, if G' = {} or there exists H in G' such that o-(H) = P
("In misere play, a game is a win for the next player if it either has
no successors or it has a successor that is a win for the previous
player.")
- P, if G' =/= {} and there does not exist an H in G' such that o+(H) = P
("In misere play, a game is a win for the previous player if it has at
least one successor and all of its successors are wins for the n or it
has a successor that is a win for the previous
player.")
Examples:
- o+(*0) = P
- o+(*1) = N
- o+(*n) = N, for integer n > 1 (for example, o+(*100) = N, because the next player can always remove all the objects from the pile, leaving the next player no moves)
- o-(*0) = N
- o-(*1) = P
- o-(*n) = N, for integer n > 1
- o+(S1) = P
- o+(S1+S1) = P
- o+(S1+*2) = N
- o-(S1) = N
- o+(S2) = P
- o-(S2) = P
- o-(S15) = P
POP QUIZ #1Fill in the blanks in the following:
- o+(*2+*2) = ?
- o-(*2+*2) = ?
-
o+(*2+*3) = ?
- o-(*2+*3) = ?
GRUNDY NUMBERS
The normal-play Grundy number of a game
G, written Grundy+(
G) is the unique nonnegative integer x such that o+(
G+*x) =
P. Again, think of the "+" as a superscript, not as addition.
Examples:
- Grundy+(*0) = 0
- Grundy+(*1) = 1
- Grundy+(*1+*1) = 0
- Grundy+(S1) = 0
- Grundy+(S2) = 0
- Grundy+(S2+*1) = 1
Similarly, the misere-play Grundy number of a game
G, written Grundy-(
G) is the unique nonnegative integer
x such that o-(
G+*
x) =
P.
Examples:
- Grundy-(*0) = 1
- Grundy-(*1) = 0
- Grundy-(*1+*1) = 1
- Grundy-(S1) = 1
- Grundy-(S2) = 0
- Grundy-(S2+*1) = 1
POP QUIZ #2
Fill in the blanks in the following:
- Grundy+(*2+*2) = ?
- Grundy-(*2+*2) = ?
- Grundy+(*2+*3) = ?
- Grundy-(*2+*3) = ?
NIM-VALUESFollowing Winning Ways, the "nim-values" of G, written
a^
b, are the pair of nonnegative integers such that
a = Grundy+(
G) and
b = Grundy-(
G).
Examples:
- nim-values(*0) = 0^1
- nim-values(*1) = 1^0
- nim-values(*2) = 2^2
- nim-values(S2) = 0^0
TAME"Game G is tame" means nim-values(G) are one of 0^1, 1^0, 0^0, 1^1, 2^2, 3^3, 4^4, 5^5, etc... and for every H in G', either H is tame or all of the following are true:
- Grundy+(H) > Grundy+(G) or G has a tame child K such that Grundy+(H) = Grundy+(K). (This as a way of saying "H does not affect Grundy+(G)".)
- Grundy-(H) > Grundy-(G) or G has a tame child K such that Grundy-(H) = Grundy-(K). (This as a way of saying "H does not affect Grundy-(G)".)
- There exists a J in H' such that J is tame and Grundy+(J) = Grundy+(G)
- There exists a J in H' such that J is tame and Grundy-(J) = Grundy-(G)
A game which is not tame is called "wild".