I have to get a set of Towers of Hanoi now!
Some of my CS professors had wooden Towers of Hanoi in their offices. These are used to demonstrate a cool process (usually described recursively) to move a stack of different-sized discs from one place to another. The stack starts off with the largest disc on the bottom, with successively smaller discs all the way up. At each step of the moving process, no discs are allowed to be placed on discs smaller than themselves. While moving the stack from one location to the next, you are only allowed to use one other place to stack, besides the start and ending places.
No matter how high the stack of discs begins, you are always able to move the discs, one at a time, to shift the stack at the destination.
Cool problems like this are often the best inspiration for new combinatorial games, and the Towers of Hanoi are no different! The result is the game Hanoi Stick-up. (Does anyone know who created this game?)
In this game, all discs start off on their own separate stack. A move consists of moving one stack on top of another; the whole thing, not just one disc. The bottom disc on the stack being moved must still be placed on top of a larger disc. Under normal play, you lose the game if you cannot move a stack on top of another.
Hanoi Stick-up is an impartial game, since both players can move whichever discs they like. This is a game with very simple rules, but it misses one of the main concepts of the Towers by allowing players to move more than one disc in a turn. However, trying to enforce doesn't lead to an interesting game; both players will just move the same disc back and forth without going anywhere. If you're going to lose the game, you can instead just undo the last move. In Hanoi Stick-up, you have to combine two stacks together each turn. Perhaps a partisan game with a coloring of the discs could lead to something more "traditional".
On a less relevant, but cool note, Andy posted about WittCon from this past weekend! Bonus!
Jokes from the Audience
3 days ago
My recollection is that this game (and many variants) was "in the air" at the first combinatorial game meeting at BIRS. Certainly JHC was very interested in it, and a student of RGs, whose name unfortunately escapes me, was also.
ReplyDeleteI subsequently looked at a different game -- played with the traditional Hanoi configuration, where each player is to make a single allowed move subject to never repeating a position, nor making it impossible to reach the goal. Game ends when the goal position is achieved. This analyses (in terms of who wins) quite nicely and recursively as you'd expect, and I actually gave a talk about it at a conference in Brisbane. If I can dig out the slides (several computers ago ...) I'll send you a set.
See also: http://arxiv.org/abs/1503.03345
ReplyDelete