Parallelizing information set generation for game tree search applications

Mark Richards, Abhishek Gupta, Osman Sarood, Laxmikant V. Kalé

Research output: Contribution to journalConference articlepeer-review

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.

Original languageEnglish (US)
Article number6374779
Pages (from-to)116-123
Number of pages8
JournalProceedings - Symposium on Computer Architecture and High Performance Computing
DOIs
StatePublished - Dec 1 2012
Event24th International Symposium on Computer Architecture and High Performance Computing, SBAC-PAD 2012 - New York, NY, United States
Duration: Oct 24 2012Oct 26 2012

Keywords

  • combinatorial search
  • game tree search
  • grain size
  • information sets
  • kriegspiel
  • load balancing

ASJC Scopus subject areas

  • Hardware and Architecture
  • Software

Fingerprint Dive into the research topics of 'Parallelizing information set generation for game tree search applications'. Together they form a unique fingerprint.

Cite this