Expansion Counts under Standard A* Tie-Breaking Strategies on the Final Plateau
cs.AI
Quick verdict
Proves pairwise incomparability of nine standard A* tie-breaking rules plus low-h/high-h extremal results and a sharp alpha=1 boundary; proofs sound, purely theoretical, no empirical validation.
Summary
This is a purely theoretical analysis of how tie-breaking among states with equal f = g + h affects the number of states A* expands on the final f = C* plateau. First, for nine standard strategies built from FIFO, LIFO, and uniform-random final tie-breakers combined with low-h or high-h criteria, the paper constructs positive-cost trees with a consistent heuristic on which every pair of strategies beats the other by an arbitrarily large additive expansion gap (Theorem 1, via a star construction), so no rule dominates. A parameterized four-neighbor unit-cost grid with Manhattan distance gives unbounded additive gaps and Theta(m) expansion-count ratios between [h, FIFO] and [h, LIFO], reversed by transposing the grid. Second, in unit-cost search with h > 0 at non-goals, if h is exactly perfect on final-plateau states with h <= k, every low-h strategy performs exactly m further expansions from a common configuration with minimum eligible h-value m <= k, which is provably minimal; a weaker condition (every h = 1 plateau state is a goal predecessor) makes every high-h strategy maximize total expansions, regardless of the final tie-breaker (Theorems 2-3). Third, with the weighted evaluation f_alpha = g + alpha*h, any weight 0 <= alpha < 1 makes the expanded set identical for all tie-breakers, with a sharp boundary at alpha = 1 (Corollary 3). Limitations: no experiments; strongest guarantees require unit costs and locally perfect heuristics.
Review complete
Assessment at a glance
2
risk flags identified
● high 0
● medium 0
● low 2
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Under a consistent heuristic with positive edge costs, no one of the nine standard tie-breaking strategies (FIFO, LIFO, RANDOM, each alone or combined with low-h/high-h) dominates any other: every pair admits instances favoring each side by an arbitrarily large additive expansion gap (Theorem 1).
- On four-neighbor unit-cost grids with Manhattan distance and a fixed successor order, [h, FIFO] and [h, LIFO] have unbounded additive gaps and unbounded expansion-count ratios, and transposing the grid reverses which strategy wins.
- In unit-cost search with h > 0 at non-goals, if h is perfect on the final-plateau layers B<=k, every low-h strategy performs exactly m remaining expansions from a common configuration with minimum eligible h-value m <= k, and this is minimal (Theorem 2, Corollary 1).
- If every final-plateau state with h = 1 is a goal predecessor, every high-h strategy expands exactly S< on nonpathological instances and S< union (S= \ B1) plus one B1 state on pathological ones, thereby maximizing total expansions among all tie-breakers (Theorem 3).
- With f_alpha = g + alpha*h and h > 0 at non-goals, every weight 0 <= alpha < 1 makes all tie-breakers expand the identical set S(alpha)<, with a sharp boundary at alpha = 1 (Corollary 3).
Strengths
Complete impossibility result with an elementary, reusable construction
The star construction (Lemma 2, Sec. 3.1) decouples insertion order from h-values, letting Theorem 1 separate all 9 strategies of P pairwise with additive gaps 2 vs M+2 in both directions, including exact expectations (M/2) for the three randomized pairs. A bounded-degree chain variant removes the unbounded-branching objection.
Separation holds on familiar domains, not exotic structures
Sec. 3.2 gives unbounded [h, FIFO] vs [h, LIFO] gaps on four-neighbor unit-cost grids with Manhattan distance, with successor order Up/Right/Down/Left fixed; transposing the grid reverses which strategy wins, with expansion-count ratio Theta(m).
Extremal results characterize whole strategy classes, not individual rules
Sharp boundary result is clean and connects to Dechter-Pearl nonpathology
Careful model conventions and honest scoping
Weaknesses
Purely theoretical; no experiments quantify when large gaps actually occur
The strongest guarantees rest on restrictive assumptions rarely met in practice
Maximality in Theorem 3 is relative, and the significance of expansion-count maximization is not discussed
Novelty relative to known results is partly incremental
No code or artifact statement; minor numeric inconsistency in Figure 2 caption
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
This is a theory paper on A* (Hart-Nilsson-Raphael 1968) that asks which states get expanded on the *final plateau* — the last layer of nodes with f = C* — as a function of the tie-breaking rule. Three claims: (1) **Pairwise incomparability** (Sec. 3, Theorem 1): for the nine strategies P = {FIFO, LIFO, RANDOM, [h, FIFO], [h, LIFO], [h, RANDOM], [−h, FIFO], [−h, LIFO], [−h, RANDOM]}, every pair admits positive-cost instances with a consistent heuristic where each beats the other by an arbitrarily large additive gap (counts 2 vs M+2, either direction; expected gap ≥ M/2 for randomized pairs). (2) **Extremal classes** (Sec. 4, Theorems 2–3): in unit-cost search with h > 0 at non-goals, if h is perfect on B≤k then every [h, τ] performs exactly m further expansions from a common configuration (m ≤ k), provably minimal; if h is perfect only on B1, every [−h, σ] maximizes total expansions, with the exact expanded set S< ∪ (S= \ B1) ∪ {p} on pathological instances (Eq. 1). (3) **Sharp weight boundary** (Sec. 5, Corollary 3): with fα = g + αh and h > 0 at non-goals, every α < 1 makes all tie-breakers expand exactly S(α)<.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 2 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
Does tie-breaking matter for A* search performance?
Yes. This paper proves that on the final f = C* layer (the last part of an optimal A* search), any two of nine standard tie-breaking strategies (FIFO, LIFO, random, each with or without low-h/high-h preference) can be made to differ by an arbitrarily large number of expansions, so no strategy dominates another in general. Large gaps even occur on ordinary unit-cost grids with Manhattan distance.
Which A* tie-breaking strategy is best: low-h (high-g) or high-h (low-g)?
In general neither is universally better - the paper shows each can be arbitrarily worse than the other. However, when the heuristic is exactly correct near the goal: in unit-cost search, low-h tie-breaking provably minimizes the remaining expansions once the search enters the perfectly estimated region, while high-h tie-breaking provably maximizes the total expansion count when every h = 1 plateau state is a goal predecessor.
Why is weighted A* with weight below 1 insensitive to tie-breaking?
With evaluation f = g + alpha*h and alpha < 1, if the heuristic is positive at every non-goal, the scaled heuristic is strictly optimistic along optimal paths, which makes every state with f* <= C* a compulsory expansion. All tie-breaking rules then expand exactly the same set of states. At exactly alpha = 1 (standard A*) this collapses and tie-breaking gaps can be arbitrarily large.
Is this paper peer-reviewed?
It is an arXiv preprint (arXiv:2609.23293, cs.AI, September 2026) by Alex Fukunaga (University of Tokyo), an established heuristic-search researcher. The review here is an automated preliminary assessment, not a peer review; the paper cites prior work at AAAI, IJCAI, JAIR, SoCS, and JACM.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Review is based on the extracted full text; figures are available only through their text captions, so the Figure 2 m = 3 caption count (27) could not be checked against the rendered grid (formulas in the text imply 28 cul-de-sac states).
- Formal proofs were assessed by reading, not by mechanical verification; the constructions are elementary and hand-checkable, and no gaps were found.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.