Sokoban: Improving the Search with Relevance Cuts
- Andreas Junghanns
- Jonathan Schaeffer, Department of Computing Science, University of Alberta
Humans can effectively navigate through large search spaces, enabling them to solve problems with daunting complexity. This is largely due to an ability to successfully distinguish between relevant and irrelevant actions (moves). In this paper we present a new single-agent search pruning technique that is based on a move's influence. The influence measure is a crude form of relevance in that it is used to differentiate between local (relevant) moves and non-local (irrelevant) moves
Citation
A. Junghanns, J. Schaeffer. "Sokoban: Improving the Search with Relevance Cuts". Theoretical Computer Science, 252(1-2), pp 151-175, June 1999.Keywords: | |
Category: | In Journal |
BibTeX
@article{Junghanns+Schaeffer:99, author = {Andreas Junghanns and Jonathan Schaeffer}, title = {Sokoban: Improving the Search with Relevance Cuts}, Volume = "252", Number = "1-2", Pages = {151-175}, journal = {Theoretical Computer Science}, year = 1999, }Last Updated: June 05, 2007
Submitted by Staurt H. Johnson