In the game of NIM, a winning strategy exists where players should always leave their opponent with piles whose binary representations have paired ones (even counts in each bit position); this general strategy, discovered through position analysis and recognizing the fractal Sierpinski triangle pattern in losing positions, allows the first player to force a win in normal NIM (where taking the last marble wins) when starting from non-symmetrical configurations.
The Game of Nim: Binary Strategy & Winning Solutions
Added:[Music] hello this is the third and final video on position analysis in the game theory problem solving series make sure you watch the first two videos as they are a primer for this video today we're going to be looking at just one game the game of nim nim is a game with a very simple rule set but turns out to have really complex and interesting gameplay as we work towards finding a winning strategy we'll find some really interesting and surprising maths comes up along the way variants of nim have been played for centuries as far back as the 1600s in europe but thought to originate in ancient china in fact the game of 21 dares which we looked at a couple of videos ago is a simple variant of one pile nem and withhoff's game is a variant of two pile nym let me quickly remind you how nim works we are looking at the variant called normal nym there are three piles containing three five and seven marbles respectively two players take turns to choose a pile and remove any number of marbles from it as long as they take at least one so they could take the whole pile if they wanted to the player who takes the last marble wins before we think about the full game let's get our hands dirty and think about a simpler version of the game what happens if there's just one pile of marbles this version of the game is quite boring because it's easy to see that player one can win by just taking the whole pile on their first turn this also means that if we start with more than one pile we want to avoid reducing the game to a single pile because this will allow our opponent to win what if we start with two piles of size three and five say this already is a lot more complex than the one pile game the strategy is not obvious at all before launching straight into position analysis we can put a bit of effort into finding a strategy by intuition we already know that we don't want to completely remove a pile because this allows our opponent to win what if we take all of the marbles from a pile except one well then the other player can empty the other pile of all but one marble and then they can win on their next turn we want to avoid this and instead force our opponent either to leave a single pile or leave two piles one of which has a single marble clearly if we leave two marbles in each pile our opponent will be forced to do one of these things but we can't arrange this on our first turn so we want to aim for this and prevent our opponent from leaving us with two piles of two there's something special about the configuration of two piles of two which stands out to me as a problem solver there is a symmetry since both piles have the same size finding symmetry in your problem can often be very useful and this is the case here suppose we leave our opponent with two equal piles each with n marbles because they can only take marbles from one pile on their go they must leave the piles uneven after their turn this means that if we can make the two piles even on our first turn then our opponent will always make the piles uneven and we can always even them up again this way we can be sure of eventually leaving them with two piles of two or two piles of one and win always supposing that they don't remove an entire pile which gives us the win anyway the first player can do this on their first turn taking two marbles from the pile of five leaving two piles of three so the first player has the winning strategy in fact this will be the same for any game of nim starting with two piles of unequal size if the game starts with two equal piles then player two has the winning strategy because player one must make the piles uneven on their first turn that was already quite hard work and there were only two piles actually if you think about it carefully what we were doing was position analysis in a roundabout and convoluted way now we want to think about having three piles of the start with sizes three five and seven if you haven't already i encourage you to pause the video and really think about the three pile case can you do something like what we did with two piles you should be able to convince yourself that you don't want to just reduce the game to two piles and the strategy of making all three piles equal doesn't work either what about making two of the piles equal solving the problem with such an approach is not impossible but it's very difficult let's now do position analysis you'll see that it's very procedural you can easily get a computer to do it for example which in some ways is a good thing but on the other hand it's less insightful about how the game is working as always we need to label all the possible game positions the state of the game is determined by the number of marbles in each pile at the start of a player's turn so say a b and c the order of these numbers matters so we can represent a state of the game by the ordered list a b c the starting position for the game is 3 5 7. we need some way to represent all the possible positions in the game you may have noticed that a triple a b c corresponds to a point in three dimensional space so the ideal way of representing the positions would be using three dimensions alas youtube doesn't support holograms yet so i'm going to do my best to use two dimensions i shall represent the number of marbles in piles two and three using a two dimensional array and i'll represent the number of marbles in the first pile using different copies of this array so this point here corresponds to position zero four two and this point corresponds to position two zero six the triple of numbers zero zero zero does not correspond to a position of the game because if all the piles are empty the game has already finished we know that if there is just a single pile left this is a winning position so we can mark all positions corresponding to there being just one non-empty pile as winning positions now we need to spot the first set of losing positions these are the positions where however many marbles you take from any of the piles you will leave your opponent in a winning position we can interpret this geometrically these positions correspond to points where every point to the left or below them in the array or in the corresponding position in another array representing a smaller first pile is a winning position at this stage there are three new losing positions corresponding to there being two non-empty piles with one marble each we've worked through this process a few times so i'm going to fast forward through it let's sit back roll the music and watch the algorithm play out [Music] do the result is that the starting position three five seven is a winning position so player one has a winning strategy which is always to move to leave player 2 in a losing position it's not very easy to interpret this strategy and say why it works beyond that it does we have solved the problem i set but as with the other games we have looked at it's natural to want to generalize to a game of nim starting with n piles containing x1 x2 x3 up to xn marbles respectively there is a problem with trying to do position analysis for the general game the larger n is and the larger the x eyes are the longer it will take and it's not possible to do position analysis for every game because we can make the number of piles arbitrarily large how then to proceed well let's look more closely at the geometry this is a 3d plot of all the states in our 3-5-7 game of nim it's difficult to see what is going on so let's just focus on the losing positions as there are fewer of them that's tidier but still not clear what is going on we can see however that it's not random see here some of those points form a tetrahedron which doesn't seem likely to be coincidental what we need is more points here i have plotted all the losing positions for a game of nim starting with three piles of 100 marbles each look at that astonishingly this complex mathematical pattern is hiding in the losing states you may recognize this pattern it's a three-dimensional version of sipinski's triangle but can we use this to describe the winning strategy for any game of nim well there are some losing positions which jump out as interesting they are the positions where the pattern transitions from filled in to empty tetrahedra this position for example is 0 64 64. this one is 0 32 32 and we also have 0 16 16 0 8 8 0 4 4 and 0 2 2.
this suggests that powers of 2 are important indeed if you've come across sipinski's triangle before you may know that it is closely connected to powers of two also you may remember that something interesting happened during position analysis when we filled in the first four rows and columns which is another manifestation of this same power of two phenomenon after playing about with different ideas you might try representing the sizes of the piles using binary numbers instead of normal base 10 numbers and try and spot a pattern here are some losing positions chosen more or less at random writing them out in binary is there anything you notice it's kind of odd the ones seem to pair up there might just be coincidence but if you check other losing positions you will see that this pattern persists how do ones pairing up relate to picking up marbles writing the pile sizes in binary corresponds to breaking up the piles into smaller piles of size 1 2 4 8 16 and so on then pairing ones means that we can pair up these sub-piles does this remind you of anything we did earlier when we were looking at the two-pile game of nim we reasoned that the winning strategy was always to try and make the two piles the same size this strategy didn't translate obviously to the three pile game but here we can see a version of it working in binary we can visualize this strategy working for our 3-5-7 game at the start player 1 wants to even up the sub-piles and then just do the same on each of their turns all this suggests a conjecture for the winning strategy of three pile nem always play to leave your opponent with piles such that the binary subpiles pair up in fact this strategy is applicable to an n-pile gain of nim having made a conjecture we still have to prove that it's correct that's a job i'm going to leave for you in the comments there are two things that you need to show the first is that if the binary subpiles don't pair up then the player can always move to make them pair up this means that the player with the winning strategy can always employ it the second is that if the binary sub-piles do pair up then any move the other player makes will leave some sub-pile unpaired this means that the player without a winning strategy can't steal the winning strategy try proving these for the three pile game and then generalizing to m-piles we might have already seen a visual verification of one of these points earlier in the video see if you can spot it i will put a link in the description to the 1901 paper by charles bauton who was the first person to mathematically study nim and provide a winning strategy it's a charming and short paper which is quite easy to read as i mentioned at the start the game we have looked at is just one of many variants of nim called normal normal in the context of mathematical games just means that the last player to move is the winner usually people play the variant of nim called mizer nim where the player who takes the last marble loses another challenge for you in the comments is to modify the winning strategy for normal nym slightly to turn it into a winning strategy for misera nim in the next video we are sticking with mathematical games but looking at a new technique as a teaser for that have a look at the following problem on a variant of knots and crosses miss air naughts and crosses i'm sure you're all aware of how to play knots and crosses or tic-tac-toe two players take it in turns placing either a naught or a cross in a three by three grid just as with mizun nim in mizai naughts and crosses the first person to make three in a row is the loser rather than the winner the question is does either player have a winning strategy or can both players force a draw as ever put your solution to or ideas about the problem in the comments thank you for watching i know i went slightly off-piste in this video but i was so excited when i found sipinsky's triangle i just had to share it i hope you enjoyed see you in the next video
Up Next

John Conway on the Game of Life & Set Theory
@istraillab
115.9K views•2012-08-24

JEE Maths | Circles: Pole & Polar Explained with Equations
@TargetPublications
14.4K views•2019-02-23

Fourier Series Introduction: The Big Idea Explained
@DrTrefor
387K views•2021-05-03

The Mathematical Impossibility of Accurate World Maps
@Vox
23.3M views•2016-12-02
Related Study Plans & Knowledge Roadmaps
Structured learning paths in Mathematics









