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?

-

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 maximum number of possibilities it might eliminate from S. From the set of guesses with the minimum 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)

-

I play Mastermind with numbers instead of colours, because I first learned it in the second grade as Bagel Pico Fermi which uses numbers. For the rest of my answer, I will refer to red pegs as "bagels", and white pegs as "picos" (and holes without pegs as "fermis").

The system I tend to use is suboptimal but very easy to follow. It goes as follows:

1. Start with 0000. You can never get picos if all digits are the same, only bagels.

• If the secret number was 0187, then you will get one bagel and three fermis.

• If the secret number was 2966, then you will get four fermis and you know that 0 is not in the secret number at all.

2. If there are any bagels with 0000, include that many 0's in your next answer, and replace the rest with 1's.

• If the secret number was 0187, then you'd keep one of the 0's in your answer, and guess 0111 next, getting two bagels.

• If the secret number was 2966, then you'd guess 1111 next, getting four fermis again.

3. Keep increasing the extra digits by 1. Those digits are "background digits", while the digits that you've kept the same should never change values and are "foreground digits".

However many more pegs there are when you change the background digits, that many background digits then become foreground digits.

4. Eventually you'll get to a point where you have a total of four pegs. If you have four bagels, congratulations, you have the right answer. But if some of them are picos, then some of them are in the wrong order. At this point, just try rearranging them, paying attention to whether your arrangement matches the number of switched digits in each of your previous guesses.

An example of this algorithm at work might be as follows:

Secret number: 4034
Every round there are A bagels and B picos.

[BG digit: 0] 1. 0000  1A0B  (so there's one 0)
[BG digit: 1] 2. 0111  0A1B  (so there's no 1's, and the 0 is in the wrong place)
[BG digit: 2] 3. 2022  1A0B  (so there's no 2's either, but we know where the 0 is now)
[BG digit: 3] 4. 3033  2A0B  (so there's one 3, because A+B increased by 1)
[BG digit: 4] 5. 3044  2A2B  (you now have all the numbers, just not in the right order)
[BG digit: -] 6. 4043  2A2B  (the switch didn't work, try another one)
[BG digit: -] 7. 4034  4A0B  (you win!)


This isn't as good as the algorithm that a computer would use, but it's very simple and systematic, and very easy to get the hang of once you understand what you're doing.

-

A simple strategy which is good and computationally much faster than Knuth's is the following (I have programmed both)

Create the list 1111,...,6666 of all candidate secret codes

Repeat the following 2 steps:

1) After you got the answer (number of red and number of white pegs) eliminate from the list of candidates all codes that would not have produced the same answer if they were the secret code.

2) Pick the first element in the list and use it as new guess.

This requires in general no more than 5 guesses.

This is the Swaszek (1999-2000) strategy that was mentioned in another answer.

-

It may not be the fastest technique, but I generally take the trivial solution of starting with a row with all one color. This tells me how many of that color exist in the solution.

If none, I simply move on to another color. If one or more match, I leave that many of the color and move on to the next color for the remaining spaces. Using this technique it will determine the exact set of colors within 6 moves, but not the order.

While I am working on that technique, I also start working on determining position by swapping positions to rule out possible positions for each color. This is where the technique I use gets a bit more complicated.

I look carefully at the previous combinations and select combinations that will eliminate positions for certain colors based on whatever output I get, for example, placing colors I know are not present (or already know the position of) to blank portions of the board. For each color I lock in, the number of possible guesses is reduced on future guesses.

If possible, I will also try solving more than one peg simultaneously by leaving one in place and moving the other. If I don't lose a black peg, then I know that the one I didn't move was correct, if I gain a black peg, I know that both are correct. If I lose a black peg, I know that the one I moved was correct.

Using this technique, I can reliably win pretty much any mastermind game, though I do sometimes use most of my guesses, so it isn't the most efficient solution out there.

-