Nim game

from Wikipedia, the free encyclopedia
Starting position with matches

The Nim game is a game for two people in which a number of objects, such as matches , are taken away alternately . In the standard game, the winner is the one who takes the last stick, while in the Misère variant, the winner is the one who has to take the last stick.

If you play the game with only one row (similar to Bachet's game ), a maximum number of sticks that can be removed per move is set.

In terms of game theory, the type of game described in this article is interesting, in which several rows (in literature also: piles) of matches are given. Two players take turns taking one or more woods from one of the rows. How many you take doesn't matter; However, only matches may be taken from a single row during a move.

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

In Grundy's work , the optimal strategy for neutral games is traced back to the strategy for Nim games using so-called Grundy values ​​(see Sprague-Grundy's theorem ). Furthermore, the theory of the Nim game generalized to the combinatorial game theory from around 1970 .

Winning strategy according to Bouton

For all these games, Standard-Nim, Misère-Nim and many other games, it is known and easy to calculate at every score whether the player to move can force victory and in what way. And if the attracting cannot force victory, then the subsequent can force it. The following winning strategy applies to Standard Nim and Misère Nim:

The number of matches in the rows is displayed in two ways and is calculated from these column or digit sums.

If you find a position with only even column sums, this is a losing position (for the player who draws), which, if the opponent plays optimally, means that you remain in the losing role, and at the end of the game the opponent has a winning template for his last move to give. If at least one of the column totals is odd, this is a winning position (exception: Misère-Nim endgame ). It is then possible to reach even column totals with your own move, whereby you give your opponent a losing position.

This check for the even number of the column sums corresponds to the (bitwise exclusive OR) sum (“XOR sum”) of the dual representations.

From a losing position nothing other than a winning position can be generated, from a winning position (up to the winning position of the last move) one can always generate a losing position. Since the winner will only find one row on the last move, the column sums after the penultimate move are also odd.

Example of the strategy

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

|  

| |  

| | |  

| | | |  

| | | | |  

The dual representations for it

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 (binary number of 5)

The sums of the '1' s per column result in:
2-2-3

The right column (units column) has an odd sum, namely 3, all other column sums are even.

If in this game position, according to the winning strategy, 1 match is removed from either the 1st, 3rd or 5th row, the successor will be in a losing position with only even column sums. There are other allowable moves, but they are not optimal according to the strategy because they would result in the opponent getting a winning position instead of a losing position. - Here as an example the position after a move that removes a stick from the 5th row:

The binary numbers after removing a stick from the 5th row:

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 losing position for the player who now has his turn. He must take at least 1 match from exactly one row and must therefore turn at least a '1' into a '0' in this row, which gives this dual digit an odd column total. So he has to generate a winning position. There is no other way.

However, there is always at least one possibility to turn a winning position (which you find) into a losing position (for the opponent): To do this, you determine the first (i.e. the highest-ranking) odd column total from the left. There must then be a row that has a '1' in this column. Take matches out of such a row in such a way that in this column and in all columns further to the right (left is correct before) straight column sums are created.

Early Nim computers

Nimrod in the Computer Games Museum Berlin

Bouton's strategy makes Nim a game that is easy to program. Early computers were designed for the Nim game. In 1940 the Westinghouse company exhibited its Nimatron device at the New York World's Fair and in 1951 an electronic computer called Nimrod built in England impressed the public by beating the then Minister of Economics Ludwig Erhard in the Nim game at the Berlin industrial exhibition .

Misère

In the Misère game, the player who takes the last match did not win, but lost. A common variant of Misère-Nim is Marienbad , the starting position of which is shown in the illustration.

In the main, the same winning strategy rules as with the standard Nim. Only at the end is deviated from it. At some point there will be exactly one row with more than one match. From this row you can normally remove all or all but one of the matches. If you want to win, you hand over an odd number of rows of ones. (With the standard Nim it would be an even number, which in this case is, by the way, the same as the even number of the column sums .)

Other variants

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

In Lasker-Nim , a player either removes sticks from a row or divides the row into two parts that are not necessarily the same size.

Sometimes the mentioned rules of the game are restricted so that you can only take a certain number of sticks in a row. With the Kegel-Nim one or two sticks can be taken from a row, whereby the row can also be divided.

Black and white Nim is played with towers made of checkers . You choose a stone of your own color and remove it together with the stones above.

Nimbi is a Nim variant with twelve stones on twelve straights according to the misère rule. It was invented by Piet Hein , a co-inventor of the hex game , around 1950. The starting position is a losing position.

literature

Web links

Individual evidence

  1. ^ CL Bouton: Nim, a game with a complete mathematical theory. In: Annals of Mathematics. (2) 3 (1901), pp. 35–39 ( abstract in the Electronic Research Archive for Mathematics )
  2. ↑ Bouton developed a Nim addition. (Compare: Bewersdorff: Glück, Logic ... 2010, p. 117.) There binary numbers are added to a dual sum in such a way that no carryovers are made during this addition. This sum is called the Nim sum. It is '0' if and only if all column totals are even and '1' if at least one column total is odd.
  3. ↑ Once the row has been selected, the rest of the move is clear, namely (new number of matches): = (number of matches) XOR (XOR sum of all rows). Because of the high-ranking '1', the new number of matches is smaller, so the move complies with the rules.
  4. ^ Elwyn R. Berlekamp, ​​John H. Conway, Richard K. Guy: Winning - Strategies for Mathematical Games , Volume 1
  5. ^ Solution in B. Kummer, Games on Graphs. Deutscher Verlag der Wissenschaften, Berlin 1979; Birkhäuser, Basel 1980 (ISNM Series, Vol 44), doi: 10.1007 / 978-3-0348-5481-8 , p. 47, exercise 1.
  6. ^ Bewersdorff: Glück, Logic 2010, p. 124.
  7. ↑ Bewersdorff: Glück, Logic 2010, p. 176.