Editing Mastermind (board game) (section)

====Worst case: Five-guess algorithm====

In 1977, [[Donald Knuth]] demonstrated that the codebreaker can solve the pattern in five moves or fewer, using an algorithm that progressively reduces the number of possible patterns.<ref>{{Cite journal |url = http://www.cs.uni.edu/~wallingf/teaching/cs3530/resources/knuth-mastermind.pdf | author-link = Donald Knuth | last = Knuth | first = Donald | title = The Computer as Master Mind | journal = J. Recr. Math. | issue = 9 | pages = 1–6 | year = 1976–1977 | archive-url = https://web.archive.org/web/20160304020808/http://www.cs.uni.edu/~wallingf/teaching/cs3530/resources/knuth-mastermind.pdf | archive-date = 4 March 2016 | url-status = live }}</ref>
Described using the numbers 1–6 to represent the six colors of the code pegs, the algorithm works as follows:

# Create the set {{mvar|S}} of 1,296 possible codes {1111, 1112, ... 6665, 6666}.
# Start with initial guess 1122.<!--- Knuth specifically uses 1122 here --> (Knuth gives examples showing that this algorithm using first guesses other than "two pair"; such as 1111, 1112, 1123, or 1234; does not win in five tries on every code.)
# Play the guess to get a response of colored and white key pegs.
# If the response is four colored key pegs, the game is won, the algorithm terminates.
# Otherwise, remove from {{mvar|S}} any code that would not give that response of colored and white pegs.
# The next guess is chosen by the [[minimax]] technique, which chooses a guess that has the least worst response score.  In this case, a response to a guess is some number of colored and white key pegs, and the ''score of a response'' is defined to be the number of codes in {{mvar|S}} that are still possible even after the response is known.  The ''score of a guess'' is pessimistically defined to be the worst (maximum) of all its response scores.  From the set of guesses with the best (minimum) guess score, select one as the next guess, choosing a code from {{mvar|S}} whenever possible.  (Within these constraints, Knuth follows the convention of choosing the guess with the least numeric value; e.g., 2345 is lower than 3456. Knuth also gives an example showing that in some cases no code from {{mvar|S}} will be among the best scoring guesses and thus the guess cannot win on the next turn, yet will be necessary to assure a win in five.)
# Repeat from step 3.