home | index | units | counting | geometry | algebra | trigonometry & functions | calculus
analysis | sets & logic | number theory | recreational | misc | nomenclature & history | physics

Final Answers
© 2000-2014   Gérard P. Michon, Ph.D.

Mathematical Games
(Two Players)

Games of No Chance
 border
 border  border
 border
 border
 border
 border

Related articles:

Related Links (Outside this Site)

Mathematical Games.   |   Games in the Classroom.
Clever Games by Nancy Casey (Megamath  at Los Alamos and U. of Idaho).
Combinatorial Game Theory (including Clobber) by David Wolfe (Berkeley).
Dots and Boxes (Google Web Directory).
Jeux de type Nim  by  Jean-Paul Davalan.
Games and Puzzles Page at cut-the-knot.com.
Combinatorial Game Theory by David Eppstein (UC Irvine).
Octal Games by Achim Flammenkamp (Universität Bielefeld).
Games Mathematicians Play by Gregory McColm (University of South Florida).
Games of No Chance (Downloadable Articles) edited by Richard Nowakowski.
Combinatorial Games  and  Notes on Misère Games  by  Thane Plambeck.
The Math Less Traveled  (game archive)  by  Brent Yorgey.
 
Vsauce Video :   Why do we play games?   by  Michael Stevens.
 
Wikipedia :   Sprague-Grundy theorem   |   Combinatorial Game Theory (CGT)

DMOZ: Combinatorial Game Theory

 
border
border

Mathematical Games (Two Players)

 The Boxer's Puzzle 
 by Sam Loyd
(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. 3 by 3 (American) game
of Dots and Boxes

Note that the entire game has been analyzed by computer for small boards. If there are n open lines left, there are 2n 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 2n. We thus analyze n! possible sequences of moves (legal or not) by analyzing only 2n 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
    "The Dots and Boxes Game: Sophisticated Child's Play"
    A K Peters (Natick, MA)   ISBN 1-56881-129-2. © 2000
 

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.   Last Year 
 at Marienbad 
 (1961) 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

Game of 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!

 Play misere nim 
 against Juan...
Play
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 Some nim-like game...
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.

Remove something
from at most two rows. 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)


Kayles (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:
012345 678910111213 14151617181920
    0 1231 43214264 12714321

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):
120012011202120312041205 120612071208120912101211
4128 14721827
There are only 14 exceptional values:
03691115 1821222834395770
0334 67346563 46

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).

 Dudeney's Game of Kayles


    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.)

012345 678910111213 14151617181920
2012 31 43214264 12714321
3012 34 16321674 581105476
4012 34 56732897 65432894
5012 34 5678321112 765432116
6012 34 5678931112 1376543216
7012 34 5678910312 13147654316
8012 34 56789101112 131415765416
9012 34 56789101112 131415167654
10012 34 56789101112 1314151617765
11012 34 56789101112 13141516171876
12012 34 56789101112 131415161718197

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:
0123 45 678910111213 14151617181920
     00010 21021021 32132430

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) Wythoff's Game
on a Chessboard 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
012345678 910111213141516 1718192021222324
01346891112 1416171921222425 2729303233353738
02571013151820 2326283134363941 4447495254576062

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

un  =  ë n f û       and       vn  =  ë n f2û  =  n + un   ,

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 f2 = 1 + f ). A sequence [like either of the above] whose nth 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!

 Come back later, we're
 still working on this one...
Grundy values of Wythoff's game on 25 by 25 board
(use lower left portion for smaller boards)
2425262723222129 13201928303256 3433353614371738 31
2321221924262728 11182025430 22931933161214 3038
2223212025242618 28292730231432 3334103513361914 17
2122232420192511 27282616129330 3132141533183612 37
2018192221232425 26272830129 113093112173313 1614
1920181714211116 2422231542627 2810132512153533 36
1819202117161522 2345032425 711261213311410 935
1715161318111412 193452322824 252126109323431 33
1617151419182021 12214610229 1325112830313329 34
1516171810131219 140321228 23209247271130 3226
1412131615171810 912202171123 22825262934 05
131412111615172 056192097 8102224412931 332
121314151191617 18197810202122 62335012 430
1191071214213 17618158192021 450131630 2528
10119813120 1516171418762 314523282627 2019
9101112871314 15161761951 0234222728 291820
8671012534 1516171809 1412192324262728 1113
7869014 5314151317210 1921122216251118 2829
6781910345 1302161718 1220141511242526 2721
53406810 127121491517 1318111621231924 2622
4532769 018131211 1615101918171421 20252423
3456201 9101287151116 1814132117222420 1927
2015348 6711910141213 1715162018192321 2226
1204537 8610119131412 1617151920182223 2125
0123456 7891011121314 1516171819202122 2324

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

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

border
border
visits since Feb. 12, 2002
 (c) Copyright 2000-2014, Gerard P. Michon, Ph.D.