(2) = 2. A pile of three chips can be moved to a pile of two or one chips,
(SG-value 1 and 2) or to two piles of one chip each (SG-value 0), so
g
(3) = 3. Continuing
in this way, we find more of the Sprague-Grundy values in Table 4.1.
y
\
z
0
1
2
3
4
5
6
7
8
9
10
11
0
0
1
2
3
1
4
3
2
1
4
2
6
12
4
1
2
7
1
4
3
2
1
4
6
7
24
4
1
2
8
5
4
7
2
1
8
6
7
36
4
1
2
3
1
4
7
2
1
8
2
7
48
4
1
2
8
1
4
7
2
1
4
2
7
60
4
1
2
8
1
4
7
2
1
8
6
7
72
4
1
2
8
1
4
7
2
1
8
2
7
Table 4.1. The SG-values for Kayles. Entries for the Table are for
g
(
y
+
z
)
where
y
is on the left side and
z
is at the top.
From
x
= 72 on, the SG-values are periodic with period 12, with the values in the
last line repeating forever. The 14 exceptions to the sequence of the last line are displayed
in bold face type. The last exception is at
x
= 70. Since we know all the SG-values, we
may consider the game as solved. This solution is due to Guy and Smith (1956).
3.
Dawson’s Chess.
One of T. R. Dawson’s fanciful problems in
Caissa’s Wild Roses
(1935), republished in
Five Classics of Fairy Chess
by Dover (1973), is give-away chess
played with pawns. “Given two equal lines of opposing Pawns, White on 3rd rank, Black
on 5th,
n
adjacent files, White to play at losing game, what is the result?” (Captures must
be made, last player to move loses.) We treat this game here under the normal play rule,
that the last player to move wins.
Those unfamiliar with the movement of the pawn in chess might prefer a di
ff
erent way
of describing the game as a kind of mis´
ere tic-tac-toe on a line of
n
squares, with both
players using X as the mark. A player may place an X on any empty square provided it
is not next to an X already placed. (The player who is forced to move next to another X
loses.)
This game may also be described as a game of removing chips from a pile and possibly
splitting a pile into two piles. If
n
= 1 there is only one move to
n
= 0, ending the game.
For
n >
1, a move of placing an X at the end of a line removes the two squares at that end
of the line from the game. This corresponds to removing two chips from the pile. Similarly,
placing an X one square from the end corresponds to removing three chips from the pile.
Placing an X in one of the squares not at the end or next to it corresponds to removing
three chips from the pile and splitting the pile into to parts. Thus the rules of the game
are: (1) You may remove one chip if it is the whole pile, or (2) you may remove two chips
from any pile, or (3) you may remove three chips from any pile and if desired split that
pile into two parts.
The Sprague-Grundy sequence for Dawson’s chess begins
x
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
g
(
x
)
0
1
1
2
0
3
1
1
0
3
3
2
2
4
0
5
2
2
3
I – 25

It is eventually periodic with period 34. There are only 7 exceptions and the last exception
occurs at
n
= 51. Can you find the winning move on a line of 18 squares? Armed with the
above Sprague-Grundy sequence, you may hone your skill at the game by playing against
the computer at
˜
tom/Games/dawson.html .