A General Solution to the Graph History Interaction Problem

Abstract

Since the state space of most games is a directed graph, many game-playing systems detect repeated positions with a trans-position table. This approach can reduce search effort by a large margin. However, it suffers from the so-called Graph History Interaction (GHI) problem, which causes errors in games containing repeated positions. This paper presents a practical solution to the GHI problem that combines and ex-tends previous techniques. Because our scheme is general, it is applicable to different game tree search algorithms and to different domains. As demonstrated with the two algo-rithms and df-pn in the two games checkers and Go, our scheme incurs only a very small overhead, while guarantee-ing the correctness of solutions.