A mathematical game is a multiplayer game whose rules, strategies, and outcomes can be studied and explained by mathematics. Examples of such games are Tic-tac-toe and Dots and Boxes, to name a couple. On the surface, a game need not seem mathematical or complicated to still be a mathematical game...
game of strategy in which two players take turns removing objects from distinct heaps. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap.
Variants of Nim have been played since ancient times. The game is said to have originated in China
China
Chinese civilization may refer to:* China for more general discussion of the country.* Chinese culture* Greater China, the transnational community of ethnic Chinese.* History of China* Sinosphere, the area historically affected by Chinese culture...
(it closely resembles the Chinese game of "Jianshizi", or "picking stones"), but the origin is uncertain; the earliest European references to Nim are from the beginning of the 16th century. Its current name was coined by Charles L. Bouton of Harvard University
Harvard University
Harvard University is a private Ivy League university located in Cambridge, Massachusetts, United States, established in 1636 by the Massachusetts legislature. Harvard is the oldest institution of higher learning in the United States and the first corporation chartered in the country...
, who also developed the complete theory of the game in 1901, but the origins of the name were never fully explained. The name is probably derived from German
German language
German is a West Germanic language, related to and classified alongside English and Dutch. With an estimated 90 – 98 million native speakers, German is one of the world's major languages and is the most widely-spoken first language in the European Union....
nimm meaning "take", or the obsolete English verb nim of the same meaning. It should also be noted that rotating the word NIM by 180 degrees results in WIN (see Ambigram
Ambigram
An ambigram is a typographical design or art form that may be read as one or more words not only in its form as presented, but also from another viewpoint, direction, or orientation. The words readable in the other viewpoint, direction or orientation may be the same or different from the original...
).
Nim is usually played as a misère game, in which the player to take the last object loses. Nim can also be played as a normal play game, which means that the person who makes the last move (i.e., who takes the last object) wins. This is called normal play because most games follow this convention, even though Nim usually does not.
Normal play Nim (or more precisely the system of nimber
Nimber
In mathematics, the proper class of poo poo nimbers is introduced in combinatorial game theory, where they are defined as the values of nim heaps, but arise in a much larger class of games because of the Sprague–Grundy theorem...
s) is fundamental to the Sprague-Grundy theorem, which essentially says that in normal play every impartial game
Impartial game
In combinatorial game theory, an impartial game is a game in which the allowable moves depend only on the position and not on which of the two players is currently moving, and where the payoffs are symmetric...
is equivalent to a Nim heap that yields the same outcome when played in parallel with other normal play impartial games (see disjunctive sum
Disjunctive sum
The disjunctive sum of two games is a game in which the two games are played in parallel, with each player being allowed to move in just one of the games per turn...
).
While all normal play impartial games can be assigned a nim value, that is not the case under the misère convention. Only tame games can be played using the same strategy as misère nim.
A version of Nim is played—and has symbolic importance—in the French New Wave
French New Wave
The New Wave was a blanket term coined by critics for a group of French filmmakers of the late 1950s and 1960s, influenced by Italian Neorealism and classical Hollywood cinema. Although never a formally organized movement, the New Wave filmmakers were linked by their self-conscious rejection of...
L'Année dernière à Marienbad is a 1961 French film directed by Alain Resnais from a screenplay by Alain Robbe-Grillet....
(1961).
It was probably the first ever electronic computerized game (1952). Herbert Koppel, Eugene Grant and Howard Bailer, engineers from the W.L. Maxon Corporation, developed a 50-pound machine which played Nim against a human opponent and regularly won.
Poset games are mathematical games of strategy where, given a poset P, two players alternate on choosing one point in P, removing it and and all points that are greater...
In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...
(the heaps).
Game play and illustration
The normal game is between two players and played with three heaps of any number of objects. The two players alternate taking any number of objects from any single one of the heaps. The goal is to be the last to take an object. In misère play, the goal is instead to ensure that the opponent is forced to take the last remaining object.
The following example game is played between fictional players Alice and Bob
Alice and Bob
The names Alice and Bob are commonly used placeholder names for archetypal characters in fields such as cryptography and physics. The names are used for convenience; for example, "Alice sends a message to Bob encrypted with his public key" is easier to follow than "Party A sends a message to Party...
who start with heaps of 3, 4 and 5 objects. The winning strategy is for a player to leave always an even total number of 1's, 2's, and 4's. In the example, Alice implements this strategy.
Sizes of heaps Moves
A B C
3 4 5 Alice takes 2 from A
1 4 5 Bob takes 3 from C
1 4 2 Alice takes 1 from B
1 3 2 Bob takes 1 from B
1 2 2 Alice takes entire A heap, leaving two 2s.
0 2 2 Bob takes 1 from B
0 1 2 Alice takes 1 from C leaving two 1s. (In misère play she would take 2 from C leaving (0, 1, 0).)
0 1 1 Bob takes 1 from B
0 0 1 Alice takes entire C heap and wins.
Mathematical theory
Nim has been mathematically solved for any number of initial heaps and objects; that is, there is an easily calculated way to determine which player will win and what winning moves are open to that player. In a game that starts with heaps of 3, 4, and 5, the first player will win with optimal play, whether the misère or normal play convention is followed.
The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...
The digital sum in base b of a set of natural numbers is calculated as follows: express each of the numbers in base b, then take the sum of corresponding digits and discard all carry overs...
of the heap sizes, that is, the sum (in binary) neglecting all carries from one digit to another. This operation is also known as "exclusive or" (xor) or "vector addition over GF(2)
Finite field
In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...
Combinatorial game theory is a branch of applied mathematics and theoretical computer science that studies sequential games with perfect information, that is, two-player games which have a position in which the players take turns changing in defined ways or moves to achieve a defined winning...
it is usually called the nim-sum, as will be done here. The nim-sum of x and y is written x ⊕ y to distinguish it from the ordinary sum, x + y. An example of the calculation with heaps of size 3, 4, and 5 is as follows:
The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...
The decimal numeral system has ten as its base. It is the numerical base most widely used by modern civilizations....
0112 310 Heap A
1002 410 Heap B
1012 510 Heap C
---
0102 210 The nim-sum of heaps A, B, and C, 3 ⊕ 4 ⊕ 5 = 2
An equivalent procedure, which is often easier to perform mentally, is to express the heap sizes as sums of distinct powers
Exponentiation
Exponentiation is a mathematical operation, written as an, involving two numbers, the base a and the exponent n...
of 2, cancel pairs of equal powers, and then add what's left:
3 = 0 + 2 + 1 = 2 1 Heap A
4 = 4 + 0 + 0 = 4 Heap B
5 = 4 + 0 + 1 = 4 1 Heap C
---
2 = 2 What's left after canceling 1s and 4s
In normal play, the winning strategy is to finish every move with a Nim-sum of 0. This is always possible if the Nim-sum is not zero before the move. If the Nim-sum is zero, then the next player will lose if the other player does not make a mistake. To find out which move to make, let X be the Nim-sum of all the heap sizes. Take the Nim-sum of each of the heap sizes with X, and find a heap whose size decreases. The winning strategy is to play in such a heap, reducing that heap to the Nim-sum of its original size with X. In the example above, taking the Nim-sum of the sizes is X = 3 ⊕ 4 ⊕ 5 = 2. The Nim-sums of the heap sizes A=3, B=4, and C=5 with X=2 are
A ⊕ X = 3 ⊕ 2 = 1 [Since (011) ⊕ (010) = 001 ]
B ⊕ X = 4 ⊕ 2 = 6
C ⊕ X = 5 ⊕ 2 = 7
The only heap that is reduced is heap A, so the winning move is to reduce the size of heap A to 1 (by removing two objects).
As a particular simple case, if there are only two heaps left, the strategy is to reduce the number of objects in the bigger heap to make the heaps equal. After that, no matter what move your opponent makes, you can make the same move on the other heap, guaranteeing that you take the last object.
When played as a misère game, Nim strategy is different only when the normal play move would leave no heap of size 2 or larger. In that case, the correct move is to leave an odd number of heaps of size 1 (in normal play, the correct move would be to leave an even number of such heaps).
In a misère game with heaps of sizes 3, 4 and 5, the strategy would be applied like this:
A B C Nim-sum
3 4 5 0102=210 I take 2 from A, leaving a sum of 000, so I will win.
1 4 5 0002=010 You take 2 from C
1 4 3 1102=610 I take 2 from B
1 2 3 0002=010 You take 1 from C
1 2 2 0012=110 I take 1 from A
0 2 2 0002=010 You take 1 from C
0 2 1 0112=310 The normal play strategy would be to take 1 from B, leaving an even number (2)
heaps of size 1. For misère play, I take the entire B heap, to leave an odd
number (1) of heaps of size 1.
0 0 1 0012=110 You take 1 from C, and lose.
The previous strategy for a misère game can be easily implemented (for example in Python
Python (programming language)
Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
, below).
def nim(heaps, misere=True):
"""Computes next move for Nim in a normal or misère (default) game, returns tuple (chosen_heap, nb_remove)"""
X = reduce(lambda x,y: x^y, heaps)
if X 0: # Will lose unless all non-empty heaps have size one
if max(heaps) > 1:
print "You will lose :("
for i, heap in enumerate(heaps):
if heap > 0: # Empty any (non-empty) heap
chosen_heap, nb_remove = i, heap
break
else:
sums = [t^X < t for t in heaps]
chosen_heap = sums.index(True)
nb_remove = heaps[chosen_heap] - (heaps[chosen_heap]^X)
heaps_twomore = 0
for i, heap in enumerate(heaps):
n = heap-nb_remove if chosen_heap i else heap
if n>1: heaps_twomore += 1
# If move leaves no heap of size 2 or larger, leave an odd (misère) or even (normal) number of heaps of size 1
if heaps_twomore
1 for t in heaps)
# misère (resp. normal) strategy: if it is even (resp. odd) make it odd (resp. even), else do not change
nb_remove = heaps[chosen_heap]-1 if heaps_one%2!=misere else heaps[chosen_heap]
return chosen_heap, nb_remove
Proof of the winning formula
The soundness of the optimal strategy described above was demonstrated by C. Bouton.
Theorem. In a normal Nim game, the player making the first move has a winning strategy if and only if the nim-sum of the sizes of the heaps is nonzero. Otherwise, the second player has a winning strategy.
Proof: Notice that the nim-sum (⊕) obeys the usual associative
Associativity
In mathematics, associativity is a property of some binary operations. It means that, within an expression containing two or more occurrences in a row of the same associative operator, the order in which the operations are performed does not matter as long as the sequence of the operands is not...
In mathematics an operation is commutative if changing the order of the operands does not change the end result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it...
laws of addition (+), and also satisfies an additional property, x ⊕ x = 0 (technically speaking, the nonnegative integers under ⊕ form an Abelian group
Abelian group
In abstract algebra, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on their order . Abelian groups generalize the arithmetic of addition of integers...
of exponent 2).
Let x1, ..., xn be the sizes of the heaps before a move, and y1, ..., yn the corresponding sizes after a move. Let s = x1 ⊕ ... ⊕ xn and t = y1 ⊕ ... ⊕ yn. If the move was in heap k, we have xi = yi for all i ≠ k, and xk > yk. By the properties of ⊕ mentioned above, we have
t = 0 ⊕ t
= s ⊕ s ⊕ t
= s ⊕ (x1 ⊕ ... ⊕ xn) ⊕ (y1 ⊕ ... ⊕ yn)
= s ⊕ (x1 ⊕ y1) ⊕ ... ⊕ (xn ⊕ yn)
= s ⊕ 0 ⊕ ... ⊕ 0 ⊕ (xk ⊕ yk) ⊕ 0 ⊕ ... ⊕ 0
= s ⊕ xk ⊕ yk
(*) t = s ⊕ xk ⊕ yk.
The theorem follows by induction on the length of the game from these two lemmas.
Lemma 1. If s = 0, then t ≠ 0 no matter what move is made.
Proof: If there is no possible move, then the lemma is vacuously true
Vacuous truth
A vacuous truth is a truth that is devoid of content because it asserts something about all members of a class that is empty or because it says "If A then B" when in fact A is inherently false. For example, the statement "all cell phones in the room are turned off" may be true...
(and the first player loses the normal play game by definition). Otherwise, any move in heap k will produce t = xk ⊕ yk from (*). This number is nonzero, since xk ≠ yk.
Lemma 2. If s ≠ 0, it is possible to make a move so that t = 0.
Proof: Let d be the position of the leftmost (most significant) nonzero bit in the binary representation of s, and choose k such that the dth bit of xk is also nonzero. (Such a k must exist, since otherwise the dth bit of s would be 0.)
Then letting yk = s ⊕ xk, we claim that yk < xk: all bits to the left of d are the same in xk and yk, bit d decreases from 1 to 0 (decreasing the value by 2d), and any change in the remaining bits will amount to at most 2d−1. The first player can thus make a move by taking xk − yk objects from heap k, then t = s ⊕ xk ⊕ yk (by (*))
= s ⊕ xk ⊕ (s ⊕ xk)
= 0.
The modification for misère play is demonstrated by noting that the modification first arises in a position that has only one heap of size 2 or more. Notice that in such a position s ≠ 0, therefore this situation has to arise when it is the turn of the player following the winning strategy. The normal play strategy is for the player to reduce this to size 0 or 1, leaving an even number of heaps with size 1, and the misère strategy is to do the opposite. From that point on, all moves are forced.
The subtraction game S(1,2,...,k)
In another game which is commonly known as Nim (but is better called the subtraction game S (1,2,...,k)), an upper bound is imposed on the number of objects that can be removed in a turn. Instead of removing arbitrarily many objects, a player can only remove 1 or 2 or ... or k at a time. This game is commonly played in practice with only one heap (for instance with k = 3 in the game Thai 21 on Survivor: Thailand
Survivor: Thailand
Survivor: Thailand is the fifth season of the United States reality show Survivor. It was filmed in the summer of 2002 and aired from September 19 – December 19, 2002 on CBS. It was set on the island of Ko Tarutao in Thailand. Fourteen episodes aired weekly. The two initial tribes were Chuay...
, where it appeared as an Immunity Challenge).
Bouton's analysis carries over easily to the general multiple-heap version of this game. The only difference is that as a first step, before computing the Nim-sums, we must reduce the sizes of the heaps modulo
Modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....
k + 1. If this makes all the heaps of size zero (in misère play), the winning move is to take k objects from one of the heaps. In particular, in a play from a single heap of n objects, the second player can win iff
If and only if
In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
n ≡ 0 (mod k+1) (in normal play), or
n ≡ 1 (mod k+1) (in misère play).
This follows from calculating the nim-sequence of S(1,2,...,k),
In combinatorial game theory, the Sprague–Grundy theorem states that every impartial game under the normal play convention is equivalent to a nimber. The Grundy value or nim-value of an impartial game is then defined as the unique nimber that the game is equivalent to...
.
The 21 game
The game "21" is played as a misère game with any number of players who take turns saying a number. The first player says "1" and each player in turn increases the number by 1, 2, or 3, but may not exceed 21; the player forced to say "21" loses. This can be modeled as a subtraction game with a heap of 21–n objects.
The winning strategy for this game is to say a multiple of 4 and after that it is guaranteed that the other player will have to say 21, barring a mistake from the first player.
This game has a Sprague-Grundy value of zero, i.e., it is biased in favor of the 2nd player as s/he can get to 4 first and then control the game from there, as no matter what, the 1st player will never be able to say a multiple of 4 as s/he is only allowed increments of either 1, 2 or 3.
The 21 game can also be played with different numbers, like "Add up to 5 and Lose on 34".
Proof (via a sample game of 21)-
Player Number
1 1
2 4
1 5,6 or 7
2 8
1 9,10 or 11
2 12
1 13,14 or 15
2 16
1 17,18 or 19
2 20
1 21
A multiple-heap rule
In another variation of Nim, besides removing any number of objects from a single heap, one is permitted to remove the same number of objects from each heap.
Circular Nim
Yet another variation of Nim is 'Circular Nim', where any number of objects are placed in a circle, and two players alternately remove 1, 2 or 3 adjacent objects. For example, starting with a circle of ten objects,
. . . . . . . . . .
three objects be taken in the first move
_ . . . . . . . _ _
then another three
_ . _ _ _ . . . _ _
then one
_ . _ _ _ . . _ _ _
but then three objects cannot be taken out in one move.
Grundy's game is a two-player mathematical game of strategy. The starting configuration is a single heap of objects, and the two players take turn splitting a single heap into two heaps of different sizes. The game ends when only heaps of size two and smaller remain, none of which can be split...
, another variation of Nim, a number of objects are placed in an initial heap, and two players alternately divide a heap into two nonempty heaps of different sizes. Thus, 6 objects may be divided into piles of 5+1 or 4+2, but not 3+3. Grundy's game can be played as either misère or normal play.
Dr. NIM was a game manufactured by E.S.R., Inc. in the mid-1960s. It consisted of a plastic computer and a set of marbles. The machine would play a person at the game of Nim. The machine was powered by the action of the marbles falling through the machine....
In combinatorial game theory, a fuzzy game is a game which is incomparable with the zero game: it is not greater than 0, which would be a win for Left; nor less than 0 which would be a win for Right; nor equal to 0 which would be a win for the second player to move...
In mathematics, the proper class of poo poo nimbers is introduced in combinatorial game theory, where they are defined as the values of nim heaps, but arise in a much larger class of games because of the Sprague–Grundy theorem...
The Nimrod was a special purpose computer that played the game of Nim, designed and built by Ferranti and displayed at the Exhibition of Science during the 1951 Festival of Britain. Later, when the Festival ended, the computer was shown in Berlin...
Subtract-a-square is a two-player mathematical game of strategy starting with a positive integer and both players taking turns subtracting a non-zero square number not larger than the current value...
In combinatorial game theory, the zero game is the game where neither player has any legal options. Therefore, the first player automatically loses, and it is a second-player win. The zero game has a Sprague–Grundy value of zero...
Pawn duel is a logical chess game. Two players are taking part, each one has three pawns, placed in opposite to each other on controversial ending lanes. First move belongs to the player controlling the white pawns. Each move means changing the position of a single pawn of your color...
Android Nim is a game written by Leo Christopherson for the TRS-80 computer in 1978 and published by SoftSide. A version for the Commodore PET by Don Dennis was released July 1979. A new version rewritten for Microsoft Windows was released in 2005....
Archimedes-lab.org is a free and collaborative edutainment website developed and maintained by Gianni A. Sarcone and Marie-Jo Waeber, two authors and writers with more than twenty years of experience in the fields of visual thinking and education...
Cut-the-knot is a free, advertisement-funded educational website maintained by Alexander Bogomolny and devoted to popular exposition of many topics in mathematics. The site has won more than 20 awards from scientific and educational publications, including a Scientific American Web Award in 2003,...
Cut-the-knot is a free, advertisement-funded educational website maintained by Alexander Bogomolny and devoted to popular exposition of many topics in mathematics. The site has won more than 20 awards from scientific and educational publications, including a Scientific American Web Award in 2003,...
