Thursday, December 29, 2005

Evil little puzzles

-complicating a simple problem with biggish words like metastable state, control input, activation energy and domain.

Most of us would probably have seen some of those little clear puzzle boxes in our lives. Housed within the little cube would invariably be a collection of little chrome spheres and an ‘environment’ for the spheres to move in.

Often, solution of the puzzle comes when the spheres are put into some specific locations in the environment. A typical puzzle might have a surface with dimples in it, and the spheres would have to be manoeuvred into the dimples.

The states (location) of each ball can be described using two orthogonal directions parallel to the main plane of the environment, and the height of the ball is the gravitational potential energy of the ball. As one can imagine, a ball’s gravitational potential energy is a function of the location of the ball, with the domain being the area bounded by the plastic box.

This particular problem requires that the balls be placed in the holes around the big hole. A brief inspection of the environment will show that the target holes are not as deep as the central trap, which implies that the global minima of the potential energy function lies within the central trap. Each of the target holes are a local minima, which means that a ball within the target is merely in a metastable state. Jerk it hard enough (give it enough activation energy) and it might roll out of the metastable state into the global minimum.

The difficulty is that there are many balls, and it is very possible that there will be one or two within the central trap at any one time. To relocate the balls away from the central trap, one would need to give it sufficient energy to jump out of the potential well. Unfortunately, this energy will also be supplied to the other balls, and they might jump out of their metastable target holes, and in turn drop into the central trap.

Control of the system is done by manipulating the box. There are 6 degrees of freedom in the control inputs: translation in 3 directions and rotation in 3 directions. However, the system itself has far more than 6 degrees of freedom (each ball can move independently of other balls), even if we neglect spin and potential energy of the balls. In short, it is impossible to deterministically control the system using the 6 control inputs- solution of the puzzle appears to be merely a probabilistic event.

Having noted a few characteristics (metastable state, global minima, activation energy, controllability) that contribute to the difficulty of these puzzles, we can go on to design harder and harder puzzles.

Of course we want the solution to be a metastable state. Once arrived at the solution, the balls should stay where they are unless jerked out of place. If the solution is in the global minima, the puzzle is almost trivial, which makes it less of a puzzle.

To make life difficult for the player, the global minima can be made to be very low compared to the metastable states. This would imply that sending a ball from the global minima to a metastable state requires a big bump, potentially disturbing other balls in the system.

Also, to make balls in the target metastable states easy to accidentally dislodge, the activation energy required to jump out of the metastable state can be made very small. This being the case, any small disturbance might easily remove the ball from its desired position.

Finally, use many balls to ensure that the 6 control inputs cannot fully account for all the balls’ behaviour.

If these concepts are taken too far, the puzzle will be impossible to solve in a reasonable time. Try shaking a room to try getting all 6 x 10^23 molecules of air to one corner of the room.

Labels: ,