Fair expectimax
Look a few moves ahead, take the best column on your own turns, and average honestly over every disc the game might deal — no hoping, no fearing.
Look a few moves ahead, take the best column on your own turns, and average honestly over every disc the game might deal — no hoping, no fearing. That is the whole family. The strongest policy this repository has is one of these searches, and every other idea in the project is measured against it.
Why anyone thought this would work
A Drop7 turn is two things glued together: a choice (which of the seven columns) and then chance (which disc is dealt next, and what number a newly opened gray disc turns out to hold). A player who only asks "which column scores the most right now?" is answering half the question.
The alternative is to enumerate: for each column, imagine every disc that could come next, work out the best reply to each, and average. That average is what the search compares. Averaging is not the only attitude available — you could assume the disc you want (optimistic), the disc you fear (pessimistic), or ignore the future (greedy) — and on a real position those four attitudes pick different columns:
table view
| column | Greedy | Optimistic | Fair (expectimax) | Pessimistic |
|---|---|---|---|---|
| 0 | 7 | 162 | 76.1 | 53 |
| 1 | 7 | 162 | 76.1 | 53 |
| 2 | 7 | 162 | 76.1 | 53 |
| 3 | 14 | 169 | 55.3 | 21 |
| 4 | 7 | 162 | 70.6 | 53 |
| 5 | 53 | 99 | 67.6 | 60 |
| 6 | 14 | 169 | 55.3 | 21 |
The repository's first durable conclusion is that the fair attitude is the one that survives contact with a random disc stream: optimistic, worst-case, and tiny reused reveal samples ranked moves incorrectly in measured games (research status). Everything in this family starts from that.
For the ideas behind the figure — choice and chance nodes, depth, strata, leaf evaluator — read the concept page first; the pages here link rather than re-explain.
How the reference search works, step by step
- Read the public position. The visible board, the visible next disc, and how many drops remain before the next row rise. Nothing else: not the seed, not the hidden gray numbers, not the score or the move number.
- Try every legal column at the root. No pruning, no shortlist.
- At each chance point, take a fixed handful of representative outcomes instead of enumerating everything — five of them in the frozen reference. These are the strata.
- Repeat for four of the player's own moves, alternating choice and chance, and stop.
- Score the boards at the bottom with a hand-tuned evaluator that rewards ready-to-fire chain structure and latent potential and penalises height, buried gray discs, low-number clogs, and danger close to a rise. A modelled game over is charged a flat −1,000,000.
- Average back up — best at the player's nodes, mean at chance nodes — and play the winning column.
The search has fixed work and cache ceilings that are proved, at compile time, to be larger than the whole four-move tree, so a played move is always the promised depth rather than a silently truncated one.
What happened
The four-move search (depth 4) beat the three-move search (depth 3) on the recorded comparison, and nothing since has displaced it. On the eight paired games of its confirmation cohort, replayed under corrected Hardcore scoring, it averaged about 400,675 points to depth 3's 235,071 and won seven of the eight games. That is the strongest dependable public-information result here — and it is roughly 40% of the score the project is aiming for.
The technical record
- Reference sources.
approaches/fair-expectimax/reference/fair-only-horizon.cpp(full-width depth 3, five strata) andfair-only-depth4.cpp(the same leaf, four completed plies). Both completed — ledger-recorded in the experiment index. - Depth-4 confirmation, corrected 17,000-point Hardcore scoring (ledger, "Corrected Hardcore scoring replay"): eight-game confirmation, D3 235,071.25 points / 71.0 moves, D4 400,675.25 / 116.375, paired gains +165,604 points and +45.375 moves, D4 winning 7 of 8; neither arm censored at 1,000 moves. The four-game screen: D3 318,528.75 / 93, D4 399,951.75 / 115.
- Cost. The depth-4 confirmation used 1,351,112.6 logical work units per move and ran at 0.744 moves per aggregate game-second; peak resident memory 30,441,472 bytes.
- Original 7,000-point figures. The same trajectories were first recorded under the historical Sequence scoring (D3 102,571.25, D4 176,925.25). The replay changed no decision — identical move counts — so those sections are archival, not separate evidence.
- Broad reference cohort. 308,295.578 points and 90.031 moves over 64 games, recorded once in the ledger inside the regenerative expert-iteration experiment. Evidence: ledger-recorded, cohort unidentified.
- Full context: experiment ledger, experiment index, strategy landscape.
The variants, and what each one settled
Every page below is one bounded change to the reference search. Most made it worse, which is the useful part: each is a specific configuration ruled out.
| Idea | What changed | Outcome |
|---|---|---|
| The fair leaf | The evaluator itself, and how its coefficients were fitted | Completed; produced the reference weights |
| A rise-cycle residual | Added a phase-throughput term to the leaf | Completed; part of the recovered depth-3 lineage |
| Seven chance samples | Five representative next discs became seven — exact coverage | Rejected in the ledger; an exploratory re-test found the opposite |
| Deeper than four moves | A fifth move, selectively or full width | Two rejected, one stopped by its runtime budget |
| Weighting the downside | Root value became part average, part worst-case | Rejected; score, survival and flow all fell |
| Tuning the leaf on whole games | Eight coefficients optimised, then frozen | Rejected at its fresh screen and at depth 4 |
| The old placement rewards | Restored a one-move policy's landing-geometry terms | Rejected; the geometry was already in the leaf |
| Paying for clears and reveals | Explicit reward per numbered clear or per reveal | Rejected on held-out games after promising fits |
| Stacking a column deliberately | A leaf term for energy stored in a vertical ladder | Cheap probe positive; the transfer to depth 4 failed |
| Playing the position out | Root actions scored by short simulated continuations | Rejected; worse than the one-move policy it improved on |
What this taught us, and what is still open
Fair chance handling matters, and it may still be the binding constraint. The reference search draws five representative outcomes at each chance point, but the next disc has seven equally likely values. An audit measured that, on average, 2.41 of the seven receive zero weight at every node (audit 02). An exploratory experiment then set the count to seven and measured +101,171 points and +27.5 moves over the frozen reference on 64 previously unread games, and found that the fourth move of look-ahead is worth almost nothing at five samples but about 86,000 points at seven (finding 05, development tier, headline arm replicated on two cohorts). That directly contradicts the ledger's own rejection of seven samples; the chance-strata page below sets the two records side by side without resolving them.
Depth is a dial, not a ladder. Every recorded attempt to search a fifth move — selectively, at rise boundaries, or full width with fewer chance samples — lost score, lost survival, or ran out of its time budget. The exploratory work suggests a mechanism: with a biased chance estimator, extra depth propagates the bias rather than the signal.
Bolting rewards onto the leaf keeps failing the same way. Clear rewards, reveal rewards, restored placement terms, vertical-ladder energy and machine-tuned coefficients all fitted well on the games used to select them and regressed on fresh ones. Small fitting cohorts and heavy-tailed scores are a bad combination; one long game can carry a mean.
What is still open. A properly powered corrected-scoring re-test of exact seven-sample chance coverage; whether covered-disc reveals, not the next disc, are now the binding sampling bias; and whether depth 5 pays once the estimator is exact — an in-progress exploratory arm reports it is currently far behind on a partial, admittedly biased sample (finding 15).
Approaches in this family
Let an optimiser adjust eight coefficients of the search's board evaluator by playing complete games, then freeze the winner and test it on games it never saw.
The next disc has seven equally likely values, but the reference search only samples five of them — this asks what happens if it samples all seven.
The hand-written board evaluator every search in this family uses at the bottom of its look-ahead, and the tuning bench its coefficients came from.
An earlier one-move policy scored where a disc landed and what the drop achieved; this puts those rewards back inside the deeper search, then strips them down to the two that seemed most defensible.
Bolt a small extra term onto the board evaluator that cares about where you are in the five-drop cycle before the next row rise — and keep the weights it left behind.
The reference search itself — four moves of look-ahead, honest averaging over chance, and a hand-tuned board evaluator at the bottom.
Score each column by simulating the next eight to twenty-four moves with a fast policy on identical imagined futures, instead of by looking a fixed few moves ahead.
Instead of judging a column by its average outcome, judge it partly by its worst outcomes — and find that the resulting policy dies much sooner.
Three attempts to search a fifth move — for the most promising columns only, only at a row rise, or everywhere with fewer chance samples — and why none of them paid.
Give the search a bonus every time a move clears a numbered disc or exposes a hidden one, on the theory that a policy that keeps the board flowing survives longer.
Reward the search for building columns that are one quiet drop away from collapsing in several waves, and see whether deliberately stored energy makes games longer.