Towers of Hanoi
Inspired by this FiveThirtyEight Riddler problem.
The setup: we have three pegs and N rings of increasing size, and our goal is to restack all the rings on another peg, one at a time, without ever stacking a larger ring on a smaller one.
Suppose we approach this game blindly, choosing a random legal move at each turn. What's the expected number of moves we have to make before we succeed?
Let's play a bunch of games.
First, set the number of rings and the number of times we play the game. We'll save all our results as samples.
If you choose 5 or more rings, I recommend you set the number of trials lower by orders of magnitude. (e.g. at most 100 for 8). You can check the console to see the progress.
| Number of rings | Number of trials |
Click "start" to collect your samples!
With these samples, let's get a bootstrapped estimate of the variance.
Set the bootstrapping parameters below:
| Number of samples | Sample size |
Click "Bootstrap" to estimate the variance!
Finally, let's visualize a random walk.
Deriving the expected value relies beautifully on the fractal-like structure of the Markov decision graph (and a little intuition for circuits!). Let's observe how we walk from node to node as we simulate a random set of moves with 2 rings. Notice that our goal is to reach the bottom two vertices, so take note of when we hit that.
If you understand circuits, something that might jog your inuition: when there are multiple paths from one node to another, wouldn't you get there faster? Does that remind you intuitively of...equivalent resistance?
Credit again to Alekseyev & Berger (2014), though one of the states is redundant! Can you catch which one?