Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1109/SBAC-PAD.2012.42 | SBAC-PAD |
Keywords | Field | DocType |
computer games,parallel processing,resource allocation,search engines,tree data structures,trees (mathematics),ISG,Kriegspiel,combinatorial search problems,computational granularity,game tree search applications,game-playing agents,general-purpose combinatorial search engine,grain size parameters,information set generation parallelization,load balancing strategies,partially-observable chess,player observations,combinatorial search,game tree search,grain size,information sets,kriegspiel,load balancing | Search engine,Load balancing (computing),Computer science,Parallel computing,Tree (data structure),Theoretical computer science,Perfect information,Combinatorial search,Game tree,Information set,Scalability | Conference |
Citations | PageRank | References |
0 | 0.34 | 12 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mark Richards | 1 | 0 | 0.68 |
| Abhishek Gupta | 2 | 14 | 10.61 |
| Osman Sarood | 3 | 201 | 10.14 |
| Laxmikant V. Kale | 4 | 2871 | 248.18 |