3 views

Skip to first unread message

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:

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:

Examples:

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:

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:

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*) =

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*) =

Examples:

POP QUIZ #1

Fill in the blanks in the following:

FICKLE AND FIRM

"*G* is fickle" means at least one of the following is true:

"*G* is firm" means at least one of the following is true:

--

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

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 *

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

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

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

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

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) = {}

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

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. 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

Examples:

- (*1+*2)' = { *0+*2, *1+*1, *1+*0 }
- (*1+S2)' = { *0+S2, *1+A2, *1+0L0 }

Note that each game falls into one of two disjoint "normal-play outcome classes", called

- The normal-play outcome class

- The normal-play outcome class

Similarly, each game also falls into one of two disjoint "misere-play outcome classes", also called

By o+(

More precisely, o+(

**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-(

More precisely, o-(

**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) =
**P** - o-(S1) =
**N** - o+(S2) =
**P** - o-(S2) =
**P** - o-(S15) =
**P**

POP QUIZ #1

Fill in the blanks in the following:

- o+(*2+*2) = ?
- o-(*2+*2) = ?
- o+(*2+*3) = ?
- o-(*2+*3) = ?

FICKLE AND FIRM

"

- For all games
*H*, o+(*G*+*H*) = o+(*0+*H*) and o-(*G*+*H*) = o-(*0+*H*) - For all games
*H*, o+(*G*+*H*) = o+(*1+*H*) and o-(*G*+*H*) = o-(*1+*H*)

"

- 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*) - For all games H, o+(
*G*+*H*) = o+(*2+*2+*H*) and o-(*G*+*H*) = o-(*2+*2+*H*) - 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>

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

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

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>

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

"Gis fickle" means at least one of the following is true:

- For all games
H, o+(G+H) = o+(*0+H) and o-(G+H) = o-(*0+H)- For all games
H, o+(G+H) = o+(*1+H) and o-(G+H) = o-(*1+H)

"Gis firm" means at least one of the following is true:

- There exists an integer
n> 1 such that for all gamesH, o+(G+H) = o+(*n+H) and o-(G+H) = o-(*n+H)- For all games H, o+(
G+H) = o+(*2+*2+H) and o-(G+H) = o-(*2+*2+H)- For all games H, o+(
G+H) = o+(*2+*3+H) and o-(G+H) = o-(*2+*3+H)

The definition could be corrected by replacing "For all games

--

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

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:

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:

POP QUIZ

Fill in the blanks in the following:

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:

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:

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>

GRUNDY NUMBERS

The normal-play Grundy number of a game

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

Examples:

- Grundy-(*0) = 1

- Grundy-(*1) = 0

- Grundy-(*1+*1) = 1

- Grundy-(S1) = 1

- Grundy-(S2) = 0
- Grundy-(S2+*1) = 1

POP QUIZ

Fill in the blanks in the following:

- Grundy+(*2+*2) = ?
- Grundy-(*2+*2) = ?
- Grundy+(*2+*3) = ?
- Grundy-(*2+*3) = ?

NIM-VALUES

Following Winning Ways, the "nim-values" of G, written

Examples:

- nim-values(*0) = 0^1
- nim-values(*1) = 1^0
- nim-values(*2) = 2^2
- nim-values(S2) = 0^0

Slightly rephrasing the definition from Winning Ways, we can say that "Game

- Grundy+(
*H*) <> Grundy+(*G)* - Grundy-(
*H*) <> Grundy-(*G*) - There exists a J in H' such that Grundy+(
*J*) = Grundy+(*G*) - There exists a J in H' such that Grundy+(
*K*) = Grundy-(*K)*

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

--

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

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 "GameGis tame" means nim-values(G) are one of0^1, 1^0, 2^2, 3^3, 4^4, ... and for everyHinG', eitherHis tame or all of the following are true:

- Grundy+(
H) <> Grundy+(G)- Grundy-(
H) <> Grundy-(G)- There exists a J in H' such that Grundy+(
J) = Grundy+(G)- There exists a J in H' such that Grundy+(
K) = Grundy-(K)

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

Every wild child of

- ... a different normal-play Grundy number than
*G*. - ... a different misere-play Grundy number than
*G*. - ... a child with the same normal-play Grundy number as
*G*. - ... a child with the same misere-play Grundy number as
*G*.

--

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

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:

--

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

"Game

- Grundy+(
*H*) > Grundy+(*G*) or*G*has a tame child*K*such that Grundy+(*H*) = Grundy+(*K*). - Grundy-(
*H*) > Grundy-(*G*) or*G*has a tame child*K*such that Grundy-(*H*) = Grundy-(*K*).

- There exists a J in H' such that Grundy+(
*J*) = Grundy+(*G*)

- There exists a J in H' such that Grundy-(
*J*) = Grundy-(*G)*

--

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

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

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

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

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. :)

"GameGis 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."GameGis tame" means nim-values(G) are one of0^1, 1^0, 2^2, 3^3, 4^4, 5^5, etc... and for everyHinG', eitherHis tame or all of the following are true:

- Grundy+(
H) > Grundy+(G) orGhas a tame childKsuch that Grundy+(H) = Grundy+(K).- Grundy-(
H) > Grundy-(G) orGhas a tame childKsuch that Grundy-(H) = Grundy-(K).- There exists a J in H' such that Grundy+(
J) = Grundy+(G)- 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>

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:

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..

--

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

"Game

- Grundy+(
*H*) > Grundy+(*G*) or*G*has a tame child*K*such that Grundy+(*H*) = Grundy+(*K*). - Grundy-(
*H*) > Grundy-(*G*) or*G*has a tame child*K*such that Grundy-(*H*) = Grundy-(*K*). - There exists a J in H' such that Grundy+(
*J*) = Grundy+(*G*) - There exists a J in H' such that Grundy-(
*J*) = Grundy-(*G)*

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

--

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

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.

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:

Examples:

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:

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:

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*) =

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*) =

Examples:

POP QUIZ #1

Fill in the blanks in the following:

Fill in the blanks in the following:

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:

TAME

A game which is not tame is called "wild".

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

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) = {}

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

SUCCESSORS

The "successors" of a game

Examples:

- (*1+*2)' = { *0+*2, *1+*1, *1+*0 }
- (*1+S2)' = { *0+S2, *1+A2, *1+0L0 }

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

- The normal-play outcome class

- The normal-play outcome class

When the context is clear, as in the context of the functions below, we will omit the trailing "+" or "-" and simply write

By o+(

More precisely, o+(

**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-(

More precisely, o-(

**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 #1

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

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:

POP QUIZ #2The normal-play Grundy number of a game

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

Examples:

- Grundy-(*0) = 1

- Grundy-(*1) = 0

- Grundy-(*1+*1) = 1

- Grundy-(S1) = 1

- Grundy-(S2) = 0
- Grundy-(S2+*1) = 1

Fill in the blanks in the following:

- Grundy+(*2+*2) = ?
- Grundy-(*2+*2) = ?
- Grundy+(*2+*3) = ?
- Grundy-(*2+*3) = ?

NIM-VALUES

Following Winning Ways, the "nim-values" of G, written

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)*

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu