Mastermind, against Knuth.

Every secret at once

The strategy is deterministic, so it is a decision tree. Build the whole tree and you know how many guesses it needs for every one of the 1296 secrets.

Note

Mordecai Meirowitz, an Israeli postmaster and telecoms engineer, designed the board game in 1970. Seven years later Donald Knuth published a short paper showing that four pegs and six colours can always be broken in five guesses. His strategy is short enough to fit in this page's script.

Keep a set S of every code that agrees with all the clues so far. For each of the 1296 codes you could play next, sort S into buckets by the clue that code would get back from each member of S. The biggest bucket is how many codes could survive in the worst case. Play the code whose biggest bucket is smallest. Ties go to a code still in S, because that one might win outright, and then to the lowest code in numeric order. The opening is fixed at 1122: its worst bucket holds 256 codes, the best any opener can do.

The chosen guess is often a code that cannot be the secret. In the player mode, Ask Knuth sometimes proposes exactly that, and it is not a mistake. A guess that splits the survivors evenly is worth more than a long shot at winning on the spot. Watch the bits readout: an even split into many buckets is what earns them.

Minimax is not the best average. Knuth's tree averages 5801/1296, about 4.476 guesses. In 1993 Kenji Koyama and Tony Lai searched exhaustively and found a strategy averaging 5625/1296, about 4.340, though it needs six guesses for one secret. If you hold it to five, the best possible is 5626/1296.

I wrote the tree builder before the copy and checked the figures above against what it printed. The button above runs the same code in your browser, so you can check them too.