Understanding the Success of Perfect Information Monte Carlo Sampling in Game Tree Search

Perfect Information Monte Carlo (PIMC) search is a practical technique for playing imperfect information games that are too large to be optimally solved. Although PIMC search has been criticized in the past for its theoretical deficiencies, in practice it has often produced strong results in a variety of domains. In this paper, we set out to resolve this discrepancy. The contributions of the paper are twofold. First, we use synthetic game trees to identify game properties that result in strong or weak performance for PIMC search as compared to an optimal player. Second, we show how these properties can be detected in real games, and demonstrate that they do indeed appear to be good predictors of the strength of PIMC search. Thus, using the tools established in this paper, it should be possible to decide a priori whether PIMC search will be an effective approach to new and unexplored games.

• Publication year

  2010

• Venue

  AAAI Conference on Artificial Intelligence

• Publication date

  2010-07-03

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1609/aaai.v24i1.7562
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• GIB: Imperfect Information in a Computationally Challenging Game

  2011influential reference
• Improving State Evaluation, Inference, and Search in Trick-Based Card Games

  2009influential reference
• AN ANALYSIS OF UCT IN MULTI-PLAYER GAMES

  2008cited by this paper
• Regret Minimization in Games with Incomplete Information

  2007influential reference
• Approximating game-theoretic optimal strategies for full-scale poker

  2003cited by this paper
• Âóùöòòð Óó Öøø¬ Blockin

  2001influential reference
• Search in Games with Incomplete Information: A Case Study Using Bridge Card Play

  1998cited by this paper

• Artificial Intelligence and Analytics for Evaluating Trick-Taking Games: A Narrative Review with a Case Study on an Estimation Variant

  2025influential citation
• LeadGenius: Mastering opening leads in the game of bridge

  2025cites this paper
• Framework for Generating State-Space Graphs

  2025cites this paper
• Neural Network-Based Information Set Weighting for Playing Reconnaissance Blind Chess

  2024cites this paper
• Fuzzy Utility AI for Handling Uncertainty in Video Game Bots Implementation

  2024cites this paper
• Efficiently Training Neural Networks for Imperfect Information Games by Sampling Information Sets

  2024cites this paper
• Perfect Information Monte Carlo with Postponing Reasoning

  2024influential citation
• Enhancing Reinforcement Learning Through Guided Search

  2024cites this paper
• Transformer Based Planning in the Observation Space with Applications to Trick Taking Card Games

  2024cites this paper
• Learning in Games with progressive hiding

  2024cites this paper
• Mixture of Public and Private Distributions in Imperfect Information Games

  2023cites this paper
• AlphaZe∗∗: AlphaZero-like baselines for imperfect information games are surprisingly strong

  2023cites this paper
• Reinforcement Learning Agents Playing Ticket to Ride–A Complex Imperfect Information Board Game With Delayed Rewards

  2023cites this paper
• MultiTree MCTS in Tabletop Games

  2022cites this paper
• Visualizing Multiplayer Game Spaces

  2022cites this paper
• Deep Synoptic Monte Carlo Planning in Reconnaissance Blind Chess

  2021cites this paper
• A Heuristic Algorithm for Kriegspiel

  2021cites this paper
• Optimizing αµ

  2021cites this paper
• Single Believe State Generation for Handling Partial Observability with MCTS in StarCraft

  2021cites this paper
• Student of Games: A unified learning algorithm for both perfect and imperfect information games

  2021cites this paper
• A Social Robot as a Card Game Player

  2021influential citation
• Player of Games

  2021cites this paper
• Quantifying the Space of Hearts Variants

  2021cites this paper
• A Practical Solution to Handling Randomness and Imperfect Information in Monte Carlo Tree Search

  2021cites this paper
• Learning to Play Imperfect-Information Games by Imitating an Oracle Planner

  2020influential citation
• Predicting Cards Using a Fuzzy Multiset Clustering of Decks

  2020cites this paper
• Competing in a Complex Hidden Role Game with Information Set Monte Carlo Tree Search

  2020cites this paper
• Recursive Monte Carlo Search for Bridge Card Play

  2020influential citation
• DeltaDou: Expert-level Doudizhu AI through Self-play

  2019cites this paper
• Policy Based Inference in Trick-Taking Card Games

  2019cites this paper
• Improving Search with Supervised Learning in Trick-Based Card Games

  2019cites this paper
• The αμ Search Algorithm for the Game of Bridge

  2019cites this paper
• Improving AI in Skat through Human Imitation and Policy Based Inference

  2019cites this paper
• TradingStone: Benchmark for Multi-Action and Adversarial Games

  2019influential citation
• General Game Playing with Imperfect Information

  2019cites this paper
• Enhancing Monte Carlo Tree Search for Playing Hearthstone

  2019cites this paper
• Fuzzy Multiset Clustering for Metagame Analysis

  2019cites this paper
• Belief-State Monte Carlo Tree Search for Phantom Go

  2018cites this paper
• Symbolic Reasoning for Hearthstone

  2018cites this paper
• Reinforcement Learning with Monte Carlo Sampling in Imperfect Information Problems

  2018cites this paper
• Iterative Tree Search in General Game Playing with Incomplete Information

  2018cites this paper
• Improving Hearthstone AI by Combining MCTS and Supervised Learning Algorithms

  2018cites this paper
• Monte Carlo Continual Resolving for Online Strategy Computation in Imperfect Information Games

  2018cites this paper
• Computing and Predicting Winning Hands in the Trick-Taking Game of Klaverjas

  2018cites this paper
• Automated construction of bounded-loss imperfect-recall abstractions in extensive-form games

  2018cites this paper
• GDL-III: A Description Language for Epistemic General Game Playing

  2017cites this paper
• A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning

  2017cites this paper
• Symbolic Reasoning for Hearthstone

  2017cites this paper
• Comparison of Monte Carlo Tree Search Methods in the Imperfect Information Card Game Cribbage

  2017cites this paper
• Single believe state generation for partially observable real-time strategy games

  2017cites this paper
• A Formal Description Language for General Epistemic Games

  2017cites this paper
• UWS Academic Portal Symbolic Reasoning for Hearthstone Stiegler, Andreas; Dahal, K.; Maucher, J.; Livingstone, D. Published in: IEEE Transactions on Computational Intelligence and AI in Games

  2017cites this paper
• Machine as one player in indian cowry board game:strategies and analysis of randomness model for playing

  2017cites this paper
• Combining Prediction of Human Decisions with ISMCTS in Imperfect Information Games

  2017cites this paper
• The Scalability of the HyperPlay Technique for Imperfect-Information Games

  2016cites this paper
• Une nouvelle approche au General Game Playing dirigée par les contraintes. (Une nouvelle approche au General Game Playing dirigée par les contraintes)

  2016cites this paper
• Applying artificial intelligence and machine learning techniques to create varying play style in artificial game opponents

  2016influential citation
• Universiteit Leiden Opleiding Informatica Learning to Play Hearthstone Using Machine Learning

  2016cites this paper
• The Importance of Rank in Trick-Taking Card Games

  2016cites this paper
• Framework for Monte Carlo Tree Search-related strategies in Competitive Card Based Games

  2016cites this paper
• CS 221 Project Final : DominAI

  2016cites this paper
• Enhancements in Monte Carlo tree search algorithms for biased game trees

  2015cites this paper
• Static strategies and inference for the game of Phantom Go

  2015cites this paper
• An experimental study of action selection mechanisms to create an entertaining opponent

  2015cites this paper
• An Expert-Level Card Playing Agent Based on a Variant of Perfect Information Monte Carlo Sampling

  2015cites this paper
• Emergent bluffing and inference with Monte Carlo Tree Search

  2015influential citation
• Belief-state Monte-Carlo tree search for Phantom games

  2015cites this paper
• Online Monte Carlo Counterfactual Regret Minimization for Search in Imperfect Information Games

  2015cites this paper
• EMYS: a social robot that plays “Sueca”

  2015cites this paper
• Monte Carlo Tree Search for games with hidden information and uncertainty

  2014influential citation
• Modified UCT Algorithm with Risk Dominance Methods in Imperfect Information Game

  2014cites this paper
• Positive and Negative Results in Approximation and Parameterized Complexity

  2014cites this paper
• Monte Carlo Tree Search in Imperfect-Information Games

  2014cites this paper
• A Modified UCT Algorithm Basd on Risk Estimation Methods

  2014cites this paper
• Applying determinized MCTS in Chinese Military Chess

  2014cites this paper
• Parallelization of Information Set Monte Carlo Tree Search

  2014cites this paper
• Information capture and reuse strategies in Monte Carlo Tree Search, with applications to games of hidden information

  2014cites this paper
• Search in Imperfect Information Games Using Online Monte Carlo Counterfactual Regret Minimization

  2014cites this paper
• Czech Technical University in Prague Faculty of Electrical Engineering

  2014cites this paper
• Using Modified UCT Algorithm Basing on Risk Estimation Methods in Imperfect Information Games

  2014cites this paper
• Solving Games and All That

  2013cites this paper
• Recursive Monte Carlo search for imperfect information games

  2013influential citation
• Symmetries and search in trick-taking card games

  2013influential citation
• Evaluating Answer Set Clause Learning for General Game Playing

  2013cites this paper
• A study of Monte Carlo Methods for Phantom Go

  2013cites this paper
• Simulation-Based General Game Playing

  2012cites this paper
• Ensemble Determinization in Monte Carlo Tree Search for the Imperfect Information Card Game Magic: The Gathering

  2012cites this paper
• Analysis of UCT algorithm policies in imperfect information game

  2012cites this paper
• Applying machine learning techniques to an imperfect information game

  2012cites this paper
• Monte Carlo Tree Search for the Hide-and-Seek Game Scotland Yard

  2012influential citation
• A Survey of Monte Carlo Tree Search Methods

  2012cites this paper
• Parallel Monte Carlo Search for Imperfect Information Game Daihinmin

  2012cites this paper
• Search, Inference and Opponent Modelling in an Expert-Caliber Skat Player

  2011cites this paper
• Game-Tree Properties and MCTS Performance

  2011cites this paper
• Determinization in Monte-Carlo Tree Search for the card game

  2011cites this paper
• Determinization and information set Monte Carlo Tree Search for the card game Dou Di Zhu

  2011cites this paper
• Understanding Sampling-based Adversarial Search Methods

  2010cites this paper