1

Review: Brain Candy

Published on Sunday, August 29, 2010 in , , , , , , , ,

Garth Sundem's Brain Candy bookAfter my review of Geek Logik and mention of The Geeks' Guide to World Domination, author Garth Sundem has very generously given me a copy of his latest book, Brain Candy: Science, Paradoxes, Puzzles, Logic, and Illogic to Nourish Your Neurons, for review.

The title Brain Candy perfectly sums up the approach to its content. Like The Geeks' Guide to World Domination (GGTWD), it's filled with brief articles, most of which can be read in 1-2 minutes. However, while GGTWD was more of a general guide to things of geeky interests, such as chess openings with cool names, or information about obscure holidays, Brain Candy's focus is topics that tend to be more challenging.

Here, you're more likely to be confronted with the counter-intuitive, and the challenging, including the odd brain maze each time that a, well, “Piece of Mind” is discussed, such as the frontal or occipital lobes. Brain Candy also feels more organized and coherent than GGTWD, where the jumps in subject matter from one article to the next feel far larger.

To get a better idea of what I'm talking about, the author has posted selected segments over on his Science 2.0 blog. The Brain Candy-specific entries are easy to spot, due to their hand-drawn icons (which also appear in the book).

Extending the candy metaphor, what usually happens when you eat it? Usually, one of two things. Either you taste the candy, enjoy it, and then move on. Other times, you try it, enjoy it, and find you want more. When you find a surprising or illogical tid-bit that grabs you, you can find out more usually with a quick internet search. Basically, Brain Candy is a quick way to pass some enjoyable time, while also serving as an inspirational springboard for exploring new concepts.

Many of the ideas in Brain Candy will be familiar to regular Grey Matters readers, such as the Monty Hall Dilemma, discussed here and here (as well as many other areas of game theory), memory, and math. There is plenty in this book that I haven't covered, but will still be likely to grab readers of this blog.

As with Garth Sundem's other books, this will definitely find a place in my geeky library, so I highly recommend that Grey Matters readers give it a look for theirs, as well.

0

Penny Puzzles (Chico Marx's Favorite Scam)

Published on Thursday, August 26, 2010 in , , , ,

Scam School logoGreat minds think alike! I recently added a new section of Penny Puzzles to the Grey Matters Store. A little over 1 week later, Scam School covers the same puzzle!

Before I get to the Scam School episode itself, let's cover the basic challenge first.

Start by drawing a 5-pointed star, and then place a penny (or button, or other small object) on one of the points, and slide it along either connecting line to another point. That's not hard so far, right?

Next, put another penny on any empty star point, and slide it along a line to any other empty star point. The challenge is to place 4 pennies on the star in this manner.

Before you try it, it seems easy. Most people find that they can only get to 3 coins, and find the 4-coin solution unusually elusive.

Let's change the puzzle a bit, but keep the rules the same. Here's an online version that uses an 8-pointed star (Java required). The rules are the same, but you're trying to place 7 pennies this time. Try playing this version without using the hint button and/or the explanation link as long as you can.

Perhaps there's something tricky about those lines? Let's try a similat 9-dot challenge, but just with counting (Flash required), both clockwise and counter-clockwise. The object this time is to turn 8 dots white.

Isn't it maddening that such a seemingly simple task should prove so elusive? As a solo game, this can provide hours of puzzlement.

Leave it to none other than Chico Marx to turn this into a hustle with money. Thankfully, Scam School shows you not only how Chico Marx turned this into a bar scam, but also how to beat this maddening puzzle:



The method taught here is taught so well, it shouldn't take long to work how it applies to all the other versions, as well.

Obviously, if you're doing the Scam School version above, you should go last, as suggested. However, if you're just challenging a friend or two to solve the puzzle, you'll find that if you can demonstrate the solution without explaining the method behind it, your friends will still have trouble solving the puzzle!

Try these out for yourself, and let me know in the comments of anything interesting that happened when you played this yourself, or challenged your friends.

0

Nim Strategy Calculator

Published on Sunday, August 22, 2010 in , , ,

NIM is WIN upside down!(NOTE: Check out the other posts in The Secrets of Nim series.)

I've received plenty of positive comments on my recent Secrets of Nim posts. Jim Wilder, of jimwilder.com, sent me a private message saying, "looked at your blog on NIM... excellent stuff there". James Grime (also known as singingbanana), gave me a great compliment on his twitter account. Even the gambling-specialists over at the Magic Cafe had many good things to say about my Nim series.

It's one thing to understand the math behind the various versions of Nim. Wouldn't it be nice if there were a quicker way to determine the best strategies for Nim?

Now there is! Today, I'm introducing my Nim Strategy Calculator! It's available as a permanent page, accessible from the Mental Gym's Workout page under Tools.

The Nim Strategy Calculator is actually 3 calculators in 1. The first is the strategy calculator for single-pile Nim, the second is for multi-pile Nim, and the final one is merely for determining the next move in the middle of a multi-pile Nim game (all these terms are defined in Part 1 of my Secrets of Nim post). You choose between them using the tabs at the top.

I've tried to make them easy to use and straightforward by asking for all the information in an interview-type format. Once you enter all the relevant information in a section, you simply click the Calculate button at the bottom of the section, and the strategy will be given to you in plain English.

Here are more details on each section:

Single-Pile Nim Strategy Calculator

Being the simplest form of Nim, you only need to provide 4 pieces of information for single-pile Nim:

Nim Screenshot 1

The first question, which is the same with all 3 calculators, is whether the person who moves last is the winner or the loser.

The next question is how many objects are used. While single-pile Nim is usually played down to 0, such as the game in Episode 8 of Scam School, there are games where you start at 0, and try and go up to a maximum amount, like in episode 80 of Scam School. This is why this is asked as the “maximum” or “limit”.

This is also why the third question asks whether the game is played down to 0 or up to the limit. Lastly, the final question asks about the range of the amount of objects that can be used per turn.

As an example, let's try using the calculator to analyze the match game from Scam School's 8th episode. The player who makes the last move is the loser, they're using 17 objects, playing down to 0, and up to 3 objects are allowed per turn, so the data would be entered as follows:

Nim Screenshot 2

Click the Calculate Nim Strategy button below all the data, and you get this response in the box:
The rules for this particular version of the game of Nim are as follows:
* There are two players.
* The players alternate taking turns.
* The game starts out with 17 objects.
* On a given player's turn, they must remove anywhere from 1 to 3 objects.
* Neither player is allowed to remove 0 objects.
* The last person to make a move is the loser.


The Scam: Although seemingly fair, you can rig this game in your favor.

For this particular version of Nim, the other person should go first. This will ensure that you can always leave certain key numbers of objects on each turn that will guarantee your win.

The key numbers of objects you need to leave on each turn, in order to safely win the game, are as follows:

13
9
5
1 (of course)


Tips:

* You don't have to hit every key number. Just make sure you get to one of the above key numbers before the goal is reached, and you'll always be able to win the game from there.

* If it's decided that you must go first, and your opponent isn't wise to the ways of Nim, it's still possible for you to win. Only play small amounts of objects on your turns, until you get an opportunity to reach a key number.

* Instead of playing single-pile Nim with physical objects, you can often just state the numbers verbally, or even use a calculator.
This data can be copied to a text editor or word processor, where you can save the information for later. Note that various tips are given, and they are often different for particular settings.

Whenever you get a response, always read it carefully! Besides the particular goal numbers, it also mentions whether you or the other person should go first, and what to do if that's not possible. I've tried to make the tips as useful as possible, as well.

Try entering the data yourself for Scam School episode 80: The person who makes the last move is the winner, the limit is 31, the game is played up to the limit, and the number of objects used per turn is from 1 to 6. When you click the Calculate Nim Strategy button, note that the advice here is exactly the same advice (for the first round, anyway), as in the video (assuming you entered the information correctly)! There are even some extra tips that aren't given in the video.

Multi-Pile Nim Strategy Calculator

The Multi-Pile Nim Strategy Calculator looks a little different than the single-pile version:

Nim Screenshot 3

The first question, as before, determines whether standard or Misère Nim is being played.

The next question is a pull-down menu that lets you select from 3 to 9 piles. When you change this number, a number of boxes equal to your choice will appear below it. These boxes allow you to specify how many objects are in the individual piles.

One of the most basic versions of multi-pile nim is taught in episode 37 of Scam School. In this version, the person who removes the last object loses, there are 3 piles, and the piles consist of 3, 5, and 7 objects respectively. The data would be entered like this:

Nim Screenshot 4

When you click the Calculate Nim Strategy button here, you might be surprised to find more safe positions than are listed in the Scam School video. In this particular case, the new moves are simply those that are 1 object different from the opening layout.

Just for fun, try using the Multi-Pile Nim Strategy Calculator to determine the best strategy for the Last Year in Marienbad version (it's Misère Nim), or to find out why the XKCD character in this comic reacts the way he does.

Next Move?

Originally, I tried using the Multi-Pile Nim Strategy Calculator to play against online versions of Nim, such as Pearls Before Swine or Nim Master (Flash required for both). Unfortunately, I often found that the number of piles and/or the number of objects involved often made it too difficult to search through the list of safe positions quickly and effectively.

To solve that problem, I added the “Next Move?” calculator. It works pretty much the same as the Multi-Pile Nim Strategy Calculator, with just one added feature: A checkbox you mark if the arrangement in question is the first move. Many computer versions of Nim let you decide who goes first, so this will give you an appropriate recommendation. Here's how the “Next Move?” calculator appears:

Nim Screenshot 5

As an example, I'll start a game of Pearls Before Swine, in which the last person to remove an object is always the loser. I see 3 piles, consisting of 3, 6, and 8 object as the opening layout. I enter this into the “Next Move?” calculator as follows:

Nim Screenshot 6

Since this calculator is only concerned with looking 1 move ahead, the reponses are much briefer. The response I get from the above entry, after clicking the Calculate Next Move button was this:
Here are the plays you can make on this turn, in order to insure a win at the end:

3, 6, 5 (8-object pile: Remove 3)
Note that it gives you the layout numerically, but also tells you in plain language how many are removed, and from which pile.

Continuing to play this same game, I make the recommended move, and am now left with 3 piles of 3, 6, and 4 (after the other player's move). Updating this to reflect the new information (including the fact that this isn't the opening move), I get this response:
Here are the plays you can make on this turn, in order to insure a win at the end:

2, 6, 4 (3-object pile: Remove 1)
Needless to say, after a few more moves, I won this particular game.

Uses

There are quite a few nice things about using these calculators.

First, if you want to understand how the strategy changes as the rules change, you can get a quick understanding here. If you have a favorite layout of, say, multi-pile Nim, and people after a few games are asking things like, “What if I go first?” or “What if we make the person who takes the last match a winner?”, you can be ready for such eventualities.

Working with the calculators can make the entire Secrets of Nim series easier to follow and understand.

Also, these calculators can help you learn a particular strategy by heart, as well. In multi-pile Nim, the same safe positions are safe in any game (with certain exceptions for Misère Nim and multiple 1-object piles). Using the “Next Move?” calculator frequently in the beginning will often make these moves very familiar.

Finally, you can use these calculators to create custom Nim variations (and learn to play them correctly). For example, what if you have a friend whose 37th birthday is coming up, and he has 4 kids. You could challenge him to a game of single-pile Nim that starts with 37 objects, where you're allowed to take up to 4 objects per turn. In this particular case, I suggest making it a Misère Nim, because the winning strategy can quickly become obvious (Why? Run it through the calculator and see for yourself).

Alternatively, what if his 4 kids are ages 4, 8, 10 and 14, respectively? You could play a game of multi-pile Nim against him, starting with piles of 4, 8, 10 and 14, and already know the best plays.

I hope you enjoy the Nim Strategy Calculator, and find it useful! If you do find it useful, please take the time to click on the ads on this page, or the calculator page.

1

Frank Armbruster's Instant Insanity

Published on Thursday, August 19, 2010 in , , , , ,

Frank Armbruster's Instant Insanity puzzle in a solved position. Click for larger image.Back in 1967, puzzlemaker Frank Armbruster released a devious puzzle through Parker Brothers that took the world by storm.

It was called Instant Insanity, and has sold over 12 million copies (and, like Rubik's Cube, spawned numerous imitations). Parker Brothers re-released it in the 1980s, while the world was going nuts over Rubik's Cube. Here's the 1980s ad for Instant Insanity:



So, what exactly was the challenge? The puzzle itself came as 4 separate cubes, with each side of each cube being one 4 colors (green, red, blue, and yellow), and the colors were arranged on different cubes in different ways. The object of the puzzle is to stack these cubes in a column so that each side (front, back, left, and right) of the stack shows each of the four colors (as shown in the top left photo in this post).

At first, this doesn't sound that hard. As a matter of fact, you can try it out here on Grey Matters (Java required). Alternatively, here's a Javascript version.

In both of the above versions, the cubes are effectively unfolded and lay flat. If you prefer to work with a version where the subes remain in 3-D, there's the online nrich Instant Insanity version (Flash required), or the even more tactile iPad version.

By 1971, the puzzle was so popular and so recognizable, it was used as part of a computer vision project at the Stanford University Artificial Intelligence Laboratory, displayed to the public at an artificial intelligence conference:



How would a human go about solving it, though?

It's not easy. Perhaps you may get a clue from this video (you might want to turn down the volume before hitting play), if you watch carefully enough:



Hmmm...what are those lines and circles? Well, they look kind of like the ones Leonard Euler (pronounced "oiler") used to solve the classic Seven Bridges of Königsberg problem.

Basically, that's exactly what this is. Since the goal of Instant Insanity is to form a particular relationship among the sides, this boils down to a networking problem.

In Ivars Peterson's August 9, 1999 column, Averting Instant Insanity, he shows how to simplify the problem down with simple graphs representing the color arrangements, much like Euler did with the Seven Bridges of Königsberg problem, and then how to use this information to find the answer.

Jaap's Instant Insanity / Buvos Golyok / Drive Ya Crazy Page discusses some of the popular variations. He shows a similar approach to the variations, making this a good page to learn how to generalize the solution approach.

Robin Wilson, Professor of Geometry at Gresham College, has made a video detailing the graph solution that may help you visualize the solution process better:



Although the graph theory approach is the one most commonly used, there is a surprising 2nd approach, using prime numbers, as well. If you're interested, Professor Wilson discusses that 2nd approach in this video.

Be honest, did you peek at the solutions before you even tried the puzzle?

1

Quick Snippets

Published on Sunday, August 15, 2010 in , , , , , ,

LinksIt's time for the August snippets! This month's snippets have two themes – Math fun and FREE stuff!

• The folks over at MathTutorDVD.com have a free weekly video podcast called Mental Math Secrets (iTunes Link). Each week, one math trick is taught on a whiteboard, and explained in detail. They're quite clear, and the weekly nature of the podcast gives you time to master it before learning the next one.

• Ever play Dots and Boxes? You can try a free javascript version online, playing against the computer here, or against another player here. If you play long enough, you might be wondering if there's strategies that can help you win. There sure are, and the best place to learn them that I've ever found is Ilan Vardi's free online course Mathter of the Game. Check it out for an eye-opening look at a seemingly simple game.

• After writing about things like Nim and Corner The Lady, I thought it would be fun to be able to play these against others on my iPad. While there are limited Nim choices and zero Corner the Lady choices in iPad apps, there is a solution: Metaversal Studios' free GameRoom app (iTunes Link) to the rescue! Besides playing the built-in games of Checkers, Go, Reversi, Mancala, and Halma, there's a custom mode that allows you to choose the board size (7x7 up to 20x20), and various features of the look of the board, and will enable you to play just about any grid-based game (or even some games where grids are irrelevant) against another player who agrees on the rules. Check it out!

• While I'm thinking about free iTunes apps, check out Peg Solitaire - BrainVita from TouchMeme (iTunes Link). This is the standard English Peg Solitaire (as opposed to the triangular “Cracker Barrel” version). It's no more or less than what it claims: The standard puzzle where you try to leave a peg in the center. If it fries your brain, there's an excellent and easily-remembered purge-and-package approach to solving it taught here.

1

Fun With Phi

Published on Thursday, August 12, 2010 in , , , , , , ,

Phi SymbolI've talked quite a bit about Pi on this blog, but today, I'm turning my attention to a different number: phi. Like Pi, phi goes on forever, and can only be approximated. It's equal to roughly 1.6180339887, but is also known as the golden ratio.

What makes phi as a number so special? And what's with the name golden ratio, anyway? Of course, Grey Matters readers have an additional question: What kind of fun can we have with it?

The Basics

Let's start with a quick video history of phi, its discovery, and its original uses:


The Fibonacci Addition Trick

Let's try making a column of 10 numbers in a Fibonacci sequence, using the same process mentioned in the above video. Have someone choose any two numbers, both below 10, to help keep the numbers manageable. As an example, let's choose 8 and 3. Let's see...8 and 3 make 11, 3 and 11 make 14, 11 and 14 make 25...if we continue, we wind up with this column of numbers:
  8
  3
 11
 14
 25
 39
 64
103
167
270
How fast do you think you could find the sum of these numbers? It wouldn't take too long with a calculator, but what if you could add these numbers in your head quicker than a calculator?

How? Find the 7th number from the top (4th from the bottom), and simply multiply it by 11! In this case, the 7th number is 64, so we multiply 64 times 11 and get 704!

At this point, you probably have at least one of two questions. First, how do I multiply by 11 mentally? It's easier than you might think. Here's a video showing you how to multiply by 11 with up to 5 digit numbers:



For a further explanation, as well as some practice exercises, check out Math World's Math Tricks: Multiply by 11 page.

The other question you probably have is, “Why does multiplying the 7th number by 11 always work?” The surprisingly simple explanation is given here by Dr. Math.

One common addition to this trick is to have people divide the 10th number in the column by the 9th number, which you can also do without a calculator. In the example above, it would be 270/167, which is 1.6167664671. Look familiar? It's an approximation of phi! Thanks to the pattern imposed by the Fibonacci, you can always look like you're mentally calculating, say “1.61”, and you have one routine that makes you look like a mathematical genius!

Game: Corner The Lady

Here's a game known as Corner The Lady (Java required), invented around 1960 by Rufus P. Isaacs. The rules are described at the link, so read them carefully. I suggest starting with the smallest board, which is 4 by 4, and working your way up as you discover how to win.

Hmmm...the title on the page reads Wythoff's Nim. Perhaps this is a form of Nim, and therefore always winnable with the proper strategy? Yep!

Technically, Corner The Lady and Wythoff's Nim are two different games. Wythoff's Nim is played with two piles of objects, each with a different number of objects. Like standard Nim, you can take as many matches as you want from either pile on your turn, and the object is to take the last remaining object. However, in Wythoff's Nim you can also take objects from both piles on your turn, with the restriction that you have to take the same number of objects from both piles.

In chapter 8 of Martin Gardner's book, Penrose Tiles to Trapdoor Ciphers, he points out the surprising fact these two games have exactly the same winning strategy, because they're mathematically the exact same game! Much of that chapter is reprinted here online, in case the chapter link at the start of this paragraph ceases to work.

So why is this included in a post on phi? It turns out that the safe positions (that is, the positions which will guarantee you a later win, assuming the goal square to be 0,0) can be generated using phi! If you want to find the N safe position, you multiply N by phi, round it down to the nearest whole number, and you've got your first coordinate. How do you get the second coordinate of a safe position? Simply add N to the first coordinate!

For example, if we're looking for the 1st pair of coordinates that's safe, we work through this way. N=1 (for the 1st pair), and N times 1.61 equals 1.61, which is rounded down to 1. That 1 is our first coordinate. 1 plus 1 = 2, so 2 is our second coordinate.

So, now we have 1 and 2, does that mean our first safe square is plotted at 1,2 or 2,1? Surprisingly, both are correct! The formula we used actually generates a pair of safe squares each time you use it. Isn't phi nice? It gives us a formula with which it's hard to make a mistake.

Where do we go from here? I suggest taking a look around the web, including images and videos, and searching mainly for the terms Fibonacci and golden ratio. There's so much more to discover about these fascinating concepts. Phi is one of those ratios, like Pi, that pops up in the most surprising of places.

0

The Secrets of Nim (Wrap-up)

Published on Sunday, August 08, 2010 in , , , , , , ,

NIM is WIN rotated 180 degrees!(NOTE: Check out the other posts in The Secrets of Nim series.)

I hope you've enjoyed The Secrets of Nim series. I'm going to wrap it up today, with a brief, yet possibly surprising, look back at Nim.

For most of history, the various versions of multi-pile Nim were played as a regular game, as opposed to a swindle. It was known that if you got to certain positions in some select games that you could win from that point on, but nobody knew whether it was possible to guarantee a win from the start.

That all changed in 1901, when Charles L. Bouton of Harvard University discovered the approaches to multi-pile nim that were detailed in part 2 and part 3 of this series.

Just over three decades later, R. P. Sprague and P. M. Grundy, working independently, both discovered that larger numbers of objects in Nim (among other games) could be made easier to handle by reducing them to smaller ones via certain functions. A good introduction to the Sprague–Grundy theorem, as well as variations of Nim, is available via this PDF from the UCLA Math Department.

If you really want to see where analysis of Nim can take you, including a mind-boggling array of variations, I highly recommend checking out Winning Ways, for Your Mathematical Plays, Volume 1, Volume 2, Volume 3, and Volume 4, by Elwyn R. Berlekamp, John Horton Conway, and Richard K. Guy.

Naturally, once it was proven that you could win Nim from the beginning, and safe moves could be determined throughout, it quickly became a favorite of swindlers. Equipment began to show up to make the game portable and easy to play. The Gambler's Beads were an interesting version of single pile Nim, but multi-pile versions were also developed.

Even while the earliest computers were being developed, compters such as Nimatron were being displayed at the 1940 New York World's Fair. The Nimrod computer, a vastly improved version of Nimatron, was displayed at the 1951 Festival of Britain.

This effectively makes Nim among the first, if not THE first, computer games!

Thanks to the simplicity of Nim, it can also be played against mechanical computers, instead of just electronic ones. In 1961, a single-pile Misère game called Dr. Nim was released. Check out the impressive operation of this simple plastic machine in the video below:



In one of his Scientific American columns, Martin Gardner discussed Hexapawn (PDF), and how you can play against a simple set of matchboxes and stones that learn to improve their play via a system of punishments and rewards (More on this in my Computing . . . Without Computers! post).

On the last page of that same column, there's mention of a Bell Labs research director who used a similar approach to build a matchbox learning machine for Nim! Impressively, the machine required only 18 matchboxes, could go first or second in different games, and yet would play almost perfectly after only around 30 games. I think if I lost a game of Nim to a set of matchboxes and stones, I'd feel dumber than a box of rocks.

When the first pocket calculators were released in the 1970s, Nim was adapted to those just as quickly as it had been with the first electronic computers. I wouldn't be surprised to learn that someone tried getting several pocket calculators together and use them to play some form of multi-pile Nim.

It's not hard to find Flash versions today, but there are a few that really stand out. Pearls Before Swine goes for the whole experience, and constantly challenges you with more and larger piles, while keeping track of your wins and losses.

Ricardo Rix's version of Nim (multi-pile Misère Nim) lets you choose the level of your opponent's play, as well as how many piles will be involved, so you can develop your skill and analytical abilities at your own pace.

1961 must've been a great year for Nim. Not only was the aforementioned Dr. Nim released, but it was also featured in a French art film that year, called Last Year in Marienbad, where it makes 3 appearances. At that link, you can see 2 of them via an embedded Flash or downloadable iPod video. The 3rd can be seen on YouTube:



As a matter of fact, to this day, many people refer to multi-pile Misère Nim played with 1, 3, 5, and 7 objects as Marienbad Nim, or simply Marienbad. You can try a Javascript version here, and try a Flash version here.

If you're geeky enough to analyze and enjoy Nim, as well as being geeky enough to enjoy XKCD, you'll probably get a good laugh from this Spiked Math cartoon, which pays tribute to both.

I'd like to hear your comments and criticisms, especially concerning The Secrets of Nim posts, in the comments below!

1

The Secrets of Nim (Part 3)

Published on Thursday, August 05, 2010 in , , , , , , ,

NIM is WIN rotated 180 degrees!(NOTE: Check out the other posts in The Secrets of Nim series.)

At this point, you should have learned and practiced about standard and Misère single-pile Nim, as well as standard multi-pile Nim. Now, we move onto multi-pile Misère Nim.

Trying It Out


Instead of starting with an explanation, I'm going to take a different tack here, and have you try out multi-pile Misère Nim first. Go over to Archimedes' Lab's Nim game. Remember here that, in Misère Nim, the loser is the person who removes the last object.

If you're comfortable analyzing standard multi-pile Nim, as taught in the previous post, try applying those same analytical skills to the Misère version. Ask yourself, what changes in the analysis might be needed to accommodate the new goal?

Winning Moves


Thankfully, Scam School covered multi-pile Misère Nim back in episode 37. You'll notice that this version uses piles of 3, 5, and 7 coins, just like the game analyzed in part 2 of this series, so you'll have an basis for comparison to the standard Nim strategy.

In this video, you'll learn the winning moves, and then I'll go on to explain WHY these are winning moves.



Did you notice anything familiar about the list of winning moves that was shown in this video?

When analyzing safe moves for standard multi-pile Nim, we were able to determine that you wanted to leave the board with the safe positions of 2/4/6, 1/4/5, 1/2/3, or 2 equal rows. Strangely enough, these are also given on the video as safe positions for Misère Nim! What's going on? And what's with the addition of that 1/1/1 arrangement?

The Endgame


The method of working out safe arrangements using binary aren't simply safe because they will always allow you to take the last piece. They're safe because they allow you to keep control of the board for ANY objective.

This is good news, as it means you don't have to learn a whole new system for analyzing multi-pile Misère Nim. Once you've analyzed safe positions for a given standard Nim layout, you can also use that list of positions for the same layout in Misère Nim.

There are differences, of course, but you only have to worry about the differences in the endgame. But what are those differences?

Let's try a very trivial version of multi-pile Misère Nim: There's only one match on the table, the player who takes the last match loses, and it's your turn. Naturally, you lose!

What about the same situation, except with 2 piles, each containing a single match? Well, you take 1 match from 1 pile, I'm left with the other one, and so I lose. 3 single-match piles? You take 1 match, I take 1 match, and you're left with the remaining match, and you lose!

It's not hard to see that, when you're left with an odd number of piles, each consisting of a single match, that you're going to lose the game. This is why the new 1/1/1 arrangement appears on the safe positions list for multi-pile Misère Nim, but not on the one for multi-pile standard Nim.

Technically, 1 match in 1 pile should be mentioned on the list from the Scam School video above, but it's not because, being the object of the game, it's assumed you're already going to remember it.

In a nutshell, there's the approach for multi-pile Misère Nim: Perform an analysis of a given layout to find the possible safe positions for standard Nim (and memorize them!), then add odd single-match piles (1, 1/1/1, 1/1/1/1/1, and so on) as appropriate for the particular layout (for example, if you're starting with 4 piles, obviously only 1 and 1/1/1 are going to apply).

As always, don't forget that if the game starts in an already-safe arrangement, you want the other person to go first. Removing coins from any safe arrangement can only make it unsafe, just as discussed in part 2 of this series.

With this new knowledge, go back to Archimedes' Lab's Nim game and try analyzing the game with this new knowledge. With a little practice, you'll find that you'll start winning every time.

Archimedes' Lab also has a briefer look at the binary analysis of multi-pile Misère Nim that you might enjoy.

If you're using a browser that run Flash, try going back to Nim Master, and playing their Reverse game: Leave last stone to win, using your new-found skills. This is a different layout every time, so you'll mostly be looking for safe positions in binary.

Conclusion


If you've practiced the techniques discussed over this series, you should both be able to win any version of Nim that has been discussed here. You should also be able to create your own customized versions of Nim, such as the Douglas Adams 42 version discussed in part 2.

If you enjoyed this series on Nim, and would like to show your appreciation to Grey Matters while learning more about Nim, there are two books I would like to recommend from Amazon. The first is Nim: Serious Math With a Simple Game, by Christopher M. Freeman. The other is Creating NIM Games, by Sherron Pfeiffer.

Just because these versions of Nim have been analyzed, and are winnable, doesn't mean that there's nothing left to learn about Nim-type games. There's a game called Chomp, which is basically Nim in 2 dimensions simultaneously. It's been around since the early 1970s (the original article mentioned on this page was reprinted as Chapter 9 of Martin Gardner's Knotted Doughnuts and Other Mathematical Amusements), but to this day, remains only partially solved.

Back around 1980, B. M. Rothbart proposed another 2-dimensional version of Nim, in which various numbers of objects are arranged in rows and columns. You can remove as many objects as you like, as long as they only come from the same single column OR the same single row.

Who knows? You may be the one to solve these or similar problems.

I hope you've enjoyed this look at Nim, and found it useful. Please let me hear about anything you've learned, as well as your questions and/or results, in the comments.

0

The Secrets of Nim (Part 2)

Published on Sunday, August 01, 2010 in , , , , ,

NIM is WIN rotated 180 degrees!(NOTE: Check out the other posts in The Secrets of Nim series.)

My previous post discussed the math and logic behind single-pile nim, including several variations. Make sure you read and understand that post before reading this post.

Review and Practice


Obviously, with all the math involved, it's probably not surprising that, as soon as computer started appearing in universities in the 1970s, versions of Nim were right along there.

In the 1978 book BASIC Computer Games by David H. Ahl, several variations of Nim were included.

There was 23 Matches, which is the standard Misère Nim with 23 matches. Very close to this older version is the online version called Nim Skulls (Java required), which uses 15 skulls instead of 23 matches. Try getting the hang of this version, before moving on.

The next version up was usually Batnum, which allowed you to set more options, such as the number of objects, who went first, and whether the person who takes the last object was the winner or the loser. Rediware Software offers an online Nim version very similar to this, except that the computer chooses the number of objects, and it's always Misère Nim (Player who takes the last object loses).

If you practice these versions using what you've learned in my previous post, it shouldn't be too long before you master both of them.

Multi-Pile Nim


Another version in the same book is quite different, however. Simply called Nim, this version deals with multiple rows of objects, and you can take as many objects as you want from any single row (and ONLY one single row) on each turn.

In the late 1970s, one of the most popular versions of multi-pile Nim was a 1978 TRS-80 program called Android Nim. In 1979, it was translated for the Commodore PET computer, and it is this version which is shown below:



Leo Christopherson, who wrote the original TRS-80 version, later wrote an updated version for Windows computers.

If you want to try out Android Nim for yourself, you can either use the version, or one of the older versions with an emulator. If you download a TRS-80 Model 1/III/4/4P emulator from here, you can get the TRS-80 version of Android Nim here.

For the Commodore versions, you can get the VICE Emulator here, and then download the PET version here (Click on "Commodore PET Games" - it's on the very first "disk"), or download the Commodore 64 version here.

But how do you analyze this game in order to win it?

Binary Math


Yes, for multi-pile Nim, we have to use binary numbers (1s and 0s). Don't worry, though, as about 95% of the binary math you'll need can be explained to you in 60 seconds:



To get a clear head about binary, BetterExplained's article on number systems and bases is a great help.

Now, we will need to translate between decimal (our everyday 10-based counting system) and binary. Instead of working it out yourself, the easiest thing will probably be just to use these binary/decimal converters.

Binary Analysis of Nim


Let's look at a game of multi-pile standard Nim that's extremely easy to win. This version involves two piles of the same amount, say 5 objects. If the other person starts by taking all 5 objects from one of the piles, you win by taking the other 5 objects.

What if the other person takes less? If they took, say, 3 objects from one of the piles, leaving 2 objects in that pile, you would simply take 3 objects from the other pile, leaving 2 objects in the other pile. As you can quickly see, all the second player has to do is mirror the first, and he'll be able to take the last object every time.

Let's model this example game in binary:

Row A = 5 = 101
Row B = 5 = 101

When the board starts out, it looks this way in binary coding:

A: 101
B: 101

If the first player takes 3 from row A, he would be leaving 2 in that row. Since 2 = 010 in binary (0s on the left don't mean anything in binary, just as in decimal. Just as 12 and 012 have the same value, so do 10 and 010 in binary), the board would now look like this:

A: 010
B: 101

The 2nd player then does the same thing, so the board looks like this:

A: 010
B: 010

It's not tough to see that mimicking the other player in this particular case will always result in a win for the second player. This isn't always possible with more piles and varying numbers of objects in each pile, however.

Notice something else, though? Every time after the 2nd player made his move, the binary representation was such that there was an even number of 1s in each column (column - as in reading up and down, not across). The board began with row A being 101 (in binary), and row B being 101.

When the first player made their move by removing 3 and leaving 2 on the board, the columns became:

A: 010
B: 101

Now there's an odd number of 1s in each column! Each column has a single 1.

Regardless of the number of piles, when all columns have an even number of 1s in them, that position is considered “safe” for someone who is trying to take the last object. Ultimately, this is the trick to solving any size board of multi-pile standard Nim.

One other handy aspect to note: When a pattern has been made “safe” in this way by one player (or by being the starting pattern), the only possible remaining moves for the other player can only result in the pattern being unsafe. This means that a smart player can always keep the board safe for himself, and dangerous for the other player. Of course, if the board starts in an already-“safe” arrangement, you want the other player to go first.

Let's try using this to solve the Android Nim example above. In this case, row A has 7 objects, row B has 5 objects, and row C has 3 objects. Let's see that same situation in binary:

A: 111 (7)
B: 101 (5)
C: 011 (3)

Analysis becomes easier by making sure that all binary numbers have the same number of digits (since we're looking at columns), which is why I used “011” instead of just “11” for row C.

We start by looking at the columns. There's two 1s in the leftmost column, two 1s in the middle column, but three 1s in the rightmost column. Since there's at least a single column with an odd number of 1s, this opening layout is “unsafe” as is, and an opportunity for a smart player to go first and change it to a safe layout.

Obviously, if the opening layout is safe, then it would be to your advantage to let the other person go first.

How would we do this? Well, since only the rightmost column needs changing, changing from 111(7 in binary) to 110(6) would do it, as would changing 101(5) to 100(4), or 011(3) to 010(2). In this particular case, all we have to do is remove 1 object from any row, and we've made it safe!

Let's say we opt to go first, and take 1 object from row B, so the board now looks like this:

A: 111 (7)
B: 100 (4)
C: 011 (3)

So, let's say the other player removes 5 objects from row A (I'm using an actual game for this example), leaving 2 objects. What does the board look like in binary now?

A: 010 (2)
B: 100 (4)
C: 011 (3)

As stated earlier, the status of the board has been changed from safe to unsafe again. Notice that both the rightmost and leftmost columns have an odd number of 1s (one in both columns, as it happens)? To win, we need to make the board safe again. There aren't that many ways to do this, so it seems like row B (working with the row with largest amount is often a good starting point for this type of analysis) would be changed. We need to get rid of the 1 in the leftmost column and add a 1 in the rightmost column.

So, we need to change row B from 100(4) to 001(1). So, our next move is to remove 3 objects from row B, giving us this safe arrangement (the middle and rightmost column now have two 1s each, while the leftmost column has none):

A: 010 (2)
B: 001 (1)
C: 011 (3)

In the game I'm using for this example, the other person then took 2 objects from row C, leaving 1 object and giving us this unsafe arrangement (can you see why?):

A: 010 (2)
B: 001 (1)
C: 001 (1)

The only way to make this safe is to remove 2 objects from row A, the reasoning for which you should understand by now:

A: 000 (0)
B: 001 (1)
C: 001 (1)

It should now be obvious that the other player cannot win. They have to take the remaining object from either pile, and leaving the remaining object.

When you're always playing with the same arrangement, such as this 3, 5, and 7 arrangement, you can use this technique to analyze all the possible boards and, thanks to the memory systems you can learn from here, remember them for play.

The total number of cases for any arrangement, is the one greater than the total number of objects in each row (to account for the possibility of no objects in a row) multiplied together. In our 3, 5, and 7 arrangement, there's only 192 (8 * 6 * 4) possible arrangements to examine.

Also in that particular case, it turns out that the possible safe arrangements are small enough to remember. The first move should always be to remove 1 object from any row, and then to play to leave either rows of 2/4/6 (in any order), 1/4/5, 1/2/3, or 2 equal piles (which is easy to win, as discussed earlier).

The ease of winning standard Nim with a pair of equal piles also apples to more than 2 or more paired rows. Let's say you've left 4 piles on the board, 2 of which contain 3 objects each, and the other 2 piles contain 8 objects each (obivously, this started out as a very large game). You can easily see that the same mirroring strategy could be applied here.

For larger arrangements, you'd need a computer analysis to generate every possible safe state in which to leave the board. This game is usually played with 3, 5, and 7 precisely because the safe arrangements are few, and easy to memorize.

Review and Practice


Your homework? Go over to 21st Nim (Java required), and practice playing the game, starting with 2 piles (working eventually up to as many as you think you can handle), and win them using the analysis techniques you've learned here (don't forget to keep your binary/decimal converter handy).

If you're browsing with a browser that uses Flash, the 5-row Nim Master is a decent analytical challenge, as well. Make sure to choose “Normal Game: Take last stone to win”, so that you're analyzing the correct game.

Part 3 of the Secrets of Nim series will explore the unusual and surprising nature of multi-pile Misère Nim (the person who takes the last object loses).