Approaches

Subgame solving without common knowledge

Can a game-theoretic search that reasons about what the opponent does not know beat determinized search at the same time per move, and how much of that strength survives when the opponent is limited to a small portfolio of strategies?

The mechanism

Expectimax searches each sampled world with full knowledge, so its strategy is fused across worlds the real player cannot tell apart and it never values information. Obscuro (Zhang and Sandholm, 2025) searches instead over an imperfect-information subgame built from a few hundred positions sampled from the searcher's own information set, plus the positions the opponent might believe possible at distance one in the knowledge graph. The searcher's strategy at those distance-one positions is unfrozen and optimised with the rest (KLUSS), the tree grows by one-sided GT-CFR expansion guided by PUCT, and predictive CFR+ solves it with its last iterate. The move is sampled from a purified strategy: at most three actions, and mixing only when the computed strategy is at least as good as the previous turn's estimate. With a material-only leaf that search still scored 55% against the prior state of the art in Fog of War chess, and 82% behind Stockfish's evaluation.

In Stratego the searcher's information set is far too large to enumerate, so the root sample comes from the belief: the counting prior in the first study, the learned belief network afterwards. The opponent's distance-one positions are sampled by drawing the searcher's own hidden pieces as the opponent would see them. Opponent-limited subgame solving (Liu et al., 2023) shrinks the subgame further: OLSS-I weights how the opponent reaches the root by an opponent model, and OLSS-II lets the opponent choose among N whole-game strategies, which with N of one or two was enough in two-player Mahjong.

The plan

  1. kluss-vs-expectimax: a Rust searcher with the hand-written leaf and the counting belief against the 16-world depth-2 expectimax cell at 200 ms and 1 s per move, 200 paired games each.
  2. opponent-portfolio: OLSS-II with a portfolio of greedy, expectimax and the searcher's own policy at two temperatures, N in 1, 2 and 4, against full KLUSS at 50 ms, 200 ms and 1 s.
  3. learned-belief: the belief network as the root sampler for expectimax and for KLUSS, measured by held-out log-likelihood and by paired matches.

Decision rule

The first study promotes the searcher if the per-seed contrast against expectimax has a 95% interval above zero on 200 paired games at a budget of 200 ms or 1 s, with the time per move measured alone on the machine. The portfolio study reports the crossing budget where full KLUSS overtakes OLSS-II; there is no promotion, only the curve. The belief study promotes the learned belief as the default sampler when both its log-likelihood and its paired match against the prior are separated.

What could disprove it

A few hundred sampled positions may not represent an information set of Stratego's size, in which case the equilibrium gap of the subgame stays large and the searcher plays no better than its leaf. The studies record the gap and the sample counts so that a null result names its cause.

Evidence

None yet. The three studies are proposed; each is registered by its agent before a game is played.