The octal games are a class of two-player games that involve removing tokens (game pieces or stones) from heaps of tokens.
They have been studied in
combinatorial game theory
Combinatorial game theory is a branch of mathematics and theoretical computer science that typically studies sequential games with perfect information. Study has been largely confined to two-player games that have a ''position'' that the players ...
as a generalization of
Nim,
Kayles
Kayles is a simple impartial game in combinatorial game theory, invented by Henry Dudeney in 1908. Given a row of imagined bowling pins, players take turns to knock out either one pin, or two adjacent pins, until all the pins are gone. Using the ...
, and similar games.
[ Revised and reprinted as]
Octal games are
impartial
Impartiality (also called evenhandedness or fair-mindedness) is a principle of justice holding that decisions should be based on objective criteria, rather than on the basis of bias, prejudice, or preferring the benefit to one person over another ...
meaning that every move available to one player is also available to the other player.
They differ from each other in the numbers of tokens that may be removed in a single move, and (depending on this number) whether it is allowed to remove an entire heap, reduce the size of a heap, or split a heap into two heaps. These rule variations may be described compactly by a coding system using
octal
The octal numeral system, or oct for short, is the radix, base-8 number system, and uses the Numerical digit, digits 0 to 7. This is to say that 10octal represents eight and 100octal represents sixty-four. However, English, like most languages, ...
numerals.
Game specification
An octal game is played with tokens divided into heaps. Two players take turns moving until no moves are possible. Every move consists of selecting just one of the heaps, and either
* removing all of the tokens in the heap, leaving no heap,
* removing some but not all of the tokens, leaving one smaller heap, or
* removing some of the tokens and dividing the remaining tokens into two nonempty heaps.
Heaps other than the selected heap remain unchanged. The last player to move wins in ''normal play''. The game may also be played in
misère play'', in which the last player to move loses.
Games played with heaps in this fashion, in which the allowed moves for each heap are determined by the original heap's size, are called ''Taking and Breaking games'' in the literature.
Octal games are a subset of the taking and breaking games in which the allowed moves are determined by the number of tokens removed from the heap.
The octal code for a game is specified as
:0 . ''d''
1 ''d''
2 ''d''
3 ''d''
4 …,
where the octal digit ''d''
''n'' specifies whether the player is allowed to leave zero, one, or two heaps after removing ''n'' tokens from a heap. The digit ''d''
''n'' is the sum of
* 1 if leaving zero heaps is permitted, 0 otherwise;
* 2 if leaving one heap is permitted, 0 otherwise; and
* 4 if leaving two heaps is permitted, 0 otherwise.
Zero tokens are not counted as a heap. Thus the digit ''d''
''n'' is odd if a heap of ''n'' tokens may be removed entirely, and even otherwise. The specification of one-heap results in ''d''
''n'' applies to removing ''n'' tokens from a heap of more than ''n''. The two-heap results in ''d''
''n'' apply to removing ''n'' tokens from a heap of at least ''n''+2, and separating the remainder into two nonempty heaps.
Octal games may allow splitting a heap into two parts without removing any tokens, by use of the digit 4 to the left of the decimal point. This is similar to the move in
Grundy's game
Grundy's game is a two-player mathematical game of strategy. The starting configuration is a single heap of objects, and the two players take turn splitting a single heap into two heaps of different sizes. The game ends when only heaps of size two ...
, which is to split a heap into two unequal parts. Standard octal game notation, however, does not have the power to express the constraint of unequal parts.
Octal games with only a finite number of non-zero digits are called ''finite octal games''.
Particular octal games
Nim
The most fundamental game in
combinatorial game theory
Combinatorial game theory is a branch of mathematics and theoretical computer science that typically studies sequential games with perfect information. Study has been largely confined to two-player games that have a ''position'' that the players ...
is
Nim, in which any number of tokens may be removed from a heap, leaving zero or one heaps behind. The octal code for Nim is 0.333…, appearing in the published literature as
:
,
to signify the repeating part as in a
repeating decimal
A repeating decimal or recurring decimal is decimal representation of a number whose digits are periodic (repeating its values at regular intervals) and the infinitely repeated portion is not zero. It can be shown that a number is rational if an ...
. It is important to realize, however, that the repeating part does not play the same role as in octal fractions, in that the games
:
and
:
are not identical, despite their equality as octal fractions.
Kayles
The game
Kayles
Kayles is a simple impartial game in combinatorial game theory, invented by Henry Dudeney in 1908. Given a row of imagined bowling pins, players take turns to knock out either one pin, or two adjacent pins, until all the pins are gone. Using the ...
is usually visualized as played with a row of ''n'' pins, but may be modeled by a heap of ''n'' counters. One is allowed to remove one or two tokens from a heap and arrange the remainder into zero, one, or two heaps. The octal code for Kayles is 0.77 .
Dawson's Chess
''
Dawson's Chess'' is a game arising from a chess puzzle posed by
Thomas Rayner Dawson
Thomas Rayner Dawson (28 November 1889 – 16 December 1951) was an English chess problemist and is acknowledged as "the father of Fairy Chess". He invented many fairy pieces and new conditions. He introduced the popular fairy pieces grassh ...
in ''Caissa's Wild Roses'', 1938. The puzzle was posed as involving opposed rows of pawns separated by a single rank. Although the puzzle is not posed as an
impartial game In combinatorial game theory, an impartial game is a game in which the allowable moves depend only on the position and not on which of the two players is currently moving, and where the payoffs are symmetric. In other words, the only difference betw ...
, the assumption that captures are mandatory implies that a player's moving in any file results only in the removal of that file and its neighbors (if any) from further consideration, with the opposite player to move. Modeling this as a heap of ''n'' tokens, a player may remove an entire heap of one, two, or three tokens, may reduce any heap by two or three tokens, or may split a heap into two parts after removing three tokens. Dawson's Chess is thus represented by the octal code 0.137.
Dawson's Kayles
In the game 0.07, called ''Dawson's Kayles'', a move is to remove exactly two tokens from a heap and to distribute the remainder into zero, one, or two heaps. Dawson's Kayles is named for its (non-obvious) similarity to Dawson's Chess, in that Dawson's Kayles heap of ''n''+1 tokens acts exactly like a Dawson's Chess heap of ''n'' tokens. Dawson's Kayles is said to be a first cousin of Dawson's Chess.
Generalization to other bases
Octal games like
Nim, in which every move transforms a heap into zero or one heaps, are called
quaternary games because the only digits that appear are 0, 1, 2, and 3. The octal notation may also be extended to include
hexadecimal games, in which digits permit division of a heap into three parts. In fact, arbitrarily large bases are possible. The analysis of quaternary, octal, and hexadecimal games show that these classes of games are markedly different from each other,
and the behavior of larger bases has not received as much scrutiny.
Nim-sequence
The
Sprague–Grundy theorem
In combinatorial game theory, the Sprague–Grundy theorem states that every impartial game under the normal play convention is equivalent to a one-heap game of nim, or to an infinite generalization of nim. It can therefore be represented as ...
implies that a heap of size n is equivalent to a
nim heap of a given size, usually noted G(n). The analysis of an octal game then consists in finding the sequence of the nim-values for heaps of increasing size. This sequence G(0), G(1), G(2) ... is usually called the nim-sequence of the game.
All ''finite'' octal games analyzed so far have shown a nim-sequence ultimately periodic, and whether all finite octal games are ultimately periodic is an open question. It is listed by
Richard Guy as an important problem in the field of
combinatorial games.
[Richard K. Guy, Unsolved problems in Combinatorial Games, Games of No Chance, 1996]
Computation records
A complete analysis of an octal game results in finding its period and preperiod of its nim-sequence. It is shown in
Winning Ways for your Mathematical Plays that only a finite number of values of the nim-sequence is needed to prove that a finite octal game is periodic, which opened the door to computations with computers.
Octal games with at most 3 octal-digits have been analyzed through the years. There are 79 non-trivial octal games, among which 14 have been solved:
* .156 by Jack Kenyon in 1967
* .356, .055, .644 and .165 by Richard Austin in 1976
* .16, .56, .127 and .376 by Anil Gangolli and Thane Plambeck in 1989
* .454, .104, .106, .054 and .354 by Achim Flammenkamp between 2000 and 2002
[Achim Flammenkamp]
Octal games
/ref>
There remain 63 of these games, despite the computation of millions of nim-values by Achim Flammenkamp.
References
{{DEFAULTSORT:Octal Game
Combinatorial game theory
Mathematical games