World

Game

Of

Sprouts

Association

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.

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

Examples:

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

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

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 anin*H**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 next player.")

- o
^{+}(*2+*2) = - o
^{-}(*2+*2) = - o
^{+}(*2+*3) = - o
^{-}(*2+*3) =

- Grundy
^{+}(*0) = 0 - Grundy
^{+}(*1) = 1 - Grundy
^{+}(*1+*1) = 0 - Grundy
^{+}(S1) = 0 - Grundy
^{+}(S2) = 0 - Grundy
^{+}(S2+*1) = 1

Examples:

- Grundy
^{-}(*0) = 1 - Grundy
^{-}(*1) = 0 - Grundy
^{-}(*1+*1) = 1 - Grundy
^{-}(S1) = 1 - Grundy
^{-}(S2) = 0 - Grundy
^{-}(S2+*1) = 1

- Grundy
^{+}(*2+*2) = - Grundy
^{-}(*2+*2) = - Grundy
^{+}(*2+*3) = - Grundy
^{-}(*2+*3) =

Examples:

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

- Grundy
^{+}(*H*) > Grundy^{+}(*G*) or*G*has a tame successor*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 successor*K*such that Grundy^{-}(*H*) = Grundy^{-}(*K*). (This as a way of saying "*H*does not affect Grundy^{-}(*G*)".) *H*has a tame successor*J*such that Grundy^{+}(*J*) = Grundy^{+}(*G*)*H*has a tame successor*J*such that Grundy^{-}(*J*) = Grundy^{-}(*G*)

* Thanks to Dan Hoey and Jeff Peltier for their many suggestions and corrections. - Josh Purinton
*