Can an information set contain just one node?

Yes. The player can distinguish that decision history from other relevant histories in the model.

Is an information set the same as a belief state?

No. An information set identifies indistinguishable possibilities; a belief state can assign probabilities to them.

Can different players have different information sets?

Yes. Each player's observations and knowledge can differ, even within the same game.

AI Glossary / Graphs and symbolic AI / Advanced

Information sets

Definition

Information sets are groups of decision nodes that a player cannot distinguish using the information available to that player. In an extensive-form game, they specify which different histories must be treated as the same decision situation from that player's perspective.

What it means

A game tree can show the full sequence of events even when a player has not observed every event. The modeler may know that an opponent chose Left or Right, but the responding player may see only that a choice occurred.

Grouping the corresponding decision nodes into one information set prevents the model from giving that player access to the hidden choice. The player must use the same action choice, or the same distribution over actions, at those indistinguishable nodes.

An information set describes what can be distinguished. It is not itself a probability distribution over the possible nodes. Beliefs can assign different probabilities to nodes within the set, using the game's chance events and assumptions about strategies.

How it works

Construct the game's decision histories and identify which player acts at each decision node. For a given player, group nodes that the player cannot distinguish at the moment of choice. Nodes in the same information set must offer the same available actions in the standard representation.

Specify strategies at the information-set level rather than independently choosing an action at every hidden state. This avoids a policy that says to react differently to events the player never observed.

Observing additional information can split a previous information set into smaller sets. Perfect-information games have singleton information sets at players' decision points. Perfect recall is a separate property concerning whether players remember their own earlier information and choices; imperfect information does not automatically mean imperfect memory.

Three practical examples

A card-game model groups positions that differ only in an opponent's hidden card.
A negotiation simulator represents a responder who sees an offer but does not observe the other side's private condition.
An AI benchmark checks that an agent's decisions depend only on permitted observations rather than internal simulator variables.

Think of it this way

Think of receiving one of several sealed envelopes but seeing the same outer label on each. Until you open it, your decision must be based on that visible label and anything else you actually know.

The analogy captures indistinguishability. The envelopes need not be equally likely, and the information set does not by itself determine your beliefs about their contents or the best response.

Worked example

Preventing a strategy from using a hidden choice

Suppose Player A privately chooses Left or Right. Player B then chooses U or D without observing A's choice. At B's two decision nodes, the available actions are U and D, and the nodes belong to one information set.

Give B payoff 4 for U after Left and 0 for D after Left. After Right, give B payoff 0 for U and 4 for D. These numbers describe B's decision problem; they do not specify a full equilibrium analysis of A.

Assume B believes Left occurred with probability 0.75. Choosing U gives expected payoff 0.75 × 4 + 0.25 × 0 = 3. Choosing D gives 1. A strategy that chooses U with probability q therefore gives expected payoff 3q + 1(1 − q) = 1 + 2q, maximized at q = 1.

B cannot use the rule “U after Left, D after Right,” because those histories are indistinguishable. If B observes A's choice before responding, the information set separates into two singletons and that conditional rule becomes feasible, giving payoff 4. The change comes from available information, not a change in the payoff table.

Illustrative case study

The fictional Birch Games team tests an agent in a hidden-choice simulation. The training interface accidentally includes the simulator's internal record of the opponent's choice, although the intended rules conceal it.

The agent appears unusually effective because it can select a different response for each hidden branch. Reviewers draw the intended information set and compare it with the actual observations supplied to the policy. They remove the hidden variable and reassess the agent using the correct information boundary.

Birch also checks its evaluation interface so the same leakage does not return during testing. The case illustrates a modeling and implementation mismatch, not a reported benchmark result or a claim that every unusually strong agent is exploiting hidden state.

Common misconceptions and mistakes

Every node in an information set is equally likely. Probabilities require separate beliefs and may differ.
The player can choose independently at each node in the set. That would use information the player lacks.
Imperfect information means the game is random. A deterministic hidden action can also create imperfect information.
Perfect recall means knowing everything. It concerns remembering one's own information and actions, not observing other players' secrets.

Business use

Information sets help make the assumptions of a strategic model explicit. They are especially useful when a simulator, analyst or centralized system can access more information than the actual decision maker.

For an AI application, compare the information-set definition with every input supplied to the policy, including metadata, histories and diagnostic fields. A strategy evaluated with privileged information may not be implementable by the intended agent. When new signals become available, update the model deliberately and assess their effect instead of quietly allowing the policy to condition on them.

Check your understanding

Why is “U after Left, D after Right” invalid for B in the original worked game?

Answer: B does not observe Left or Right. Both decision nodes belong to one information set, so B's action rule must be the same at those nodes.

Related terms

Imperfect information
Game tree
Strategy
Belief state
Extensive-form game
perfect recall
behavioral strategy
information asymmetry

Learn next

Change B's belief about Left to 0.5 and recompute the expected payoff for U, D and a randomized choice. Then add a signal that sometimes reveals the hidden choice and describe how the information sets would change.

Sources

The Gambit developers demonstrate information sets and shared behavior across indistinguishable nodes: https://gambitproject.readthedocs.io/en/latest/tutorials/03_stripped_down_poker.html

Their extensive-form tutorial explains game-tree representation: https://gambitproject.readthedocs.io/en/latest/tutorials/02_extensive_form.html

AIMA's author slides discuss decision-making under partial observability in games: https://aima.cs.berkeley.edu/4th-ed/slides-pdf/chapter06.pdf

The Left/Right payoff exercise and Birch Games case are original examples.

Previous: Information sensitivity Next: Information value theory