nim for other uses see nim disambiguation nim is a mathematical game of strategy in which two players take turns removing objects from distinct heaps or piles 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 heappile the goal of the game is to be the player who removes the last object variants of nim have been played since ancient times but the origins of the name were never fully explained nim is typically played as a misre game in which the player to take the last object loses nim can also be played as a normal play game where the player taking the last object wins this is called normal play because the last move is a winning move in most games nim is usually played so that the last move loses normal play nim or more precisely the system of nimbers is fundamental to the spraguegrundy theorem which essentially says that in normal play every impartial game is equivalent to a nim heap that yields the same outcome when played in parallel with other normal play impartial games see disjunctive sum while all normal play impartial games can be assigned a nim value that is not the case under the misre convention only tame games can be played using the same strategy as misre nim nim is a special case of a poset game where the poset consists of disjoint chains the heaps at the 1940 new york worlds fair westinghouse displayed a machine the nimatron that played nim the game of nim was the subject of martin gardners february 1958 mathematical games column in scientific american a version of nim is playedand has symbolic importancein the french new wave film last year at marienbad 1961 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 misre 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 bob and alice who start with heaps of three four and five objects sizes of heaps moves a b c 3 4 5 bob takes 2 from a 1 4 5 alice takes 3 from c 1 4 2 bob takes 1 from b 1 3 2 alice takes 1 from b 1 2 2 bob takes entire a heap leaving two 2s 0 2 2 alice takes 1 from b 0 1 2 bob takes 1 from c leaving two 1s in misre play he would take 2 from c leaving 0 1 0 0 1 1 alice takes 1 from b 0 0 1 bob takes entire c heap and wins winning positions the practical strategy to win at the game of nim is for a player to get the other into one of the following positions and every successive turn afterwards they should be able to make one of the lower positions only the last move changes between misere and normal play 2 heaps 3 heaps 4 heaps 1 1 1 1 1 1 1 1 1 2 2 1 2 3 1 1 n n 3 3 1 4 5 1 2 4 7 4 4 1 6 7 1 2 5 6 5 5 1 8 9 1 3 4 6 6 6 2 4 6 1 3 5 7 7 7 2 5 7 2 3 4 5 8 8 3 4 7 2 3 6 7 9 9 3 5 6 2 3 8 9 n n 4 8 12 4 5 6 7 4 9 13 4 5 8 9 5 8 13 n n m m 5 9 12 n n n n only valid for normal play only valid for misere for the generalisations n and m can be any value 0 and they may be the same mathematical theory nim has been mathematically solved for any number of initial heaps and objects and there is an easily calculated way to determine which player will win and what winning moves are open to that player the key to the theory of the game is the binary digital sum 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 gf2 within combinatorial game theory it is usually called the nimsum as it will be called here the nimsum of x and y is written xy to distinguish it from the ordinary sum xy an example of the calculation with heaps of size 3 4 and 5 is as follows binary decimal 0112 310 heap a 1002 410 heap b 1012 510 heap c 0102 210 the nimsum 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 of 2 cancel pairs of equal powers and then add what is 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 is left after canceling 1s and 4s in normal play the winning strategy is to finish every move with a nimsum of 0 this is always possible if the nimsum is not zero before the move if the nimsum 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 nimsum of all the heap sizes find a heap where the nimsum of x and heapsize is less than the heapsize the winning strategy is to play in such a heap reducing that heap to the nimsum of its original size with x in the example above taking the nimsum of the sizes is x3452 the nimsums of the heap sizes a3 b4 and c5 with x2 are a x 3 2 1 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 misre game nim strategy is different only when the normal play move would leave only heaps of size one in that case the correct move is to leave an odd number of heaps of size one in normal play the correct move would be to leave an even number of such heaps in a misre game with heaps of sizes three four and five the strategy would be applied like this a b c nimsum 3 4 5 0102210 i take 2 from a leaving a sum of 000 so i will win 1 4 5 0002010 you take 2 from c 1 4 3 1102610 i take 2 from b 1 2 3 0002010 you take 1 from c 1 2 2 0012110 i take 1 from a 0 2 2 0002010 you take 1 from c 0 2 1 0112310 the normal play strategy would be to take 1 from b leaving an even number 2 heaps of size 1 for misre play i take the entire b heap to leave an odd number 1 of heaps of size 1 0 0 1 0012110 you take 1 from c and lose example implementation the previous strategy for a misre game can be easily implemented for example in python below import functools misere misere normal normal def nimheaps gametype computes next move for nim for both game types normal and misere if there is a winning move return tupleheapindex amounttoremove else return you will lose midgame scenarios are the same for both game types printnim misere misere you will lose printnim normal normal you will lose printnim misere misere 2 1 printnim normal normal 2 1 endgame scenarios change depending upon game type printnim misere misere you will lose printnim normal normal 0 1 printnim misere misere 0 1 printnim normal normal you will lose printnim misere misere 1 5 printnim normal normal 1 4 printgametype heaps end ismisere gametype misere isnearendgame false countnon01 sum1 for x in heaps if x 1 isnearendgame countnon01 1 nim sum will give the correct endgame move for normal play but misere requires the last move be forced onto the opponent if ismisere and isnearendgame movesleft sum1 for x in heaps if x 0 isodd movesleft 2 1 sizeofmax maxheaps indexofmax heapsindexsizeofmax if sizeofmax 1 and isodd return you will lose reduce the game to an odd number of 1s return indexofmax sizeofmax intisodd nimsum functoolsreducelambda x y x y heaps if nimsum 0 return you will lose calc which move to make for index heap in enumerateheaps targetsize heap nimsum if targetsize heap amounttoremove heap targetsize return index amounttoremove if name main import doctest doctesttestmod 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 nimsum of the sizes of the heaps is nonzero otherwise the second player has a winning strategy proof notice that the nimsum obeys the usual associative and commutative laws of addition and also satisfies an additional property xx0 let x1xn be the sizes of the heaps before a move and y1yn the corresponding sizes after a move let sx1xn and ty1yn if the move was in heap k we have xiyi for all ik and xkyk 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 and the first player loses the normal play game by definition otherwise any move in heap k will produce txkyk from this number is nonzero since xkyk 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 yksxk we claim that ykxk 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 2d1 the first player can thus make a move by taking xkyk objects from heap k then t s xk yk by s xk s xk 0 the modification for misre 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 misre strategy is to do the opposite from that point on all moves are forced variations the subtraction game s1 2 k interactive subtraction game players take turns removing 1 2 or 3 objects from an initial pool of 21 objects the player taking the last object wins in another game which is commonly known as nim but is better called the subtraction game s 12k 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 k3 in the game thai 21 on survivor thailand where it appeared as an immunity challenge boutons analysis carries over easily to the general multipleheap version of this game the only difference is that as a first step before computing the nimsums we must reduce the sizes of the heaps modulo k1 if this makes all the heaps of size zero in misre play the winning move is to take k objects from one of the heaps in particular in ideal play from a single heap of n objects the second player can win if and only if n0modk1 in normal play or n1modk1 in misre play this follows from calculating the nimsequence of s12k 0123 k 0123 k 0123 0 123 k displaystyle 0123ldots k0123ldots k0123dots dot 0123ldots dot k from which the strategy above follows by the spraguegrundy theorem the 21 game the game 21 is played as a misre 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 21n objects the winning strategy for the twoplayer version of this game is to always say a multiple of 4 it is then guaranteed that the other player will ultimately have to say 21 so in the standard version where the first player opens with 1 they start with a losing move the 21 game can also be played with different numbers like add at most 5 lose on 34 a sample game of 21 in which the second player follows the winning strategy 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 the 100 game a similar version is the 100 game two players start from 0 and alternately add a number from 1 to 10 to the sum the player who reaches 100 wins the winning strategy is to reach a number in which the digits are subsequent eg 01 12 23 34 and control the game by jumping through all the numbers of this sequence once reached 89 the opponent has lost he can only tell numbers from 90 to 99 and the next answer can in any case be 100 a multipleheap rule see also wythoffs game 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 see also kayles yet another variation of nim is circular nim where any number of objects are placed in a circle and two players alternately remove one two or three adjacent objects for example starting with a circle of ten objects three objects are taken in the first move then another three then one but then three objects cannot be taken out in one move grundys game in grundys game 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 six objects may be divided into piles of 51 or 42 but not 33 grundys game can be played as either misre or normal play greedy nim greedy nim is a variation where the players are restricted to choosing stones from only the largest pile it is a finite impartial game greedy nim misre has the same rules as greedy nim but here the last player able to make a move loses let the largest number of stones in a pile be m the second largest number of stones in a pile be n let pm be the number of piles having m stones pn be the number of piles having n stones then there is a theorem that game positions with pm even are p positions this theorem can be shown by considering the positions where pm is odd if pm is larger than 1 all stones may be removed from this pile to reduce pm by 1 and the new pm will be even if pm 1 ie the largest heap is unique there are two cases if pn is odd the size of the largest heap is reduced to n so now the new pm is even if pn is even the largest heap is removed entirely leaving an even number of largest heaps thus there exists a move to a state where pm is even conversely if pm is even if any move is possible pm 0 then it must take the game to a state where pm is odd the final position of the game is even pm 0 hence each position of the game with pm even must be a p position indexk nim a generalization of multiheap nim was called nim k displaystyle k or indexk nim by e h moore who analyzed it in 1910 in indexk nim instead of removing objects from only one heap players can remove objects from at least one but up to k different heaps the number of elements that may be removed from each heap may be either arbitrary or limited to at most r elements like in the subtraction game above the winning strategy is as follows like in ordinary multiheap nim one considers the binary representation of the heap sizes or heap sizes modulo r1 in ordinary nim one forms the xorsum or sum modulo 2 of each binary digit and the winning strategy is to make each xor sum zero in the generalization to indexk nim one forms the sum of each binary digit modulo k1 again the winning strategy is to move such that this sum is zero for every digit indeed the value thus computed is zero for the final position and given a configuration of heaps for which this value is zero any change of at most k heaps will make the value nonzero conversely given a configuration with nonzero value one can always take from at most k heaps carefully chosen so that the value will become zero building nim building nim is a variant of nim where the two players first construct the game of nim given n stones and s empty piles the players alternate turns placing exactly one stone into a pile of their choice once all the stones are placed a game of nim begins starting with the next player that would move this game is denoted bnns higher dimensional nim nd nim is played on a k1kn board where any number of continuous pieces can be removed from any hyperrow the starting position is usually the full board but other options are allowed dr nim fibonacci nim wythoffs game fuzzy game nimber nimrod computing octal games star game theory subtract a square zero game android nim raymond redheffer notakto w w rouse ball mathematical recreations and essays the macmillan company 1947 john d beasley the mathematics of games oxford university press 1989 elwyn r berlekamp john h conway and richard k guy winning ways for your mathematical plays academic press inc 1982 manfred eigen and ruthild winkler laws of the game princeton university press 1981 walter r fuchs computers information theory and cybernetics rupert hartdavis educational publications 1971 g h hardy and e m wright an introduction to the theory of numbers oxford university press 1979 edward kasner and james newman mathematics and the imagination simon and schuster 1940 m kaitchik mathematical recreations w w norton 1942 donal d spencer game playing with computers hayden book company inc 1968 wikimedia commons has media related to nim 50pound computer plays nim the new yorker magazine talk of the town august 1952subscription required the hot game of nim nim theory and connections with other games at cuttheknot nim and 2dimensional supernim at cuttheknot subtraction game a subtraction game illustration on appstore classic nim implementation of nim for ios matchstick nim implementation of nim for android devices 