Related Links (Outside this Site)

DMOZ: Combinatorial Game Theory

(2002-02-12) [abridged]
According to Sam Loyd, the American school game of "Dots and Boxes" was played in the East on a grid of 16 dots [conveniently identified here by latin letters]. Each player moves in turn by drawing a vertical or horizontal line between 2 adjacent unconnected dots. The same player moves again if this line completes one of the 9 "boxes" (or elementary squares). The purposes of the game is to complete ("own") as many boxes as possible. Whoever owns the most at the end wins.
In the situation pictured here, what's the best play for the next player? How many boxes will she own against a skillful opponent?

By playing GH, the first player will end up owning 7 boxes and leave only 2 boxes to the opponent.

Before showing the strategy to do so, let's demonstrate that any of the other 11 available moves would give a lesser result: MN, IJ, EF, BF and CG allow the opponent to obtain 4 boxes on the next turn alone (so best play would necessarily yield at least that). Similarly, GK, JK, KO and LP allow the opponent to capture 3 boxes in the next turn. The first player should definitely avoid playing DH or HL: If she plays either one, her opponent could play the other and would capture all 9 boxes on her next turn, irrespective of the first player's reply.

On the other hand, if the first player's (brilliant) first move is to mark GH, then she will always be able to capture 7 boxes, no matter what her opponent does. Her best strategy is always to "give away" 2 boxes (that's all she will have to give up) by playing a waiting move on her next turn... Let's see:

If the opponent marks IJ, the first player will take 3 boxes by marking MN, EF, BF, then play the waiting move DH (instead of taking the 2 boxes still available). This way, the opponent cannot avoid giving up 4 boxes.  The same thing applies if the opponent's first move is MN, EF, BF, CG or DH (in the last two cases, the closing waiting move must be MN). If the opponent's first move is to mark JK, GK, KO, LP or LH, the first player then takes only two boxes out of the 4 available (her waiting move is either HL or LP). The opponent is then forced to give up the chain of 5 squares. In all cases, therefore, the first player will obtain at least 7 boxes with skillful play, starting with the marking of GH.

Note that the entire game has been analyzed by computer for small boards. If there are n open lines left, there are 2ⁿ positions that could appear in the future (present position included). By evaluating all such positions, starting with those with the fewest numbers of open lines, the current position can be evaluated perfectly in a time proportional to 2ⁿ. We thus analyze n! possible sequences of moves (legal or not) by analyzing only 2ⁿ positions.

The above 3 by 3 game (9 boxes, 16 dots, n = 24 open lines at the beginning) turns out to be a win for the second player who can always capture at least 6 boxes and leave only 3 for the first player. (The first player's opening move turns out to be irrelevant to the final score in perfect play.) It is customary to rate games from the first player's perspective, so that the 3 by 3 game is rated -3 (the first player ends up with 3 boxes less than the opponent).

References

• Dots and Boxes  (Applet)  by Cory Alleyne  (before 2004-12-31).
• Sam Loyd [Edited by Martin Gardner]
  "Mathematical Puzzles of Sam Loyd" (#91, pp. 88-89 & 152-153)
  A selection from the Cyclopedia of Puzzles (1914)
  Dover Publications (New York, NY)   ISBN 0-486-20498-7. © 1959
• Elwyn R. Berlekamp  (1940-2019)
  "The Dots and Boxes Game: Sophisticated Child's Play"
  A K Peters (Natick, MA)   ISBN 1-56881-129-2. © 2000

This game was known to all French children of my generation as  petits carrés  (small squares).  According to  John Conway,  it surfaced at  Polytechnique  (my  alma mater)  during the  Napoleonic era. and was once called  Jeu de Polytechnique.

ianscott (2002-02-13)   The Game of Nim
Please, explain how this card scam works:  There are 16 cards in 4 rows of   1, 3, 5 and 7 cards.  The two players take turns removing as many cards from one row as they like.  Whoever picks up the last card loses.  After playing for money, I realized my opponent knew a secret for winning...  What's the formula for winning?

If you play first, you will always lose against a skillful opponent.  This game was made popular in 1961 by the cult film of Alain Resnais, written by Alain Robbe-Grillet  "L'année dernière à Marienbad"  ( Last Year at Marienbad ) starring Delphine Seyrig ("A"), Giorgio Albertazzi ("X"), and Sacha Pitoëff ("M").

This game is of a well-known variety where the winning strategy is almost the same for the two standard rules of play [normal and misère] described below.  The thing was first analyzed in 1901 by C.L. Bouton, an associate professor of mathematics at Harvard University who gave the game its modern name:  "Nim". Bouton derived the word from the imperative form (nimm) of the German verb nehmen ["to take"]; it's only a coincidence that the Chinese nian character [also meaning "to pick up" or "to take"] happens to be pronounced nim in Cantonese! Nim is superficially similar to some ancient games, but it's not clear whether it was actually played exactly this way before Bouton's analysis...  In a 1902 article from Naturwissenschaftliche Wochenschrift (Scientific Weekly Review) , the German mathematician Paul Ahrens debunked Bouton's original identification of Nim with the unrelated Chinese game of Fan-Tan (which Bouton did recant), but the myth still persists to this day.

The game described above is the so-called misère version of Nim (whoever picks up the last card loses) but there's also a normal Nim (whoever picks up the last card wins), which seems less commonly played.

Winning Strategy for Normal Nim

We'll describe first the winning strategy for normal Nim [whoever plays last wins] because it's somewhat simpler [and easier to prove] than its misère counterpart:

What you do is express in binary the numbers of cards in each row.  There may be any number of rows and any number of cards in each row.  One is "1", two is "10", three is "11", four is "100", five is "101", six is "110", seven is "111", eight is "1000", nine is "1001", ten is "1010", etc.  Then, you add up all these numbers without carry.  In other words, count the rightmost bits and if there's an odd number of them that are equal to "1", the rightmost bit of the result is a "1", otherwise it's a "0".  Do the exact same thing for the second rightmost bits, the third rightmost bits, etc. to compute the corresponding bits in the result. For example with rows of 1,3,5,7 cards, adding without carry the binary numbers "1", "11", "101" and "111" gives you "000" (or "0") because there's an even number of bits in each "column".  This special type of binary addition without carry is commonly called a Nim-sum or a bitwise xor (in logic, the value "A xor B" is true when either A or B is true but not both). It is available under related names in many computer languages, all the way down to machine language itself.

It turns out that a position which has such a zero value is a loss for the first player against a skilled opponent.  On the other hand, a nonzero value is a first-player win.  To see this, you have to realize that there's always at least one (winning) move which will turn a nonzero value into a zero one, whereas any move from a zero value makes the resulting value nonzero and is therefore a losing move (this is not difficult to prove if you care to do so).  Under the "normal" rule, the empty position with no card on the table is a losing position (the other guy just took the last card and claimed a win) and this would allow us to establish neatly (by induction) the above claim for any nonzero number of cards.

Winning Strategy for Misère Nim

Under the misère rule of play [whoever plays last loses], the proof by induction we just outlined for the normal game will not work as is, but it can easily be fixed by reconsidering only one type of endgame situations:  It turns out that the winning strategy is still to force your opponent to play from a zero value (as under the normal rule presented above) except that you should never leave your opponent with an even number of rows with just a single item in each (these are the only positions which have a different win/loss status under the two different rules).  Whenever you are called upon to play in a situation where there's only one row containing more than one item, you should therefore leave an odd number of rows with a single item [and you may always do so, either by removing all the items from the largest row or by leaving just one in it].  Other than that, you should play misère Nim exactly like you would play normal Nim!

With this strategy, you can't lose if you play second from the classical "Marienbad" initial position described in the question.  If you have to play first, you'll win only if your opponent makes a mistake (but opponents who are not aware of the above will very rarely play perfectly).

The reason why the "normal" rule of play is called that way is because it's more logical to decide that you lose when you no longer have any move available.  (If you don't have a good move, you're losing.  If you don't have any move at all, you've lost.)  What the above shows is that winning is all about keeping the upper hand:  Paradoxically, the winning "nodes" of the game tree are very often independent of the win/lose status of the "leaves" (except in the endgame).

References

• Charles Leonard Bouton (1869-1922)
  "Nim, a game with a complete mathematical theory"
  Ann. Math. Princeton, Series 2, Vol. 3, pp. 35-39 (1902).

(2002-02-19)
What's the  Sprague-Grundy number  of a position in a game?

Loosely speaking, it's the size of the Nim-row that's equivalent to the position. More precisely, the Grundy number of any game position is the nonnegative integer which is recursively defined as equal to the minimal excluded value (mex) among the Grundy numbers of all the positions that can be reached in one legal move from that particular game position.

The minimal excluded value, or mex, of a set of nonnegative integers is the lowest nonnegative integer not in the set. For example, the mex of the empty set is 0. The mex of {0,1,3} is 2, the mex of {1,3} is 0, etc.

I'll leave it to the reader to prove that the so-called Nim-sum of the Grundy numbers of several games is the Grundy number of the game obtained by playing them simultaneously under the rules of normal Nim (whereby both players take turns making a move in one and only one of such game component until no move is available and whoever played last is declared the winner). A special case of this is the ordinary game of normal Nim itself, described above, where the Grundy number of a Nim-row turns out to be simply the size of that row.

The next article shows that it's also easy to obtain the Grundy number of the game obtained by allowing a player to make a move in fewer than b such components at each turn (regular Nim being the special case b = 2).

This was discovered independently by  Roland Sprague  (who was a grandson of Hermann Schwarz, 1843-1921)  in 1935  and  Patrick Grundy  in 1939.

References :

• Roland Percival Sprague  (1894-1967)
  "Über mathematische Kampfspiele"
  Tôhoku Mathematical Journal, vol. 41,  pp. 438-444  (1936). 
• Dr. Patrick Michael Grundy (1917-1959)
  "Mathematics and Games"
  Eureka, vol. 2,  pp. 6-8  (1939).   [ &  vol. 27,  pp. 9-11  (1964) ]

(2002-02-17) Moore's Nim
A winning strategy for some game is to assign each independent component of the game [the equivalent of a "row" in the previous article] some bit pattern.  The "value" of the combined components is obtained by adding up such bit patterns without carry in base b  (say b = 3).  A zero "value" indicates a losing position;  a first-player win has nonzero value. What could be the rules for such a game?

This strategy is the correct one for a  normal  game  [whoever plays last wins]  in which a turn consists of playing at least one and at most (b-1) components each associated with a "bit pattern" equal to the nim-value described in the previous article for rows of cards.  [We'll use this as a concrete example.]

As posed, this is definitely a solution looking for a problem, but the easy winning strategies (similar to that of Nim) are so rare that it does make sense to describe them first and then find what "actual" games they may correspond to.

If we are allowed to play simultaneously ["remove cards"] in at least one and at most b-1 components ["rows"], we can't possibly go from a zero value to another zero value.  That's because for each bit column, a player can only change the value of at most b-1 bits this way.  For such changes to add up to zero modulo b, not a single bit can change.  If that's true of every bit column, it's not difficult to see that not a single bit row can change.  As a player is required to change at least one such row, there's indeed no move from a zero position into another zero position.

That remark is half of what we need to prove our claim...  We'll skip the tedious proof that there's always a legal move from any nonzero position to a zero one.

Here is a concrete example:  Let's consider the {1,3,5,7} starting position pictured at right with b = 3  [each player must play in 1 or 2 rows at each turn].  The position's ternary value is "221" and implies that the leftmost bit tally must be reduced by 2 (modulo 3), which can clearly be done only if we play the lower two rows.  For every column of bits to add up to zero modulo 3, we must leave these last two rows with respectively 2 and 3 items in them.  Which of these rows is left with which is entirely irrelevant (although this makes for two apparently distinct legal moves:  either remove 3 items from the third row and 4 items from the last one, or remove 2 items from the third row and 5 from the last one). 
      Discarding the order of the rows, we may describe a position as the set of the numbers in the remaining rows. After the above (winning) move, the first player is thus said to have left a {1,2,3,3} position to the opponent.  This compact notation allows the winning strategy described above to be made explicit in this simple case (from a {1,3,5,7} initial position).  The corresponding table below shows that the first player wins in 2, 3, or 4 moves:

Player 1 Move 1	Player 2 Move 1	Player 1 Move 2	Player 2 Move 2	Player 1 Move 3	Player 2 Move 3	Player 1 Move 4
{1,2,3,3}	{1,2,2,2} {1,2,2,3} {2,2,3} {2,3,3}	{2,2,2}	{1,2,2} {1,1,2}	{1,1,1}	{1,1} {1}	{}
			{1,2} {2,2} {2}	{}
	{1,1,2,3} {1,1,3,3} {1,2,3} {1,3,3}	{1,1,1}	{1,1} {1}	{}
	{1,2} {1,3} {2,3} {3,3}	{}

References

• E.H. Moore (1862-1932)
  "A Generalization of the Game Called Nim"
  Ann. Math. Princeton, Series 2, Vol. 11, pp. 93-94 (1909-1910)

(2002-02-18) Normal Kayles
Consider the following game, invented by H.E. Dudeney (1857-1930) and known as "Kayles":  A number of pins are arranged in separate rows.  A legal move consists of knocking down either one pin or two adjacent pins from the same row. This may break up the row into two smaller rows.  Whichever player knocks down the last pin wins.  What's the winning strategy for the game of Kayles?

It turns out that the winning strategy for Kayles reduces to that for normal Nim (the misère version of Kayles is more difficult to analyze).  The same remark would apply to the normal [as opposed to misère] version of any impartial game [that is, a game where no part of the playing field is the "private property" of either player] where a legal move consists of replacing one of several components by zero or more new components [read this again, if you must].

In normal Nim, the "components" are rows and the rules of Nim state essentially that a legal move consists of eliminating a component or replacing it by a strictly smaller one.  In Kayles, components are also rows and there are similar principles in force about the replacement of a component.  The fact that a component may be replaced by several (two in the case of Kayles) is not a problem because several rows of Nim have been shown to be equivalent to a single Nim-row of the same value [obtained by adding without carry the binary expressions for the numbers in each row, as explained above].  This will allow us to show that a Kayles-row of length n is entirely equivalent to some Nim-row whose length can be determined.  Let's first examine the shortest Kayles-rows:

From a Kayles-row of length 0,1, or 2, you have exactly the same moves available (under Kayles rules) as you do from a Nim-row of the same length (under Nim rules). Theses short rows are thus equivalent for either game.  A Kayles-row of length 3 is also equivalent to a Nim-row of length 3:  Although you may not knock down all 3 pins from such a Kayles-row, you are allowed to knock down the center pin and leave two separate one-pin rows, and that's equivalent to an empty Nim-row (remember we are playing under the normal rule here, we would be in trouble at this point with misère play).  Things are different for a Kayles-row of length 4:  From a Kayles-row of size 4, legal moves will leave one of the following sets of Kayles-row sizes: {3}, {2}, {1,2}, {1,1}, whose respective Nim-values are 3, 2, 3 and 0.  The number "1" is the smallest nonnegative integer not in this list (it's the minimal excluded value, also called minimal excludant or mex). Therefore, a Kayles-row of length 4 is equivalent to a Nim-row of size 1. 

The equivalent Nim-value of a position is indeed the least Nim-value which is not accessible from a position, because when you play in a Nim-row you change its size.  In standard Nim, you will always lower the size of the row you play (a so-called "canonical move"), but you may convince yourself that allowing some (noncanonical) Nim moves which increase the size of a row will not change the outcome of the game in perfect play (provided we know the game eventually terminates).  This is so because whoever is winning is always able to revert back to a zero position after a "noncanonical" move, for example by playing in the same row again...

In general, we see that the Nim-value of a Kayles-row is the smallest value not obtainable as the Nim-sum of the Nim-values of the two [possibly empty] Kayles-rows resulting from a legal move.  (Such a value is called the minimal excluded value, minimal excludant, or mex for short. The process is a special case of the computation of so-called Grundy numbers for impartial games.)  This makes it easy to compute the following table:

The Nim equivalence in Kayles for rows with a length of 20 or less:

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
	0	1	2	3	1	4	3	2	1	4	2	6	4	1	2	7	1	4	3	2	1

If we continue the above table (see A002186), we notice that the values ultimately repeat with period 12.  (it turns out that only 14 special cases do not follow the general periodic pattern).

The regular period, starting at some multiple of 12 (e.g. 1200):

1200	1201	1202	1203	1204	1205	1206	1207	1208	1209	1210	1211
4	1	2	8	1	4	7	2	1	8	2	7

There are only 14 exceptional values:

0	3	6	9	11	15	18	21	22	28	34	39	57	70
0	3	3	4	6	7	3	4	6	5	6	3	4	6

To prove this ultimate periodicity, we may remark that it cannot fail in the long run if it has been observed to hold long enough (this is a form of proof by induction):

To be more precise, suppose that the Grundy numbers of Kayles rows of sizes n and n-12 have been shown to be the identical for any n between 83 and some M at least equal to 167. We may prove that the same must holds for n = M+1.  We'll do so by showing that any position which results from a move in a row of size M+1 has the same Grundy number as some position resulting from a legal move in a row of size M-11. Establishing this and the converse will show that rows of size M-11 and M+1 have identical Grundy numbers:

Consider any legal move from a row of size M+1. It breaks that row into two rows, let P be the size of the smaller one (P may be zero) and Q be the size of the larger one.  Since M+1 is at least 168, Q is at least 83 and this larger row has therefore the same Grundy number as a row of size Q-12.  Any legal move from a row of size M+1 is thus seen to result in the same Grundy number as some move from a row of size M-11 (which may indeed be broken up into two rows of size P and Q-12).  The set of all such results is thus included in the corresponding set for a row of size M-11, which implies that the minimal excluded value of the former is less than or equal to that of the latter.  In other words, the Grundy number for a row of size M+1 is at most the Grundy number for a size M-11.

Conversely, when breaking up a row of size M-11 into two rows of size P' and Q' (with Q' at least equal to P' and P' possibly zero), Q' is at least 78 and at most M-12 (Q'+12 is at least 90 and at most M). This implies that rows of size Q' and Q'+12 have the same Grundy number.  As a breakup into sizes P' and Q'+12 is a legal move from a row of size M+1, the same argument as above now shows that the Grundy number for a row of size M+1 is at least the Grundy number for a row of size M-11.  This completes the demonstration that these two numbers are indeed equal and formally terminates the proof (by induction) that the sequence of Grundy values of Kayles rows is forever periodic of period 12, simply because it is observed to be so between 71 and 167...

The above proof of the ultimate periodicity of the Kayles sequence is by no means difficult, although the question has been listed as open [sic!] by some Internet authors (who probably mistook the problem with its difficult counterparts concerning similar games like Grundy's game, which is described below).

    Henry Ernest Dudeney (1857-1930), whose name rhymes with "scrutiny", first proposed this combinatorial game in his regular puzzle column (see 1902-01-26 issue of The Weekly Dispatch).  It appears also in Dudeney's first book (1907), "The Canterbury Puzzles", with the illustration at right. "Kayles" used to be the name of several British bowling games, dating back at least to the 14th century.  The word comes from the French word "quilles" (bowling pins or skittles), mispronounced and retranscribed phonetically... In French, Dudeney's Kayles are called "les quilles de Dudeney".
    The association of this mathematical game with bowling comes from Dudeney's original presentation, also popularized by Sam Loyd, as a straight row of bowling pins which players can easily knock down, either singly or in adjacent pairs (by aiming between them).  Both Dudeney and Loyd only proposed the particular starting position shown in either one of the above two illustrations (the first of which we clipped from Loyd's own version): A row of 13 pins with the second one already knocked down.  Dudeney's solution does not involve the whole theory given above... He merely states that: "To win at this game, you must, sooner or later, leave your opponent an even number of similar groups.  Then whatever he does in one group, you repeat in a similar group." On that basis, he explains [in only 21 short lines] that "the first player can always win, but only by knocking down the sixth or tenth kayle (counting the one already fallen as second)".
    For the record, "Dawson's Kayles" is a variant of the game where knocking down a single pin is not allowed... (It was not invented by Dawson; it's merely similar to another one of Dawson's own games.)

What if the rules allow up to k adjacent pins to be knocked down?

The same general arguments apply, but the Grundy numbers (or "Nim-values") for various row sizes are different.  Each line of the table below gives the Grundy sequence for the value of k which heads it.  (For k = 2, the first line corresponds to ordinary Kayles. Therefore, it's only a copy of the table given above.)

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
2	0	1	2	3	1	4	3	2	1	4	2	6	4	1	2	7	1	4	3	2	1
3	0	1	2	3	4	1	6	3	2	1	6	7	4	5	8	1	10	5	4	7	6
4	0	1	2	3	4	5	6	7	3	2	8	9	7	6	5	4	3	2	8	9	4
5	0	1	2	3	4	5	6	7	8	3	2	11	12	7	6	5	4	3	2	1	16
6	0	1	2	3	4	5	6	7	8	9	3	11	12	13	7	6	5	4	3	2	16
7	0	1	2	3	4	5	6	7	8	9	10	3	12	13	14	7	6	5	4	3	16
8	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	7	6	5	4	16
9	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	7	6	5	4
10	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	7	6	5
11	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	7	6
12	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	7

Play Kayles  (in French)  by  Jean-Paul Davalan.

(2002-02-23)   Grundy's Game
The so-called Grundy's Game is a normal game [whichever player is unable to move loses] in which a legal move consists of splitting one row into two rows of unequal sizes (thus, rows of sizes 1 or 2 can't be split). What's the Grundy number of a row of size n in this game?

Grundy's Game is another example of a game which, like Kayles, is easy to play once we work out a table of Grundy numbers. The table below is computed using the same principles presented above for the game of Kayles: Here, this means that the Nim-value of a certain row size (n) is the minimal excluded value (mex) among all the possible Nim-sums of two Nim-values corresponding to two unequal row sizes which add up to n. [Whew! Read that again!]

The Nim-values in Grundy's Game for rows with a size of 20 or less:

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
	0	0	0	1	0	2	1	0	2	1	0	2	1	3	2	1	3	2	4	3	0

It's not clear whether this sequence (A002188) is ultimately periodic (like the one for ordinary Kayles). Here are its first 1000 terms (20 per line):

  0: (0) 0  0  1  0  2  1  0  2  1  0  2  1  3  2  1  3  2  4  3
 20:  0  4  3  0  4  3  0  4  1  2  3  1  2  4  1  2  4  1  2  4
 40:  1  5  4  1  5  4  1  5  4  1  0  2  1  0  2  1  5  2  1  3
 60:  2  1  3  2  4  3  2  4  3  2  4  3  2  4  3  2  4  3  2  4
 80:  5  2  4  5  2  4  3  7  4  3  7  4  3  7  4  3  5  2  3  5
100:  2  3  5  2  3  5  2  3  5  2  3  5  2  3  5  2  3  5  2  3
120:  5  2  3  5  2  4  5  2  4  5  2  4  5  2  4  5  2  4  8  2
140:  4  8  2  4  3  2  6  3  2  6  3  2  6  3  2  8  3  2 11  3
160:  2 11  3  2 11  3  2 11  3  2  8  3  5  8  3  5  7  3  5  7
180:  3 12  7  3  8  7  3  8  7  3 12  5  3 12  5  3 10  5  3  4
200:  5  3  4  2  3  4  2  3  4  2  3  4  2  3  4  2  3  4  2  3
220:  4  2  3  4  2  3  4  2  3  4  2 10  1  2  5  1  2  5  1  2
240:  5  3  2  5  3  4  5  3  4  5  3  4  5  3  4  2  3  4  2  3
260:  4  2  3  4  2  3  4  2  3  4  0  3  4  0  3  4  0  3  4  2
280:  3  1  0 14  1  0 14  1  0  5  1 13  5  1 13  5  1 13  2  1
300: 13  2  1 13  2  1 13  2  1 13  2  3 13  2  3 13  0  3 14  2
320:  3 16  2  3  1  2 16  1  2 16  1  2 16  1  0 16  1  0 12  1
340:  0 12  1  5  2  1  0  2  1  5  2  1  5  2  8  3  2  4  3  0
360:  8  5  0  3  5  0  3  5  2  3  5  2  4  5  2  4  5  2  4 12
380:  7  4  3  7  4  3  0  4  3  0  2  3  0  2  3  5  2  3  5  2
400:  3  5  2  3  5  2  3  5  2  3  5  2  3  5  2  3  5  2  4  5
420:  2  4  5  2  4  5  2  4  5  2  4 16  2  4  3  2  4  3  2  8
440:  3  2  8  3  2  8  3  2  8  3  2 11  3  2 11  3  7 11  3  5
460: 11  3  5  4  3  5 14  3  5  7  3  5  2  3  7  2  3  8  2  3
480:  8  2  3  8  2  3 16  2  3 16  2  3  4  2  3  4  2  3  4  8
500: 11  4  2 11  9  2  4  6  5  4  6  5 13  6  2 13  6  2 16  6
520:  2 16  6  2 10  1  2 10  1  2  5  3  2  5  3  2  5  3  4  5
540:  3 21  5  3 21  5  3  9  2  3  9  2  3 16  5  3 16  5  3 16
560:  2  3 16  2  3  4  0  3  4  2  3  4  2  3  4  2 14  4  2  5
580:  4  2  5  4 13  5  4 13  5  4 13  5  4 13  5  4 13  5  4 13
600:  5  1 13  5  1 13  5  3  2  5  3 21  5  3 22  5  3  4  5  3
620: 18  5 16 18 13 22 18 13 22 18  0 22  3  0 12 16  0  2 16  0
640:  2 14  5  2  4 24 17  4 21 17  4 13 17  3 16 17  3 16 17  3
660: 21 17  3 24  2  4 24  2  4 22  9  4 22  0  4  3  0  4  3  5
680: 12  3  0  2 16  0  2 14 15  2 14  5  2  3 15 17  3 15  2  3
700:  5  2  3  5  2  3  5  2  3  5  2  4  5  2  4  5  2  4  5  2
720:  4  3  2  4  3  2  4  3  2  4  3  2  4  3  2 11  3  2 11  3
740:  2 11  3  2  4  3  2  4  3  5  4  3  5  4  3  5  4 12  5 22
760: 12  5  2 12  5  2 14 16  2  4 16  2 17 16  2 17 16  2  4 16
780:  2  4 10  2  3 10  2  3 24  2  4 26  2  4 23  2  4 23  2  4
800:  3  2  4  3  5 22  3  5 22  3  2 13  3  2 16  3  2 22  3  2
820: 22  3 16  5  3  2  5  3 10  5  4 10  5  4 23  8  3 23  8  3
840: 23  5  3 16  5  3 16  5  3 16  5  3 24  2  9 11  2  9 11  2
860: 20 23  2 20 23  2 20 23 26 22  4 26 22  4  2 22  4 24  5  4
880: 23  5  4 13  8  4 13  5  4  2  8  4  2  8  3  2  5  3  2  5
900:  3  2  5  3  2  5  3  4  5  3  4  5  3  4  5 12  4 26 12  4
920: 13 12  4  0 22  4  0 12  4  0 12  4  0 22  4  2 22  4  2 28
940:  4 13 17  4 13  5  3 16  5  3 16 17  3 16 17  1 24 17  1 21
960:  2  1 21 17  1 26  9 12  3 10 12  3 15 12  3 15 12 16  2 12
980: 14  2 17  4  2 17  4  2 17  3  2 17  3  2 22  3  5 22  3  5

Convincing heuristic arguments have been presented which imply that this sequence must be ultimately periodic, but this is not known for sure at this writing... The question has been open for decades!

For Grundy rows of sizes less than 10000, the highest Grundy number is 101, which is achieved for rows of sizes n=8337 and n=8511. That record is first broken with rows of size 11261, 11432 and 11551, all of which have a Grundy number of 113. The next record breaker is n=11621 (with a Grundy number of 118). For n below 32768, the highest Grundy number is 195 (achieved for n=28304 and n=28435). The highest such Grundy number we have seen listed anywhere is 297 (obtained for n=21544358589). However, this slow growth does not seem destined to go on forever, as the sequence has a structure which seems to imply that it cannot avoid ultimate periodicity. (The values break down into common and rare ones and the latter set of rare values seems to die out.)

Theoretically, if a periodic behavior were eventually observed to hold long enough (essentially, for at least one period longer than the length of the initial nonperiodic part) it would be easy to show that the pattern would hold forever, using a proof by induction virtually identical to the one we used to establish period 12 for the sequence of Grundy numbers in Kayles. For Grundy's game, however, the very large numbers involved make such a direct observation of periodicity extremely unlikely. This robs the direct proof of a proper basis. So far, more powerful (indirect) methods have been unsuccessful as well.

(2002-03-25) Wythoff's Game
Wythoff's Game is played with two heaps of counters under the normal play rule [whichever player is unable to move loses]. A move consists of either removing counters from one heap or the same number of counters from both. What's the winning strategy for Wythoff's Game?

This game used to be known in China as tsyan-shidzi ("choosing stones"). It was reinvented by the Dutch mathematician Willem Abraham Wythoff (1865-1939) [the Dutch spelling is Wijthoff ], who published its full analysis in 1907. Half a century later (around 1960) and unaware of this, the mathematician Rufus P. Isaacs (of Johns Hopkins University) gave another description of the same game in terms of the moves of a chess queen allowed only to travel south and/or west [the heap sizes are the queen's cartesian coordinates, both of which are zero when the queen is at the chessboard's southwest corner].  Under the name of Last Biscuit, the game is played by removing cookies from two jars  (either from a single jar, or the same number from both jars).

It turns out that there is a beautiful mathematical expression for the so-called safe positions in this game. The safe or zero positions are those for which whoever has to play may be forced to lose. When you play a game, you want to move into such a safe position, whenever one is available.

The Sequence of Safe (Zero) Pairs in Wythoff's Game

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24
0	1	3	4	6	8	9	11	12	14	16	17	19	21	22	24	25	27	29	30	32	33	35	37	38
0	2	5	7	10	13	15	18	20	23	26	28	31	34	36	39	41	44	47	49	52	54	57	60	62

The safe positions are {0,0}, {1,2}, {3,5}, {4,7}, {6,10}, {8,13}, ... {u_n,v_n}, where u_n and v_n are the n-th terms in a pair of sequences known as the lower and upper Wythoff sequences, which have very simple closed expressions:

u_n  =  ë n f û       and       v_n  =  ë n f²û  =  n + u_n   ,

where ë x û denotes the largest integer not exceeding x (known as the floor of x) and f is the ubiquitous Golden Ratio (1+Ö5)/2 = 1.6180339887498948482... (which is such that f² = 1 + f ). A sequence [like either of the above] whose n^th term is ë n q û, for an irrational number q >0, is known as the Beatty sequence associated with q.  If 1/a+1/b = 1, the Beatty sequences associated with a and b are said to be complementary and have the wonderful property that every positive integer appears once in either sequence, but never in both. The above two Wythoff sequences happen to be complementary Beatty sequences!

When playing Wythoff's game with several southwest-bound chess queens, each chessboard square (i,j) should be numbered [as above] with the Grundy number Wyt(i, j) of a single Wythoff game with heaps of sizes i and j. The overall Grundy number of the position is then equal to the Nim-sum of the numbers in the squares occupied by an odd number of queens, and the winning strategy is the same as in normal Nim: If at all possible, move to a zero Grundy number (which you may always do, unless you are in a zero position yourself).

When playing with an actual board, use checkers pieces which are stacked when several "queens" occupy the same square. Alternately, an extra rule could be introduced, stating that whenever a queen lands on a square occupied by another, both pieces are removed from play. This shortens the game but does not modify the strategy to use.

The above numbering of the chessboard (infinitely extended to the entire first quadrant) seems to have a number of wonderful features worth investigating, including the observation that every nonnegative integer appears once and only once in every row, every file, the main diagonal (Wyt(n, n); A047708) and every other infinite diagonal (Wyt(k+n, n), for some constant k). The fact that an integer cannot appear more than once in such lines is trivial, but the conjecture that any integer eventually appears is not obvious. For the main diagonal, the thing was proved by Howard A. Landman and Thomas S. Ferguson in July of 2000 (MSRI workshop on combinatorial games).

A. Flammenkamp et al. showed that every row or file has additive periodicity. A simpler proof of that fact was later given independently by H.A. Landman, in September 2000: Wyt(k,n)-n is ultimately periodic for any constant k, and the ultimate periods are [starting with k=0]: 1, 3, 3, 6, 12, 24, 12, 24, 24, 24, 24, 48, 48, 96, 96, 96, 192, 192, 384, 384, 384, 768, 768, ... (see A046875). The periodic parts of the sequences start respectively at the following values of n: 0, 0, 0, 8, 9, 27, 37, 92, 102, 127, 224, 277, 347, 382, 613, 693, 771, 865, 919, 1032, 1165, 1252, 1293, 1373, 1732, 2208, 2314, ... (see A046874).

References

• Willem Abraham Wythoff (1865-1939)
  "A Modification of the Game of Nim"
  Nieuw Archief voor wiskunde (2), pp. 199-202 (1905-1907).
• From N.J.A. Sloane's On-Line Encyclopedia of Integer Sequences:
  • A000201 is the lower Wythoff sequence.
  • A001950 is the upper Wythoff sequence.
  • A004481 is the Wyt(i, j) table (as concatenated antidiagonals).
  • A001477 is Wyt(0, n), the nonnegative integers.
  • A004482 is Wyt(1, n).
  • A004483 is Wyt(2, n).
  • A004484 is Wyt(3, n).
  • A004485 is Wyt(4, n).
  • A004486 is Wyt(5, n).
  • A004487 is Wyt(6, n).
  • A047708 is Wyt(n, n), the main diagonal.
  • A046875 gives the ultimate periods of Wyt(k,n)-n.
  • A046874 gives the n after which Wyt(k,n)-n is strictly periodic.

Wythoff's Game  and its  Grundy Function  (in French)  by  Jean-Paul Davalan.