Making Best Use of Available Memory When Searching Game Trees

Subir Bhattacharya, Amitava Bagchi

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*.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.