Search enhancements realize either of the following:
- lower bound improvements,
- forward pruning (safe and unsafe),
- depth reduction (macros), and
- move ordering.
|
|
IDA*() {
/** Compute the best possible lower bound **/
lb = ComputeLowerBound();
lb += UsePatterns();
lb += UseDeadlockTable();
lb += UseOverestimate( CntrlOverestimate() );
lb += ReadTransTable();
if( cutoff ) return;
/** Preprocess **/
PatternSearch( CntrlPatternSearch() );
lb += UsePatterns();
if( cutoff ) return;
/** Generate searchable moves **/
movelist = GenerateMoves();
RemoveDeadMoves( movelist );
IdentifyMacros( movelist );
OrderMoves( movelist );
for( each move ) {
if( Irrelevant( move, CntrlIrrelevant() )) next;
solution = IDA*();
if( solution) return;
if( GoalCut() ) break;
/** Use New Knowledge **/
UpdateLowerBound();
if( cutoff ) return;
}
/** Post-process **/
SaveTransTable( CntrlTransTable() );
return;
}
|
