In this paper we propose a new algorithm for solving general two-player turn-taking games that performs symbolic search utilizing binary decision diagrams (BDDs). It consists of two stages: First, it determines all breadth-first search (BFS) layers using forward search and omitting duplicate detection, next, the solving process operates in backward direction only within these BFS layers thereby partitioning all BDDs according to the layers the states reside in. We provide experimental results for selected games and compare to a previous approach. This comparison shows that in most cases the new algorithm outperforms the existing one in terms of runtime and used memory so that it can solve games that could not be solved before with a general approach.
Bartak, Roman (Charles University in Prague) | Dvorak, Filip (Charles University in Prague) | Gemrot, Jakub (Charles University in Prague) | Brom, Cyril (Charles University in Prague) | Toropila, Daniel (Charles University in Prague)
This paper deals with planning domains that appear in computer games, especially when modeling intelligent virtual agents. Some of these domains contain only actions with no negative effects and are thus treated as easy from the planning perspective. We propose two new techniques to solve the problems in these planning domains, a heuristic search algorithm ANA* and a constraint-based planner RelaxPlan, and we compare them with the state-of-the-art planners, that were successful in IPC, using planning domains motivated by computer games.
This work combines recent advances in AI planning under memory limitation, namely bitvector and symbolic search. Bitvector search assumes a bijective mapping between state and memory addresses, while symbolic search compactly represents state sets. The memory requirements vary with the structure of the problem to be solved. The integration of the two algorithms into one hybrid algorithm for strongly solving general games initiates a BDD-based solving algorithm, which consists of a forward computation of the reachable state set, possibly followed by a layered backward retrograde analysis. If the main memory becomes exhausted, it switches to explicit-state two-bit retrograde search. We use the classical game of Connect Four as a case study, and solve some instances of the problem space-efficiently with the proposed hybrid search algorithm.
A promising approach to solving large state-space search problems is to integrate heuristic search with symbolic search. Recent work shows that a symbolic A* search algorithm that uses binary decision diagrams to compactly represent sets of states outperforms traditional A* in many domains. Since the memory requirements of A* limit its scalability, we show how to integrate symbolic search with a memory-efficient strategy for heuristic search. We analyze the resulting search algorithm, consider the factors that affect its behavior, and evaluate its performance in solving benchmark problems that include STRIPS planning problems.