Skip to content

Seeing the future, assuming the worst, or betting on the odds

Every decision is made before you know what happens next: the opponent has not moved yet, the next apple has not appeared, the next case has not arrived. There are three honest ways to decide anyway, and each one can promise something different. This page shows the three side by side on the same games and the same random seeds, prices each one in wins, and explains how the same three ideas sit under the library's decision runtime.

It is written for evaluators and data scientists who have met the games on Games: one engine, four games. It assumes you know what a probability and a confidence interval are. When you leave you will be able to say, for any player or any production decision, which of the three it is, what its statements are worth, and how to measure what it gives up, with grounded-decision audit.

Three ways to decide without seeing the future

Think of a card player. One player has peeked at the deck. A second plays as if the dealer were cheating against them. A third knows the deck is shuffled fairly and plays the odds. We call these the three information regimes:

Regime What the player knows about the future What it can promise Real player?
clairvoyant the future itself: the opponent's actual next moves, private dice included nothing useful: it is a benchmark, the best any player could have done no
worst-case nothing: it assumes the worst possible future hard guarantees, true for every future ("never loses", "finishes within N moves") yes
probabilistic the distribution of the future (a model of the opponent, "apples land uniformly") high-probability statements ("wins with probability in [0.88, 0.96]") that hold for the model, not for one particular game yes

The worst-case and probabilistic players are online: they decide with current information only. The clairvoyant one exists to answer a question no online player can answer for itself: how much did not seeing the future cost? Every place it appears (the play header, the decision panel, the tables below) it is labelled clairvoyant (benchmark).

How the engine keeps them apart

The rule is enforced by the engine, not by good manners. Each agent declares its regime with a regime attribute (grounded_decision.examples.games.regimes.Regime), and the engine decides what it may see:

flowchart LR
    S[true state<br/>including future randomness] -->|game.observe| O[observation:<br/>no random number generator]
    O --> A[worst-case agent]
    O --> P[probabilistic agent]
    S --> F[Foresight:<br/>true state, the opponent's<br/>actual policy, future events]
    F --> C[clairvoyant agent<br/>benchmark]
  • An online agent's decide receives the game's observation of the state. In snake the apples come from a random number generator stored with the state; the observation leaves it out. A test walks every object an online agent receives in every game and checks that no random number generator can be reached from it: online agents are structurally unable to read the future, not just asked not to.
  • A clairvoyant agent's plain decide raises an error. The engine calls decide_with_foresight instead and hands it an explicit Foresight: the true state, and for each opponent a sealed copy of its policy, private random numbers included, which predicts its next moves without disturbing the real opponent.

Tic-tac-toe: the whole picture, exactly

Tic-tac-toe is small enough that every agent can be exact. Five agents play two opponents, a uniformly random one and a noisy rule of thumb (the textbook win-block-centre-corner rule, but a random square one time in five):

  • minimax (worst-case): keeps the best result the solved game proves against a perfect opponent, and nothing more.
  • expectimax (probabilistic): among the squares that keep that proved result, picks the one with the highest exact chance of winning against a model of the opponent (uniformly random). expectimax_rule uses the noisy rule of thumb as its model.
  • gambler (probabilistic, uninsured): the same as expectimax, but allowed every square, so it bets on the model alone.
  • clairvoyant (benchmark): searches against the opponent's actual future moves.

Every agent plays every one of 100 seeds from both sides, 200 games per row; the interval is an exact 95% Clopper–Pearson interval for the win rate. From make audit-tictactoe:

  agent [regime]                           opponent         games       W/D/L  rate (95% interval)
  minimax [worst-case]                    random             200    178/22/0  win 0.890 [0.838, 0.930]
  expectimax [probabilistic]               random             200    186/14/0  win 0.930 [0.885, 0.961]
  gambler [probabilistic]                  random             200     194/1/5  win 0.970 [0.936, 0.989]
  clairvoyant [clairvoyant (benchmark)]    random             200     200/0/0  win 1.000 [0.982, 1.000]
  minimax [worst-case]                    noisy_rule         200    67/133/0  win 0.335 [0.270, 0.405]
  expectimax_rule [probabilistic]          noisy_rule         200    111/89/0  win 0.555 [0.483, 0.625]
  gambler [probabilistic]                  noisy_rule         200    70/0/130  win 0.350 [0.284, 0.420]
  clairvoyant [clairvoyant (benchmark)]    noisy_rule         200    140/60/0  win 0.700 [0.631, 0.763]

Read it as two prices.

The cost of not seeing the future is the clairvoyant benchmark's win rate minus the best online player's: +0.070 against the random opponent (simultaneous 95% interval [+0.014, +0.121]) and +0.145 against the noisy rule of thumb ([−0.013, +0.297]). Even expectimax_rule, whose model is the opponent's true distribution, cannot know which square the dice will pick this time; only the benchmark can.

The cost of insuring against the worst case is what the worst-case assumption gives up against the opponent you actually face: expectimax_rule beats minimax by +0.220 against the noisy rule of thumb ([+0.058, +0.373]); against the random opponent the difference, +0.040, is too small to separate from zero with 200 games ([−0.056, +0.134]). Both still never lose: the insurance is kept, only the tie-breaking among safe squares changes.

What the insurance buys shows in the gambler row. Dropping it wins a little more against the random opponent it was built for (194 wins against 186), but it loses 5 of those games, loses 130 of 200 against the noisy rule of thumb, and an exhaustive search over every opponent strategy finds a forced loss for it from both sides. minimax, expectimax and expectimax_rule cannot be beaten by any strategy. The clairvoyant agent beats the deterministic rule of thumb every game as X; as O it only draws, and the exhaustive search confirms why: no strategy at all beats the rule of thumb when it moves first.

Checkers: the same search, three views of the opponent's reply

In checkers the three agents run the same 3-ply search and differ only at the opponent's ply: alphabeta (worst-case) assumes the reply worst for it, expectimax (probabilistic) averages over a model (greedy play, random 10% of the time), and clairvoyant (benchmark) asks a sealed copy of the real opponent. Every agent wins almost every game against these opponents, so the table measures how quickly: the share of games won within 50 plies, over 20 seeded openings from both colours. From make audit-checkers:

  agent [regime]                           opponent         games       W/D/L  rate (95% interval)          mean plies  risky moves
  alphabeta [worst-case]                  greedy              40      40/0/0  win in <=50 plies 0.775 [0.615, 0.892]         46.6        0/943
  expectimax [probabilistic]               greedy              40      40/0/0  win in <=50 plies 0.900 [0.763, 0.972]         37.4       26/758
  clairvoyant [clairvoyant (benchmark)]    greedy              40      40/0/0  win in <=50 plies 0.975 [0.868, 0.999]         33.9       65/687
  alphabeta [worst-case]                  noisy_search        40      37/1/2  win in <=50 plies 0.175 [0.073, 0.328]         92.2       0/1853
  expectimax [probabilistic]               noisy_search        40      38/0/2  win in <=50 plies 0.250 [0.127, 0.412]           74      38/1488
  clairvoyant [clairvoyant (benchmark)]    noisy_search        40      40/0/0  win in <=50 plies 0.800 [0.644, 0.909]         45.2       27/915

noisy_search is a 2-ply search that plays a random move one time in four. Against it, seeing the actual replies is worth +0.550 in quick wins ([+0.187, +0.806]): the cost of not seeing the future is large when the opponent's choices are hard to model, and the expectimax model (built for greedy play) does not match this opponent. Against greedy, whose behaviour the model matches, it shrinks to +0.075 ([−0.127, +0.257]).

The risky moves column is what assuming the worst protects against: moves whose guaranteed value in the same 3-ply tree, with the worst reply assumed, falls more than half a man below the best guaranteed value. Alpha-beta makes none, by definition; expectimax makes 26 to 38 over several hundred moves, and wins faster for it, because the model says the punishing reply is unlikely.

Chinese checkers: a proof and a statistic about the same races

The solo race (fill the opposite point alone) has no opponent and no environment randomness, so it isolates the difference between the two kinds of statement. The gated player carries a proof (Chinese checkers): every move strictly lowers a potential, so it finishes within \((R_0 + 1)(H + 1)\) moves, where \(R_0\) is the starting distance to go and \(H\) the number of holes. The same 100 races (seeds 0–99 vary its tie-breaks) also support a statistical statement. From make audit-chinese-checkers:

Solo race, gated player, 100 seeds (tie-breaks): proved (worst-case): finishes within 14762 moves in every race; observed worst 82; statistical (probabilistic): with 95% confidence, 90% of runs: moves to finish ≤ 78.

The proof holds for every race, including ones never run, but is 180 times looser than anything observed. The statistical bound is tight and useful for planning, but it is about the distribution of races (here, of tie-breaks), holds with 95% confidence rather than certainty, and says nothing about the slowest 10%.

Against two-player opponents the gated player's guarantee is about its own progress, not about winning, and it shows: it wins 10 of 16 games against greedy and 1 of 16 against the two-move lookahead player, where expectimax (two own moves deep, averaging greedy-with-noise replies) wins 15 and 8, and the clairvoyant benchmark 16 and 10. With 16 games per row every difference is inside its interval; pass --regime-seeds for more games and narrower intervals.

Snake

In snake the future randomness is in the environment: where the next apple lands. The worst-case players are the proven ones (the grounded cycle player, and a planner whose every plan is certified safe for any apple placement); a probabilistic player chooses among certified plans by the expected distance to the next apple; the clairvoyant benchmark plans through the actual next apples under the seed. The snake section of Games: one engine, four games has its numbers.

The other axis: what the world actually does

A regime is what a player assumes about the future. Whether the assumption is right depends on the game's world: the rule that actually produces the randomness. In the standard games the world is fair (random), which is exactly what the probabilistic players assume. --world changes it without changing any player, so each regime's claim can be tested against a world that breaks the others' assumptions.

random world any other world (kind, static, adaptive adversary, mixture)
worst-case its guarantee holds its guarantee still holds: it assumed nothing
probabilistic its statements hold for this world reported as assumption not met; only its worst-case parts (such as a safety proof) still hold
clairvoyant a benchmark: the seed fixes the future refused when the world reads the player's moves: there is no fixed future to see

The word adversarial belongs to the world: an adversarial world plays against the agent (snake's --world adversarial simulates the actual player and puts each apple where that player needs longest). A worst-case player is one that is safe even then. Snake is the first game with worlds; Who controls the randomness runs every snake player in every world, with real numbers, and shows the cycle proof's bound being attained exactly.

uv run grounded-decision compare snake --agents grounded,probabilistic,greedy_with_tail_check --size 8x8 --world random,adversarial
uv run grounded-decision audit snake --world farthest --size 8x8

The statements, precisely

Clopper–Pearson interval. Out of \(n\) independent games, \(k\) were wins. The 95% interval \([L, U]\) has \(L\) the one-sided 97.5% exact lower bound and \(U\) the one-sided 97.5% exact upper bound on the binomial success probability (from grounded_decision.learn.statistics, the same code that certifies learned settings). With probability at least 95% over the games, the true win rate lies in \([L, U]\).

Price interval. For a difference of two win rates, each interval is taken at level 97.5%; both hold together with probability at least 95% (union bound), so the difference lies in \([L_1 - U_2,\; U_1 - L_2]\).

Quantile bound. Sort \(n\) independent samples \(X_{(1)} \le \dots \le X_{(n)}\) of a measure (moves to finish) and take the smallest order \(k\) with \(P(\mathrm{Binomial}(n, q) \le k - 1) \ge C\). Then with probability at least \(C\), a fraction at least \(q\) of all runs have measure at most \(X_{(k)}\), whatever the distribution (Wilks' tolerance bound; the proof is in the docstring of quantile_bound). With \(q = 0.9\) and \(C = 0.95\), 29 samples are the minimum, and then the bound is the largest sample; with 100 samples it is the 96th.

What these statements do not establish

The intervals are about the distribution the games were sampled from: these opponents and these seeds. They say nothing about a different opponent; the gambler row is what happens when the model is wrong. The clairvoyant rows are not achievable by any real player; they bound what better information could buy.

Auditing single decisions against a stronger oracle

The tables price a whole regime. To see which individual moves cost something, grounded-decision audit replays one match and asks a stronger, slower oracle to judge every decision of one agent: the oracle's best move, the value of both moves, and the regret (oracle value of its move minus oracle value of the move played), in a unit the report names. For tic-tac-toe the oracle is the exact solver and regret is in outcome classes (win 1, draw 0, loss −1). Auditing the rule of thumb as O against the clairvoyant X:

uv run grounded-decision audit tictactoe --agent rule_of_thumb --opponent clairvoyant --seat 1 --no-regimes

Decisions audited: 3
  total regret 1, mean 0.3333 per decision
  agreed with the oracle: 2/3 (P(agrees with the oracle) ∈ [0.09, 0.99] (95%, 3 trials))
  gate overrides: 0

Worst #1: move 4 (O): played O takes square 3 = -1; oracle prefers O takes square 2 = 0 (regret 1)
     X | 2 | 3
    ---------
     4 | O | 6
    ---------
     7 | 8 | X
    note: rule of thumb: takes a corner

The corner the rule prefers walks into a fork; a side square would have held the draw. The gated grounded player never has regret against the solver; the tests check it against random, rule-of-thumb and clairvoyant opponents from both sides.

In checkers the oracle is a deeper alpha-beta search (depth 6 by default, --oracle-depth to change it), so regret is in evaluation points (100 = a man) and measures disagreement with a deeper heuristic search, not with perfect play. make audit-checkers audits the gated player against the depth-6 search: on seed 0 it agrees with the oracle on 90 of 100 decisions, with a total regret of 72 points (under a man over the whole game) and 18 gate overrides. In Chinese checkers the oracle is a 3-own-move race lookahead, and regret is in spaces of distance to go.

--view json prints the audit and the regime table as one line of JSON for further analysis.

What this means for production decisions

The decision runtime is always an online decision-maker: it decides each case with the evidence available at that moment, and never sees the label that arrives later. Its statements come in the two online kinds:

  • Worst-case. A check at trust level proven (see Trust levels and honest limits) holds for every input, like minimax's "never loses". So do the statechart's liveness and safety proofs about a policy.
  • Probabilistic. Settings learned with Learn-then-Test carry a certificate of exactly the kind in the tables above: with probability at least \(1 - \delta\) over the history, the error rate of the settings is at most the target, an exact binomial bound computed by the same code. Like expectimax, it holds for the distribution the history came from; if cases shift, it can fail, which is why the runtime monitors for drift.

There is no clairvoyant decision in production. Its counterpart is hindsight evaluation: once outcomes are known, compare what was decided with what would have been best (the audit above), and use the gap to decide whether better information or a better model is worth its cost.