Misere play of the G4G7 (Gathering for Gardner) Heptagon Game

Misere play of G-A-R-D-N-E-R, the G4G7 Heptagon Game
March 2006

At the Seventh Gathering for Gardner (G4G7) in Atlanta (March 2006), I plan to hand out a game board that looks like this on the front side:

The game is called G-A-R-D-N-E-R. It is based on one of the logos of the G4G7 conference, which looks like this:

There are two players. To set up the board for play, stacks of coins are placed on various vertices of the game board, excluding the topmost "G" node. It doesn't matter how many coins are placed on the board, but it should be at least six to ten, and they should be scattered amongst the various vertices. For example, one might start with one, two or three coins at each non-G vertex.

On a player's move, he slides one coin along a single directed edge of the game board. The direction of the arrows ensures that all coins will eventually reach the "sink" node "G" at the top of the board.

Normal Play

As a warm-up, let's work out a complete winning strategy for normal play of G-A-R-D-N-E-R. In normal play, the last player to slide a coin to the "G" node is declared the winner of the game. We can describe a simple strategy for normal-play G-A-R-D-N-E-R using the Sprague-Grundy theory. The figure below illustrates the nim-heap equivalents for each vertex of the board:

The values *0, *1, *2, and *3 are added using the rule of nim addition (binary addtion without carrying):

$\reverse\begin{tabular}{c|cccc} + & \ast 0 & \ast 1 & \ast 2 & \ast 3 \\ \hline \ast 0 & \ast 0 & \ast 1 & \ast 2 & \ast 3 \\ \ast 1 & \ast 1 & \ast 0 & \ast 3 & \ast 2 \\ \ast 2 & \ast 2 & \ast 3 & \ast 0 & \ast 1 \\ \ast 3 & \ast 3 & \ast 2 & \ast 1 & \ast 0 \\ \end{tabular}$

A given normal-play position is a winning position for the next player to move (a so-called "N-position") if and only if when we sum up the nim values of each coin, the result is *1, *2, or *3. Positions that add up to *0 are winning for the second player to move ("P-positions").

For example, suppose two coins are at vertex "N". The nim sum

*1 + *1 = *0

says that the position is a P-position in normal play.

Misère Play

In misere play, the last player to slide a coin to the "G" node is declared the loser of the game. Is it possible to give a similar assignment of values to the single vertices of the G-A-R-D-N-E-R board so that we can determine who wins in misere play by "adding" up values? The answer is yes, but the desired values are not nim-heaps, and the addition is not nim-addition. Instead we assign to the vertices of the board values taken from a particular commutative 14-element monoid Q, the misere indistinguishability quotient of G-A-R-D-N-E-R.

A monoid is a semigroup with an identity. To write down the addition of misere G-A-R-D-N-E-R, we can use a commutative monoid presentation:

$\reverse Q = \langle \ a,\ b,\ c\ | \ a^2=1,\ b^3=b,\ b^2c=c,\ c^3=ac^2\ \rangle$
A general monomial of the form

$\reverse a^i b^j c^k$

Can always be reduced to one of the fourteen elements of Q:

$\reverse Q = \{ 1,\ a,\ b,\ c,\ ab,\ ac,\ b^2,\ ab^2,\ bc,\ abc,\ abc^2,\ c^2,\ ac^2,\ bc^2 \}$
The 14 elements of Q partition into two subsets

$\reverse Q = P \ \cup \ N$
where

$\reverse P = \{ a, \ b^2,\ c^2,\ bc \}$
are the P-positions and

$\reverse N = \{ 1,\ b,\ c,\ ab,\ ac,\ ab^2,\ abc,\ abc^2,\ ac^2,\ bc^2 \}$
are the N-positions.

To win at misere G-A-R-D-N-E-R from a given N-position, we need to a move to a P-position. This is simplified by using the following graphical information that is given on the back of the game board (it also shows the assignment quotient elements to the game board vertices, in the upper right hand corner):

Finding a move in an example misere G-A-R-D-N-E-R position

For example, consider the misere G-A-R-D-N-E-R position P consisting of exactly one coin at each of the non-"G" vertices of the game board. Moving counterclockwise from the "G" around the diagram shown in the upper right-hand corner of the figure above, the corresponding single-coin monomials are

$\reverse a,\ b,\ c^2,\ c,\ 1,\ a.$
To determine the monomial for the multi-coin position P, we multiply these corresponding single-coin monomials together, apply commutativity, and reduce the resulting monomial via the four G-A-R-D-N-E-R relations (shown in blue). The product of the six monomials above is

$\reverse a \cdot b \cdot c^2 \cdot c \cdot 1 \cdot a = a^2bc^3,$
which can then be reduced via the relations a²=1 and c³= ac² to obtain the monomial

$\reverse abc^2,$
which cannot be further reduced using the four G-A-R-D-N-E-R relations. Again consulting the diagram, we see that abc² is one of the green monomials in the diagram (ie, an N-position). The original position P therefore has a forced winning move for the first player. The winning move

$\reverse R \rightarrow A$
is shown as a green edge in the (small) abc² monomial diagram. In terms of single-coin monomials, the winning move is a transition

$\reverse b \rightarrow a.$
Next, let's check that the resulting position after the recommended move has been made is indeed a P-position. After the winning move has been made, the resulting position has two coins at "A", none at the the "R" labelled b, and one each at each other non-G vertex. The corresponding result monomial is

$\reverse a^2 \cdot c^2 \cdot c \cdot 1 \cdot a = a^3c^3,$
which reduces to the red monomial

$\reverse ac^3 = a \cdot a \cdot c^2 = c^2.$

For more information on the indistinguishability quotient construction

Taming the Wild in Impartial Combinatorial Games [ http://arxiv.org/abs/math.CO/0501315 ]
Advances in losing [ http://arxiv.org/abs/math.CO/0603027 ]

To make the game board and print the stickers that go on back

front board (PDF), (print it on card stock and cut on lines)
sticker sheet #1 (PDF), suitable for 4-up printing [5168 Avery labels]
sticker sheet #2 (PDF), suitable for 14-up printing [5262 Avery labels]