March 12, 2007 8:25 PM |
["Beyond Tetris" is a column from Tony "Tablesaw" Delgado about puzzle games that transcend mere abstract action and instead plunge deep into the heart of problem-solving. This installment looks at an old and widely reviled videogame cliché: the Tower of Hanoi.]
I think it's safe to assume that anyone reading this blog has played a fair share of videogames. It is therefore safe to assume that you have seen the Tower of Hanoi at least once. And I'd also wager good money that you're sick of it. Frankly, I'm sick of it. I play too many puzzle and adventure games to have to deal with hoary mechanical exercises like this. But it does have an interesting history, which may give you some perspective on how it came to be such a cliché.
The End of the World as We Know It
In 1882, a mechanical puzzle appeared in Paris called "La Tour D'Hanoï," or "The Tower of Hanoi." It had three pegs, eight disks, and an instruction booklet telling of the game's history in China, Japan and Tonkin (northern Vietnam), where the disks were porcelain instead of wood. (An English translation by Paul K. Stockmeyer is available.) It also included the legend of "Indian Brahmins" who played the game with sixty-four disks of gold, in the belief that when the tower is completely moved, the universe will end.
All of this was a lie, or at the very leastmisleading advertising. The credited inventor "Professor N. Claus (De Siam)" was merely a pseudonym for "E. Lucas (D'Amiens)," the mathemetician Édouard Lucas. Previously, he had developed a method that could be used to verify if Mersenne numbers were prime, and in 1876, he verified that 2127-1 was prime. (This number would be the largest known prime until 1951 and the age of computers). In 1880, he published the solution to the Baguenaudier or Chinese Rings puzzle. Both of these achievements will be important.
The Tower of Hanoi was a relatively popular mathematical curiosity; it was reproduced many times under different names (as can be seen in this collection at James Dalgety's Puzzle Museum). It also appeared outside of a physical form. Sam Loyd discussed the Tower in his Cyclopedia of Puzzles in 1914. It was mentioned in Martin Gardner's Scientific American column in 1957, and in Eric Frank Russell's science-fiction story "Now Inhale" in 1959. But these textual appearances weren't related to actually carrying out the mechanics of the puzzle, instead, they focused on the surprising math behind the device.
The original French instruction booklet aims at giving players a look at how exponents work, specifically powers of two. The Tower of Hanoi is a very compact device, even as the number of disks increases. But the number of moves required for each grows massive quickly. In fact, the sixty-four–disk tower described in the "legend" is revealed to require 18,446,744,073,709,551,615 moves, which would take, as noted by Lucas, more than five billion centuries. To help explain why, Lucas includes a chart of the minimum moves required for different disks: for 2 disks, it would take 3 moves; for 3 disks, 7 moves; for 4 disks, 15 moves; all the way up to 8 disks requiring 255 moves.
To the modern computer-savvy individual, that last pair should look familiar; in the age of bits and bytes, binary numbers are much more commonly recognizable. And in fact, the minimum number of moves for the Tower of Hanoi with n disks is 2n-1, which is also the maximum decimal value of an n-digit binary number. So, the Tower of Hanoi replicates the Mersenne numbers that Lucas had been studying. Understanding the link between the mechanical movements of the Tower and the powers of two was the main point of the exercise; and the process of mechanically moving the disks (which includes moving the disks in more or less the same order, doubling the amount of work for every added level) gave solvers a way to see how the process worked.
Specifically, the Tower of Hanoi models a reflected binary code, also known as a Gray Code. In a Gray code, only one binary digit is changed from one number to the next. Moreover, if you look at a list of Gray code numbers (like the ones on the Wikipedia page), you'll see that all of the digits in the first are reflected in the second half of the list. (Imagine folding the list over in half, and the ones and zeroes will match up.) Because of the way the Tower of Hanoi requires duplicating your work, the reflective nature of the Gray code is a map to solving. Look again at the solution for a four-disk Tower at Mathworld, and compare it to the four-bit Gray code at Wikipedia. The number in the solution is the same as the position of the digit that changes in the Gray code.
Gray codes are used in many scientific fields, but they're also the basis for several puzzles, including Spin Out and The Brain Puzzler. It's also the basis of the Baguenaudier puzzle that Lucas had solved a few years before. But as Jaap Scherphuis notes, the puzzles are all very simple. "In any position there are at most two possible moves, the equivalent of going up or down the list of Gray code numbers. If you never take back a move, you will always go on until you reach the end/beginning of the list."
After all of this, we've discovered that the mathematical interest behind the Tower of Hanoi make it unpleasant to actually complete; the only "interesting" move is the first one. So how come it's everywhere?
Death by Computer
In addition to the mathematical intricacies noted above, the solving of the Tower of Hanoi has some interesting things to say about an important aspect of computer programming: recursion. So the Tower of Hanoi went from being a mathematical curiosity to a programming exercise. Miroslav Kolar has a page that deals extensively with solving algorithms for the Tower of Hanoi, and Amit Singh has a simliar, but less serious collection. Jack Beidler, a CS professor at the University of Scranton, has a page showing how the recursive algorithm works in simpler terms. This explains how the mathematical curiosity was introduced to the new computer programmers, and why, to this day, there remain far too many small stand-alone programs that replicate the puzzle.
I don't know precisely when the Tower made the jump from computing class assignment to videogame, but the most notable implementation was in Zork Zero: The Revenge of Megaboz in 1988. In the '90s, it appeared in the kid-oriented educational puzzlers The Island of Doctor Brain and The Secret Island of Dr. Quandry. It also appeared in the adventure game The Legend of Kyrandia: Hand of Fate and in the role-playing game Ultima VIII: Pagan. Things started getting weirder when it showed up in the god game Black and White. And I don't even want to count the number of second-rate text and graphic adventure games where it shows up (and I did consider trying). Of course, before all of these, a Tower solver was written for the word-processing
game program Emacs.
One of the most egregious examples was in Star Wars: Knights of the Old Republic where a four disk Tower was made needlessly tiresome by a difficult-to-understand menu and penalties id you accidentally put a large disk on top of a smaller one. It inspired Peterb to write at Tea Leaves that the Tower of Hanoi was the "lava level" of puzzles:
If Towers of Hanoi is in your game, you should just eliminate it and instead put a big sign in your environment that reads "I am completely out of ideas." Word to the wise: if Emacs ships with a module that solves the puzzle you're putting in your game, that's a good sign that the puzzle isn't actually any fun. So am I saying that it's never legitimate to include a classic oldie like Towers of Hanoi in your game? Well, yes. I am.And I must agree. As I said in my introduction, I'm pretty sure that you've solved the Tower of Hanoi at some point in your gaming life. But I also imagine that most of the stuff in this article—the mathemetical surprises that make the Tower interesting—are new to you. Because unlike Lucas's original puzzle, the videogame implementations don't encourage you to learn anything; they're just gruntwork to click through. Hopefully, now, the next time you see the it hamfistedly hacked into a videogame, you won't hate the Tower of Hanoi, you'll merely hate the game designer who didn't understand why it isn't fun to play.
[Tony Delgado is a member of the National Puzzlers' League, and a solver and creater of puzzles of all sorts. He also works as the copy chief of The Gamer's Quarter, which just published its eighth issue.]
Categories: Column: Beyond Tetris