Editing Mastermind (board game) (section)

==Algorithms and strategies==
Before asking for a best strategy of the codebreaker one has to define what is the meaning of "best": The minimal number of moves can be analyzed under the conditions of [[Best, worst and average case|worst and average case]] and in the sense of a [[Minimax#In_zero-sum_games|minimax value of a zero-sum game]] in [[game theory]].

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

===Genetic algorithm===
A new algorithm with an embedded [[genetic algorithm]], where a large set of eligible codes is collected throughout the different generations. The quality of each of these codes is determined based on a comparison with a selection of elements of the eligible set.<ref>{{cite journal |url=https://lirias.kuleuven.be/bitstream/123456789/164803/1/kbi_0806.pdf |last=Berghman |first=Lotte |title=Efficient solutions for Mastermind using genetic algorithms |journal=K.U.Leuven |issue=1 |pages=1–15 |year=2007–2008 |archive-url=https://web.archive.org/web/20140909031305/https://lirias.kuleuven.be/bitstream/123456789/164803/1/kbi_0806.pdf |archive-date=9 September 2014 |url-status=dead }}</ref><ref>{{cite book |author1=Merelo J.J. |author2=Mora A.M. |author3=Cotta C. |author4=Fernández-Leiva A.J. |title=Learning and Intelligent Optimization |chapter=Finding an Evolutionary Solution to the Game of Mastermind with Good Scaling Behavior |series=Lecture Notes in Computer Science |editor1-last=Nicosia |editor1-first=G. |editor2-last=Pardalos |editor2-first=P. |date=2013 |volume=7997 |publisher=Springer |isbn=978-3-642-44973-4 |pages=288–293 |doi=10.1007/978-3-642-44973-4_31 |chapter-url=https://doi.org/10.1007/978-3-642-44973-4_31 |access-date=22 December 2021}}</ref> This algorithm is based on a heuristic that assigns a score to each eligible combination based on its probability of actually being the hidden combination. Since this combination is not known, the score is based on characteristics of the set of eligible solutions or the sample of them found by the evolutionary algorithm.

The algorithm works as follows, with ''P'' = length of the solution used in the game, ''X''<sub>1</sub> = exact matches ("red pins") and ''Y''<sub>1</sub> = 
near matches ("white pins"):
# Set ''i'' = 1
# Play fixed initial guess ''G''<sub>1</sub>
# Get the response ''X''<sub>1</sub> and ''Y''<sub>1</sub>
# Repeat while ''X<sub>i</sub>'' ≠ ''P'':
## Increment ''i''
## Set ''E<sub>i</sub>'' = [[Empty set|∅]] and ''h'' = 1
## Initialize population
## Repeat while ''h'' ≤ ''maxgen'' and |''E<sub>i</sub>''| ≤ ''maxsize'':
### Generate new population using crossover, mutation, inversion and permutation
### Calculate fitness
### Add eligible combinations to ''E<sub>i</sub>''
### Increment ''h''
## Play guess ''G<sub>i</sub>'' which belongs to ''E<sub>i</sub>''
## Get response ''X<sub>i</sub>'' and ''Y<sub>i</sub>''

===Complexity and the satisfiability problem===

In November 2004, Michiel de Bondt proved that solving a ''Mastermind'' board is an [[NP-complete]] problem when played with ''n'' pegs per row and two colors, by showing how to represent any [[one-in-three 3SAT]] problem in it. He also showed the same for ''Consistent Mastermind'' (playing the game so that every guess is a candidate for the secret code that is consistent with the hints in the previous guesses).<ref>{{citation
|last=De Bondt
|first=Michiel C.
|title=NP-completeness of Master Mind and Minesweeper
|publisher=Radboud University Nijmegen
|date=November 2004
|url=http://www.math.ru.nl/onderzoek/reports/rep2004/rep04_18.ps.gz
}}</ref>{{better source needed|reason=This is a compressed pdf file on a university server. As such it is effectively self-published as per WP:RS/SPS.|date=August 2021}}

The ''Mastermind satisfiability problem'' (MSP) is a [[decision problem]] that asks, "Given a set of guesses and the number of colored and white key pegs scored for each guess, is there at least one secret pattern that generates those exact scores?"  (If not, then the codemaker must have incorrectly scored at least one guess.) In December 2005, Jeff Stuckman and Guo-Qiang Zhang showed in an [[arXiv]] article that MSP is NP-complete.<ref>{{Cite arXiv| title=Mastermind is NP-Complete | date=13 December 2005 | first1=Guo-Qiang | last1=Zhang | last2=Stuckman | first2=Geoff| eprint=cs.CC/0512049 }}</ref>{{better source needed|reason=This is a preprint, which means it is not a reliable source as per WP:PREPRINTS.|date=August 2021}}