Stochastic Two-Player Game

The game involves exactly two players, typically labeled Player 1 (Maximizer) and Player 2 (Minimizer), with diametrically opposed goals. Player 1 aims to maximize the expected cumulative reward or probability of winning, while Player 2 aims to minimize it. This creates a zero-sum dynamic, where one player's gain is the other's loss. The adversarial nature distinguishes it from cooperative or single-agent stochastic environments.

The game evolves through a set of states (S). When a player takes an action from a state, the resulting next state is not deterministic. Instead, it is governed by a transition probability function P(s' | s, a), which defines the probability of moving to state s' given the current state s and action a. This stochasticity models uncertainty, randomness in the environment, or hidden information, making the game more complex than its deterministic counterpart.

Each state s has an associated action set A(s) available to the player whose turn it is. Games are typically turn-based, with control alternating between players. In some formulations, chance nodes (representing stochastic events) are also treated as a pseudo-player. The structure of available actions can be discrete (e.g., chess moves) or continuous, though discrete actions are most common in analytical and algorithmic treatments.

A reward function R(s, a, s') provides immediate feedback after a transition. In zero-sum games, rewards are often expressed from Player 1's perspective (e.g., +1 for win, -1 for loss, 0 for draw). The game ends upon reaching a terminal state, belonging to a set T ⊂ S, where no further actions are possible. The objective is to maximize the expected total reward (or value) from the initial state, considering the opponent's optimal counter-strategy and stochastic transitions.

A player's strategy (or policy) π defines a rule for selecting actions in each state. It can be:

• Pure Strategy: A deterministic mapping from states to actions.
• Mixed Strategy: A probability distribution over actions for each state.
• Behavioral Strategy: A mixed strategy for each information set (in imperfect information games). The solution concept is often a Nash equilibrium in strategies, where neither player can benefit by unilaterally changing their policy.

The core computational problem is finding the game value V(s), defined as the expected total reward for Player 1 when both players follow optimal strategies from state s. For finite, zero-sum stochastic games, the Minimax Theorem holds: the maximum expected value Player 1 can guarantee (via their strategy) equals the minimum expected value Player 2 can force (via their counter-strategy). This value satisfies the Bellman optimality equation for zero-sum games: V(s) = max_{a ∈ A(s)} min_{π_2} E[ R + γ V(s') ], where the expectation is over the opponent's policy and stochastic transitions.

A sequential game where all players have complete knowledge of the entire game state and the full history of actions taken. This is the classic domain for standard Monte Carlo Tree Search (MCTS).

• Examples: Chess, Go, Checkers.
• Contrast with Stochastic Games: No hidden information or random state transitions.
• Algorithmic Impact: Search algorithms can reason over a single, deterministic state tree.

An extension of Monte Carlo Tree Search specifically designed for games of imperfect information, where a player's knowledge is represented as an information set—a collection of states indistinguishable to that player.

• Key Innovation: The search tree is built over information sets, not specific game states.
• Applications: Card games like Poker, Bridge, or any scenario with hidden information.
• Relation to Stochastic Games: Handles uncertainty about opponent's private state, complementing the randomness in state transitions.

A foundational mathematical framework for modeling sequential decision-making by a single agent in a stochastic environment. It is defined by states, actions, transition probabilities, and rewards.

• Core Components: A state s, an action a, a transition function P(s'|s,a), and a reward function R(s,a,s').
• Relation to Stochastic Games: An MDP is the single-agent analogue; a stochastic game extends this to multiple, interacting agents.
• Solution Methods: Solved via algorithms like Value Iteration or Policy Iteration to find an optimal policy.

A generalization of an MDP where the agent cannot directly observe the true state of the environment, receiving only partial, noisy observations. This adds a layer of perceptual uncertainty on top of environmental stochasticity.

• Key Challenge: The agent must maintain a belief state—a probability distribution over possible true states.
• Relation to Stochastic Games: A POMDP models a single agent's struggle with uncertainty, while stochastic games model multi-agent competition and randomness.
• Applications: Robotics, healthcare diagnostics, and any domain with sensor noise or occlusions.

A game representation that explicitly models the sequential structure of player interactions, including the order of moves, the information available to each player at each decision point, and chance events.

• Representation: Typically depicted as a game tree.
• Stochastic Element: Chance nodes represent random events (like dice rolls or card deals).
• Encompasses Models: Perfect/imperfect information games, stochastic games, and POMDPs can all be represented in extensive form.
• Solution Concept: Often solved for Nash Equilibria or Subgame Perfect Equilibrium.

A class of reinforcement learning (RL) algorithms where the agent learns an explicit internal model of the environment's dynamics (transition function) and reward function. This model is then used for planning.

• Core Idea: "Learn the rules of the game, then think ahead."
• Relation to Stochastic Games: Algorithms like MuZero learn a latent dynamics model to enable planning with MCTS in environments (including games) where the true rules are unknown.
• Contrast with Model-Free RL: Model-free methods (e.g., Q-learning) learn a policy or value function directly without constructing a world model.