Sokoban: improving the search with relevance cuts

Humans can effectively navigate through large search spaces, enabling them to solve problems with daunting complexity. This is largely due to an abili ty to successfully distinguish between relevant and irrelevant actions (mov es). In this paper we present a mew single-agent search pruning technique t hat is based on a move's influence. The influence measure is a crude form o f relevance in that it is used to differentiate between local (relevant) mo ves and non-local (irrelevant) moves, with respect to the sequence of moves leading up to the current state. Our pruning technique uses the m previous moves to decide if a move is relevant in the current context and, if not, to cut it off. This technique results in a large reduction in the search ef fort required to solve Sokoban problems. (C) 2001 Elsevier Science B.V. All rights reserved.