Making Best Use of Available Memory When Searching Game Trees

Proceedings of the AAAI Conference on Artificial Intelligence, 5

Volume

Science

Search

When searching game trees, Algorithm SSS* examines fewer terminal nodes than the alphabeta procedure, but has the disadvantage that the storage space required by it is much greater. ITERSSS* is a modified version of SSS* that does not suffer from this limitation. The memory M that is available for use by the OPEN list can be fed as a parameter to ITERSSS* at run time. For successful operation M must lie above a threshold value MO . But MO is small in magnitude and is of the same order as the memory requirement of the alphabeta procedure. The number of terminal nodes of the game tree examined by ITERSSS* is a func- tion of M, but is never greater than the number of terminals examined by the alphabeta procedure. For large enough M, ITERSSS* is identical in operation to SSS*.