ISMCTS and the Hidden Hand

When a card is face down, the right move cannot depend on what the card is.

That sentence is the whole difficulty of search in card games. Ordinary Monte Carlo Tree Search (built step by step in MCTS from scratch) assumes every node is a fully known state. In bridge, hearts, or poker, the player to move knows its own hand and the cards already played, and nothing else. This note builds a small trick-taking game, shows the obvious fix (guess the hidden cards, then search), constructs a game where that fix provably fails, and then implements single-observer Information Set MCTS (Cowling, Powley and Whitehouse, 2012), which searches over what the player knows instead of what is true.

The game#

Twelve cards: three suits, four ranks. Each player is dealt four; four stay in the stock, unseen by anyone. The leader plays any card. The follower must follow suit if able. The highest card of the led suit wins the trick, and the winner leads next. After four tricks, more tricks wins.

import math, random
 
SUITS, RANKS, HAND = "SHD", range(4), 4
DECK = [(s, r) for s in SUITS for r in RANKS]     # 12 cards
 
class Tricks:
    """Two-player trick-taking. Follow suit if you can; highest card of the led suit wins."""
    def __init__(self):
        deck = DECK[:]; random.shuffle(deck)
        self.hands = {1: deck[:HAND], 2: deck[HAND:2*HAND]}
        self.stock = deck[2*HAND:]               # never dealt, never seen
        self.trick = []                          # [(player, card)] for the current trick
        self.tricks = {1: 0, 2: 0}
        self.to_move = 1
 
    def clone(self):
        g = Tricks.__new__(Tricks)
        g.hands = {p: h[:] for p, h in self.hands.items()}
        g.stock, g.trick = self.stock[:], self.trick[:]
        g.tricks, g.to_move = dict(self.tricks), self.to_move
        return g
 
    def moves(self):
        hand = self.hands[self.to_move]
        if self.trick:
            led = self.trick[0][1][0]
            follow = [c for c in hand if c[0] == led]
            if follow:
                return follow
        return hand[:]
 
    def play(self, card):
        p = self.to_move
        self.hands[p].remove(card)
        self.trick.append((p, card))
        if len(self.trick) == 1:
            self.to_move = 3 - p
            return
        led = self.trick[0][1][0]
        winner = max((c[1], q) for q, c in self.trick if c[0] == led)[1]
        self.tricks[winner] += 1
        self.trick, self.to_move = [], winner
 
    def over(self):
        return not self.hands[1] and not self.hands[2]
 
    def result(self, p):
        """1 if p took more tricks, 0.5 tie, 0 otherwise."""
        a, b = self.tricks[p], self.tricks[3 - p]
        return 1.0 if a > b else 0.5 if a == b else 0.0

The object holds the true deal. No agent below is allowed to read hands[opponent] or stock directly; it may only ask for a determinization.

Step 1: determinization#

A determinization is one complete guess at the hidden state that is consistent with everything the observer has seen. Here, that means: keep the observer's own hand and the public history, and reshuffle the opponent's hand together with the stock.

    def determinize(self, observer):
        """Same public history, but the cards the observer cannot see are reshuffled."""
        g = self.clone()
        opp = 3 - observer
        hidden = g.hands[opp] + g.stock
        random.shuffle(hidden)
        g.hands[opp] = hidden[:len(g.hands[opp])]
        g.stock = hidden[len(g.hands[opp]):]
        return g

This is the simplest consistent sampler, and it is slightly wrong: if the opponent failed to follow hearts earlier, it holds no hearts, and a correct sampler would respect that. The constraint is easy to add by rejection; leaving it out keeps the code short and is noted again at the end.

Given determinizations, the obvious algorithm is Perfect Information Monte Carlo (PIMC): sample many worlds, solve each one as if it were the truth, and vote. It is what Ginsberg's bridge program GIB did, and it is often strong.

class Node:
    def __init__(self, move=None, parent=None, just_moved=None):
        self.move, self.parent, self.just_moved = move, parent, just_moved
        self.children, self.N, self.W, self.avail = [], 0, 0.0, 1
 
def uct(state, iters, c=0.7):
    """Plain UCT: assumes `state` is the truth. Returns root visit counts per move."""
    root = Node()
    for _ in range(iters):
        node, s = root, state.clone()
        tried = lambda n: {ch.move for ch in n.children}
        while not s.over() and set(s.moves()) == tried(node) and node.children:
            node = max(node.children, key=lambda ch: ch.W / ch.N + c * math.sqrt(math.log(node.N) / ch.N))
            s.play(node.move)
        if not s.over():
            m = random.choice([m for m in s.moves() if m not in tried(node)])
            p = s.to_move; s.play(m)
            node.children.append(Node(m, node, p)); node = node.children[-1]
        while not s.over():
            s.play(random.choice(s.moves()))
        while node:
            node.N += 1
            if node.just_moved: node.W += s.result(node.just_moved)
            node = node.parent
    return {ch.move: ch.N for ch in root.children}
 
def pimc(state, iters, dets=20):
    """Perfect Information Monte Carlo: solve many guessed worlds, vote."""
    votes = {}
    for _ in range(dets):
        for m, n in uct(state.determinize(state.to_move), iters // dets).items():
            votes[m] = votes.get(m, 0) + n
    return max(votes, key=votes.get)

Step 2: where determinization fails#

Frank and Basin (1998) named two failure modes of this approach.

Strategy fusion. Inside each sampled world, the search is allowed to choose different later moves in different worlds, because in each world it knows the hidden cards. In the real game, the player must choose one action per information set, the same action in every world it cannot tell apart. PIMC averages over a set of clairvoyant players, and a clairvoyant player overvalues every line that needs a guess.

Non-locality. In a perfect-information tree, a node's value depends only on its subtree. In a hidden-information game, it also depends on how play got there: an opponent who chose to lead a low spade has told you something about its hand. A search that samples hidden cards uniformly at every node ignores that evidence.

Strategy fusion is easy to make concrete. Here is a one-player game built to trigger it: take a sure 0.6, or gamble and then call a coin flip you never get to see.

class CoinGuess:
    """Take a sure 0.6, or gamble: then guess a hidden coin you never see. Right = 1, wrong = 0."""
    def __init__(self, coin=None):
        self.coin = coin if coin is not None else random.choice("HT")
        self.history, self.to_move = [], 1
    def clone(self):
        g = CoinGuess(self.coin); g.history = self.history[:]; return g
    def determinize(self, observer):
        g = self.clone(); g.coin = random.choice("HT"); return g   # the coin is hidden
    def moves(self):
        return ["safe", "gamble"] if not self.history else ["guess H", "guess T"]
    def play(self, m): self.history.append(m)
    def over(self):
        return self.history[:1] == ["safe"] or len(self.history) == 2
    def result(self, p):
        if self.history[0] == "safe": return 0.6
        return 1.0 if self.history[1][-1] == self.coin else 0.0

The gamble is worth 0.5 to anyone who cannot see the coin, so the correct first move is safe. In each determinized world, though, the coin is known, the guess is always right, and the gamble is worth 1.0. Measured over 200 decisions with 1,000 iterations each:

PIMC gambles every time, for an expected 0.5, because every one of its sampled worlds told it the gamble was free. The fix has to make the guess a single decision whose statistics are shared across worlds.

Step 3: a tree over information sets#

ISMCTS keeps one tree, and its nodes are indexed by the sequence of moves, not by the hidden state. Every iteration samples a fresh determinization and uses it only to decide which moves are legal and how the rollout plays out. Statistics from every world land in the same nodes.

That makes the guess node in CoinGuess one node with two children, and each child's mean is an average over both coin values: 0.5. The gamble's value is backed up as 0.5, below 0.6, and the search takes the safe option.

One new quantity is needed. In plain UCT every child of a node is legal whenever the node is reached, so the parent's visit count $N_p$ is the right "number of times this child could have been chosen". In ISMCTS a child is legal only in the determinizations where that card is in hand. The exploration term must count availability $A_i$, the number of times child $i$ was legal when its parent was visited:

Without it, a rarely legal card would accumulate a large $\ln N_p$ bonus while its own visits stayed small, and the search would overselect it every time it appeared.

def ismcts(state, iters, c=0.7):
    """One tree over information sets; a fresh determinization per iteration."""
    root, me = Node(), state.to_move
    for _ in range(iters):
        node, s = root, state.determinize(me)
        # Select: only children whose move is legal in THIS determinization.
        while not s.over():
            legal = s.moves()
            seen = {ch.move for ch in node.children}
            if any(m not in seen for m in legal):
                break                                     # something to expand here
            compatible = [ch for ch in node.children if ch.move in legal]
            for ch in compatible:
                ch.avail += 1                             # it was available this time
            node = max(compatible, key=lambda ch: ch.W / ch.N + c * math.sqrt(math.log(ch.avail) / ch.N))
            s.play(node.move)
        # Expand
        if not s.over():
            seen = {ch.move for ch in node.children}
            m = random.choice([m for m in s.moves() if m not in seen])
            p = s.to_move; s.play(m)
            node.children.append(Node(m, node, p)); node = node.children[-1]
        # Simulate
        while not s.over():
            s.play(random.choice(s.moves()))
        # Backpropagate
        while node:
            node.N += 1
            if node.just_moved: node.W += s.result(node.just_moved)
            node = node.parent
    return max(root.children, key=lambda ch: ch.N).move

The four phases are the same as in MCTS. Two lines changed: selection filters by legality in the current world, and the bonus uses avail instead of the parent's visits.

Step 4: measuring it on the card game#

Each comparison below plays 300 deals twice, with seats swapped, so luck of the deal cancels. Every agent gets 1,000 iterations per move. Scores are the first agent's mean (win 1, tie 0.5); with 600 games the standard error is about 0.02.

def match(a1, a2, games, seed=0):
    """Play each deal twice with seats swapped. Return a1's mean score."""
    random.seed(seed); total = 0.0
    for g in range(games):
        deal = Tricks()
        for swap in (False, True):
            s = deal.clone()
            while not s.over():
                agent = (a1 if s.to_move == 1 else a2) if not swap else (a2 if s.to_move == 1 else a1)
                s.play(agent(s))
            total += s.result(2 if swap else 1)
    return total / (2 * games)

This is the honest result: on this game, ISMCTS and PIMC are indistinguishable. The game has four tricks and almost no decisions where the right card depends on a guess that must be made the same way across worlds, so strategy fusion has little to bite on. The cheating row measures how much hidden information is worth here at all: seeing every card buys about 0.04. Games with bidding, bluffing, or long trick sequences, like the full card games studied by Cowling, Powley and Whitehouse, are where the gap between the two methods opens up. The CoinGuess result shows the mechanism; the card game shows that a mechanism is not always a margin.

What SO-ISMCTS still gets wrong#

Single-observer ISMCTS fixes strategy fusion for the searching player. It does not fix everything.

• The opponent is modelled as fused. Opponent nodes pool statistics across every guess of the opponent's hand, so the search models an opponent who chooses without regard to its own cards. Multiple-observer ISMCTS, in the same paper, keeps one tree per player to fix this.
• Non-locality remains. Determinizations are uniform over consistent deals. A stronger sampler weights deals by how likely the opponent's observed moves were under each, which is belief inference and the core of modern poker agents.
• Void inference is missing. The sampler above ignores that a player who failed to follow suit is void in it. Rejecting determinizations that violate public voids is a few lines and always worth adding.

What to try next#

1. Build a CoinGuess-style test for any new imperfect-information search. If the agent gambles, it is fusing strategies.
2. Add void tracking to determinize, and remeasure all four matchups.
3. Grow the game (six-card hands, a trump suit, a bid before play) and find the size at which ISMCTS starts beating PIMC by more than two standard errors.
4. Replace the avail term with the parent's visit count and measure what changes; in this game, check how often a rarely legal card is selected first.
5. Implement multiple-observer ISMCTS and play it against the single-observer version.
6. For games where the opponent adapts, the next question is not search but training; see self-play and the arms race.