Sokoban

Preprocessing

Pre-search processing happens at several levels:

Domain: e.g. pattern and endgame databases

Instance: e.g. efficient encodings, parameter settings and macros

Some of our most valuable enhancements use preprocessing:

goal macros

pattern databases

for( each domain ) {

   /* Preprocess */
   BuildDeadlockTable( CntrlDeadlockTable() );

   for( each instance ) {

       /* Preprocess */
       FindTunnelMacros();
       FindGoalMacros( CntrlGoalMacros() );

       while( not solved ) {
           SetSearchParamaters();
           IDA*();
       }

       /* Postprocess */
       SavePatterns( CntrlSavingPatterns() );
   }
}

GPW'99, October 16, 1999. Pushing the Limits: New Developments in Single-Agent Search