Editing Mastermind (board game) (section)

===Best strategies with four holes and six colors===
With four holes and six colors, there are 6<sup>4</sup> = 1,296 different patterns (allowing duplicate colors but not blanks).

====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.

====Average case====
Subsequent mathematicians have been finding various algorithms that reduce the average number of turns needed to solve the pattern: in 1993, Kenji Koyama and Tony W. Lai performed an exhaustive [[depth-first search]] showing that the optimal method for solving a random code could achieve an average of {{nowrap|5,625/1,296 ≈ 4.340}} turns to solve, with a worst-case scenario of six turns.<ref>{{Cite journal | last1 = Koyama | first1 = Kenji | last2 = Lai | first2 = Tony | title = An Optimal Mastermind Strategy | journal = Journal of Recreational Mathematics | issue = 25 | pages = 230–256 | year = 1993}}</ref>

====Minimax value of game theory====
The minimax value in the sense of game theory is {{nowrap|5,600/1,290 ≈ 4.341.}} The minimax strategy of the codemaker consists in a [[Discrete uniform distribution|uniformly distributed]] selection of one of the 1,290 patterns with two or more colors.<ref>{{cite book |first=Donald |last=Knuth |title=Selected papers on fun and games |publisher=Center for the Study of Language and Information |year=2011 |isbn=9781575865843|page=226}}</ref>