An Optimum Combination

Michael P. McLaughlin

I never thought that I would ever write a computer game. I am a scientist, and our attention is typically focused elsewhere. Still, problems do arise, sometimes computational problems and, every once in a while, the solution technique proves as interesting as the original task.

My task, on this occasion, was to find the best arrangement of a large number of objects where “best” was defined by a complicated mathematical function, a long story for another time. Such a task falls under the heading of combinatorial optimization.

An example of combinatorial optimization is the famous problem of placing eight queens on a chessboard so that none of them can capture any other (ignoring colors). If you think this is easy, then go ahead and try it. Seven is easy; eight is not.

Arranging eight objects is just a toy problem. Imagine accomplishing the same thing with thousands of objects. Any algorithm that can do that is a real winner. Simulated annealing (SA) is just such an algorithm and I was so impressed with it that I decided to create a demonstration of SA in the form of a computer game called Poker Solitaire Challenge (PSC). PSC was written several years ago for Macintosh Ô computers and, although in desperate need of updating (I'm working on it!), is downloaded frequently even today.

The game begins with a 5 x 5 tableau of random playing cards (Fig. 1).

Figure 1. An initial poker solitaire tableau.

In the default “Amateur” mode, the five rows and five columns are each considered to be a hand of straight poker, with a score assigned to each according to the strength of the hand (Table 1). In “Expert” mode, the two diagonals are considered to be two additional hands. The task, of course, is to maximize the total score.

Table 1. PSC Scoring

The “challenge” in Poker Solitaire Challenge is that, while you are playing this game, the computer is secretly playing the same tableau in the background. Once you finish, or give up, you can see the computer's solution. Beating the computer is almost impossible, all because of simulated annealing which I described in the documentation, in a section entitled...

You have to hold your hands just right—palms down, fingers curled towards you, with the glass tubes resting lightly on your fingers and only your thumb and index finger for rotating and manipulating. The leftmost end is fused closed and the rightmost capped with a rubber tube that goes to your mouth, a high-tech hookah in the interests of science. That's the easy part.

Borosilicate (Pyrex™) glass does not melt very readily. An ordinary Bunsen-burner flame will not even soften it; you need a hotter flame, with its own oxygen supply. For this reason, Pyrex glass is ubiquitous in laboratories all over the world. Test tubes, beakers, flasks and condensers are, almost without exception, fabricated from this special kind of glass. On the other hand, it is glass and, as a graduate student in organic chemistry, I had ample opportunity to experience that singular weakness common to all objects made of glass. They break.

At the University of Massachusetts (Amherst ), there were a lot of graduate students in the chemistry department. Consequently, the glassblowing course, an unofficial, noncredit class offered by our in-house cadre of professionals, was very popular. You had to sign up for it months in advance. There, under the watchful, if disdainful, eye of the instructor, we amateurs would don our blue spectacles (without which superheated glass is just a glare of sodium light) and prod, bend, twist, and puff our little pieces of tubing into something resembling a useful piece of equipment that we could take back to the lab as our very own.

Almost.

There was always one final step that we could not do ourselves. Even though, strictly speaking, glass is a liquid, as opposed to a crystalline solid, the atoms still objected to being contorted into the shapes that we forced upon them. Their displeasure took the form of excess potential energy. That is, they were too “hot,” making the glass object half-broken, in a sense, and just waiting for the slightest bump against a support or table to finish the job. After expending so much effort, we were loath to grant them this last laugh, and so the trick was to allow the atoms to release their extra energy in a harmless fashion. The technical term for this trick is annealing .

Our fragile creations were annealed in a large oven. The temperature of this oven was raised ever so slowly to a point such that the glass was extremely hot but not quite hot enough to become deformed. At this stage, all of the atoms in the glass had much more energy than normal and could use this energy to adjust their position, relative to neighboring atoms, thus releasing any stresses due to the strains of manufacture. Then, the temperature was slowly lowered again, gradually freezing the atoms in place and giving them the opportunity to find their optimum positions, minimizing their potential energy under ambient conditions.

Annealing is a very common procedure, usually carried out with objects fabricated from glass or metal. These objects are strengthened considerably in the process.

Which brings us to the game of Poker Solitaire Challenge.

If you have tried this little demo and checked your result against the computer's, then you probably lost. The game is a lot harder than it looks. Ignoring symmetry, the 5 x 5 tableau has 25! (15,511,210,043,330,985,984,000,000) possible configurations. If a computer could evaluate a thousand configurations per second, without repetition, it would take about 4.9 x 10¹⁴ years (approximately the age of the Universe) to try them all and find the best score.

Fortunately, nobody cares. However, there are a lot of similar optimizations about which people do care. Designing the best arrangement for the components of a microprocessor is an obvious example. Determining the best DNA sequence for a chromosome based upon a set of overlapping gene fragments is another. Finding the best match between the 3-D structure of a protein molecule and its X-ray diffraction pattern is a continuous analogue. In fact, the whole area of nonlinear optimization compasses much of what is often categorized as applied mathematics.

The general statement of the problem is easy: Given a set of “elements” and an associated objective function measuring some quantity of interest, determine “values” for the elements that maximize (or minimize) the objective function. In other words, find the best score.

In general, this is very difficult. Indeed, with large problems, it is often impossible.

Mark Twain once said, “The difference between the right word and the almost-right word is the difference between seeing lightning and just hearing about it.” This is not always true of optimizations. Sometimes, the global optimum may not be absolutely necessary. Frequently, especially with very large problems (many elements), the practical difference between the best solution and the second or third best, for instance, may be so small that the effort required to improve on the latter is not worth the incremental cost. If so, then a technique that guarantees to find a solution close to optimal might be sufficient, especially if that technique is generic, that is, applicable to any optimization problem. One such technique is simulated annealing (SA) .

To understand how and why SA works, you must appreciate the process of physical annealing, described above, and the realization, now commonplace in science, that what seems initially to be a metaphor is, very often, a model of Nature.

Consider, for example, the initial tableau of cards in PSC. The starting score is suboptimal because the starting configuration is random and there are a lot more bad configurations than good ones. If you think of the cards as atoms in a piece of glass, then this “suboptimalness” could be treated as a stress relative to the global optimum. When glass is properly annealed, the atoms end up with minimal potential energy. When the 25 cards are optimally arranged, they also exhibit minimal “potential energy” in the sense that they are where they would like to be, notwithstanding the fact that the latter is now defined by an objective (scoring) function rather than by some physical law. The principle is the same and the analogy holds.

To implement SA along these lines, we need definitions for “potential energy” and “temperature” consistent with the intended application. In the physical world of statistical mechanics, the relevant relationship is the Boltzmann distribution, a simplified version of which is shown in Eq.1.

In this equation, N hi and N lo are the numbers of atoms found in a high (or low) energy level at some absolute temperature, T, on the Kelvin scale. The respective energies are E hi and E lo and k is a constant, known as Boltzmann's constant .

There are infinitely many energy levels available to the atoms of any object/substance, at any temperature. The atoms populate these levels in accordance with the Boltzmann distribution, provided only that the system is in thermal equilibrium with its surroundings. What this means is that the relative probability of finding any atom at energy E hi rather than E lo is given by the right-hand-side of Eq. 1. Since E, T, and k are all positive numbers, this relative probability decreases as the energy difference increases and as the temperature decreases. Moreover, the lower the temperature, the faster this probability decreases.

Consequently, at high temperatures, the atoms can populate lots of different energy levels. They have no trouble at all jumping up to energies that would be nearly unreachable at room temperature. With so much energy, the atoms can do a lot of hard work. They can reposition themselves, for instance. At low temperatures, with just a little energy, they can move about just a little bit.

The atoms of any object in an annealing oven at high temperature are moving randomly and they are so hot that they do not care very much where they are. However, by the time the oven cools down to room temperature, they have shed all of their excess energy and have nestled into their optimum positions. Like gravity, it happens automatically. With an optimization problem, the situation is analogous and PSC provides an excellent demonstration.

The key to simulated annealing is the term “relative probability.” When you modify a PSC tableau, you usually get a different score, especially if you modify it randomly. If the cards were atoms and high scores corresponded to low energies, the Boltzmann distribution would dictate the relative probability of the two scores. At high temperature, a worse configuration might still be acceptable (i.e., of reasonable relative probability) even though some other configuration had a better score. At low temperature, the best score would be, by far, the most probable (see Eq. 1).

We can follow Nature's lead and turn these observations into an algorithm for finding the best score. In principle, all we have to do is to reconfigure the tableau randomly and repeatedly, accepting a new configuration only when i) it is better than the current one or ii) when its probability is consistent with the Boltzmann distribution at the current “temperature.” Here, “accept” means to move to the new configuration and forget the current configuration unless it is the best one found so far, in which case it is recorded separately.

In mathematical terms, a worse configuration is accepted with a probability given by Equation 2, where S is a score and T is an algorithmic variable corresponding to temperature.

Simulated annealing is a stochastic technique. Even if you know the two scores and the temperature, that alone does not tell you whether a new, worse configuration should be accepted. Every time you have to make such a decision, you have to “flip a coin.” To do this, compute the acceptance probability, P, using Eq. 2. Then, generate a random number, x, uniform in the interval (0, 1) and accept the worse configuration/score if and only if x < P . Doing this consistently, as T decreases, is the essence of SA.

Of course, as with all algorithms, there are a number of minor but crucial details such as picking a starting temperature, deciding when to decrease the temperature and by how much, etc. If you are interested, check out the References below.

OK, so maybe it doesn't always win…but, then, maybe it does when you play.

While you are looking around for a better arrangement, the computer is carrying out SA on the same tableau. It starts thinking as soon as you make your first move. If you play with a single tableau for more than about five minutes, the computer will have converged to its best result and will start from scratch all over again, continuing in this fashion until you give up.

Since SA is a stochastic technique, it does not find the best answer every time. In fact, although the annealing subroutine incorporated into PSC is almost totally adaptive, the few SA parameters that are hardwired into the code are deliberately suboptimal in order to make the computer converge faster than it normally would with this algorithm. Therefore, it is possible to beat the computer, but it is very, very difficult, especially at the Expert level.

You might suppose that this is simply because the computer is much faster than you are, but, in fact, computation speed has almost nothing to do with it. The computer reconfigures the tableau randomly and it hardly ever finds a better score or, at low temperature, even a new, acceptable score. The real reason that the computer always wins is that simulated annealing works a lot better than the technique that humans tend to use.

If you watch humans play PSC, you will notice that they never accept a new tableau unless it is better than their current tableau. In computer science, such a technique is referred to as a greedy algorithm , for the obvious reason. What is not so obvious is that, unless the configuration space is very smooth, greedy algorithms have virtually no chance of beating an algorithm that can go backwards, such as SA. In order for a configuration space to be smooth enough for a greedy algorithm to work well, it must be true that i) a tiny perturbation of the configuration always results in a tiny change in score and ii) there are no local optima (traps). If a small perturbation can sometimes cause a large change in score, the space is said to be rough and greedy algorithms will then tend to skip over avenues of investigation that often lead to the global optimum. If there are local optima, then greedy algorithms will get permanently stuck in them and never have a chance to find the global optimum. PSC is an example of a very small (size = 25) problem with an extremely rough configuration space and millions of local optima.

If a greedy algorithm converges fast enough, then you could apply it many times, with random starting configurations, and then pick the best result while SA is converging just once. With PSC, however, even this approach is not competitive. On average, SA still wins easily (see Fig. 2).

Figure 2. Computer's final score (10 hands) = 210

Summary

Poker Solitaire Challenge is just a game, a toy problem of no particular significance. However, it does furnish a very difficult combinatorial optimization despite its small size. It also gives us the opportunity to observe the power of a stochastic algorithm based on a model from the world of quantum mechanics. For computer science, this is an unusual source of inspiration. Most computer algorithms are drawn from the results of mathematics, not from physics.

That simulated annealing works so well is due largely to the validity of the annealing model and the Boltzmann distribution upon which it is founded. That a stochastic algorithm works so much better than the deterministic methodology seen when humans play PSC is also of great interest. Clearly, there are a number of lessons to be learned here.

Simulated annealing is not the only technique that might be applied to combinatorial optimization. Nevertheless, it is intuitive and easy to understand. Moreover, it is applicable to virtually any optimization with relatively little modification. More details are provided in the References.

References

Simulated Annealing @ Wikipedia

Press, William H., et al., Numerical Recipes in C, Cambridge University Press, New York , NY , p. 444 (1992).

McLaughlin, Michael P., “The Art of Simulated Annealing,” Algorithm 3, 16 (October 1992).

McLaughlin, Michael P., “Simulated Annealing,” Dr. Dobb's Journal 14, 26 (September 1989).