The ultimate winning strategy in the game of NIM

In the game of NIM, a few rows of objects are laid out. Each row can contain a number of objects, not necessarily the same number as the other rows.

There are two players that alternate playing.

Each player HAS to take A LEAST ONE object up to AS MANY AS they like including ALL objects BUT ONLY FROM ONE OF THE ROWS. Which row this should be is up to the player to decide.

The two players decide in advance who wins and who loses. Either they decide that the player who picks the last object wins or that the player who picks the last object loses.

I will now present an analysis of the game.

I will start by giving an example configuration.

Suppose we have the following 4 rows of objects (coins, paperclips, cards, it doesn’t matter):

object
object object object
object object object object object
object object object object object object object

Let me transform the above to an equivalent representation that depicts the number of objects in each row:

1
3
5
7

Let me transform the above to an equivalent representation that depicts the number of objects in each row in binary number format:

001
011
101
111

We are interested in the 1’s. In the above configuration, the 1’s are balanced.
What does it mean that the 1’s are balanced? It means that each column contains an even number of 1’s.
So, we call this configuration balanced.

Well, the state of the game is completely determined at this point. Completely determined.

Not only is the state of the game completely determined at this point, but it is completely determined at any point, even if we begin with more or less rows and/or more or less objects.

The state of this game is completely determined if we have five rows of 363, 356, 5467, 4674, 254 objects, or six rows of 2, 4, 5, 35, 1000 objects or whatever else we can think of.

I will explain why I am saying this, but first I would like to explain what I mean by completely determined. I mean that both players know the ultimate winning strategy and no player plays in a naive manner.

If these conditions are met, the state of the game is completely determined before it even begins, if we are given the following:

1) The number of rows and how many objects each row has (the whole configuration).
2) Who is going to play first and who is going to play second.
3) Who wins: the player that takes the last card or the player who does not.

Given the above, the state of the game is always predetermined. (Actually, as we will see, number 3 is irrelevant. The first two conditions fully determine the outcome of the game.)

Given conditions 1 and 2, the state of the game is always predetermined and this is because a configuration can always be transformed to an equivalent representation that depicts the number of objects in each row in binary number format.
And from that representation we can find if the configuration is balanced or unbalanced.

If a player has a balanced configuration in front of her and she has to play, she will create an unbalanced configuation. Always. Even if she wants to or not.

If a player has a unbalanced configuration in front of her and she has to play AND SHE KNOWS THE ULTIMATE WINNING STRATEGY, she will create a balanced configuration if she wants to. Always. If she wants to.

So, between two players that know the ultimate winning strategy, the game will be predetermined.

So, who will win? I will tell you who will lose. The player that first is in front of a balanced configuration and is her turn to play, she will definetely lose.

So, if we begin with an unbalanced configuration, the first player will choose to create a balanced configuration. So the second player will have in front of her a balanced configuration, thus she will definitely lose. I will explain why later on.

And if we begin with a balanced configuration, the first player will definitely lose. For the same reason as before, which I will explain later on.

Before I give you an example of the ultimate winning strategy, I would like to give you an example of unbalancing and balancing.

Suppose we are at the beginning:

1 001
3 011
5 101
7 111

The above is balanced, because each column has an even number of 1’s.

Player1 will have to play because she is the first player.
No mattter what she does, she will leave an unbalanced configuation for Player2.

Suppose Player1 takes the whole last row. Player2 is left with an unbalanced configuration:

1 001
3 011
5 101

Wow! This is hugely unbalanced. All three columns have an odd number of 1’s. This is as unbalanced as it can be!

Player2 can, if she wants to, go back to a balanced configuaration. How? Here is how: She can take 3 objects from the last row, thus creating the following balanced configuration:

1 001
3 011
2 010

Ok, now let us see who wins and who loses.

I will consider the configuration given at the start of this analysis.

I assume that both players are knowledgeable and do not play in a naive manner.

The state of the game is always and completely determined when it is the turn of a player to play and this player is in front of a balanced configuration.

When a player is in front of a balanced configuration and it is her turn to play, then she will definitely lose the game. Definitely. Always. Assuming of course that the other player is knowledgeable. So she will always lose the game, even if she is knowledgeable, too.

When a player is in front of a balanced configuration and it is her turn to play, the fate of the game is completely determined and she will definitely lose, always, no matter if the player who takes the last object wins or loses. No matter what was decided beforehand, concerning who wins and who loses, the player that comes in front of balanced configuration and its her turn to play, will always lose.

Let me say this one more time: It does not matter if it was decided that the player who takes the last object wins or that the player that takes the last object loses. Either way, if a player is in front of a balanced configuration and it is her turn to play, she will always lose the game.

Crazy, huh? Crazy, but correct. Let me explain why the above statements are correct.

I will study the two cases individually. The first case concerns the games where the player that takes the last object wins. The second case concerns the games where the player that takes the last object loses.

But before I do that, I have to stress the following points:

When a player is in front of a balanced configuration, and it is her turn to play, she will definitely create an unbalanced configuration. There is no other way, no matter how knowledgeable she is.

The mathematical reason for this is because she draws from only one line. Thus, something that was even among all lines, will stop being even.

When a player is in front of an unbalanced configuration, she has a choice. She can make the configuration balanced if she wants to, or she can produce a configuration that remains unbalanced.

Thus, when a player is in front of a balanced configuration, she is forced to make it unbalanced. But when a player is in front of an unbalanced configuration she has a choice of whether to balance it or to make it to remain unbalanced.

To be completely without choice when a player is in front of a balanced configuration is what creates the advantage for the other player. The other player can, with mathematical precision, literaly, win.

OK. Let me study the first case, the easy case, where the player that takes the last object wins.

This is the easy case.

So, the first player is front of a balanced configuration. From this, I know that the first player will definitely lose. Let us see why.

The first player will play and will make the configuration unbalanced. There is no other way. Even if she wants to, event is she does not want to, there is no other way for the first player but to leave the configuration unbalanced.

Then the second player will play and she will choose to balance the configuration.

Then the first player will play and she will make the configuration unbalanced again. Whether she wants to or not.

Then the second player will choose to balance the configuration, again.

And so on, until we reach the end of the game and the second player takes the last object, thus making the configuration balanced (zero objects is balanced, since zero is an even number).

So the first player is pushed around and guided unwillingly to the end of the game by the second player.

OK, the same thing happens with the second case. In the second case, too, the first player is pushed around and guided unwillingly to the end of the game by the second player.

But the analysis is way trickier in the second case.

OK. Let me study the second case, which is the case where the player that takes the last object loses.

So, the first player is front of a balanced configuration. From this, I know that the first player will definitely lose. Let us see why.

The first player will play and will make the configuration unbalanced. There is no other way.

Then the second player will play and she will choose to balance the configuration.

And so on, until we reach a very specific point in the game, where the second player will choose to reverse her strategy and leave the configuration unbalanced.

The reason why the second player will need to reverse her strategy should be obvious. If she doesn’t, we have the first case where she will end up taking the last object.

So, at a point in the game, the second player will need to reverse her strategy and leave the configuration unbalanced.

But this point in the game is very specific.

The second player must not choose to reverse her strategy at any point. No. In order to win, the second player must reverse her strategy, but at a very specific point and in a very specific way.

Which is this point and why?

Well, this point is the point where all remaining lines have only one object, with the exception of only one line which can have more than one object.

And why this is so? This is because only from this point onwards, the unbalanced configuration cannot be left unbalanced a second time by the first player.

If the second player would choose to leave the configuration unblanaced at a premature point, then the first player would balance it, bringing the second player at a disadvantage.

But if the second player leaves the configuration unbalanced at the specific point that I am talking about, from then on the configuration has to alternate between balanced and unbalanced.

Let me analyze this very subtle point: I described how from balanced we always go to unbalanced, but from unbalanced we go to balanced if we want to.

Well, yes, this is so, but from this specific point in the game onwards, from balanced we always go to unbalanced AND from unbalanced we always go to balanced.

So, from this specific point in the game onwards, if the second player reverses her strategy and leaves the configuration unbalanced, the first player cannot continue this trend but is instead forced to provide a balanced configuration.

Which the second player will make unbalanced and at last, the first player will make balanced by taking the last object, thus losing.

Do not be fooled that this very specific point (where the second player changes her strategy) is somewhere in the middle of the game. No. This specific point is at the very end of the game.

So, let us study this specific point.

As I said, this specific point is when all remaining lines (except one) contain only one object.

From this point onwards, from balanced we always go to unbalanced AND from unbalanced we always go to balanced.

And this is the point where the second player must reverse her strategy and leave the configuration unbalanced, for the first player to balance it (the first player has no other choice, whereas usually she would have a choice to let it remain unbalanced). And so on. From there we can only alternate between balanced and unbalanced, but not for long. We are already at the end of the game.

An example of this point is the following, The second player has to play to the following unbalanced configuration:

object
object
object
object object object

The second player will produce the following configuration, which remains unbalanced, and since it remains unbalanced, this is the change in her strategy that we were talking about:

object
object
object

From then on, it is the first player’s turn and the game is certainly in favor of the second player, as it was all along.

Another example of the point to change the strategy is the following:

object
object
object object object

Here, the second player will choose to produce the following configuration which remains unbalanced, and since it remains unbalanced, this is the change in her strategy that we were talking about:

object
object
object

Let me give you another example of this point where the second player has to change her strategy. We already said that this point is where all but one line have only one object.

So, let us suppose that the second player has in front of her the following configuration and is her turn to play:

object
object object
object object

We are near the end of the game. What must she do? She must change her strategy, yes? No, no yet. Remember, we said that the point where she needs to change her strategy is when only one line has more than one object. Here, two lines have more than one object.

So, she will need to continue with her initial strategy some more. So, she will still choose to balance the configuration:

object object
object object

Now, the first player will play, and unbalance the configuration.

Let us suppose that the first player produces the following unblanced configuration:

object
object object

Now this is the point where the second player will reverse her strategy and provide an unbalanced (instead of a balanced) configuration:

object

And the first player will play and take the last object, thus losing.

So, the second player had to change her strategy at the very end.

And this concludes my analysis.

The result of this analysis is that whenever a player has in front of her a balanced configuration, the other player has total control of the game from this point onwards and until the completion of the game.

So, this is a pointless game, just like tic-tac-toe.

In tic-tac-toe, if BOTH players know the ultimate playing strategy, the game will always end in a draw.

In NIM, if BOTH players know the ultimate winning strategy, the game will always end in favor not for the player that first comes in front of a balanced configuration to play, but in favor of the other player.

So, this game is pointless. But there is a way that this gane can be “saved” from being pointless. We can add chance to it, by using a dice, and one may, for example, take the number of objects denoted by the number which she rolls.

OK, so I have described how the game works and what the ultimate winning strategy is, but why does it work this way? Why do we need to use binary representations? (Equivalently we could have also used powers of two, and mentally consider the objects in groups of 1, 2, 4, 8, 16, 32, and so on, in each row, it is the same thing.) So, why do we need to transcend to the binary realm or to the powers of two to generate and use the ultimate winning strategy?

This is because we have 2 players. We have 2 players and they alternate playing. Player1 plays, then player2, then player1, then player2 and so on. One time we go from a balanced to an unbalanced configuration and the next time we may go from an unbalanced to a balanced configuration, if the current player wants to.

This means that we need to mind the binary representation’s 1’s as pairs. When a player plays, at least one of these 1’s is destroyed. The other player then has to aknowledge this fact and play accordingly.

And the ultimate winning strategy of the game is that since 2 players play, they need to consider these 1’s as pairs in each column for the configuration to be balanced.

Advertisements

About Dimitrios Kalemis

I am a systems engineer specializing in Microsoft products and technologies. I am also an author. Please visit my blog to see the blog posts I have written, the books I have written and the applications I have created. I definitely recommend my blog posts under the category "Management", all my books and all my applications. I believe that you will find them interesting and useful. I am in the process of writing more blog posts and books, so please visit my blog from time to time to see what I come up with next. I am also active on other sites; links to those you can find in the "About me" page of my blog.
This entry was posted in Science. Bookmark the permalink.