Formula- and Memory-based Heuristics In Video-game Pathfinding
Bibliographic record
Abstract
The performance of a heuristic search depends substantially on the quality of its heuristic functions. A preferred heuristic is accurate, fast to query, and takes little memory. Recent research has explored two routes for building highperformance heuristics. Memory-based heuristics use a precomputed database containing optimal distances between a set of pivot states and all other states in the search graph. More pivot states tend to increase heuristic accuracy while slowing down heuristic computation and increasing memory cost. Alternatively, formula-based heuristics produced via program synthesis capture information about the search graph in short, human-readable formulae. These formulae have negligible memory cost and are fast to query, but generally perform worse than a memory-based heuristic. This paper presents the first empirical comparison between the two approaches for pathfinding. We find that formulabased heuristics can yield better performance than memorybased heuristics with a small number of pivots while being still more compact. With more pivots memory-based heuristics yield better speed-ups but take orders of magnitude more memory. We then investigate the degradation of search performance as the map changes and find that the performance of formula-based heuristics degrades more gracefully than that of memory-based heuristics.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
How this classification was reachedexpand
Full frame distilled prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. Learned from the 10,348 direct Codex labels and 10,348 direct Gemma labels. Candidate is the union of thresholded teacher heads; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels or direct frontier model labels.
Codex and Gemma teacher scores by category
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.000 | 0.000 |
| Meta-epidemiology (narrow) | 0.000 | 0.000 |
| Meta-epidemiology (broad) | 0.000 | 0.000 |
| Bibliometrics | 0.000 | 0.000 |
| Science and technology studies | 0.000 | 0.000 |
| Scholarly communication | 0.000 | 0.000 |
| Open science | 0.000 | 0.000 |
| Research integrity | 0.000 | 0.000 |
| Insufficient payload (model declined to judge) | 0.000 | 0.000 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from itClassification
machine, unvalidatedMachine predicted; a candidate call from one teacher head, not a consensus.
How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".