Men­tal match­sticks

Learn­ing pat­terns is the key to win­ning a game of Nim.

Cosmos - - Contents -

NIM IS A POP­U­LAR strategy game the world over. Play is sim­ple: Play­ers take turns re­mov­ing coun­ters (coins or match­sticks are per­fect play­ing pieces) from any one of three piles. The loser is the per­son who is forced to take the last ob­ject. An equally pop­u­lar vari­ant is to have the per­son tak­ing the last ob­ject win the game rather than lose. The strate­gic con­cepts for ei­ther ver­sion are es­sen­tially the same. Nim is one of the old­est strategy games known. Its ori­gins date back to at least the 1500s and pos­si­bly ear­lier. It’s very sim­i­lar to an an­cient Chi­nese game us­ing only two piles of stones called Tsyan-shizi (Pick­ing Stones).

Al­though there are po­ten­tially dozens of start­ing ar­range­ments, we’ll ex­am­ine the one I was first shown by my fa­ther, an ex­cel­lent Nim player. He ar­ranged three piles of match­sticks. Pile A had 3 match­sticks, Pile B had 5 and Pile C had 7. He ex­plained that the per­son who took the last match­stick would lose. My fa­ther also added the stip­u­la­tion that play­ers could only re­move 1, 2 or 3 match­sticks at a time. I’ll ex­plain why he did this in a mo­ment. The start­ing setup looked like this:


My fa­ther went first. He re­moved 1 match­stick from Pile A. With the mis­placed confidence of youth, I re­moved the re­main­ing 2 match­sticks from Pile A. My fa­ther re­moved 2 from Pile C, leav­ing me star­ing at two groups of 5. I took 2 from Pile B. He took 2 from Pile C. As I looked at the two re­main­ing groups of 3 match­sticks each, I knew I was in trou­ble. In des­per­a­tion, I took 3 from Pile B. He took 2 from Pile C and left me star­ing at the last (los­ing) match­stick. I was 8 years old and I was hooked.

Af­ter crush­ing me sev­eral games in a row, my fa­ther al­lowed me to go first. I still lost a dozen or so games un­til I fi­nally won one. Un­for­tu­nately, I couldn’t re­mem­ber the move se­quence, so I didn’t know how I’d won! Even­tu­ally he tipped me to his strategy. Grab some coins, but­tons or match­sticks and fol­low along. Make up a pile of 3, a pile of 5 and a pile of 7. Here’s the se­cret: Your goal is to get to cer­tain pat­terns while leav­ing your op­po­nent with the move. The most ob­vi­ous los­ing “pat­tern” is a sin­gle pile with only 1 match­stick. Who­ever is on move is lost. Ok, so that’s not much of a pat­tern but we build from there! Imag­ine you have a 1-1 pat­tern (1 match­stick in Pile A and an­other in Pile B). If you have the move, you take 1 from ei­ther pile and leave your op­po­nent to take the fi­nal match­stick. Leav­ing your op­po­nent star­ing at any of th­ese con­fig­u­ra­tions while he has the move is a win for you: 2-2, 3-3, 4-4, 5-5, 1-1-1, 1-23, 1-4-5, 2-2-4, 2-4-6, 2-5-7, 3-4-7 or 3-56. If you like, you can do a quick in­ter­net search for “Nim” and you’ll find a fairly sim­ple ex­pla­na­tion for why th­ese pat­terns are losers for the per­son that’s on move. A ba­sic understanding of bi­nary num­bers is all that’s re­quired to un­der­stand it and the “proof” is rather el­e­gant. But for now, just mem­o­rise th­ese pat­terns.

Let’s look at an ex­am­ple. For in­stance, if you can ever get to a 1-2-3 pat­tern and your op­po­nent is on move, then your op­po­nent has no way to win. If he takes 3 from Pile C, you take 2 from Pile B and he’s left with the last move in Pile A. Like­wise, if he takes 1 from Pile 2, you can take 2 from Pile C. He’ll have to take 1 from some Pile and leave you with a 1,1 sce­nario.

Con­sider an­other ex­am­ple: You leave your op­po­nent star­ing at 2-4-6. We know that’s a los­ing pat­tern for who­ever is on move. No mat­ter which pile your op­po­nent takes from, and no mat­ter how many he takes, you will still be able to leave him with an­other los­ing pat­tern af­ter your move. Let’s say he takes 1 from Pile C. That leaves you with 2-4-5. Well, we know from our mem­o­rised list that 1-4-5 is a los­ing pat­tern if you have the move, so take 1 from Pile A and your op­po­nent is again look­ing at a los­ing pat­tern. If he were to take 2 from Pile B (giv­ing you 2-2-6), you would take 2 from Pile C giv­ing him back the los­ing pat­tern 2-2-4.

You may have no­ticed that if the first player takes a sin­gle match­stick from any of the three start­ing piles, he will al­ways be leav­ing his op­po­nent star­ing at a los­ing pat­tern. This means that the first player can al­ways force a win! By tak­ing a sin­gle match­stick at the be­gin­ning of the game, your op­po­nent has to be look­ing at 2-57, 3-4-7, or 3-5-6. And all of those are guar­an­teed losers. But wait, I men­tioned ear­lier that my fa­ther let me go first and he was still able to beat me. How is that pos­si­ble? It’s sim­ple – I made a mis­take at some point in the game and he was able to get me to a los­ing pat­tern. And now we see the rea­son for his ad­di­tional rule that you can only take up to 3 match­sticks at a time. This rule has the ef­fect of ex­tend­ing the num­ber of turns. And the more turns I had, the more likely I was to make a mis­take at some point – a mis­take that he could cap­i­talise upon. If you play this game against your friends, I sug­gest you add the rule of only tak­ing a max­i­mum of 3 match­sticks per turn. It won’t hurt you when you go first, but it will give your op­po­nent more op­por­tu­ni­ties to mess up when you al­low them to go first.

Newspapers in English

Newspapers from Australia

© PressReader. All rights reserved.