Safe Subgame Resolving in Multiplayer Games
Organizations: Institute for Interdisciplinary Information Sciences, Tsinghua University
Abstract
Poker and other games with hidden information are too large to solve in one pass. Strong systems compute a complete blueprint strategy offline and refine it in real time inside the reached subgame. In 2p0s games, a safety theorem guarantees that subgame resolving never increases how much an adversary can gain by exploiting the resolved strategy relative to the blueprint strategy. With three or more players acting independently, no such guarantee exists yet, and heuristic resolving can increase the profile's best-response gap. We prove the first conditional safety theorem for uncorrelated multiplayer subgame resolving, a post-hoc certificate for any delivered update. The best-response gap of the resolved profile exceeds that of the blueprint by at most four terms. Two concern the resolver: the subgame value the blueprint promised without realizing () and the resolver's subgame solve error (). The other two are the opponents' best-response gains inside the subgame over their promised values () and a structural tax (), which measures how much the players' total utility can change. The tax is zero in constant-sum games, including every rake-free poker variant. Constructions attain each term with equality. On three-player Leduc poker and on Kuhn poker with up to six players, resolving without a certificate raises the gap beyond a small tolerance in 12% to 100% of the updates. The certificate flags every such update and accepts 41% (Kuhn) and 86% (Leduc) of the standard resolving updates. A resolver that keeps the blueprint whenever the certificate exceeds the tolerance delivers no harmful update. The certificate needs only one best-response pass per opponent inside the subgame, so real-time multiplayer solvers that refine a blueprint can attach it as a safety check. Code is available at https://github.com/lbn187/MultiPlayerSolver
Figures & tables
| Game | Resolver | Median | Harmful updates | Accepted at | Accepted at | Resolver gain | Max after gating |
|---|---|---|---|---|---|---|---|
| Kuhn | best response | +0.0620 | 80% | 0% | 5% | +0.0164 | +0.0068 |
| Kuhn | standard gadget | +0.0096 | 29% | 0% | 41% | +0.0082 | +0.0182 |
| Kuhn | belief-corrected gadget | +0.0016 | 20% | 0% | 43% | +0.0087 | +0.0170 |
| Leduc | best response | +0.0000 | 12% | 53% | 80% | +0.0063 | +0.0094 |
| Leduc | standard gadget | +0.0000 | 2% | 47% | 86% | +0.0031 | +0.0135 |
| Leduc | belief-corrected gadget | -0.0000 | 2% | 52% | 87% | +0.0034 | +0.0083 |
| Resolver | Median | Harmful updates | Accepted at | Resolve (s) | Certificate (s) | Exact evaluation (s) | |
|---|---|---|---|---|---|---|---|
| 3 | best response | +0.0509 | 80% | 0% | 0.010 | 0.004 | 0.003 |
| 3 | standard gadget | +0.0097 | 40% | 40% | 0.340 | 0.004 | 0.004 |
| 3 | belief-corrected gadget | +0.0043 | 20% | 60% | 0.340 | 0.004 | 0.004 |
| 4 | best response | +0.0489 | 100% | 0% | 0.080 | 0.048 | 0.048 |
| 4 | standard gadget | +0.0221 | 57% | 43% | 9.82 | 0.062 | 0.057 |
| 4 | belief-corrected gadget | +0.0028 | 43% | 57% | 9.56 | 0.062 | 0.058 |
| Game | Activation term (s) | Margin pass (s) | Full certificate / exact evaluation | Margin pass / exact evaluation |
|---|---|---|---|---|
| 3-player Kuhn | 0.003–0.003 | 0.001–0.002 | 1.34–1.52 | 0.46–0.65 |
| 3-player Leduc | 0.450–0.493 | 0.065–0.075 | 1.01–1.11 | 0.13–0.15 |
| 4-player Kuhn | 0.030–0.041 | 0.015–0.031 | 1.17–1.26 | 0.32–0.64 |
| 5-player Kuhn | 0.745–0.787 | 0.241–0.694 | 0.86–1.12 | 0.20–0.54 |
| 6-player Kuhn | 15.1–17.9 | 4.48–16.5 | 0.76–1.24 | 0.17–0.59 |
| Game | Rake | Max | Max / utility scale | Max |
|---|---|---|---|---|
| Kuhn | 0.0% | 0.0000 | 0.0% | 0.0000 |
| Kuhn | 2.5% | 0.0702 | 1.8% | 0.0010 |
| Kuhn | 5.0% | 0.1381 | 3.7% | 0.0008 |
| Kuhn | 10.0% | 0.2858 | 8.4% | 0.0010 |
| Leduc | 0.0% | 0.0000 | 0.0% | 0.0000 |
| Leduc | 2.5% | 0.0730 | 0.5% | 0.0012 |
| Cached exact (ms) | Local / cached | |
|---|---|---|
| Certificate | Acc. | Acc. |
|---|---|---|
| ( Eq. 1 ) | ||
| ( Corollary 3 ) | ||
| (realized leak) | ||
| (confined bound) | ||
| (sharp tax) | ||
| ( Corollary 6 ) |
Appendix figures & tables11 assets
Supplementary material from the paper’s appendix.
Appendix
| (trunk) | (inside ) | ||
|---|---|---|---|
| Game | Claimed bound | convention | Relative scale |
|---|---|---|---|
| 3-player Kuhn (deck 4) | restricted-support lower bound | ||
| blind Goofspiel | exact (216 profiles) | ||
| blind Goofspiel | exact (13,824 profiles) | ||
| observed Goofspiel | restricted-support lower bound |
| blueprint | pub | , opp. 1 | , opp. 2 | |||
|---|---|---|---|---|---|---|
| cfr200 | b | 2 | -0.432 / -1.097 | -0.386 / -0.102 | -0.432 / -1.097 | -0.386 / -0.102 |
| cfr200 | b | 3 | -0.433 / -0.688 | -0.404 / -0.032 | -0.433 / -0.688 | -0.404 / -0.032 |
| cfr200 | k | 1 | -0.025 / -0.016 | -0.025 / -0.016 | -0.025 / -0.016 | -0.025 / -0.016 |
| cfr200 | k | 2 | -0.023 / -0.027 | -0.037 / -0.006 | -0.023 / -0.027 | -0.037 / -0.006 |
| cfr200 | k | 3 | +0.004 / -0.014 | +0.004 / -0.016 | +0.004 / -0.014 | +0.004 / -0.016 |
| cfr1000 | b | 2 | -0.422 / -0.991 | -0.015 / -0.029 | -0.422 / -0.991 | -0.015 / -0.029 |
| Game | #matched | mean | harmful | mean | |
|---|---|---|---|---|---|
| Kuhn | 0.25 | 56 | +0.0001 | 2% | +0.0020 |
| Kuhn | 0.50 | 56 | +0.0038 | 9% | +0.0040 |
| Kuhn | 0.75 | 56 | +0.0092 | 18% | +0.0061 |
| Kuhn | 1.00 | 56 | +0.0159 | 29% | +0.0082 |
| Leduc | 0.25 | 540 | -0.0007 | 0% | +0.0007 |
| Leduc | 0.50 | 540 | -0.0010 | 1% | +0.0015 |
| Quantity | count |
|---|---|
| replayed updates | 162 |
| violations of | 0 |
| violations of | 0 |
| updates with | 53 |
| updates with | 119 |
| but | 0 |
| Tier | Margin condition | condition | Hits ( ) |
|---|---|---|---|
| 1 (strict) | 0 | ||
| 2 | 0 | ||
| 3 | 0 | ||
| 4 (very loose) | 3 (each with or margin ) |
| Source | Condition | ||
|---|---|---|---|
| Corollary 6 | coefficients of , ( ) | ||
| Fitted (LP) | |||
| Fitted (LP) | |||
| Fitted (LP) | pinned | ||
| Fitted (LP) | pinned (margin-only) | infeasible | |
| Form | Cover | Slack med. / q90 | Acc. / / / | Time (ratio) |
|---|---|---|---|---|
| ( Eq. 1 ) | / | / / / | ms ( ) | |
| ( Corollary 3 ) | / | / / / | ms ( ) | |
| (realized leak) | / | / / / | ms ( ) | |
| (confined bound) | / | / / / | ms ( ) | |
| (sharp tax) | / | / / / | ms ( ) | |
| ( Corollary 6 ) | / | / / / | s ( ) |
| Infosets | Full | Cached exact | , whole tree | , local | Whole tree / cached | Local / cached | |
|---|---|---|---|---|---|---|---|
| ms | ms | ms | ms | ||||
| ms | ms | ms | ms | ||||
| ms | ms | ms | ms | ||||
| ms | ms | ms | ms | ||||
| ms | ms | ms | ms | ||||
| ms | ms | ms | ms |
| ID | Implementation | Theorem convention | Consequence |
|---|---|---|---|
| D-a | Counterfactual action values normalized by the weight sum | aggregates with unnormalized weights | Per-infoset margin signs agree, while cross-infoset aggregation differs |
| D-b | Margin’s Follow-branch valued under the opponent’s own average strategy | Margin valued against the exact subgame best response | Implementation margin optimistic on 33/40 infosets, worst overestimate |
| D-c | Follow-branch evaluated under the gadget-internal measure, which depends on the opponent ordering in the gadget chain (opponents’ gadgets nested one inside the next) | Both branches evaluated under the game-side measure and environment | Measures coincide only when entries follow a public chance node with no trunk actions and the other opponents play Terminate purely (the benchmark families) |
| D-d | Zero-denominator entry infosets fall back to a raw mean (flagged) | Assumes | Such carry weight in |
| D-e | LP defined on the reduced pure-strategy profile table | Same | A literal terminal-history-dependent witness would force on all zero-sum games, contradicting the Kuhn bound |
| D-f | LP constraint is per-edge constant-sum : | Same (constant-sum) | Proofs use only that is constant on the class |
Imperfect-Information Games
Imperfect-information games study strategic decisions when players have private information or cannot fully observe the state or actions.
See all 96 papers