World
Game
Of
Sprouts
Association

Firm and Fickle Games

April 26, 2008

Overview of firm and fickle games

This is mostly from Winning Ways (by Berlekamp, Conway and Guy), 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 p1, p2, p3, ... such that each pi+1 is in Options(pi).

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(G1+G2+...+Gn) = H1+H2+...+Hn, such that exactly one Hi is in Options(Gi), and Hj=Gj for ji.

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).
  1. The normal-play outcome class P+ consists of those games which, with perfect play, can always be won by previous player in normal play.
  2. 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. 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.

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

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

    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 ab (or with a caret like "a^b" if superscript notation is not available), are the pair of nonnegative integers such that a = Grundy+(G) and b = Grundy-(G).

    Examples:

    1. nim-values(*0) = 01
    2. nim-values(*1) = 10
    3. nim-values(*2) = 22
    4. nim-values(S2) = 00

    Tame

    "Game G is tame" means nim-values(G) are one of 01, 10, 00, 11, 22, 33, 44, 55, 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 successor 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 successor K such that Grundy-(H) = Grundy-(K). (This as a way of saying "H does not affect Grundy-(G)".)
    3. H has a tame successor J such that Grundy+(J) = Grundy+(G)
    4. H has a tame successor J such that Grundy-(J) = Grundy-(G)

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

    Fickle & firm

    Every tame game is either firm or fickle. A game is fickle if it is tame and its nim-values are 01 or 10. A game is firm if it is tame and its nim-values are of the form xx. However, the converse of these statements is not necessarily true. For example, 0P3 has nim-values 11, but it is wild. To see this, note that the children of 0P3 have nim values 03, 30, and 33, so the nim-values of 0P3 itself are 11. But 0P3 is wild, because its 03 option is wild (because of its nim values) and it fails "tame condition #1" (since 0 < 1). Similarly, S4 has nim-values 10, but it is wild (its children are 0L3, 2L1, and A4, which have nim values 03, 03, and 33, respectively).


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


    Back to WGOSA Classic