Sokoban: Enhancing general single-agent search methods using domain knowledge

DOI10.1016/S0004-3702(01)00109-6zbMath0971.68151OpenAlexW1971439026WikidataQ128111118 ScholiaQ128111118MaRDI QIDQ5941317

A. Junghanns, Jonathan Schaeffer

Publication date: 20 August 2001

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0004-3702(01)00109-6

zbMATH Keywords

IDA*pattern databasepattern searchrapid random restartsingle-agent searchSokobantransposition table

Mathematics Subject Classification ID

Searching and sorting (68P10) Knowledge representation (68T30)

Related Items

\textsc{Pull} and \textsc{PushPull} are PSPACE-complete ⋮ Heuristics for planning with penalties and rewards formulated in logic and computed through circuits ⋮ Benefits of using multivalued functions for minimaxing ⋮ Planning with Critical Section Macros: Theory and Practice ⋮ Optimal Sokoban solving using pattern databases with specific domain knowledge ⋮ A genetic algorithm for the zen puzzle garden game ⋮ Finding optimal solutions to the graph partitioning problem with heuristic search ⋮ Computer Go: An AI oriented survey ⋮ On-the-Fly Macros ⋮ Games, computers, and artificial intelligence ⋮ Automated planning as an early verification tool for distributed control

Cites Work

• Unnamed Item
• Linear-space best-first search
• Macro-operators: A weak method for learning
• Some methods of controlling the tree search in chess programs
• Sokoban: Improving the search with relevance cuts
• SOKOBAN and other motion planning problems
• \(\text{BIDA}^*\): An improved perimeter search algorithm
• A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems