Parallelizing Information Set Generation for Game Tree Search Applications.

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.

@inproceedings{Richards2012,
 author = {Richards, Mark and Gupta, Abhishek and Sarood, Osman and Kale, Laxmikant V.},
 title = {{Parallelizing Information Set Generation for Game Tree Search Applications}},
 booktitle = {Proceedings of the 2012 IEEE 24th International Symposium on Computer Architecture and High Performance Computing},
 series = {SBAC-PAD '12},
 year = {2012},
 isbn = {978-0-7695-4907-1},
 pages = {116--123},
 numpages = {8},
 url = {http://dx.doi.org/10.1109/SBAC-PAD.2012.42},
 doi = {10.1109/SBAC-PAD.2012.42},
 acmid = {2419767},
 publisher = {IEEE Computer Society},
 address = {Washington, DC, USA},
 keywords = {game tree search, information sets, load balancing, kriegspiel, grain size, combinatorial search},
}