# Re: glossary: fickle and firm

3 views
Skip to first unread message

### Josh Purinton

unread,
Mar 21, 2008, 6:30:56 AM3/21/08
to sprouts...@googlegroups.com, Jeff Peltier, danny purvis
OVERVIEW FIRM AND FICKLE GAMES

This is mostly from Winning Ways, Vol I p 424, with additional background material. Questions, corrections and/or suggestions for clarification are welcome. Not all the terminology and concepts are standard (in particular, "ruleset" and "position" are not part of the lexicon of combinatorial game theory as I know it), but this is how I think about the subject.

INFORMAL DEFINITION

Let *n denote a nim-heap of size n. Then, roughly speaking, a component is "fickle" if we can pretend it is a nim heap of size 0 or 1 and a component is "firm" if we can pretend it is one of the following:
• A nim heap of size 2 or greater
• A pair of nim heaps, each of size 2
• A pair of nim heaps, one of size 2 and one of size 3

To understand precisely what is meant by pretending that a component is a set of nim heaps, we must first understand several other concepts: "ruleset", "position", "children", "nim", "game", "component", "successor", "normal-play outcome class", "misere-play outcome class", P, and N. Let's take them in order.

RULESETS, POSITIONS, CHILDREN, & NIM

First we need to discuss the intertwined 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 R is a function such that each element of the range is a subset of the domain, the directed graph representing it has a countable number of vertices and is acyclic. A "position" in R is then an element of the domain of R.

One very important ruleset is nim, which is defined by:

nim(*x) = {*a,*b,*c,...} where 0 <= a < b < c < ... <= *x.

Examples:
1. nim(*5) = {*0,*1,*2,*3,*4}
2. nim(*0) = {} (there are no children of the empty pile since no moves can be made from it).
3. sprouts(S2) = {A2,0L1}. (Let S2 be the sprouts position consisting only of a biosphere with two original spots)
4. sprouts(S1) = {0L0}
5. sprouts(0L0) = {0P0}
6. sprouts(0P0) = {}
GAMES & COMPONENTS

A "game" is a multiset of (position,ruleset) pairs; each pair is called a "component". (In ordinary usage, "game" has many meanings, but in combinatorial game theory it has a more precise meaning.) We will denote the components in a game by G+H+I+...+K.

Examples:
1. *1 is a game with just one component: the nim heap with one element
2. *1+*1+*2+*3 is a game with four nim heaps: two of size 1, one of size 2, and one of size 3.
3. S2 is a game with one sprouts component of two original spots
4. S2+S3 is a game with two sprouts components of 2 and 3 original spots, respectively
5. *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. 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.

SUCCESSORS

The "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. (*1+*2)' = { *0+*2, *1+*1, *1+*0 }
2. (*1+S2)' = { *0+S2, *1+A2, *1+0L0 }
OUTCOME CLASSES

Note that each game falls into one of two disjoint "normal-play outcome classes", called P and N.
- 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.

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) =
1. 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.")
2. 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) =
1. 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.")
2. 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:
1. o+(*0) = P
2. o+(*1) = N
3. 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)
4. o-(*0) = N
5. o-(*1) = P
6. o-(*n) = N, for integer n > 1
7. o+(S1) = P
8. o+(S1+S1) = P
9. o+(S1+*2) = P
10. o-(S1) = N
11. o+(S2) = P
12. o-(S2) = P
13. o-(S15) = P

POP QUIZ #1

Fill in the blanks in the following:
1. o+(*2+*2) = ?
2. o-(*2+*2) = ?
3. o+(*2+*3) = ?
4. o-(*2+*3) = ?

FICKLE AND FIRM

"G is fickle" means at least one of the following is true:
1. For all games H, o+(G+H) = o+(*0+H) and o-(G+H) = o-(*0+H)
2. For all games H, o+(G+H) = o+(*1+H) and o-(G+H) = o-(*1+H)

"G is firm" means at least one of the following is true:
1. There exists an integer n > 1 such that for all games H,  o+(G+H) = o+(*n+H) and o-(G+H) = o-(*n+H)
2. For all games H, o+(G+H) = o+(*2+*2+H) and o-(G+H) = o-(*2+*2+H)
3. For all games H, o+(G+H) = o+(*2+*3+H) and o-(G+H) = o-(*2+*3+H)

--
Josh Purinton <josh.p...@gmail.com>

### Jeff Peltier

unread,
Mar 21, 2008, 6:52:01 AM3/21/08
to Josh Purinton, sprouts...@googlegroups.com, danny purvis
Josh,

o+(S1+*2) = P ?

If S1 is the Sprouts position with 1 spot this is the nim game *0 of genus 0^1, then S1+*2 is *2...
For the rest I do agree, thnx for these remindings.

Could you point to the pages of WWI on "Firm and Fickle Games" as they do not give same definitions I copied from WWII and a search in Google books for these terms gives nothing.

--
Jeff
--
--
Jean-François

### Josh Purinton

unread,
Mar 21, 2008, 12:38:12 PM3/21/08
to jfpe...@gmail.com, sprouts...@googlegroups.com, danny purvis
On Fri, Mar 21, 2008 at 6:52 AM, Jeff Peltier <jfpe...@gmail.com> wrote:

o+(S1+*2) = P ?

If S1 is the Sprouts position with 1 spot this is the nim game *0 of genus 0^1, then S1+*2 is *2...

Oops, thanks! That should definitely be an N.

Could you point to the pages of WWI on "Firm and Fickle Games" as they do not give same definitions I copied from WWII and a search in Google books for these terms gives nothing.

This URL takes me to p 424 of Winning Ways v1 which begins with the section on "Firm and Fickle Games":

http://books.google.com/books?id=ObnlI6vnawAC&pg=PA424&lpg=PA424&ots=DCjxiWFGOc&sig=cV4CZgK9aScOiXAkmz2AkUgkyAg

--
Josh Purinton <josh.p...@gmail.com>

### Josh Purinton

unread,
Mar 21, 2008, 2:33:47 PM3/21/08
to sprouts...@googlegroups.com, Jeff Peltier, danny purvis

On Fri, Mar 21, 2008 at 6:30 AM, Josh Purinton <josh.p...@gmail.com> wrote:
FICKLE AND FIRM

"G is fickle" means at least one of the following is true:
1. For all games H, o+(G+H) = o+(*0+H) and o-(G+H) = o-(*0+H)
2. For all games H, o+(G+H) = o+(*1+H) and o-(G+H) = o-(*1+H)

"G is firm" means at least one of the following is true:
1. There exists an integer n > 1 such that for all games H,  o+(G+H) = o+(*n+H) and o-(G+H) = o-(*n+H)
2. For all games H, o+(G+H) = o+(*2+*2+H) and o-(G+H) = o-(*2+*2+H)
3. For all games H, o+(G+H) = o+(*2+*3+H) and o-(G+H) = o-(*2+*3+H)

Thanks to Jeff Peltier for pointing out, by way of a counterexample, that my definitions of fickle and firm were wrong. He notes that the sprouts position S2 (= {*2}) is firm but none of the three conditions in the above definition of "firm" apply. It might seem that condition 2 applies, but if we take H = {*1,*2+*3,*3}, then o-(S2+H) = P but o-(*2+*2+H) = N.

The definition could be corrected by replacing "For all games H" with "For all tame games H", but this requires a definition of "tame", and once we have that, there is a simpler way to define firm and fickle.

--
Josh Purinton <josh.p...@gmail.com>

### Josh Purinton

unread,
Mar 21, 2008, 3:22:59 PM3/21/08
to sprouts...@googlegroups.com, Jeff Peltier, danny purvis
Here's a corrected definition of "fickle" and "firm". This definition is stated in terms of the additional preliminary concepts "grundy numbers", "nim-values", and "tame".

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:
1. Grundy+(*0) = 0
2. Grundy+(*1) = 1
3. Grundy+(*1+*1) = 0
4. Grundy+(S1) = 0
5. Grundy+(S2) = 0
6. 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:
1. Grundy-(*0) = 1
2. Grundy-(*1) = 0
3. Grundy-(*1+*1) = 1
4. Grundy-(S1) = 1
5. Grundy-(S2) = 0
6. Grundy-(S2+*1) = 1

POP QUIZ

Fill in the blanks in the following:
1. Grundy+(*2+*2) = ?
2. Grundy-(*2+*2) = ?
3. Grundy+(*2+*3) = ?
4. Grundy-(*2+*3) = ?

NIM-VALUES

Following 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:
1. nim-values(*0) = 0^1
2. nim-values(*1) = 1^0
3. nim-values(*2) = 2^2
4. nim-values(S2) = 0^0
TAME

Slightly rephrasing the definition from Winning Ways, we can say that "Game G is tame" means nim-values(G) are one of 0^1, 1^0, 2^2, 3^3, 4^4, ... and for every H in G', either H is tame or all of the following are true:
1.       Grundy+(H) <> Grundy+(G)
2.       Grundy-(H) <> Grundy-(G)
3.       There exists a J in H' such that Grundy+(J) = Grundy+(G)
4.       There exists a J in H' such that Grundy+(K) = Grundy-(K)
FICKLE & FIRM

Every tame game is either firm or fickle. A game is fickle if it is tame and its nim-values are 0^1 or 1^0. A game is firm if it is tame and its nim-values are of the form x^x.

--
Josh Purinton <josh.p...@gmail.com>

### Josh Purinton

unread,
Mar 21, 2008, 3:28:29 PM3/21/08
to sprouts...@googlegroups.com, Jeff Peltier, danny purvis

On Fri, Mar 21, 2008 at 3:22 PM, Josh Purinton <josh.p...@gmail.com> wrote:
Slightly rephrasing the definition from Winning Ways, we can say that "Game G is tame" means nim-values(G) are one of 0^1, 1^0, 2^2, 3^3, 4^4, ... and for every H in G', either H is tame or all of the following are true:
1.       Grundy+(H) <> Grundy+(G)
2.       Grundy-(H) <> Grundy-(G)
3.       There exists a J in H' such that Grundy+(J) = Grundy+(G)
4.       There exists a J in H' such that Grundy+(K) = Grundy-(K)

Oops, condition 4 should be: There exists J in H' such that Grundy-(K) = Grundy-(G).

In English, those would be (using the term "wild" to mean "non-tame"):

Every wild child of G has ...
1. ... a different normal-play Grundy number than G.
2. ... a different misere-play Grundy number than G.
3. ... a child with the same normal-play Grundy number as G.
4. ... a child with the same misere-play Grundy number as G.

--
Josh Purinton <josh.p...@gmail.com>

### Josh Purinton

unread,
Mar 21, 2008, 3:35:42 PM3/21/08
to sprouts...@googlegroups.com, Jeff Peltier, danny purvis
Oops, I messed up again. Maybe I should stop trying to "rephrase" Winning Ways, but I can't resist.

"Game G is tame" means nim-values(G) are one of 0^1, 1^0, 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:
1. Grundy+(H) > Grundy+(G) or G has a tame child K such that Grundy+(H) = Grundy+(K).
2. Grundy-(H) > Grundy-(G) or G has a tame child K such that Grundy-(H) = Grundy-(K).
1. There exists a J in H' such that Grundy+(J) = Grundy+(G)
1. There exists a J in H' such that Grundy-(J) = Grundy-(G)

--
Josh Purinton <josh.p...@gmail.com>

### Jeff Peltier

unread,
Mar 22, 2008, 6:27:23 AM3/22/08
to Josh Purinton, sprouts...@googlegroups.com, danny purvis
Hi,

Still not right I think and maybe this class can be broadened to other games with all theorems about tame games still true.
The main result which is Noah's Ark Theorem should appear in the glossary too as it is useful for misere sprouts if you have the courage to rephrase it in a meaningful way...

"Game G is tame" means nim-values(G) are those which appear in the Nim game namely :
0^1,1^0,0^0,1^1,2^2,3^3,...etc.

Conditions 3. and 4. are only needed and true for "wild" options whose genus is not needed to compute by mexing the nim-values G+(G) and G-(G). Berlekamp adds that for 3. and 4. J can be the same game.

--
Jeff
--
--
Jean-François

### Josh Purinton

unread,
Mar 22, 2008, 12:06:45 PM3/22/08
to jfpe...@gmail.com, sprouts...@googlegroups.com, danny purvis
On Sat, Mar 22, 2008 at 6:27 AM, Jeff Peltier <jfpe...@gmail.com> wrote:
Still not right I think and maybe this class can be broadened to other games with all theorems about tame games still true.

Thank you for taking the time to help me with this. First I'd like to understand precisely how the definition is still not right, then I'll worry about extending it. :)

"Game G is tame" means nim-values(G) are those which appear in the Nim game namely :
0^1,1^0,0^0,1^1,2^2,3^3,...etc.
Conditions 3. and 4. are only needed and true for "wild" options whose genus is not needed to compute by mexing the nim-values G+(G) and G-(G).

According to the WW page I linked, to, 3 and 4 are needed for all wild options. In addition, no wild option is allowed to affect the nim-values of G (conditions 1 and 2). Conditions 1,2,3, and 4 only apply to wild options since the definition says "either H is tame or H satisfies conditions 1,2,3, and 4.".

Do you have another counterexample at hand?

Berlekamp adds that for 3. and 4. J can be the same game.

Do you mention this because you are suggesting that it would be helpful if my definition included a remark like that? As I read it, the existing wording of the definition already permits the J the of conditions 3 and 4 to be the same game, so adding another sentence to that effect would be redundant.

--
Jeff
On Fri, Mar 21, 2008 at 8:35 PM, Josh Purinton <josh.p...@gmail.com> wrote:
Oops, I messed up again. Maybe I should stop trying to "rephrase" Winning Ways, but I can't resist.
"Game G is tame" means nim-values(G) are one of 0^1, 1^0, 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:
1. Grundy+(H) > Grundy+(G) or G has a tame child K such that Grundy+(H) = Grundy+(K).
2. Grundy-(H) > Grundy-(G) or G has a tame child K such that Grundy-(H) = Grundy-(K).
3. There exists a J in H' such that Grundy+(J) = Grundy+(G)
4. There exists a J in H' such that Grundy-(J) = Grundy-(G)
--
Josh Purinton <josh.p...@gmail.com>
--
--
Jean-François

--
Josh Purinton <josh.p...@gmail.com>

### Josh Purinton

unread,
Mar 23, 2008, 4:47:54 PM3/23/08
to jfpe...@gmail.com, sprouts...@googlegroups.com, danny purvis
After some discussion, Jeff and I agree that the definition is correct provided 0^0 and 1^1 are added to the list of nim-values. Here's the (hopefully final) version of my definition:

"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:

1. Grundy+(H) > Grundy+(G) or G has a tame child K such that Grundy+(H) = Grundy+(K).
2. Grundy-(H) > Grundy-(G) or G has a tame child K such that Grundy-(H) = Grundy-(K).
3. There exists a J in H' such that Grundy+(J) = Grundy+(G)
4. There exists a J in H' such that Grundy-(J) = Grundy-(G)
Jeff also suggests that adding a note to the effect that the J in (3) and (4) can be the same option might help avoid confusion, but we agree that, logically speaking, this is already implied in the current wording of the definition..

On Sat, Mar 22, 2008 at 6:27 AM, Jeff Peltier <jfpe...@gmail.com> wrote:

--
Josh Purinton <josh.p...@gmail.com>

### Josh Purinton

unread,
Mar 26, 2008, 8:13:56 PM3/26/08
to sprouts...@googlegroups.com, Jeff Peltier, danny purvis
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:
1. nim(*5) = {*0,*1,*2,*3,*4}
2. nim(*0) = {} (there are no children of the empty pile since no moves can be made from it).
3. sprouts(S2) = {A2,0L1}. (Let S2 be the sprouts position consisting only of a biosphere with two original spots)
4. sprouts(S1) = {0L0}
5. sprouts(0L0) = {0P0}
6. sprouts(0P0) = {}
GAMES & COMPONENTS

A "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. *1 is a game with just one component: the nim heap with one element
2. *1+*1+*2+*3 is a game with four nim heaps: two of size 1, one of size 2, and one of size 3.
3. S2 is a game with one sprouts component of two original spots
4. S2+S3 is a game with two sprouts components of 2 and 3 original spots, respectively
5. *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).

SUCCESSORS

The "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. (*1+*2)' = { *0+*2, *1+*1, *1+*0 }
2. (*1+S2)' = { *0+S2, *1+A2, *1+0L0 }
NEXT & PREVIOUS PLAYER

In 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) =
1. 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.")
2. 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) =
1. 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.")
2. 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:
1. o+(*0) = P
2. o+(*1) = N
3. 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)
4. o-(*0) = N
5. o-(*1) = P
6. o-(*n) = N, for integer n > 1
7. o+(S1) = P
8. o+(S1+S1) = P
1. o+(S1+*2) = N
1. o-(S1) = N
2. o+(S2) = P
3. o-(S2) = P
4. o-(S15) = P

POP QUIZ #1

Fill in the blanks in the following:
1. o+(*2+*2) = ?
2. o-(*2+*2) = ?
3. o+(*2+*3) = ?
4. 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:
1. Grundy+(*0) = 0
2. Grundy+(*1) = 1
3. Grundy+(*1+*1) = 0
4. Grundy+(S1) = 0
5. Grundy+(S2) = 0
6. 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:
1. Grundy-(*0) = 1
2. Grundy-(*1) = 0
3. Grundy-(*1+*1) = 1
4. Grundy-(S1) = 1
5. Grundy-(S2) = 0
6. Grundy-(S2+*1) = 1

POP QUIZ #2

Fill in the blanks in the following:
1. Grundy+(*2+*2) = ?
2. Grundy-(*2+*2) = ?
3. Grundy+(*2+*3) = ?
4. Grundy-(*2+*3) = ?

NIM-VALUES

Following 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:
1. nim-values(*0) = 0^1
2. nim-values(*1) = 1^0
3. nim-values(*2) = 2^2
4. 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:

1. 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)".)
2. 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)".)
3. There exists a J in H' such that J is tame and Grundy+(J) = Grundy+(G)
4. 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".
Reply all
Reply to author
Forward
0 new messages