G13GAM -- Game Theory

Octal Games

Many impartial games can be described in ways which are variants of Nim or Kayles. As variants of Nim, you have heaps of matches [pebbles, whatever], and you remove some of the matches from one of the heaps at each turn; the precise rules by which you remove matches determine the variant. As variants of Kayles, you have rows of skittles, and you knock down some of the skittles from one of the rows at each turn. All of these games also have logical equivalents in terms of drawing lines through or round dots [Rims and Rayles], moving coins [Silver Dollar], and other grouping or crossing-off rules [examples in the coursework].

Octal games are simply a way of codifying the rules of such games. Each possible game [within this general scheme] is described by a number, 0.abcdef..., where a describes the rule under which you may remove one match or knock down one skittle, b the rule under which you may remove two, c for three, d for four, and so on. Each digit, a, b, c, ... is in the range 0 to 7, so the number is in fact an octal [base-8] `decimal' expansion of a real number; hence `octal' games,

What does each digit signify? A digit in the range 0 to 7 comprises: (a) a `component' 1 [= 20], which is `switched on' in the odd digits, 1, 3, 5 and 7, and `switched off' in the even digits, 0, 2, 4 and 6; (b) a `component' 2 [= 2¹], which is switched on in 2. 3. 6 and 7 and off in 0, 1, 4 and 5; and (c) a `component' 4 [= 2²], which is switched on in 4, 5, 6 and 7 and off in 0, 1, 2 and 3. The component 2j is switched on if and only if removing the current number of matches or skittles is allowed to leave j heaps or rows from the current one. For example, the digit is odd if and only if you are allowed, under this rule, to empty a heap completely. The component 2 covers whether or not you are allowed to remove the current number of matches from a large heap. The component 4 covers whether or not you may take this number from the middle of a row of skittles [so that two disjunctive rows are left].

Thus, our standard Nim is 0.333333... [you may remove any number of matches you like from any heap with at least that number of matches], and Kayles is 0.77 [you may remove either one or two skittles, which may be the whole of a row, or from the end of a row (leaving one row behind) or from the middle of a row (leaving two rows behind)]. Further, 0.222222... would be a variant of Nim in which you could never take the last match from any pile; and 0.137 [Dawson's Kayles] is the version of Kayles in which you must select for removal a skittle and its immediate neighbours, so that you can take three skittles from anywhere, but two only from the end of a row [so that the skittle has only one neighbour] and one only from a row of size one [so that the skittle has no neighbours].

It should be clear that 0.222222... is not an interesting variant of Nim: if you mark one match in each pile, then the rule is that you play exactly like Nim except that you can never remove the marked match; but in that case, the marked matches are never used, and you might just as well remove them before play, and then play ordinary Nim, but on heaps that are one smaller than the ones you started with. This is an example of one of the `cousinhood' rules: a rule of type 2 is exactly equivalent to a rule of type 3 applied to heaps or rows that are one smaller.

Are there other similar cousinhood rules? Take the simplest one first: a rule of type 1 [`you can take away all the matches of a heap'], if applied to heaps one smaller, remains a rule of type 1, but must take away one fewer match, so the digit moves `left' in the octal number. The other case is the rule of type 4. To see how this might change, consider for example the game 0.04 [`take two skittles from the middle of a row']. The smallest row this can be applied to is one of size 4, from which the only move is to take the two middle skittles. From a row of size, for example, 10, there are 4 moves: you can take skittles 2 and 3 [equivalently 8 and 9], or 3 and 4, or 4 and 5, or 5 and 6, leaving behind rows of sizes 1 and 7, 2 and 6, 3 and 5 or 4 and 4 respectively. How would this apply if all the rows, both before and after, were one smaller? Then the rule would have to be such that a row of 3 could be removed completely [instead of leaving two single skittles], and from a row of [for example] 9, you could move to 0 and 6, 1 and 5, 2 and 4 or 3 and 3. But these are exactly the moves you get if you apply the rule `take any three consecutive skittles from a row of at least 3' which is the game 0.007.

So the general rule is that any octal game has a theory which applies equally to a certain octal game which has heaps or rows one smaller, provided that (a) each constituent 1 is moved left; (b) each constituent 2 becomes a 3; and (b) each constituent 4 is moved right and becomes a 7. This process stops when the leading digit becomes odd, so that the resulting 1 cannot be moved left. For example, 0.0423 becomes 0.0073 becomes 0.0137 becomes 0.11337, which is the `canonical form' of this game as the leading 1 can no longer be moved left. The first step in this can be thought of as 0.0423 = 0.0400, 0.0022, 0.0001 becomes 0.0070, 0.0033, 0.0010 = 0.0073. Note that 7, 3, 1 is still 7; the components merely describe possibilities, and things that are possible in several ways do not thereby become either more or less possible. We see that 0.04, 0.0401, 0.007 and several other games also have 0.11337 as canonical form, and are therefore essentially the same game as 0.0423; the extra possibilities in 0.0423 have no effect [as you can see if you look at the available moves when 0.0423 is played with heaps or rows of various sizes].

In other words, the way to play 0.0423 is: (a) remove any heaps or rows of size less than 4 [in which there are no legal moves]; (b) take 3 matches from each heap [as the canonical game is the 3rd cousin of 0.0423]; (c) now determine the correct move in 0.11337, from its Grundy sequence, etc.; and (d) translate that back into 0.0423 by adding 3 matches back to every heap. So, you don't need to understand all octal games, only those that are in canonical form!

Winning Ways includes much more information about octal games, including tables of Grundy sequences, canonical forms, periodicities, reasons for frequent and rare Grundy numbers, and much besides. There is plenty of scope for projects in all this! As we have seen, many of the most important impartial games can be described as octal games; but many others cannot, including Grundy's game [`split a heap into two unequal parts'] and Nim-variants in which matches are taken from two or more heaps under various conditions.

top of page


E-mail: [my initials] [at] cuboid.me.uk, home page: http://cuboid.me.uk/anw.

Copyright © Dr A. N. Walker, 1997, 2016.