Tree search

Instead of examining every column to a fixed depth, grow the look-ahead only where it looks promising, guided by quick simulated playouts.

Why anyone would want this

The reference policy in this repository is fair expectimax at depth 4: at every turn it considers all seven columns, then all seven again after the game deals the next disc, and so on for four of the player's own moves. Nothing is skipped. That completeness is what makes it trustworthy, and it is also what makes it expensive: the number of positions at the bottom of the tree multiplies by roughly forty-nine every time you look one move further ahead.

Monte Carlo tree search asks a different question. Rather than how do I cover everything four moves out, it asks where is my next unit of thinking best spent. It plays a future forward quickly, sees roughly how it turned out, records that against the first move it made, and lets that record decide where to look next time. Moves that keep doing well get explored deeply; moves that keep doing badly are visited a few times and left alone. The tree ends up lopsided — very deep along a few lines, one node thick along the rest.

Two consequences follow, and both matter here. A lopsided tree can reach much further ahead than a complete one for the same cost, which is attractive in a game where the thing that kills you — falling behind on clearing discs over dozens of row rises — happens far beyond four moves. But its answer is a sample, not a calculation. Run it twice and it may pick differently; run it with a bad quick-playout policy and it will confidently rank moves by a future no good player would ever have.

How it works, step by step

At a turn, the search reads only what a player can see: the visible board, the visible next disc, the number of moves until the next rise, and whether the game is over. Its output is one column. In between, it repeats one loop a few hundred to a few thousand times:

1. Select. Walk down from the current board, at each step preferring the column whose recorded results are best, with a bonus for columns that have been tried least. That bonus is the only thing stopping the search from falling in love with the first move that worked.
2. Expand. When the walk reaches a position the tree has not stored yet, store it.
3. Play out. From there, finish the line with a cheap policy — in this repository usually a one-move-ahead fair search — until a horizon is reached, and score whatever happened.
4. Back up. Add that result to every column choice on the path, so the next walk is a little better informed.

After the last repetition, play the column with the best record at the root.

The part that is specific to Drop7

Between your move and your next move, the game does two things you cannot predict: it deals a disc, and, if your move cracked a gray disc open, it shows you a number that was hidden. A tempting shortcut is to guess all of that in advance — imagine a complete future, plan perfectly inside it, and average over many such imagined futures. That shortcut is called determinization, and it quietly cheats: it credits a first move with a plan that could only have been made by someone who already knew the hidden number. The ledger calls that failure strategy fusion, and the family's main implementation avoids it by sampling each chance event only at the moment the search actually crosses it, and by identifying tree nodes purely by the visible position that resulted. See choice, chance, and looking ahead for how the reference handles the same problem.

What happened

Every member of this family that was tested was retired, and the one that was never tested is still sitting there unrun.

The record shows that the tree machinery worked and the thing it was built on did not. Nodes stayed within their memory budgets, the searches were deterministic and passed their information-boundary self-tests, and one variant genuinely improved on the depth-3 comparator on two of the three quantities it reported, missing only the frozen top-choice gate. But no version ever demonstrated a better whole game, and the most informative experiment in the family found that making the search bigger made it worse at the thing it was being asked to do. Scaling up the number of simulations, the horizon, and the chance sampling turned the search into a much better imitator of the short-horizon reference, while making it a worse predictor of how a position would look twenty-five moves later. The audit's own conclusion was that the weak quick-playout policy and the small replayed pool of chance outcomes were optimizing the wrong future, so the next experiment should replace the continuation, not buy a bigger budget.

A note on the leaderboard

A small Monte Carlo tree search — 400 simulations, a sixteen-move horizon — is registered as a policy in the benchmark playground and plays the scripted rounds on the leaderboard. That is a demonstration you can watch, not evidence. Eight fixed rounds cannot separate policies whose scores are heavy-tailed, and the rounds are visible in the repository, so nothing there is ever used as a research result.

What this taught us, and what is still open

• Budget was not the bottleneck. This is the family's one durable, general lesson, and it was earned by a measurement that went the wrong way: more simulations, a longer horizon, more chance samples, and a proper leaf made long-horizon ranking worse, not better.
• What that leaves open is the continuation policy. Every playout in this family finished with a myopic one-move-ahead policy. A search cannot rank futures better than the player it imagines playing them, and this is exactly the direction strategies.md lists as still worth trying: replace the continuation, not the budget.
• One experiment in this family has simply never been run. The PUCT lab is complete and carries its own frozen gates. Until it is run, "PUCT does not work here" is not something this repository knows.