Winning Kaggle the Reproducible Way

Chapter 55

Pancake Sorting as a Constructed Search Example

An unfinished path is not a solution, however promising its heuristic score.

A search is judged by completed, replayed solutions under one budget. One demonstration runs beam search on 8-pancake instances with three rankings and measures how many it solves, how many flips it wastes against the true optimum, and how often an unfinished path looks almost sorted.

Every example is constructed for teaching. Its numbers come from running the chapter activity's code, not from a competition result.

Demonstration 1 of 1

Beam search with three rankings, by beam width, against the true optimum

Under the same beam width, how many instances does each ranking actually solve, and how far from optimal are its solutions?

The number of misplaced positions is not a lower bound for prefix flips: it overestimates the remaining flips for a large share of states, so the search loses any optimality guarantee. Worse for a beam, which keeps states by order alone, it barely tracks the true distance, so a narrow beam keeps the wrong states and loses the path. The gap count counts the adjacent pairs that must still be separated, so it never overestimates, tracks the true distance closely, and a narrow beam finds short solutions. A beam with no ranking only gets lucky. More width buys a weaker ranking more completions, at the price of more states generated.

Equation: the gap ranking of a state s counts the positions i up to n where the absolute difference between s i and s i plus 1 is not 1, with s n plus 1 equal to n plus 1 for the plate; the excess of a solution is its flip count minus the optimal flip count d star of s

Scroll sideways for the whole equation

s_i is the size of the i-th pancake from the top (sizes 1 to n), s_{n+1} = n + 1 stands for the plate, and d*(s) is the optimal flip count of state s. W is the beam width. A ranking h assigns each state a number, and the beam keeps the W lowest. A ranking is a lower bound when it never exceeds the true number of flips left. The excess of a solution is its flip count minus the optimal flip count of the same start.

Predict first. With a beam width of 4, what share of the 200 instances does the misplaced-position ranking solve?

Your prediction

Choose an example

Scroll sideways for the whole figure

Figure: Beam search with three rankings, by beam width, against the true optimum. Left: share of 200 8-pancake instances solved at beam width 4: misplaced 21%, gap count 100%, no ranking 0.5%. Right: extra flips over the optimum among the solved runs.
Beam width (states kept after each flip): 4
Constructed example: 200 seeded random 8-pancake instances, optimal flip counts from breadth-first search, measured by the chapter activity.

Calculated values

Misplaced ranking, solved
21%
Gap ranking, solved
100%
No ranking, solved
0.5%
Gap minus misplaced, solve rate
0.790
Misplaced overestimates
45% of states

With a beam width of 4, the misplaced-position ranking solves 21% of 200 instances and the gap count 100%, so 1.000 - 0.210 = 0.790 of the instances separate them; with no ranking 0.5% are solved. Solved runs use 3.55 extra flips for the misplaced ranking and 0.11 for the gap count. The misplaced count overestimates the true flips left in 45% of all 40,320 states and the gap count in 0%, and their rank correlations with the true flips left are 0.06 and 0.85. The gap beam generates 169 states per instance and the misplaced beam 300.

Worked steps

  1. Solve rate gap minus misplaced: 1.000 - 0.210 = +0.790.
  2. Failed misplaced runs that ended within 2 positions of sorted: 26 of 158 (still failures).
  3. Share of states where the misplaced count exceeds the true flips left: 45%.
  4. Mean optimal flips over all 40,320 states: 6.64, longest 9.

Use the idea

Measure completed, replayed solutions against a trusted baseline on small instances before scaling a search. Choose a ranking that tracks the real remaining cost, and treat an unfinished state with a good score as a failure.

Where the conclusion applies

A constructed 8-pancake puzzle, not the Santa 2024 competition; random tie-breaks make single-instance results noisy, so 200 instances give the rates. The gap ranking is a known strong ranking for pancake flipping; its quality here says nothing about other puzzles. Beam search is one policy among those the chapter lists; nested Monte Carlo search is not run. A 12-flip limit counts as the budget end.

Check your understanding: Why can the misplaced-position ranking mislead the beam, and why does a failed run with an almost sorted state not count as a result?
Misplaced positions are not a lower bound: they overestimate the flips left in 45% of the states, so nothing guarantees short solutions. For a beam, which uses only the order, the bigger problem is that they barely track the true distance: their rank correlation with the optimal flip count over all states is 0.06, against 0.85 for the gap count. A narrow beam ordered by them keeps states that are no closer to sorted and throws away useful ones. A path that ends one or two positions from sorted has not reached the goal, so it is not a legal completed solution; the search returns failure and the replay confirms it.

Chapter 55 source: section "A Heuristic Is Not Automatically a Lower Bound".