Beam search
Keep the K most promising partial boards alive at once and grow them cell by cell. Beam search is the workhorse behind this project's from-scratch builders, and a clean illustration of why breadth alone stalls in the deep interior.
Keep the K most promising partial boards alive at once and grow them cell by cell. Beam search is the workhorse behind this project's from-scratch builders, and a clean illustration of why breadth alone stalls in the deep interior.
A depth-first backtracker commits to one partial board and digs. Beam search hedges: it keeps the best partial boards alive at once, extends every one of them by a single cell, scores all the children, and keeps the top again. The idea goes back to Bruce Lowerre's HARPY speech-recognition system in the 1970s; Zhou and Hansen's beam-stack search paper is a good modern treatment of the family and its trade-offs.
Fix a scan order over the 256 cells. A beam state is a partial placement, the set of pieces already spent, and a matched-edge score. Extending a state at depth means trying every legal (piece, rotation) for cell (legal with respect to the placed neighbours and the remaining inventory) and adding the number of newly matched edges to the score. Pool all children from all survivors, sort, truncate to , repeat 256 times, and every survivor is a complete board.
The inventory is what makes this different from beam search on a generic constraint problem: each piece exists exactly once, so a placement is not just a local choice but a withdrawal from a global budget. That detail decides everything below.
The lab below runs a beam down a synthetic tree: branching factor , depth , deterministic hash-based scores, no board, because the pathologies are easier to see when the instance is small enough to draw. Two features are planted deliberately: node scores are partly heritable (a good prefix tends to have good children, which is what makes a beam collapse onto one prefix), and a few trap nodes pay a large immediate score while quietly poisoning every descendant: a two-line synthetic model of piece theft, where a placement that scores now spends a piece the deep interior will need later.
Beam search is exponential search with the exponential deleted by fiat:
for width , branching factor and depth (plus an sort per level). Both are linear in , which is the whole appeal. The price is incompleteness: a beam offers no optimality guarantee, no certificate on failure, and no way back to a pruned prefix. Its one systematic failure mode is the collapse the lab shows: when the survivors become copies of one prefix, the effective width is 1 regardless of what you paid for.
At Eternity II scale the arithmetic is friendly, which is exactly why beams are the from-scratch workhorse here: cells, = the legal (piece, rotation) candidates per cell, a few hundred early, dwindling as the inventory drains, so even costs on the order of – child evaluations per complete board: minutes on a laptop, incomparably cheaper than any exhaustive figure on the dead ends page. What really says is not "cheap" but "only as good as its scoring function": the beam evaluates a vanishing fraction of the tree, and no known score predicts which depth-100 prefixes still complete well. Width is bought in linear coin; foresight is not for sale.
At the beam is plain greedy construction, and greedy with random restarts has a brutally heavy tail: on this project's engine, tens of thousands of random greedy runs topped out around 408 of 480, and extrapolating the tail put a 440 at billions of restarts. Widening the beam is far better, but the returns are roughly logarithmic. A beam of a few hundred states builds boards around 450; pushing past ten thousand reached the mid-450s and then flattened. (Measured on this project's engine; not independently replicated.)
There is a structural reason a plain beam cannot be much more than "greedy, wider". A beam state at depth faces exactly the same edge-matching and inventory constraints as a DFS node at depth ; keeping many states alive relaxes nothing. Without a scoring function that reliably predicts which depth-100 prefixes still complete well (and no such heuristic is known for Eternity II), the beam's extra breadth mostly duplicates what randomized restarts of a backtracker already provide.
Left to itself a beam collapses: within a few dozen cells most survivors share one high-scoring prefix, and the beam degenerates toward greedy with extra bookkeeping. Standard fixes are prefix deduplication and sampling from the top instead of taking the top , and this project's builders use both. But the strongest diversity lever found here was not inside the beam at all: it was the scan order. Running the same beam under nine different visit orders (GAUNTLET) produced eighteen distinct board families where sixteen seeds of a single order had produced one.
The other productive dial is the tiebreak. PRIOR breaks score ties toward pieces that are frequent at that position in a corpus of strong boards, lifting the from-scratch ceiling by a few edges and reaching 460 after refinement. LODESTONE breaks ties toward pieces that serve scarce demands, buying a small median gain and much better consistency, then collapsing badly the moment the prior is promoted from tiebreaker to objective.
Every beam variant tried here stalls the same way. The border and early interior fill almost perfectly; the mismatches concentrate in the last rows, where the pieces a cell needs were already spent serving easier cells long ago: the piece theft problem. A greedy local objective cannot see that global budget, and doubling pushes the wall back by only an edge or two. From-scratch beams on this engine ceiling in the mid-450s; the remaining distance is bought by destroy-and-repair polish, not by more width. Beam search, on this puzzle, is a fine way to reach the plateau quickly, and no way at all to leave it.