Octal game
Octal game
Octal games are a subclass of heap games that involve removing tokens (game pieces or stones) from heaps of tokens. They have been studied in combinatorial-game-theory as a generalization of nim, kayles, and similar games.
Octal games are impartial 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 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. 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, 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 a 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,
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 167 inequivalent octal games with no more than 3 octal-digits: 144 beginning with 0 and 23 beginning with 4. Of those, 79 of the former and 14 of the latter have nim-sequences that repeat within 250 terms. Of the rest, only 20 have been solved, despite the computation of millions of nim-values by Achim Flammenkamp: .45 in 1956 .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 4.064, 4.344, 4.364, 4.404, and 4.406