Searching Game Trees Under Memory Constraints

Subir Bhattacharya, Amitava Bagchi

The best-first game-tree search algorithm SSS* has greater pruning power than the depth-first algorithm Alpha-Beta. Yet it is seldom used in practice because it is slow in execution and requires substantial memory. Variants of SSS* have been proposed in recent years that overcome some, but not all, of its limitations. The recursive controlled-memory best-first search scheme MemSSS* described here is a new derivative of SSS* that compares favourably with Alpha-Beta in respect of all three major performance measures, namely, pruning power, running time and memory needs. MemSSS* improves upon an earlier controlled-memory algorithm IterSSS* which has most of the desired properties but is slow in execution.

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.