Nimble Strategy

I was first introduced to Nim in junior high school when a friend, for a school project, built a box with 13 lights in a row.

At your turn, you could switch off one to three lights.

Whoever faced the last light lost.

My friend always won even though he gave you the option of starting first or passing the first move.

This kind of game has a guaranteed win for either the one who starts or the one who goes second given proper play. However the 13 lights were enough that, if someone made the right choice to start or pass, they would eventually fritter away their advantage and my friend would take charge and win the game.

When I saw the abstract art film “Last Year at Marienbad”, I was intrigued by the version of Nim played at the hotel.

It consists of a triangular array of playing cards dealt face down on a table. (Also match sticks, tiles and photographs.)

One card in the top row; three cards in the second row; five cards in the third row; seven cards in the bottom row.

Take from one to all the cards in one row.

Whoever is forced to take the last card loses.

The cuckold wins each time whether he plays first or second against the seducer.

The kibitzers propose various strategies for the game.

When Criterion–a company that cleans up old films–released it on DVD, I bought it and played the games in slow motion.

Looked to me like the supposed expert at the game actually misplayed one hand. He could have been defeated by perfect play.

To win a Nim game, you need to be the first to reach a safe harbor position. No matter what your opponent does, you can then corral him into a new safe harbor position. This continues till you win the game.

“Modulus” is the operation that finds the “remainder” when dividing one integer by another.

In Nim, the “divisor” is always the maximum number of cards that can be taken in a turn plus 1. For example, if the maximum number of cards you can take per turn is 4, then the divisor is 5.

If the number of cards in a row is 14 and the maximum number of cards you can take per turn is 4 so that the divisor is 5, then the remainder of the modulus operation is 14 divided by 5 which gives 4 left over. 14 = 5 x 2 + 4.

The remainder can also be found by repeatedly subtracting the divisor from the number. (Division is repeated subtraction just as multiplication is repeated addition.)

14 - 5 = 9. 9 - 5 = 4. Thus, you can subtract 5 from 14 two times and have 4 left over.

“Complementing” is one method used to move from one safe harbor to another safe harbor in a single row. (Stay awake. This is complementing with an e. This is not complimenting with an i which is telling someone how good they look.)

Whatever he moves, you complement him by moving the divisor minus that move.

Complement = divisor - his move.

If the maximum cards to take per turn is 4, then the divisor is 5. If he takes 3 cards, you take the divisor minus 3, 5 - 3 = 2.

Note: complement + his move = divisor.

That is, together the two of you have moved down the row by the size of the divisor. His 3 cards taken plus your 2 cards taken = 5.

The new position has the same remainder as the previous position. If the previous number of cards was 9, it has a remainder = 4 (9 = 1 x 5 + remainder 4). He takes 3 cards leaving 6. You take 2 cards leaving 4. The new number of cards has a remainder 4 (4 = 0 x 5 + remainder 4).

By “complementing” his move, you have kept the remainder the same. A safe harbor is defined in terms of remainder rather than actual number of cards. Thus, you have controlled him. You have moved him from one safe harbor to the next.

The safe harbor positions are the multiples of the divisor. These are the positions you want to leave your opponent facing.

For example, if the maximum number of cards you can take for a turn is 4, then the divisor is 5 and the safe harbor positions are the multiples of 5: 5, 10, 15... You want to leave him facing this number of cards.

For example, if he is facing 10 cards, you complement him:

On the next round, you will win no matter what he does by again complementing him.

The above is the general solution for the one row game where taking the last card wins.

The safe harbor positions are the multiples of the divisor plus one (since this time you want to take the next to last card and leave the last card for him to take and lose). These are the positions you want to leave your opponent facing.

For example, if the maximum number of cards you can take for a turn is 4, then the divisor is 5 and the safe harbor positions are the multiples of 5 with 1 added: 6, 11, 16... You want to leave him facing this number of cards.

For example, if he is facing 11 cards, you complement him:

On the next round, you leave him facing 1 card which he must take and lose the game.

The above is the general solution for the one row game where taking the last card loses.

Normally, your first step in analyzing a position is to do a modulus on each row and, thereby, determine the remainder for each row.

It can be confusing if the remainder for a row is zero.

You may think the row is empty.

Or you may think you can't do anything with the row.

A row is in its final frame when the remainder is the actual number of cards in the row.

For example, suppose the maximum take for a row is 4 and there are 3 cards in the row. The divisor is 5 (max take + 1 = 4 + 1 = 5). The remainder is 3 (3/5 = 0 + remainder 3). Thus, the remainder, 3, is equal to the number of cards in the row. Thus, the row is in its final frame.

If a row is in its final frame and the remainder is 0, then, by definition, the row is empty.

If a row is not in its final frame and the remainder is 0, then there are at least the divisor number of cards in the row.

For example, suppose the maximum take for a row is 4. The divisor is 5 (max take + 1 = 4 + 1 = 5).

The number of cards in a row that give a remainder of 0 are the multiples of the divisor: 5, 10, 15, ... (since you can evenly divide those numbers by the divisor and have none left over).

You can treat those cards the same as any other number of cards. You can take 1, 2, ..., max take. All that happens is that you will move down to the next frame (which may be the final frame).

After your move, there will be at least one card left in the row since you start with at least the divisor number of cards in the row and the divisor is the maximum number of cards you can take in a row plus one. So, if you take the maximum number of cards you can take in a row, you leave at least 1.

For example, in the single row game with take last = lose and max take = 4, suppose you leave him facing the safe harbor of 6 cards.

He takes 1 card, leaving 5.

You calculate the remainder. It is 0. Uh oh.

You complement him as usual. You take 4 cards, leaving him facing 1 card (in the final frame).

He has to take it and loses the game.

The simplest safe harbor to keep in mind for the two row game where taking the last card wins is both rows being equal.

If you can leave your opponent facing an equal number of cards in both rows, you simply mirror what he does. If he takes 2 cards from one row, you take 2 cards from the other row, leaving him facing two equal numbers of cards again. Eventually, he will have to take the last card in one row, then you will take the last card in the other row and win.

Actually, “both rows being equal” means after taking the modulus.

For example, in the maximum take per turn = 4 game, 6 cards in one row and 11 cards in the second row are obviously not equal. Well, actually, they are after taking the modulus.

The divisor is 5. 6/5 = 1 + remainder 1. 11/5 = 2 + remainder 1. They have equal remainders which is good enough. 6 cards in one row and 11 cards in the other is a safe harbor.

For example, if he takes 4 from the first row leaving 6 - 4 = 2, you match by taking 4 cards from the second row leaving 11 - 4 = 7 (which has a remainder of 2 when divided by the divisor 5).

If he then takes the final 2 from the first row, 2 - 2 = 0, you match by taking 2 from the second row which leaves 7 - 2 = 5. You are now down to the one row game and 5 is a safe harbor there. (See 3. A. One row game, take last = win above).

Generally, you will have two choices of move:

In the above example, the game started 6 11 actual cards, 1 1 remainders.

He took 4 cards from the first row, leaving 2 11 actual cards, 2 1 remainders.

You could complement him. He took 4 cards. You take divisor - his move = 5 - 4 = 1 from the first row, leaving 1 11 actual cards, 1 1 remainders, which is a safe harbor.

The complement will always take the divisor number of cards between the two of you. In the example, 5 cards.

The match may take fewer or more. If he took 1 card and you matched, together you'd take 2 cards which would be less than the 5 of the complement. If he took 4 cards and you matched, together you'd take 8 cards which would be more than the 5 of the complement.

(Sometimes, you can't complement him. You have to match.

For the above example, the game started 6 11 actual cards, 1 1 remainders.

He took 4 cards from the first row, leaving 2 11 actual cards, 2 1 remainders.

If you complement him. You take divisor - his move = 5 - 4 = 1 from the first row, leaving 1 11 actual cards, 1 1 remainders.

If he now takes the last card from the first row, you can't complement him since there are no cards left in the first row. You have to match by taking 1 from the second row.)

The two row game where taking the last loses essentially follows the steps above for the two row game, take last = win. Calculate the remainder for each row. Look at the smallest remainder.

*** if the smallest remainder of a row is 0, then lower the other row to 1. (If both remainders were 0, you can lower one row to 1 by taking the max take and going into the next frame.)

(If you can do one of the above, you have reached a safe harbor. If you can't do one of the above, then your opponent left you facing a safe harbor and you will lose unless he messes up.)

In the one row game, having the maximum number of cards you can take in a turn be all the cards makes for a very fast game. If taking the last card wins, then the first player takes all the cards and wins. If taking the last card loses, then the first player takes all but the last card and the second player takes it and loses. Either way, the first player always wins.

It might, therefore, seem that maximum take = all would need a separate analysis. No. It can use the general analysis by using a divisor = the maximum cards allowed in a row + 1. Which results in the remainder being the actual number of cards.

All that happens is that you never use complements (because there aren't enough cards to do a complement) and you have to know only a few safe harbors.

In the two row game, having 2 cards left in each row is a “universal safe harbor”. That is, if your opponent faces that pattern in any version of the game (take last = win, take last = lose, max take per turn = 3, ..., all) he will lose.

For take last = win:

*** if he takes 1 in one row, you take 1 in the other row leaving 1 and 1. He takes 1 from one row and you take the last from the other row and win.

For take last = lose:

*** if he takes 1 in one row, you take all in the other row leaving him facing 1 he has to take and lose.

*** if he takes 2 in one row, you take 1 in the other row leaving him facing 1 he has to take and lose.

In the three row game, having 1 card left in one row, 2 cards left in another row and 3 cards left in a third row is a “universal safe harbor”. That is if your opponent faces that pattern in any version of the game (take last = win, take last = lose, max take per turn = 3, ..., all) he will lose.

For take last = win:

For take last = lose:

A safe harbor in the final frame can be a safe harbor in other frames as well. Thus, three rows of cards, 1 in one row, 2 in a second and 3 in a third is a safe harbor in the final frame. If the remainders for three rows are 1, 2, 3, then you have a safe harbor regardless of whether it is the final frame or not.

Suppose A, B, C are the actual cards of a safe harbor in the final frame.

Suppose the maximum number of cards you can take per turn is n. (The divisor is n+1.)

Suppose k₁, k₂ and k₃ are any three integers.

are the actual number of cards. They have remainders

As long as a row is not in the final frame, complement his move.

If he takes 3 from the first row (and it is not the final frame), you take (n+1) - 3 from the first row. Together (n+1) cards are taken from the first row. This leaves (k₁-1)*(n+1) + A actual cards or remainder A.

*** For the example, he takes 3 cards from the first row. You complement by taking 2 cards leaving 1, 2, 8 actual cards or remainder 1, 2, 3.

Eventually, the first row will be reduced to the final frame. There will be A actual cards in the row.

Supposes he stays in the first row and reduces A cards to D cards. You can't complement him since there aren't enough cards. So, you check the table for the safe harbor A, B, C and see that you would reduce C cards to E cards if you were dealing with the final frame. You make the move anyway. Take C-E cards from the third row. It goes from k₃*(n+1) + C to k₃*(n+1) + E. Thus, the remainders for all three rows are D, B, E which would be a safe position in the final frame.

*** For the example, suppose he takes the only card remaining in the first row leaving you facing 2, 8 actual cards or 2, 3 remainder. From the table for the 1, 2, 3, take last = lose, safe harbor, you see that you should take 1 from the last row. So you do. He faces 2, 7 actual cards or remainder 2, 2.

You inexorably reduce each row to the safe harbor of the final frame and win.

*** To finish the example, suppose he takes 3 cards from the last row. Since that row is not yet in the final frame, you complement him by taking 2, reducing the position to 2, 2, actual cards and remainder 2, 2 which is shown above to be a safe harbor and you win.

This is how I wrote the original computer program.

I built a table of safe harbors for the final frame.

Then, I used those as remainders to target in other frames.

If you study the game enough, it will become second nature to have firmly in mind that:

If you leave your opponent facing three rows of 5, 6 and 7 cards, they may or may not be a safe harbor.

If the maximum number of cards to take is 3, then the divisor is 4, the remainders are 1, 2 and 3 which is a safe harbor. You win with proper play.

If the maximum number of cards to take is 4, then the divisor is 5, the remainders are 0, 1, and 2 which is not a safe harbor. Your opponent can take 2 cards from the first row leaving 3, 6, 7 actual cards or remainders 3, 1, and 2 for you. You are facing a safe harbor. You lose against proper play.

While I was in the laundry room loading the washer, the idea light bulb flashed in my head.

I thought I'd found the perfect way to win the take last = lose version of the game by using the take last = win version of the game.

The take last = win version of the game is very easy to program into the computer.

I figured I could mentally set aside one card from the take last = lose version of the game, then play the game as if it were the take last = win game. When I “won” the game, I would then return the card I'd mentally set aside. My opponent would have to take it and lose the game.

Alas, the idea did not pan out. I am bummed that such a simple idea didn't work.

Suppose there are three rows with number of cards 1, 2, 4.

As the above table proved, I should take one card of the 4 cards leaving 1, 2, 3 cards which is a universal safe harbor.

Instead, let's follow my idea. I face 1, 2, 4 actual cards. I mentally set aside the single card from the first row.

This leaves me mentally facing 2, 4 cards.

I take 2 cards from the 4 cards in the last row leaving 2, 2 cards which, as proved above, is a universal safe harbor.

The opponent doesn't know anything about my mental strategy. He sees three rows of actual cards 1, 2, 2. He takes the single card from the first row leaving 2, 2 cards which is a universal safe harbor.

I lose a game I should have won.

Fortunately, I quickly came up with a reversal of the strategy. It worked. I play the take last = lose game as if it were the take last = win game just as in the original idea.

However, instead of taking the mental card at the start, I wait till the end. When I'm about to “win”, I leave 1 card on the table for my opponent to pick up so he loses.

This is how the take last = lose game is programmed into the computer.

Originally, the program had a table of lots of safe harbors.

Turns out there is a relatively simple although slightly complex, single-line mathematical formula that spits out where the next safe harbor is. (There may be more than one safe harbor reachable from the current position. The mathematical formula provides all possibilities.)

Adding an explanation of the formula would probably double the size of this page which is already too long and too mind-numbing.

Once you have the mathematical formula for a safe harbor you can work on proving two fundamental theorems.

For the take last = win case, it is trivial to prove the theorem that:

It is straightforward, but requires looking inside a position to prove the reverse theorem that:

Given a position that is not a safe harbor position, it is always possible to find a move that will lead to a safe harbor position in the same frame.

The safe harbor position moved to must be in the same frame and nearer 0.

For example, suppose max take = 6, so divisor is 7.

Suppose actual number of cards in three rows is 9, 10, 13 so remainder is 2, 3, 6 which is not a safe harbor.

You could take 4 cards from the first number giving 5, 10, 13 actual cards or remainder 5, 3, 6 which is a safe harbor, but it crosses into the next frame which violates the condition of the theorem that you stay in the frame. (The frame boundary is 7, 7, 7 actual cards.)

You could add 1 card to the middle number giving 9, 11, 13 actual cards or remainder 2, 4, 6 which is a safe harbor, but it violates the condition of the theorem that you move toward 0, not increase the number of cards.

Finally, you could take 5 cards from the third number giving 9, 10, 8 actual cards or remainder 2, 3, 1 which is a safe harbor. It is in the same frame. It is a reduction in cards. It satisfies the theorem.

These two theorems guarantee that, once you trap the opponent in a safe harbor, you can keep him there and win the game.

Once you have the mathematical formula, it is trivial to prove the following theorem:

If the opponent faces a safe harbor for the take last = win game and there are multiple rows and at least one row has at least two cards, then there is at least one more of the rows that has at least two cards.

This means that if there are multiple rows and at least one row with at least two cards, then you can play the game exactly the same as the take last = win version.

The end of the game starts when the opponent faces a safe harbor from the take last = win game and there are exactly two rows left with at least two cards in them and he reduces one of the two rows to zero or one cards. There is now exactly one row with at least two cards in it and it is your move. You can reduce it to zero or one cards as necessary. This leads to what is so obvious it hardly deserves to be called a theorem:

If your opponent faced a safe harbor for the take last = win game and there were exactly two rows with at least two cards in them and he reduced one of those rows to zero or one cards, you can reduce the other row with at least two cards to zero or one cards such that there is an odd number of rows with exactly one card in them.

Further, it is obvious that:

If there are an odd number of rows with one card in them, then there is at least one row with one card in it.

Thus, your opponent faces an odd number of rows with exactly one card in each. He starts by taking the one card from one row; you reply by taking the one card from another row and, ultimately, he takes the one card from the last row and loses.

He face	He take	I face	I take	He face
123	1--	-23	--1	-22
123	-1-	113	--3	11-
123	-2-	1-3	--2	1-1
123	--1	122	1--	-22
123	--2	121	-2-	1-1
123	--3	12-	-1-	11-

He face	He take	I face	I take	He face
123	1--	-23	--1	-22
123	-1-	113	--2	111
123	-2-	1-3	--3	1--
123	--1	122	1--	-22
123	--2	121	-1-	111
123	--3	12-	-2-	1--