Rollouts and policy iteration

The technique

Judge a move by playing it out with some ordinary policy many times and averaging; then use that judgement to improve the policy, and repeat.

Read the primer

Approaches using this technique

10 approaches, featured pages first. Each card is one theory of how to choose a column and what happened when it was tried.

Rollouts and policy iterationfeatured

Public rollout policy iteration

The cheap version uses fifteen shared futures of fifty moves for one improvement step over a simple search.

rejectedrecorded

Rollouts and policy iterationfeatured

Rollout veto

Keep the depth-4 search's move unless replaying every column forward for twenty-five moves says, across all seven imagined futures, that another one is better.

recorded

Rollouts and policy iteration

Judging a move by playing the game out

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.

rejectedrecorded

Rollouts and policy iteration

Letting a long look-ahead overrule the search

Plays every candidate 25 moves forward and overrides the reference only when one column is clearly better.

rejectedreproduced

Rollouts and policy iteration

Public regenerative B0

Eliminate weak columns cheaply, test the survivors against the reference, and override it only with strong evidence.

rejectedrecorded

Rollouts and policy iteration

Public survival rollout

Judge each column by survival over thirty-one shared futures of one hundred moves each.

rejected

Rollouts and policy iteration

Rollout

Judge a column by playing twenty-five more moves under several imagined disc streams instead of scoring only the resulting board.

rejected

Rollouts and policy iteration

Structural terminal veto

Keeps the four-move search in charge unless a long simulation favors its second choice. Two independent tests still finished behind the unchanged search.

rejected

Rollouts and policy iteration

Terminal policy iteration

The full-strength version uses 255 shared futures of 200 moves and changes the reference move only with 99% confidence in both score and lifetime gains.

rejected

Rollouts and policy iteration

Terminal rollout

Compare columns by playing each one to the end of the game. This faithful version was unaffordable.

Agent contextApproach directories in this group, by family

constructive-reservoir

approaches/constructive-reservoir/structural-terminal-veto

d4-long-outcome

approaches/d4-long-outcome/rollout-veto

fair-expectimax

approaches/fair-expectimax/rollout-improvement

heuristic-search

approaches/heuristic-search/rollout

lifetime-objective

approaches/lifetime-objective/rollout-veto-17k

terminal-policy-iteration