Wythoff's Nim

The game below, which has no traditional name, was invented about 1960 by Rufus P. Isaacs, a mathematician at Johns Hopkins University. It is described briefly in Chapter 6 of the 1962 English translation of The Theory of Graphs and Its Applications, a book in French by Claude Berge. Let's call the game "Corner the Lady." Computer puts the queen on any cell in the top row or in the column farthest to the right of the board; Queen's location is designated by the red square. The queen moves in the usual way but only west, south or southwest. If, box "Hint" is checked, eligible squares are colored in magenta. You click on one of these to select a move. You move first, then the computer and you alternate moves. The player who gets the queen to the lower left corner is the winner. No draw is possible, so that one of the players is sure to win.


This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at https://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.


Buy this applet
What if applet does not run?

Following is an excerpt from
Martin Gardner's,
Penrose Tiles to Trapdoor Ciphers

Isaacs constructed a winning strategy for cornering the queen on boards of unbounded size by starting at the starred cell and working backward. If the queen is in the row, column or diagonal containing the star, the person who has the move can win at once. Mark these cells with three straight lines as is shown in part A of the illustration. It is clear that the two shaded cells are "safe," in the sense that if you occupy either one, your opponent is forced to move to a cell that enables you to win on the next move.

Part B of the illustration shows the next step of our recursive analysis. Add six more lines to mark all the rows, columns and diagonals containing the two previously discovered safe cells. This procedure allows us to shade two more safe cells as shown. If you occupy either one, your opponent is forced to move, so that on your next move you can either win at once or move to the pair of safe cells nearer the star.

Repeating this procedure, as is shown in part C of the illustration, completes the analysis of the chessboard by finding a third pair of safe cells. It is now clear that Player A can always win by placing the queen on the shaded cell in either the top row or the column farthest to the right. His strategy thereafter is simply to move to a safe cell, which he can always do. If A fails to place the queen on a safe cell, B can always win by the same strategy. Note that winning moves are not necessarily unique. There are times when the player with the win has two choices; one may delay the win, the other may hasten it.

Our recursive analysis extends to rectangular matrixes of any size or shape. Note that eligible squares are paired symmetrically with respect to the main diagonal and lie almost on two lines that fan outward to infinity. Their locations along those lines seem to be curiously irregular. Are there formulas by which we can calculate their positions nonrecursively?

Before answering let us turn to an old counter take-away game said to have been played in China under the name tsyan-shidzi, which means "choosing stones." The game was reinvented by the Dutch mathematician W. A. Wythoff, who published an analysis of it in 1907. In Western mathematics it is known as "Wythoff's Nim."

The game is played with two piles of counters, each pile containing an arbitrary number of counters. As in Nim, a move consists in taking any number of counters from either pile. At least one counter must be taken. If a player wishes, he may remove an entire pile. A player may take from both piles (which he may not in Nim), provided that he takes the same number of counters from each pile. The player who takes the last counter wins. if both piles have the same number of counters, the next player wins at once by taking both piles. For that reason the game is trivial if it starts with equal piles.

We are ready for our first surprise. Wythoff's Nim is isomorphic with the Queen-Cornering game! When Isaacs invented the game, he did not know about Wythoff's Nim, and he was amazed to learn later that his game had been solved as early as 1907. The isomorphism is easy to see. Columns and rows are numbered starting with 0. Each cell can now be given an x/y number. These numbers correspond to the number of counters in piles x and y. When the queen moves west, pile x is diminished. When the queen moves south, pile y is diminished. When it moves diagonally southwest, both piles are diminished by the same amount. Moving the queen to cell 0/0 is equivalent to reducing both piles to 0.

The strategy of winning Wythoff's Nim is to reduce the piles to a number pair that corresponds to the number pair of a safe cell in the Queen game. If the starting pile numbers are safe, the first player loses. He is certain to leave an unsafe pair of piles, which his opponent can always reduce to a safe pair on his next move. If the game begins with unsafe numbers, the first player can always win by reducing the piles to a safe pair and continuing to play to safe pairs.

The order of the two numbers in a safe pair is not important. This condition corresponds to the symmetry of any two cells on the chessboard with respect to the main diagonal: they have the same coordinate numbers, one pair being the reverse order of the other. Let us take the safe pairs in sequence, starting with the pair nearest 0/0, and arrange them in a row with each smaller number above its partner, as in the table below. Above the pairs write their "position numbers." The top numbers of the safe pairs form a sequence we shall call A. The bottom numbers form a sequence we shall call B.

Position (n)123456789101112131415
A134689111214161719212224
B257101315182023262831343639

These two sequences, each one strictly increasing, have so many remarkable properties that dozens of technical papers have been written about them. Note that each B number is the sum of its A number and its position number. If we add an A number to its B number, the sum is an A number that appears in the A sequence at a position number equal to B. (An example is 8 + 13 = 21. The 13th number of the A sequence is 21.)

We have seen how the two sequences are obtained geometrically by drawing lines on the chessboard and shading cells according to a recursive algorithm. Can we generate the sequences by a recursive algorithm that is purely numerical?

We can. Start with 1 as the top number of the first safe pair. Add this to its position number to obtain 2 as the bottom number. The top number of the next pair is the smallest positive integer not previously used. It is 3. Below it goes 5, the sum of 3 and its position number. For the top of the third pair write again the smallest positive integer not yet used. It is 4. Below it goes 7, the sum of 4 and 3. Continuing in this way will generate series A and B.

There is a bonus. We have discovered one of the most unusual properties of the safe pairs. It is obvious from our procedure that every positive integer must appear once and only once somewhere in the two sequences.

Is there a way to generate the two sequences nonrecursively? Yes. Wythoff was the first to discover that the numbers in sequence A are simply multiples of the golden ratio rounded down to integers! (He wrote that he pulled this discovery "out of a hat.")

The golden ratio, as most readers of this book are aware, is one of the most famous of all irrational numbers. Like pi it has a way of appearing in unlikely places. Ancient Greek mathematicians called it the "extreme and mean ratio" for the following reason...

There is an additional implementation that is closer to the orginal Wythoff's game.

Reference

  1. M. Gardner, Penrose Tiles to Trapdoor Ciphers, W. H. Freeman and Company, 1989

Fibonacci Numbers

  1. Ceva's Theorem: A Matter of Appreciation
  2. When the Counting Gets Tough, the Tough Count on Mathematics
  3. I. Sharygin's Problem of Criminal Ministers
  4. Single Pile Games
  5. Take-Away Games
  6. Number 8 Is Interesting
  7. Curry's Paradox
  8. A Problem in Checker-Jumping
  9. Fibonacci's Quickies
  10. Fibonacci Numbers in Equilateral Triangle
  11. Binet's Formula by Inducion
  12. Binet's Formula via Generating Functions
  13. Generating Functions from Recurrences
  14. Cassini's Identity
  15. Fibonacci Idendtities with Matrices
  16. GCD of Fibonacci Numbers
  17. Binet's Formula with Cosines
  18. Lame's Theorem - First Application of Fibonacci Numbers

|Contact| |Front page| |Contents| |Games| |Eye opener|

Copyright © 1996-2018 Alexander Bogomolny

72099543