Nim

The Nim game is a game for two people, alternately, be taken in which a number of objects, such as matches. The winner is the standard game the one who takes the last piece of wood, on the other hand loses the Misère variant one who has to take the last piece of wood.

If you play the game with only one row (similar to the Bachet'schen game), so a maximum number of removable sticks per train is set.

Game theory interesting is the variety described in this article, in which several rows ( in the literature: Heap ) are defined by matches: Two players alternately take that away from one of the rows. How many they take, does not matter; there must be at least a match, and it may in a train only matches a single row to be taken.

The Nim game variants are classified under the games with perfect information for two players without a draw. Nim is a neutral game (English: impartial game ) because the possible moves in a position are independent of which player moves. For the multi-row game Nim Charles Leonard Bouton in 1901 found a formula as a winning strategy.

In the work of Grundy, the optimal strategy is in neutral games via so-called Grundy values ​​on the strategy for Nim game is returned ( see set of Sprague- Grundy ). Furthermore, the theory of generalized Nim game from about 1970 to combinatorial game theory.

Winning strategy according to Bouton

For all these games, standard Nim Nim Misère and many other games, is well known and easily computable at every game, if the player can train the force to win and how. And if the first player to win can not force, then force him the second player. For standard and Nim Nim Misère the following winning strategy applies:

It represents the numbers of matches in the series is dual and calculated from these columns or points totals.

If one finds a position with only straight column sums before, so this is (for the withdrawing player) a loss position, the leads at the optimal match of the enemy that you stay in the loser role, at the end of the game to the opponent a winning template for his last train to give. If at least one of the column sums of odd, so this is according to a winning position. It is then possible, just out of reach column sums by its own train to give the opponent handing a loss position.

This check on the even-numbered column sums equal to the ( bitwise exclusive- OR ) the sum of the dual representations.

From a loss position nothing more than a winning position can be generated from a winning position ( up to gain the submission of the last train ) you can always generate a loss position. As the winner of the last train safely finds only one row, the column totals are also odd after the penultimate train.

Example of the strategy

As an example, the following winning position serving with five rows 1, 2, 3, 4 and 5 matches:

| | | | | | | | | | | | | | |

0-0-1 ( binary number of 1) 0-1-0 ( binary number of 2) 0-1-1 ( binary number of 3) 1-0-0 ( binary number of 4) 1-0-1 ( dual number of 5 ) Sums of the '1 ' s per column result: 2-2-3

The right column ( column A ) has an odd sum is 3, all other columns sums are.

If according to the winning strategy from either the 1st, 3rd or 5th row 1 match is removed in this game setting, created for the successor to a loss position with only straight column sums. There are other possible moves allowed, but they are not optimal according to the strategy because they would cause the opponent gets a winning position instead of a loss position. - Here is an example of the position after a train of 5 from the series sticks away:

0-0-1 ( binary number of 1) 0-1-0 ( binary number of 2) 0-1-1 ( binary number of 3) 1-0-0 ( binary number of 4) 1-0-0 ( binary number of 4) The column totals are: 2-2-2

This is a loss position for the player who is now on the train. He must take at least one match of exactly one row and therefore must at least make a '1 ' to a '0', so this dual point gets an odd column total in this series. He must produce a winning position. There is no other way.

However, there is always at least one way to get out of a winning position ( which we find ) a loss position to make ( for the opponent ): this is calculated from the left the first ( ie the largest ) odd column sum and take out one of the rows, which in this point, a '1 ' have, matches away. Since all smaller numbers than before can be produced in this series, you can continue to affect all of the columns to the right so that there also just created column sums.

Early Nim computer

The strategy of Bouton makes Nim to a game that is easy to program. Early computers were developed for the Nim game. 1940, the Westinghouse company on the New York World's Fair their device Nimatron from 1951 impressed a built in England electronic computer called Nimrod the general public, he the former Economics Minister Ludwig Erhard struck at the Berlin Industrial Exhibition in Nim game.

Misère

When Misère game, the player who takes the last matches, not won, but lost. A common variant of the game is Misère Marienbad.

It uses the winning strategy as the standard Nim. Only at the end is departed from her. If there is a position in which you can get by a train only rows with a match, so you pull so that after the train creates an odd number of such straight-A series.

Other variants

In addition to the rules mentioned here, there are other Nim game variants.

When Lasker Nim away a player either sticks from a row or divides the series into two not necessarily equal parts.

Sometimes called the game rule is so limited that one may take only a certain number of sticks a row. With the taper - Nim may be taken from a number one or two sticks, with the series thus may also be shared.

Black and white Nim is played with constructed from lady - stones towers. You select a stone of their color and remove it together with the overlying rocks.

Nimbi is a variant of Nim with twelve stones on twelve straight after Misère rule. It was invented by Piet Hein, a co-inventor of the Hex game, about 1950. The initial position is a losing position.