Information Set MCTS (ISMCTS)

The core innovation of ISMCTS is that each node in the search tree represents an information set, not a specific game state. An information set is the collection of all possible game states consistent with a player's observations. This allows the algorithm to reason over uncertainty by aggregating statistics across all states the player cannot distinguish between.

• Example: In poker, a node represents "my hand is Ace-King, and the public board shows 10-Jack-Queen." It does not represent the exact, unknown cards held by opponents.

To perform a simulation (rollout) from an information set node, ISMCTS uses determinization. It randomly samples one fully specified game state from the current information set and then conducts a standard MCTS rollout from that concrete state. The result is backpropagated to the information set node.

• This technique bridges the gap between perfect-information planning (MCTS) and imperfect-information reality.
• Multiple rollouts from the same node will sample different underlying states, building a robust value estimate that averages over hidden information.

ISMCTS inherently models opponents' knowledge and possible strategies. Because the tree is built from the perspective of the acting player, nodes for opponent turns represent the information sets they could be in, given the acting player's view.

• This creates a nested structure of uncertainty: the algorithm plans based on what it knows, what it knows the opponent knows, and so on.
• It avoids the strategy fusion problem common in naive MCTS applications to imperfect information games, where different sequences of hidden events incorrectly lead to the same tree node.

A standard ISMCTS tree is constructed from the perspective of a single player (the observer). The algorithm searches for the best action given that player's current information, without simultaneously solving for all players' optimal strategies (which is a more complex equilibrium problem).

• This makes ISMCTS computationally tractable for many real-world games.
• It is well-suited for partially observable Markov decision processes (POMDPs) where an agent must act under uncertainty.
• For a truly adversarial multi-agent setting, multiple trees (one per player) may be built and used for decision-making.

While pioneered for games like poker and bridge, ISMCTS is applicable to any sequential decision-making problem with hidden information.

• Real-Time Strategy Games: Where enemy unit positions and intentions are unknown.
• Security & Patrol Planning: Where an agent must plan routes without knowing an adversary's exact location.
• Negotiation & Economic Agents: Where the private valuations or strategies of other parties are hidden.
• Robotics with Sensor Noise: Where the true state of the environment is inferred from noisy, partial observations.

The Partially Observable Monte Carlo Planning (POMCP) algorithm is a closely related, influential extension of MCTS for partial observability. POMCP can be viewed as a formalization of ISMCTS principles within the POMDP framework.

• Both use determinization (called particles in POMCP) to sample beliefs.
• POMCP provides stronger theoretical convergence guarantees to the optimal POMDP solution under certain conditions.
• In practice, ISMCTS and POMCP represent overlapping families of algorithms for planning under uncertainty, with ISMCTS often emphasizing game-specific optimizations.

The foundational heuristic search algorithm upon which ISMCTS is built. MCTS is used for optimal decision-making in sequential problems by building a search tree through the iterative cycle of Selection, Expansion, Simulation, and Backpropagation. Unlike ISMCTS, standard MCTS operates under the assumption of perfect information, where the full game state is observable.

• Core Cycle: Select a leaf node, expand it, simulate a random rollout, and backpropagate the result.
• Application Domain: Perfect-information games like Chess and Go, as well as planning problems.
• Key Difference: MCTS nodes represent specific, fully-known game states, whereas ISMCTS nodes represent information sets (a player's knowledge state).

In game theory, an information set is a formal representation of a player's knowledge at a given point in a game of imperfect information. It groups together all the actual game states that are indistinguishable from the player's perspective.

• Formal Definition: A set of game states that share the same observable history for the acting player.
• Purpose in ISMCTS: ISMCTS search trees are built over information sets, not specific states. Each node corresponds to a player's belief about the possible true states of the game.
• Example: In Poker, a player's information set includes all possible private card combinations their opponent could hold, given the public cards and betting history.

The canonical tree policy used during the Selection phase of MCTS (and often adapted for ISMCTS) to balance exploration and exploitation. It selects child nodes by maximizing a score derived from the multi-armed bandit problem.

• Formula: UCT = Q(s,a) + c * sqrt( ln(N(s)) / N(s,a) ) where Q is the average reward, N are visit counts, and c is an exploration constant.
• Role: Guides the search toward promising but under-explored areas of the tree.
• Adaptation for Imperfect Info: In ISMCTS, statistics (Q and N) are maintained per information set and action, not per specific state.

A fundamental classification that determines the applicability of search algorithms like MCTS and ISMCTS.

• Perfect Information Games: All players have complete knowledge of the game state and all prior actions. Examples include Chess, Go, and Checkers. Standard MCTS is designed for this domain.
• Imperfect Information Games: Players have private, hidden information. The full game state is not observable. Examples include Poker, Bridge, Stratego, and many real-world scenarios like security patrolling or negotiation. ISMCTS is specifically engineered for this challenging domain.

A leading alternative algorithm for solving large, sequential games of imperfect information. While ISMCTS is a search-based online planning method, CFR is an iterative offline learning algorithm that converges to a Nash equilibrium.

• Core Mechanism: Iteratively traverses the game tree, calculating regret for not choosing different actions and updating a strategy to minimize this regret over time.
• Comparison to ISMCTS:
  • CFR: Computes an approximate Nash equilibrium strategy for the entire game offline. Used by top Poker AIs like Libratus.
  • ISMCTS: Performs real-time, online planning from the current information set to select a single action. More flexible for unknown or large state spaces.

A family of techniques for handling imperfect information by creating determinizations—hypothetical, fully-specified game states consistent with a player's current information set. ISMCTS can be viewed as an advanced form of determinized search.

• Basic Approach (e.g., Random Determinization): Sample a possible true state, treat it as perfect information, run a standard MCTS simulation on it, and aggregate results over many samples.
• ISMCTS Enhancement: ISMCTS builds a single, consolidated tree over information sets, sharing statistics across all determinizations that belong to the same information set. This is more sample-efficient and theoretically sound than independent determinized searches.
• Example: For a card game, a determinization is one possible deal of the hidden cards.