Info-Gap Decision Theory | Voodoo Decision-Making | Robust Decisions | Severe Uncertainty | Satisficing vs Optimizing | Maximin


Towers of Hanoi

A very interesting and educationally rich puzzle. I regard it as a very good framework for describing how DP works. In fact, in my DP book I publicly declared that this is, in my mind, the Mother of all DP examples.

It is a pity that this treasure is not as popular in the official OR/MS literature as it is in the computer science literature where it is often used as a prime example to illustrate recursions.

In any case, in a an old paper, I discussed this games from an OR/MS point of view and explained how it can be solved by DP. The paper also describes a simple non-recursive solution to the problem, and there is an online interactive module for experimentation with the game.

Interestingly, in the framework of the traditional version of the problem the objective is to minimize the number of moves required to move the pieces from one platform to another (there are 2n-1 such moves). This is not very consistent with the original formulation of the problem according to which the End of the Universe will come when the task is completed.

In my paper I develop a new version of the problem involving the maximization of the number of moves. In this case the optimal solution requires 3n-1 moves.

The module animating the solutions to these two versions of the problem is an excellent tool for illustrating the difference between a 2n and a 3n complexity!

In any case, I highly recommend this paper to lectures teaching OR/MS and/or CS subjects dealing with algorithms.

An online implementation of the game is available on the front page of my site.



Disclaimer: This page, its contents and style, are the responsibility of the author (Moshe Sniedovich) and do not represent the views, policies or opinions of The University of Melbourne.