Nim Game XL strategy

The principles

Game strategy is based on evaluating game situation. There are "winning" situations. If you find game in winning situation, regardless of your stroke you do not let it in winning situation. On the other hand if you do not find it in winning situation, you can find a "winning stroke" to put it in winning situation, and your opponent will only be able to let it in not winning situation, and if you do not do errors after you are sure to win.

The choice of player who begins is very important. With the default options, beginning situation is winning, and the player who begins may only win if his opponent do a mistake (and if you play against automate and choose to begin you could not win because automate is programmed to do not mistakes!).

On the other hand you can by the preferences change the initial state in order that it will be a not winning situation. Then the beginner have an advantage since he can put game in winning situation.

For information about basic principles of this strategy, you will find a very good article on Nim games in the English version of Wikipedia.

Evaluating game situation

The evaluation of the game situation depends on the end-game option: option called "misère" (the one who is forced to pick the last object loses), or option called "normale" (the one who can pick the last object wins). This evaluation requires little arithmetic calculations that are the same for both options.

Calculations

Call the N maximum number of objects removable incremented by 1. The evaluation of the game situation requires calculations modulo N (usually denoted %N), rest of integer division by N, and binary exclusive or (usually noted ^), bitwise exclusive or on the binary representation of the two numbers.

Call n_i the number of objects in each heap and m the number of heaps.

We begin by calculating the remains mod N for the m heaps: r_i = n_i%N

We do then binary exclusive or of all remains:

s = r₁ ^ r₂ ^ ..... ^ r_m

Option called "normale" (the one who can pick the last object wins)

The situation is winning if s is zero.

Option called "misère" (the one who is forced to pick the last lost)

If there is at least one remain above 1, the situation is winning if s is zero.

If there is no remain greater than 1, the situation is winning if s = 1.

Best stroke research

If you have found the game in a winning situation, you will leave in a non-winning situation, and your only hope is that your opponent makes a mistake, try to put the game in an unusual situation for him...

If you have found the game in a non-winning you can find by calculating one or more winning strokes. According to the mathematicians you should always find at least a winning stroke. The calculation will depend partly on the end option chosen, "normale" or "misère".

We start for these calculations from N maximum number of removable objects incremented by one, n_i the numbers of objects of each heap, and calculations made to evaluate the situation, remains r_i and result s of exclusive or.

Option called "normale"

The winning strokes are those that move s from its current value to 0.

Calculate for each heap d_i=r_i-s ^ r_i, then:

A) if d_i is greater than 0, removing d_i objects from the heap i is a winning stroke,

B) if d_i is less than 0, n_i is greater than or equal to N, and N+ d_i greater than 0, removing N+ d_i objects from the heap i is a winning stroke.

Option called "misère"

The winning strokes will be those that put s from its current value to 0 with at least a remain higher one, or that will move s to 1 with all the remains at 0 or 1.

The calculation of winning strokes depends on the situation found:

A) there is more than one remain greater than 1: you can apply the same algorithm as in the option called "normale".

B) only one remain is greater than 1: for the heap where the remain is greater than 1, you can remove a number of objects that is equal to this remain, or this remain minus 1 depending on the number of already remains to 1, for giving an odd number of remains to 1 ; for others heaps you can find other winning strokes by applying the B of option called "normale".

C) all the remains are 0 or 1 (the position is supposed to be not winning, there is an even number of remains to 1): you can either remove an object from a heap where the remain is 1, or remove N -1 objects from a heap where the remain is zero but the number of objects is nonzero (if there are such heaps).

Particular cases

The calculations are simpler if there is few heaps or removable objects.

One heap game

In the option called "normale", the situation is winning if the remain modulo N of number of objects is zero.

In the option called "misère", the situation is winning if it is equal to 1.

If the situation is not winning, in the option called "normale" the winning stroke is to remove the number of objects equal to the remain. In the option called "misère", the winning stroke is to remove a number of objects equal to the remain decremented by 1 if the remain is greater than 1, and to remove N-1 objects if the remain is zero (we supppose party unfinished, then there is at least N objects).

Two heaps game

Call r₁ and r₂ remains modulo N of numbers of object of heaps, with r₁ greater or equal to r₂.

In the option called "normale" situation is winning if r₁ = r₂. If these remains are different, the winning stroke is one that gives them the same, removing a number of objects, either equal to r₁-r₂ from the r₁ remain heap, either equal to N-r₁+r₂ from r₂ remain heap if it still has at least N objects.

In the option called "misère", the situation is winning if r₁ is greater than 1 and that r₁ = r₂,or if r₁=1 and r₂=0. If r₁ and r₂ are greater than 1, the winning strokes are the same as the option called "normale". If r₁ is greater than 1 and r₂ equals 0 or 1, winning strokes are to remove r₁+r₂-1 objects from remain r₁ heap, or remove N-r₁+r₂ from r₂ remain heap, if it has at least N objects. Finally if r₁ and r₂ both are equal to 1, winning strokes are removing one object to one of the heaps, and if they both are equal to 0, removing N-1 objects from a heap that still has objects.

Case N equals 2

We can only remove an object every time, we are always in the situation where the remains are 0 or 1. In the option called "normale" situation is winning if the total number of objects is even, and in the option called "misère" if this number is odd. We can see that all strokes are equal, the heap from which one removes an object does not matter. This game case has no interest because one can know the winner before the game beginning: the first player in the option called "normale" if the total number of objects is odd, and the second player if it is even, and the reverse in the other option.