Monday, April 21, 2014

The Fundamental Strategy taught by the game of Nim: The Victory Node


Matches are commonly used to play Nim.
Nim is an old strategy game popularized in 16th century Europe, and purportedly played in China. The game is simple, and can be played with simple objects, often using stones or matches. The game is played by laying out lines of objects and taking turns taking objects away. You take objects away by choosing a line, and then taking as many objects from that line as you want. The goal is to force the opponent to take the last object. Its best explained through an example:

For example.

The game begins by laying out stones in two lines:

  1. The first player chooses one of the lines (top or bottom), and can take AS MANY stones as he wants from it. (in this case, he can take anywhere from 1-4 stones). Let's say he takes 2 stones.

    Here's how the board looks like this:
  2. Next, the second player does the same. He selects a line, and takes as many stones as he wants. Let's say he chooses line 2, and takes 1 stone.

    The board now looks like this:
  3.  It returns to the first player, who takes 1 stone

  4. The second player takes BOTH stones from the bottom

  5. The first player is forced to take the last stone, and loses.

The Fundamental Strategy

At its core, the game of Nim is a mathematical one, and guarantees victory if you don't make mistakes and have the right board positioning.

It is not a competitive back-and-forth game at all. Allow me to demonstrate:
Say we have a board position like this:
We might recognize this as the scenario in our example earlier. The ratio of beads is 1:2. And this board position basically guarantees victory for the person whose turn it is. Supposing that the person plays it our right.

By taking both stones on the bottom line, it forces the opponent to take the final bead. Of course, you can still lose if you take only 1 stone, or the top line stone, but that would be a mistake.

Let's expand this, and look at a "losing situation"
Lets call this the 2:2 board position. If you have this scenario, it is near impossible to win if your opponent knows what he is doing. Lets look at your options (note that both lines are the same, so it doesn't really matter which line you choose)
  1. Taking 1 bead makes it so that you give the opponent the 1:2 ratio board position discussed above. 
  2. Taking 2 beads allows your opponent to take 1 bead, and forces you to lose.
Let's go one more step forward and see if we recognize a pattern:
Lets call this the 3:2 board position. This is also a board position where you are guranteed to win if you play it out right. Why? Because it builds off what have established with the 2:2, and 1:2 board set up. 

By taking away 1 stone, you force your opponent into a 2:2 board position, which is a guaranteed lose if you play it right.

And so on....4:4 is a loss, 5:4 is a win, 5:5 is a loss, etc.

There are also games of Nim with multiple lines, but I don't want to get too far into those ideas as of yet.

What does this Mean?

I didn't write this article to talk about the method of winning Nim, there are mathematical equations and methods which better describe that. I wrote it out to highlight a fundamental goal behind strategy and strategic interaction: The point where all that matters is your own execution of the strategy.

I call these points "Victory Nodes". As once you are in that position, the only thing that matters is not making mistakes- your opponents actions don't matter so long as you respond appropriately. The victory nodes are different from straight out winning because you can still make a mistake, but are important to note because they are often able to forecast victory long before it actually occurs.

A good strategist makes note of these potential Victory Nodes and tries to drive the position of the game towards it, and then sweeps up victory in one fell swoop.

In essence, a victory node is a point in which your success depends solely on yourself, and is not dependent on your opponent making a non-optimal move or a mistake.

In other words, to use a victory node:

You win by putting yourself in a position where your opponent's actions won't produce victory if you respond correctly. All that matters is your own execution of the strategy.

Of course, with everything, it is often easier said than done.