Clever ways to solve Mastermind?
Is there any specific way to solve Mastermind?
Apart from the first step that is pure chance, is there any way to continue based on the colors that you think are correct?
Are you asking for a practical solution for actual gameplaý, or the optimal algorithm for programming? They are not necessarily the same, since e.g. the application of minimax for a set of 1296 codes is not trivial to perform in your head.
Wikipedia has the nice section on optimal Mastermind strategies:
In 1977, Donald Knuth demonstrated that the codebreaker can solve the pattern in five moves or fewer, using an algorithm that progressively reduced the number of possible patterns. The algorithm works as follows:
- Create the set S of 1296 possible codes, 1111,1112,.., 6666.
- Start with initial guess 1122 (Knuth gives examples showing that some other first guesses such as 1123, 1234 do not win in five tries on every code).
- Play the guess to get a response of colored and white pegs.
- If the response is four colored pegs the game is won, the algorithm terminates.
- Otherwise, remove from S any code that would not give the same response if it (the guess) were the code.
- Apply minimax technique to find a next guess as follows: For each possible guess, that is, any unused code of the 1296 not just those in S, calculate how many possibilities in S would be eliminated for each possible colored/white peg score. The score of a guess is the minimum number of possibilities it might eliminate from S. From the set of guesses with the maximum score select one as the next guess, choosing a member of S whenever possible. (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 member of S will be among the highest 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.
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 found a method that required an average of 5625/1296 = 4.340 turns to solve, with a worst-case scenario of six turns. The minimax value in the sense of game theory is 5600/1296 = 4.321.
MathWorld's page on Mastermind also gives a nice synopsis and mention a few more strategies:
Knuth (1976-77) showed that the codebreaker can always succeed in five or fewer moves (i.e., knows the code after four guesses). His technique uses a greedy strategy that minimizes the number of remaining possibilities at each step, and requires 4.478 guesses on average, assuming equally likely code choice. Irving (1978-79) subsequently found a strategy with slightly smaller average length. Koyama and Lai (1993) described a strategy that minimizes the average number of guesses, requiring on average 4.340 guesses, although may require up to six in the worst case. A slight modification also described by Koyama and Lai (1993) increases the average to 4.341, but reduces the maximum number of guesses required to five.
Swaszek (1999-2000) gives an analysis of practical strategies that do not require complicated record-keeping or use of a computer. Making a random guess from the set of remaining candidate code sequences gives a surprisingly short average game length of 4.638, while interpreting each guess as a number and using the next higher number consistent with the known information gives a game of average length 4.758.
In summary, there is a trade-off to make between the average length and the maximum length of the game. (length is expressed in the number of code guesses)
Do you know if research has been done as to the optimal strategy for a code-maker who knows the code-breaker's strategy, and what strategy would have the best average length against the most vexing code-maker?