Exploiting Graph Properties of Game Trees

Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie de Bruin

The state space of most adversary games is a directed graph. However, due to the success of simple recursive algorithms based on Alpha-Beta, theoreticians and practitioners have concentrated on the traversal of trees, giving the field the name "game-tree search." This paper shows that the focus on trees has obscured some important properties of the underlying graphs. One of the hallmarks of the field of game-tree search has been the notion of the minimal tree, the smallest tree that has to be searched by any algorithm to find the minimax value. In fact, for most games it is a directed graph. As demonstrated in chess and checkers, we show that the minimal graph is significantly smaller than previously thought, proving that there is more room for improvement of current algorithms. We exploit the graph properties of the search space to reduce the size of trees built in practice by at least 25%. For over a decade, fixed-depth Alpha-Beta searching has been considered a closed subject, with research moving on to more application-dependent techniques. This work opens up new avenues of research for further application-independent improvements.

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.