The Fix That Changed the Success Rate Far More Than the Cost

Eight queens, one per column, and a state is the eight rows they sit on. The cost of a state is the number of attacking pairs. Steepest-ascent hill climbing looks at all $8 \times 7 = 56$ single-queen moves, takes the best one (a random one of the best, on a tie), and stops when nothing is better.

From 2,000 random starts it solves 14.75% of them, 295 runs, in 4.1 steps when it wins and 3.1 steps before it gets stuck.

A. The standard fix

It gets stuck because the landscape has plateaus: whole regions where every available move leaves the cost exactly where it is. The usual remedy is to allow sideways moves, up to some limit, on the theory that a plateau might be a shoulder with more descent on the other side.

Allow a hundred consecutive sideways moves and the same 2,000 starts give

$$94.55\% \text{ solved}, \qquad 19.5 \text{ steps on success}, \qquad 63.6 \text{ on failure}.$$

A success rate that goes from 14.75% to 94.55% is the kind of number a change gets adopted on.

B. What it costs to actually get an answer

Hill climbing is cheap and restartable, so nobody runs it once. The quantity that matters is the expected work until a solution appears:

$$\mathbb{E}[\text{steps}] = \frac{1 - p}{p}\,\mathbb{E}[\text{steps} \mid \text{fail}] + \mathbb{E}[\text{steps} \mid \text{succeed}].$$

The inputs are printed to two decimals because the formula needs them: from these columns it reproduces every total to the digit shown, and from the same inputs rounded to one decimal the second row would come out as 23.2.

The plain version fails about six times out of seven, but it fails in 3.1 steps and costs 21.9 steps overall. The improved version succeeds almost always, takes 19.5 steps to do it, and costs 23.1 overall. Counted in steps, the six-fold rise in success rate is worth, on this problem, slightly less than nothing.

It is not that sideways moves do not work. They do exactly what they claim: they carry the search across plateaus. It is that the failures they eliminated were cheap, and the successes they created are expensive, and those two facts nearly cancel. How nearly depends on what a step is, which is the next section.

C. Comparing across different kinds of step

Simulated annealing looks far worse in that table, and the comparison is not fair as it stands. A hill-climbing step evaluates all 56 successors before moving; an annealing step evaluates at most one. So count the work, the successor costs actually computed, rather than the iterations. Two things the step count leaves out matter here. Every hill-climbing run that fails scans all 56 moves one last time, to find that none is good enough, and takes no step for it. And one annealing draw in eight lands on the queen's own row and evaluates nothing. Counting both, the expected work per solution is:

• hill climbing, no sideways: $1{,}547$ evaluations
• hill climbing, sideways: $1{,}298$
• annealing: $1{,}622$

Multiplying the step totals by 56 would give $1{,}224$ and $1{,}295$ and miss the final scans. Those cost the plain version $5.78 \times 56 \approx 324$ evaluations per solution, because it fails 5.78 times for every success, and cost the sideways version about 3. That one uncounted scan reverses the order: measured in evaluations, sideways moves make a solution 16% cheaper, where the step count said 6% dearer.

All three now sit within a factor of 1.25 of each other. Annealing buys the highest single-run success rate, 98.8%, at the highest cost of the three, though not by much once the same thing is counted on both sides.

That is the second half of the lesson. The table in section B counts steps, which are not the same unit on every row; this list counts evaluations, which are. They support different conclusions: a fix worth slightly less than nothing, or a fix worth 16%. Neither is the six-fold improvement the success rate suggests.

D. What to take from it

• A success rate per run is not a cost. For any restartable procedure the figure of merit is expected work to a solution, and a method that fails six times out of seven can cost only 19% more than one that fails once in eighteen.
• Measure the failures, not just the successes, and all of each failure. The difference here lives in what it costs to find out that a run is not going to work: 3.1 steps against 63.6, plus the final scan that finds nothing, which is a quarter of the cost of a failed plain run.
• Count operations, not iterations, when the iterations differ. A step is whatever the implementation says it is, and comparing steps across two algorithms with different step sizes compares nothing. Counting operations also catches the work that is not a step at all.
• Report the baseline you improved on, under the same accounting. A change that improves the headline number six-fold and the total by 16% is worth knowing about before it is adopted, not after.