Search and decisions

A point in the look-ahead where the player picks a column. Take the best.

A point where the game deals a disc or reveals a number. Take the average. → concept

The probability-weighted average outcome over chance.

A search that takes the best at choice nodes and the average at chance nodes.

Averaging sampled chance outcomes without optimism or pessimism, using only public information. "Fair" does not mean every outcome is enumerated: the reference search averages over a fixed sample of outcomes (its strata), not all possible outcomes.

How many of the player's own moves the search looks ahead.

Considering every legal column at every choice node; no pruning.

A fixed handful of representative outcomes used at a chance node when enumerating all of them is too expensive; "five strata" and "seven strata" are the common settings.

A board at the bottom of the search, and the function that scores it.

The count of leaf evaluations (and similar unit operations) a search performs; this program's fixed currency for comparing cost.

A cache of positions already evaluated, so a position reached by two routes is scored once.

One of the legal columns available at a position, as compared with the others.

The error a planner makes when it imagines a fixed future and then plans as if it had known that future all along, so it "decides" differently in worlds it could not actually tell apart. It is why determinized planners overvalue moves that depend on the covers being right.

Imagining many complete futures with the hidden values filled in, planning in each, and averaging. Reads hidden values, so it is an oracle, not a legal policy. → concept

Monte Carlo tree search: building the look-ahead tree selectively, guided by random playouts.

Playing a position forward to the end (or a horizon) with a quick policy to estimate its value.

Upper confidence bound: a rule for choosing which branch to try next that adds a bonus for branches tried less often, so the search keeps exploring while favouring what has done well.

A UCB rule whose exploration bonus is weighted by a prior probability for each move, so a learned policy steers where the tree grows.