One of the oldest versions of Nim is a Chinese game called jiǎn shízǐ, which literally means “picking stones.”
In this particular version, there are two piles of objects of various sizes. On their turn, a player may take either as many objects as they want from just one pile, OR take the same number of objects from both piles. The player who takes the last object wins.
For those familiar with Nim games, this appears to be a minor rule change at first glance. However, a proper analysis of the game yields some surprising principles behind this game.
Completely unfamiliar with the Chinese game, a mathematician named W. A. Wythoff independently reinvented the game, and analyzed the perfect winning strategy back in 1907.
Around 1962, Johns Hopkins University mathematician Rufus P. Isaacs developed a seemingly-unrelated board game using a chess board, often called “Corner the Lady.”
Isaac's game starts with a standard 8 by 8 chessboard or checkerboard, and a single chess queen being placed anywhere in the topmost row, or the rightmost column. The objective is to be the person who moves the queen into the square at the lower right corner. In the image directly below, the black queens represent the possible starting positions for the queen, and the white queen represents the goal square.
The queen moves much like in chess, moving any number of squares in a straight horizontal, vertical, or diagonal line. There is one difference in the queen's move in this game: The queen can only move east, south, or southeast. This means that the queen can never move away from the goal square, only toward it.
How do you win this game? The answer is found by working backwards. Since the goal square is obviously a safe square for winning, it follows that any move a queen's move away would guarantee a win for the next player. The closest two squares that aren't covered by a queen's move would be considered safe, because they're more than one queen's move away from the goal square.
The animation below shows how this principle is applied and re-applied (a process known as recursion) to find all the safe squares on an 8 by 8 chessboard. The queens represent the safe squares, and the pawns represent all possible paths taken to that square.
The location of the safe squares is easy to remember. Think of the goal square, and the two squares that are a knight's move away from it, and you've already remembered 3 of the safe squares. The 4th square from the left in the top row, the 4th square from the top in the left row, and the squares a knight's move from both of those (remembering those specific knight's moves) complete the set.
Interesting how, in a chess-related game with no knights, the knight's moves still play an important role, isn't it?
If we think of the goal square as the (0,0) point on a grid, then we see the nearest safe squares are at (1,2) and (2,1). The next pair is at (3,5) and (5,3), with the final pair on this board being at (4,7) and (7,4).
If you imagine trying this same process on larger boards, you get pairs like (6, 10), (8,13), (9,15), and beyond. Noting the infamous Fibonacci number pairings of 1, 2, 3, 5, 8, 13, and beyond, Isaacs looked deeper to see if Phi (the golden ratio) was somehow involved. When he did, he made three astounding discoveries!
If we call the numbers in each pair A and B, and we're looking for the kth number in each sequence, A can be calculated by multiplying k by the golden ratio, and then rounding down to the nearest whole number (known as the floor function). Here's a table of the results for k running from 0 to 15.
What about B? That was the second amazing discovery. The kth number B can be found by multiplying k by the square of the golden ratio.
Here's a table of the A & B numbers paired up, running from the 0 to the 15th pair.
What about the third discovery? It turns out that Wythoff's 1907 analysis was identical. In fact, Wythoff's game, in which a player may take either as many objects as they want from just one pile, OR take the same number of objects from both piles, is mathematically identical to Isaac's “Corner the Lady” game!
How is this possible? In Isaac's board game, the winner is the person who moves the queen to (0,0). In Wythoff's game, the winner is the person who leaves the piles with the totals of (0,0).
We've seen how it was worked out that (1,2) and (2,1) were safe squares in Isaac's game. How does this apply in Wythoff's game? If you can leave a pile with 1 object, and another pile with 2 objects, that leaves the other player with only 4 moves. They can remove 1 object from the 1-object pile (leaving a single pile of 2), remove 1 object from the 2-object pile (leaving two piles of 1), remove 2 objects from the 2-object pile (leaving a single pile of 1), or take 1 object from both piles (leaving a single pile of 1). In every one of these cases, removing the remaining object(s) is both a legal and winning play.
Similar plays and reasoning hold true for all the other number pairs, as well. You can try a version of Isaac's game online here, and see how easy it is to win, unless the computer picks a safe square.
Martin Gardner wrote about these games in more detail, too. You can read more about these games in this excerpt from Penrose Tiles to Trapdoor Ciphers, or buy the complete book here.
This isn't the first time I've examined Fibonacci numbers in connection with Nim, either. Check out my Fibonacci Nim post to see another use for them.
Posts
No Response to "Secrets of Nim (Wythoff's Nim)"
Post a Comment