Expectimax search

The technique

When some of what happens next is your choice and some is luck, look ahead by taking the best of your options and the average of luck's.

Read the primer

Approaches using this technique

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

Expectimax searchfeatured

Fair expectimax reference (D3/D4)

The reference search looks four moves ahead, averages the sampled chance outcomes, and uses a hand-tuned board evaluator at the bottom.

completedrecorded

Expectimax searchfeatured

Separate reveal and next-disc sampling

Separates next-disc and hidden-value samples inside search. The change is worth about one extra move of look-ahead.

completedreproduced

Expectimax search

Exact search

Three attempts add independent chance estimates, depth, and voters to a search. None repairs a biased board evaluation.

rejectedrecorded

Expectimax search

Looking five moves ahead

Three attempts add a fifth move for selected columns, at row rises, or with fewer chance samples. None paid off.

rejectedrecorded

Expectimax search

Seven chance samples instead of five

The next disc has seven equally likely values, but the reference samples only five. This tests all seven.

rejectedrecorded

Expectimax search

Sparse expectimax

Look several moves ahead, but instead of considering every disc the game might deal, take a small fixed handful of representative ones, and always finish the depth you promised.

completed

Expectimax search

Turning the reference search's constants into dials

Makes death penalty, search depth, and chance samples configurable to test which settings improve survival.

completedreproduced

Agent contextApproach directories in this group, by family

fair-expectimax

heuristic-search

lifetime-objective