The Computer Made of Nothing but Plastic and Marbles

The confounding logic of Dr. NIM.

|
Apr 28 2015, 7:10pm

The game board for Dr. NIM.

​"Hey, Jesse, do you want to see a really old computer?" my father asked, carrying a thin, rectangular box into the living room.

My 9-year-old self reacted predictably: bubbling with excitement, I scooted over to see what he'd brought.

He slid out a red plastic tray studded with five strangely shaped white flippers, then dumped 15 marbles into a track running along the top. "It's a computer game!" he declared.

I stared blankly back and forth from the assembly of cheap plastic to its tattered cardboard box. The box proclaimed itself "The Amazing Dr. NIM," but so far I was unimpressed. "How the heck is this a computer?"

Dr. NIM works like this: two players take turns releasing one, two, or three marbles at a time. Whoever gets stuck with the last marble loses. The twist? One of the players is the board itself.

Playing against a hunk of plastic isn't quite as absurd a suggestion as it sounds; the board does have a means of making moves.

Each time a marble entered the board, it falls through a series of flippers, flipping them back and forth:

One of the flippers indicates whose turn it is. When I was done with my turn, I would push this flipper to "Dr. NIM" and press the release lever. Dr. NIM only needs you to press the release lever once; the path of its first marble will determine whether it releases more. When one of the marbles knocks the turn flipper back, it means the computer is finished.

I played a few games, and sure enough, Dr. NIM walloped me every time. I chafed at the losses, infuriated. If this were a real computer, with a power button and a monitor, I could fathom someone programming it to win. But how could I keep losing to a bunch of plastic flippers?

A simple strategy

I confess that I did not figure out Dr. NIM's strategy myself. Skimming through webpages full of flashing GIFs and purple text (these were the early days of the internet), I learned that the winning strategy for this game—the ancient game of Nim—was far simpler than I'd assumed. If you'd like to figure it out for yourself, I suggest you go play a few rounds here, because I'm about to ruin it for you.

Ready? The strategy is this: subtract one from the number of marbles left, and divide by four. The remainder is the number of marbles you should take. (If that comes out to zero, just take one marble.) That's all it took for Dr. NIM to beat me.

Why this strategy works could fill a whole separate article. The basic reasoning is that whenever your turn ends, you leave a number of marbles from which you can force a win: if you leave one marble, the other player must take it; if you leave five, you can always get to one on your next turn; and so on for 9, 13, and beyond.

But for me, knowing the strategy just opened up a slew of more pressing questions: how did Dr. NIM know how many marbles were left? How could it calculate how many to release? Could the old bastard count?​

How does plastic compute? Just like silicon!

Clearly, Dr. NIM can count, or it couldn't possibly follow that strategy. This is precisely what makes its performance so puzzling—because the computers we generally interact with are electronic, we have a powerful intuition that calculation outside of brains requires silicon. But Dr. NIM has no silicon parts at all.

So if silicon isn't the secret to being a computer, what is? What does a flipper-strewn plastic board share with your laptop?

To answer, let's consider what your computer actually does. Say you hit the "save" button in PowerPoint. The first thing your computer must do is notice the click. It also has to know what information it's supposed to be saving (your presentation). And based on those two things, it has to transform all those fancy graphics into a compact file on your disk.

That simple process highlights the three fundamental operations that every computer needs to perform:

  1. Take in input (for example, mouse clicks).
  2. Remember some information (for example, the contents of a presentation).
  3. Produce some output based on the inputs and memory (for example, save a PPT file). This is where the actual calculation happens—what we normally think of as a computer's job.

Although a desktop computer uses circuits for all three, there's no reason they can't be done in other ways. Dr. NIM implements all three components using nothing but plastic and marbles.

Images: OpenClipArt, Wikipedia,Wikimedia.


Input

The inputs are simple. The player sets up the initial flipper configuration, and on each turn, the player inputs some number of marbles (using the release lever) and sets the turn flipper.

Memory

Dr. NIM's memory is slightly less intuitive, partly because what it's remembering is a bit subtle. On each turn, all the strategy requires Dr. NIM to know is how many marbles remain. But that's actually more information than it needs: three marbles left is the same as seven or 11, because in all those cases it should take two marbles: one, five, and nine are all winning numbers to leave. What really matters is how many marbles away the next winning number is. And since winning numbers come four marbles apart, all it has to remember is how many marbles have been taken since the last set of four was complete!

This is precisely what Dr. NIM remembers—but instead of storing it on a RAM chip, Dr. NIM uses its top row of plastic flippers.

Consider the board in its starting configuration:

As the first marble drops, it'll fall through the rightmost flipper, flattening it out:

The second marble knocks the leftmost flipper upward:

The third marble then falls between the leftmost two flippers:

And finally, the fourth marble falls between the second and third flippers, leaving the board right back where it started. Each position in the sequence of four has a unique configuration, allowing Dr. NIM to "remember" which position it's in.

Computing Output

So Dr. NIM can repeatedly count to four. But that still leaves it with the task of producing its output—a choice to take or not take another marble. Its creators "programmed" it to do this by carefully crafting the plastic tracks underneath the top row of flippers. These tracks direct the falling marble so that it will press the release lever only when its "memory" is in the second or third of the configurations above. If the board was set up correctly, this guarantees that Dr. NIM only takes another marble at the correct positions in the sequence.

It seems that my dad was dead on when he called Dr. NIM a computer. It's earned its place in the Computer History Museum in California.

Beyond Nim

Of course, we need not stop at Nim-playing toys. Dr. NIM was invented in the 1960s, and non-electronic computers have come a long way since then. Some French graduate students recently built a mechanical computer out of LEGOs, and a calculator made of 10,000 dominos was demonstrated at the 2012 Manchester Science Festival. More practically, much hay has been made of quantum computers, which use the weird physics that governs tiny particles to speed up difficult calculations. Perhaps most exciting of all is the development of biocomputers—systems that employ biological molecules, such as DNA, to store and manipulate information.

Despite my initial incredulity at Dr. NIM, I've come to love the idea that computation can happen anywhere. Now, whenever I look at a new gadget, I like to think about what it might be calculating—you never know when there's a computer hiding behind the face of even the simplest-looking toy.

This article was prepared in collaboration with Science Non-Fiction, a graduate student science blog run by Public Communication for Researchers at Carnegie Mellon University.