Solution Space Topology Guides CMTS Search

Mirco A. Mannucci · 2025

Read Solution Space Topology Guides CMTS Search by Mirco A. Mannucci (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-01701.txt.

Description

Mirco Mannucci asks what kind of map should guide a tree search through a puzzle. Earlier work fed Monte Carlo tree search with features of the puzzle grid itself. Those features came from the grid's Laplacian spectrum. They gave no benefit. Mannucci's diagnosis is blunt: grid topology is the same for every instance. It cannot tell easy puzzles from hard ones.

His fix is to measure the topology of the solution space instead. The method finds pattern rules on its own. It then builds a compatibility graph. Its nodes are cell-color pairs, linked when the two can coexist. Features such as algebraic connectivity and rigidity vary with how hard a puzzle is. Fed into node choice, they guide the search. Tests that remove one piece at a time show connectivity is the strongest signal.

Catalog record

CREATORMirco A. Mannucci
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE29 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-01701

Browse the full library · About the Tower of Babel