Clever ways to solve Mastermind?

Question

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?

Answer 1

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:

1. Create the set S of 1296 possible codes, 1111,1112,.., 6666.
2. 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).
3. Play the guess to get a response of colored and white pegs.
4. If the response is four colored pegs the game is won, the algorithm terminates.
5. Otherwise, remove from S any code that would not give the same response if it (the guess) were the code.
6. 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.)
7. 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)

Answer 2

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.

Answer 3

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

Start with 1122.

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 averages no more than 5 guesses.

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

Answer 4

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.

Answer 5

I made a custom strategy for solving with the original rules - 6 colors and 4 pegs code length with 10 guesses allowed. My solution is guaranteed to solve in 9 guesses.

Suppose the colors are red, green, yellow, orange, purple, and violet. Start by putting 1 color in the first 2 holes then another color in the second 2 holes.

Example - RRGG

Now make another guess with 2 colors that haven't been used the next guess must follow the same pattern. So after 3 guesses we will have used all the colors. So in my solution the first 3 guesses would go something like this:

guess 1 - YYOO
guess 2 - GGVV
guess 3 - RRPP

Up until now we have ignored the clue pegs - the first 3 guesses always use the same pattern. Now here's where things get a little complicated.

Our goal is to figure out what colors the first 2 pegs of the code are and what color the other 2 pegs are. I call these the front and back pegs respectively. After that we can settle the final positions in at most 3 guesses. So after making the guesses above take the guess marked with the most clue pegs (if it is a tie you can choose) and replace the back pegs with a color you know is NOT in the code then make this your new guess. Now there are 2 ways find a color not in the code. If one of the first 3 guesses has no clue pegs then none of those colors are in the code. The second method requires making a guess. If the first 3 guesses all have clue pegs choose the guess marked only by one clue peg - this is always possible! Now choose a color in that guess and simply repeat it. Now note the clue peg if there is none that color is not in the code otherwise if you still get a clue peg then the other color is not in the code. Now you can continue. Since this sounds more complicated then it is I will show examples from playing against the computer. The colors the computer uses are: blue,green,orange,purple,red,yellow. Bu stands for blue.

example 1

guess 1 - BuBuGG; no clue pegs
guess 2 - OOPP; no clue pegs
guess 3 - RRYY; 2 black 0 white
guess 4 - RRBuBu; 2 black - this is guess 3 with the last 2 holes replaced with a color not in the code.
guess 5 - RRRR; solved

example 2

guess 1 - BuBuGG; 0 black 1 white
guess 2 - OOPP; 0 black 2 white
guess 3 - RRYY; 0 black 1 white
guess 4 -BuBuBuBu; 1 black 0 white - here we are looking for a color not in the code. We could have modified guess 3 but did guess 1 instead. So we now know 1 blue peg is in the code and if we look at guess 1 we see it must go in one of the back 2 holes. So what we have of the code so far is: xxBux The x means the other pegs are unknown yet. Note that we simply stuck blue in one of the last 2 holes it's position may not yet be settled.

guess 5 - OOGG; 0 black 0 white - Since guess 2 has the most clue pegs we modify it by putting green in the last 2 holes. Green is used because we know it is not in the code. From this we can see that orange is not in the code either. If we look back at guess 2 we can alse there are 2 purple pegs and that both must go in the front 2 holes. So now the code is: PPBux Looking at guess 3 the final color must be red. The clue tells 1 peg is out of position. Since the code has only 1 spot left in the back the missing peg must be red. So now we have: PPBuR which is used as our next guess.

guess 6 - PPBuR solved - if we had gotten 2B 2W it would have been PPRBu

example 3

guess 1 BuBuGG; 2 black 0 white
guess 2 OOPP; 1 black 0 white
guess 3 RRYY; 0 black 1 white
guess 4 OOOO; 1 black 0 white - code so far is Oxxx
guess 5 BuBuPP; 1 black 0 white - code so far is OBuGR Guess 5 tells us there is 1 blue peg in the code and that it must go in front. Looking at guess 1 the other black clue peg must refer to green telling us that it goes in back. Guess 3 tells us red must go in back.
guess 6 OBuGR; 0 black 4 white
guess 7 BuORG; solved

Important! In the end game there are different ways to settle the final positions of the pegs. Once you know what pegs go in the front and back there is a pattern you can follow:

PRGY; 2 black 0 white
PRYG; 4 black 0 white
RPGY; solved

Basically if you get 4 white swap the front 2 pegs then the back 2 pegs as shown above. If you get 2 black swap the pair in the back and that will either solve or give you 4 white.

Answer 6

I think it is possible to solve all puzzles (of four unique colors) at five tries. The best way to start is picking red, green, blue, yellow. Then simply stick to those colors, starting with red... say you get three white markers after the first round, simply keep red, green, blue, but move all of them one space to the right, and fill in the last space (space #1) with the first of the remaining colors, brown. Continue doing this, systematically, and you will hit the right code within five tries.