Parallelizing Information Set Generation for Game Tree Search Applications.
International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD) 2012
Publication Type: Paper
Repository URL:
Information Set Generation (ISG) is the identification of the set of paths in an imperfect information game tree that are consistent with a player’s observations. The ability to reason about the possible game history is critical to the performance of game-playing agents. ISG represents a class of combinatorial search problems which is computationally intensive but challenging to efficiently parallelize. In this paper, we address the parallelization of information set generation in the context of Kriegspiel (partially observable chess). We implement the algorithm on top of a general purpose combinatorial search engine and discuss its performance using datasets from real game instances in addition to benchmarks. Further, we demonstrate the effect of load balancing strategies, problem sizes and computational granularity (grainsize parame- ters) on performance. We achieve speedups of over 500 on 1,024 processors, far exceeding previous scalability results for game tree search applications.
Research Areas