Observable-state MCTS

The problem

There is a cheap way to plan under uncertainty that does not work. Guess the whole future in advance: every disc the game will deal, every hidden gray number it will show. Then plan perfectly inside that imagined future, and average the results over many guesses. Each individual plan looks brilliant, because each was made by a planner who already knew the answers. Averaging brilliant plans that could never have been made by the same player produces a number that flatters the first move and cannot be achieved by anybody. The ledger calls this failure strategy fusion; the glossary entry is determinization.

Monte Carlo tree search (MCTS, primer) grows its look-ahead by simulation instead of enumerating every branch, and the usual way to run it in a game with hidden information is the guess-the-future scheme above. The question for this page was whether the search could be built so that it never gets the opportunity.

Proposed solution

Identify a position in the tree by the visible board, the visible next disc, the moves left until the next rise, whether the game is over, and how much search horizon remains, and by nothing else. No game seed, no future disc sequence and no hidden number is stored in a node or passed to any decision. A chance outcome is drawn only when the search crosses that event for the first time, and later decisions along that line see only the visible position that resulted. Because one policy has to work across all the futures, it cannot specialise to any of them.

How it works

1. Read the public position: board, next disc, rise clock, terminal flag.
2. Run many simulations. Each one walks down the stored tree preferring columns with good recorded results and a bonus for the least-tried ones, adds one new position where the walk leaves the tree, finishes the line with a cheap one-move-ahead fair search out to a fixed horizon, and credits every column choice on the path with the result.
3. Draw chance outcomes lazily. The first few times an action edge is crossed, sample a fresh outcome and keep it in a small per-edge pool; afterwards, replay from that pool. The original lab caps the pool at eight outcomes.
4. Play the column with the best record at the root. In the gated variant, hand the decision back to exact fair search unless the tree's preference clears a fixed confidence rule.

Three programs live here and read as one argument. The first asked whether the idea ranks moves at all, the second whether it can be used safely as an override on top of a search that already works, and the third whether it had been too small.

What happened

All three were rejected, and none ever played a cohort of complete games; every measurement is of how well a search ranks the columns available at stored positions, against labels made by playing those positions forward (ledger; rejected, ledger-recorded).

The plain search almost cleared its bar. On positions it had never seen it ranked pairs of columns slightly better than the exact depth-3 comparator and had lower regret, but its rate of picking the single best column was 11 correct out of 32, and the frozen gate required a rate that 11 out of 32 just misses (historical 7,000-point scoring, archival). Nothing was retuned and no further games were opened, which is the correct behaviour and also why there is no better number to report.

The gated version, allowed to override a working depth-3 search only when it was confident, cut its disagreements from 34 positions to 12 and did improve its top-choice rate, but it got worse at ranking pairs and its regret rose (historical 7,000-point scoring, archival). A rule that switches rarely and is wrong when it switches is worse than no rule.

The scaled version is the informative failure. It was given four times the simulations, twice the horizon, twice the chance pool, and a proper evaluator at the end of each playout, and its labels were recomputed under corrected scoring. Against the four-move reference's own values on the same positions it improved a great deal and became a close imitator of that search. Against what mattered, the outcome twenty-five moves later, it got worse than the small version it replaced. The audit concluded that more search would not fix the remaining failure and that this candidate should not receive a gameplay screen: the cheap one-move-ahead playout policy and the small replayed pool of chance outcomes were optimising the wrong future, and a bigger budget buys more of the wrong future.

What we learned

A sampling search can preserve the information boundary. That is an engineering result in its own right: nodes keyed only by the visible position, self-tests for determinism, reflection, metadata blindness and legality, and hard arena bounds that were never exhausted.

Ranking well against a short-horizon teacher and ranking well against the future are different skills. The scaled audit measured both at once and they moved in opposite directions, which is the sharpest version of the lesson on the sibling ranking page.

What was ruled out is this configuration: a one-move-ahead playout with a small replayed chance pool, at every budget tested. Monte Carlo tree search in this game was not ruled out. The open question, and the ledger's own recommendation, is whether a separately frozen long-horizon value or playout replacement, with unbiased sampling of fresh chance events, ranks the future better than the exact search does.

Agent contextRecords and provenanceopen ↓close ↑

• Ledger sections in docs/research/history.md: "Observable-state stochastic UCT (rejected at held-out gate)", "Confidence-gated MCTS over fair depth 3 (rejected)", and "Scaled public-state observable MCTS (rejected before gameplay)". The tree-search table in the experiment index carries the confidence-gated row: rejected, ledger-recorded, "held-out pairwise accuracy and regret worsened."
• Plain search (observable-mcts-lab.cpp): tuning on 64 roots from 32 origin games 0x3da00000...1f; held-out 32 roots from 16 disjoint games 0x3da10000...0f; the 0x3e990000...03 screen and 0x3e9a0000...07 confirmation were not read.
• Gated search (fair-mcts-confidence.cpp): fitting on 64 move-12/24 roots from 32 fair-policy origin games 0x3db00000...1f; held-out 32 roots from 16 origin-disjoint games 0x3db10000...0f; the 0x3e9f0000...07 screen and 0x3ea00000...0f confirmation were not read.
• Scaled audit (observable-mcts-scaled-audit.cpp): a ranking-only architecture audit that opened no gameplay seed and reconstructed no origin game; it replayed 36 already-stored public roots (the fixed middle root of each of 24 fitting and 12 disjoint held-out games from the public long-outcome corpus) and recomputed fair depth-3 and depth-4 values under corrected scoring. The original lab source is unchanged.

Agent contextFull results tableopen ↓close ↑

Observable-state stochastic UCT, rejected at the held-out gate (historical 7,000-point scoring, archival). Tuning used 64 roots from 32 origin games with independent 32-scenario labels and 60-move public depth-1 continuations, over all twelve combinations of 256/1,024/4,096/16,384 simulations and horizons 8/16/32; the preregistered minimum-regret rule froze 16,384 simulations and horizon 32. On 32 roots from 16 disjoint games it reached 0.6498 pairwise accuracy and 28,420 mean regret versus exact depth 3's 0.6418 and 44,142, but top-1 accuracy was 11/32 = 0.34375 against a 0.35 gate; the next attainable result was 12/32 = 0.375. Maximum active storage was 7,876,784 bytes against a fixed 8,257,960-byte reservation, with at most 15,486 nodes and 16,384 sampled outcomes.

Confidence-gated MCTS over fair depth 3, rejected (historical 7,000-point scoring, archival). Fitting used 64 roots from 32 origin games, each sibling evaluated on 64 aligned 80-move public fair-depth-1 continuations. The frozen thresholds were a Q margin of 3.2 and a visit-share margin of 0.8. Raw MCTS disagreed with fair depth 3 on 34 of 64 fitting roots and the gate reduced that to 12, but fitting regret was still worse than fair (29,783.74 versus 25,848.30). On the one allowed held-out set (32 roots from 16 origin-disjoint games) the gate switched six actions: tie-aware top-1 rose from 0.28125 to 0.34375, pairwise accuracy fell from 0.58742 to 0.54755, and regret rose from 28,165.14 to 32,443.13. Raw MCTS alone was weaker still at 0.21875, 0.51994 and 41,105.89.

Scaled public-state observable MCTS, rejected before gameplay (corrected 17,000-point scoring). The candidate was frozen before any ranking at 65,536 simulations, horizon 64, a 16-outcome reservoir, the same depth-1 playout and one public fair leaf at a surviving cutoff. On the 12 held-out roots, against corrected 25-move labels:

Predictor	Top-1	Pairwise	Normalized regret
Old observable MCTS	25.00%	61.02%	0.29450
Scaled candidate	25.00%	56.78%	0.37251
Exact public fair D3	25.00%	57.63%	0.35712
Exact public fair D4	33.33%	55.93%	0.36314

Both six-game held-out halves lost pairwise accuracy and the second more than doubled normalized regret, from 0.13592 to 0.29193, so the frozen gate failed and no fresh, protected, or final seed was opened. The diagnostic contrast: measured against corrected fair-D4 root values on the same states, scaling raised top-1 from 66.67% to 91.67%, pairwise from 66.10% to 74.58%, and cut normalized regret from 0.03896 to 0.00356. The audit ran in 550.296 seconds within a 47,710,856-byte fixed arena.

Agent contextValidity, gates and limitationsopen ↓close ↑

• The held-out sets are 32 and 12 roots. Both are small, and the 12-root table separates predictors by a single root in places.
• All three programs are root-ranking measurements against labels made by playing stored positions forward; none is a whole-game score, and no cohort of complete games was played.
• Self-tests (strict -Werror and ASan/UBSan builds) covered deterministic decisions and Q values, reflection, metadata blindness, chance-boundary equivalence, exact-depth-3 fallback parity, depth-1 rollout parity, legality, reservoir bounds, and arena bounds. No search exhausted its arena: the lab's fixed 8,257,960-byte reservation sat under a 32 MiB cap and the scaled audit's 47,710,856-byte arena under a 128 MiB cap.
• The ledger's recommendation after the scaled audit: a separately frozen long-value or playout replacement and unbiased sampling of fresh chance events, and no further budget increase for this design.

Agent contextScoring modeopen ↓close ↑

observable-mcts-lab.cpp and fair-mcts-confidence.cpp carry a compile-time assertion pinning the historical 7,000-point Sequence level bonus, so the plain-search and gated-search numbers are historical 7,000-point scoring, archival, and are not comparable with corrected Hardcore results. Only the scaled audit was recomputed at the corrected 17,000-point award; its stored roots and synthetic tape identities are valid, their original Q values predate the correction, and the historical labels and the original MCTS artifact are retained only as explicitly non-comparable provenance.