Parallelizing Information Set Generation for Game Tree Search Applications

• Mark Richards University of Illinois
• Abhishek Gupta University of Illinois
• Osman Sarood University of Illinois
• Laxmikant V. Kalé University of Illinois

Resumo

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 a 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 (grain size parameters) on performance. We achieve speedups of over 500 on 1,024 processors, far exceeding previous scalability results for game tree search applications.

Palavras-chave: Games, Program processors, Load management, Law, Runtime, Search problems, game tree search, information sets, load balancing, kriegspiel, grain size, combinatorial search