Impartial Games

This section describes CGSuite's specialized support for impartial games.

Heap Games and Grundy Sequences

Impartial games have a particularly simple structure: their canonical forms are always nimbers.  While you can use CGSuite's partizan-games engine to compute these "Nim values," it's terribly inefficient, particularly for heap games, when we often want to calculate Nim values for very large heaps.

Starting with version 0.7, CGSuite provides a massive shortcut for dealing with heap games.  Type

S := GrundySequence("0.77", 500)

This will quickly compute the Nim-values for the octal game 0.77 up to heap 500.  (You might recognize 0.77 as the octal code for Kayles.)  The values will be stored in an object of type GrundySequence, which can be manipulated in a variety of ways.  For example, try typing

CheckPeriodicity(S)

This will use the Guy-Smith criterion for determining whether the sequence is periodic.  If it's possible to determine periodicity on the basis of the 500 computed values, it will return a triple of integers [period,preperiod,saltus].  In this case, we get [12,71,0], indicating that Kayles has period 12, preperiod 71, and saltus 0.  If periodicity can't be established, then the return value will be [-1,-1,-1].

You can also type

PeriodicTable(S,12)

to display the values in a nice table, or simply

S[100]

to extract individual G-values.

There are a wide variety of codes you can supply as strings, including arbitrary octal and hexadecimal codes.  We'll detail these in a moment, but when they aren't sufficient there's a useful shortcut available.  Let f be a CGSuite function (see Functions and Lists) that maps integers to lists of lists of integers.  Then f(n) will be interpreted as a list of possible moves from a heap of size n.  Each "move" is just a list of resultant component heaps.  For example, Dawson's Kayles ("0.07", take 2 tokens from any heap, optionally splitting into two heaps) could be represented by

f := n -> seq([k,n-k-2] for k from 0 to n-2)

Then you could type f(7) to get a list of all moves from a Dawson's Kayles heap of size 7.  You can then type (say)

GrundySequence(HeapRules(f), 500)

to get a sequence for the game so defined.  You can use this to specify rules for heap games with arbitrarily complicated logic. (But be aware that the calculations will be much slower than using use the built-in codes!)

Take-and-Break Codes

CGSuite supports a wide variety of take-and-break codes.  You can use the digits 0-9 and A-F in the usual fashion for octal and hexadecimal games.  In addition, you can use G-Z for "digits" 16-35, and there is a special notation for larger "digits"; for example

&64;

for a digit of size 64.  You could also enter this as a hex code by

&x40;

In addition, it's possible to place restrictions on moves in a take-and-break game.  For example, appending ! to a digit means that all the resulting heaps must be unequal.  For example, the game

4.0

is "split a heap into two non-empty heaps".  If you compute just a few elements of the GrundySequence for this game, you'll see that it's not very interesting.  However, change this to

4!.0

and we now have Grundy's Game: "split a heap into two non-empty heaps of different sizes".  This is perhaps the most-studied heap game of them all.  Likewise,

0.4!

would be the variant "remove one token and split the remainder into two non-empty heaps of different sizes."  And so on.

There are more possibilities; refer to the CGSuite API for the full list.

Finally, certain infinite repeating codes are possible by bracketing the final digits of a code.  Here is a list of examples.

Mis่re Canonical Forms

CGSuite also supports mis่re canonical forms of games, as described in Winning Ways and ONaG.  The notation used is slightly different.  Every mis่re canonical form starts with a star, followed by an expression in brackets.  Subscripts are used to represent sums of games.  For example, *[2] is a Nim-heap of size 2 in mis่re canonical form, and *[22] is equal to *[2] + *[2].  You can enter *[22] on the worksheet as

*[2] + *[2]

or simply

*[2[2]]

The nested brackets represent subscripts.  A convenient shorthand is available for games with one option: you can type

*[2/]

for the game *[2/], which is defined to be { *[2] }.  Multiple options are designated by concatenation, so

*[022[2]2/]

is the game with four options, 0, *[2], *[22], and *[2/].  Parens can be used for grouping:

*[(2/320)/(32)]

yields the game { { *[2/320] }, *[32] }.  Finally, subscripts can be "chained", so

*[2[/22//2]]

yields *[2/22//2], which is equal to { { {*[2]} + *[2] + *[2] } } + *[2].

To compose pre-existing games into options, you can use the "Misere" method, e.g.,

Misere(0, *[2], *[2[2]], *[2/])

is equivalent to

*[022[2]2/]

If G is any impartial game, then

MisereCanonicalForm(G)

returns its canonical form.  For example,

MisereCanonicalForm(Heap("0.77", 15))

gives the canonical form of a Kayles heap of size 15.

A large number of methods are available for the manipulation of canonical forms; see the Glossary of Methods.

Mis่re Quotients

The MisereSolver plug-in, bundled with CGSuite, can be used to compute mis่re quotients.  It's turned off by default; to load it: go to Tools/Plug-in Manager; click "MisereSolver"; and click "Load".  Then you can type:

MisereQuotient(G)

for the quotient of a particular game or canonical form;

MisereQuotient("0.77")

for the quotient of a heap game;

MisereQuotient("0.77" : Heap := 24)

for a particular partial quotient.

It's returned as a two-element list.  The first element is a commutative monoid presentation; the second lists the P-portion.  See the Glossary of Methods for a list of available methods.

You can also run MisereSolver directly from the commandline; this is often useful for exploring large and complicated quotients.  Change to the plugins/ directory (where misere.jar is located) and type

java -jar misere.jar

for help.

Continue on to Loopy Games