Maximum number of "guesses" in Mastermind

Factual Questions
1

I assume that most of us are familiar with the board game Mastermind. Someone selects a secret code using colored pegs, and you have to guess the code. After every guess, you are given the number of pegs that are in the right position (indicated with black pegs) and the number of letters that are correct, but in the wrong position (indicated with white pegs).

The minimum number of guesses to arrive at the solution is, of course, 1. Is there a mathematical formula that will tell you what the maximum number of guesses would be, given N colours and M positions? To prevent someone from making the same wrong guess over and over (in which case the maximum would be infinity), I’ll postulate that each of your guesses has to be consistent with the information you’ve received from your previous guesses. But I’m not assuming that the codebreaker is trying to use the best algorithm - instead, let’s pretend that I’m trying to take as many turns as possible to break the code.

I’ll also postulate that the code can contain duplicates (pegs of the same color can appear in more than one spot in the code), but “blanks” are not allowed. (Allowing blanks would be the same as adding a color to the possible list of peg colors present in the code.)

Example:

Suppose I allow six peg colours (represented by letters) and the code has four positions. In the sample game listed below, 9 (nine) guesses were needed to find the solution, with each guess being consistent with the information from the previous guesses. (the "b"s and "w"s represent the black and white pegs telling me how many are correct in my guess.)



COLOURS: 6
a b c d e f g

SPOTS: 4

SOLUTION fgfg

9 fgfg  4b 0w - solved
8 gfgf  0b 4w
7 ffgg  2b 2w
6 ffff  2b 0w
5 eeee  0b 0w
4 dddd  0b 0w
3 cccc  0b 0w
2 bbbb  0b 0w
1 aaaa  0b 0w
2

Off-hand I’d say N x 4! or is the maximum theoretical number of turns. N is the number of turns it takes to determine the colors and 4! is naturally the number of ways to arrange those colors. Your method (aaaa, bbbb, cccc, etc) is quite efficient in only needing 6 turns.

Supposed my strategy is abcd, bcde, etc.
abcd gives me 2w and bcde gives me 2w => either a and b are both correct colors or both incorrect.
abcd gives me 2w and bcde gives me 1w => a is correct and e is incorrect.
abcd gives me 2w and bcde gives me 3w => a is incorrect and e is correct.
But unlike your method it is horribly inefficient to pick up duplicates.

3

An upper limit would be ceiling(log[sub]2/sub) = 11. That is, there are 10.3 bits of information to learn, so if you could learn only 1 bit per turn, it would take 11 turns. But, you will likely be forced to learn more than 1 bit per turn…

4

I can improve on OP’s example (which is actually for 7 colours, not 6) from 9 to 10.



COLOURS: 7
a b c d e f g

SPOTS: 4

SOLUTION gfeg

10 gfeg  4b 0w - solved
 9 gegf  1b 3w
 8 ggfe  1b 3w
 7 ggef  2b 2w
 6 feee  1b 1w
 5 ffff  1b 0w
 4 dddd  0b 0w
 3 cccc  0b 0w
 2 bbbb  0b 0w
 1 aaaa  0b 0w

BTW, it isn’t truly true that “you must learn 1 bit per turn” (even ignoring the last turn when you learn nothing).
See this most easily with 32 colors and 1 slot. There are only 2^5 possibilities, but you may need 32 turns.

(BTW, after 6 turns in the game above there were only 6 possibilities.)

5

These maximax Masterminds seem fun. Here’s another 10:



COLOURS: 7
a b c d e f g

SPOTS: 4

SOLUTION fged

10 fged 4b 0w
 9 edfg 0b 4w
 8 degf 0b 4w
 7 gfde 0b 4w
 6 gdef 1b 3w
 5 dfeg 1b 3w
 4 dddd 1b 0w
 3 cccc 0b 0w
 2 bbbb 0b 0w
 1 aaaa 0b 0w

I don’t think Minimax Mastermind is trivially solved.
What score can be guaranteed using 7 colors on 5 spots?

6

Defining minimum and maximum this way doesn’t seem to work. If the minimum is one guess, the maximum is the number of possible combinations.

It sounds to me you are actually looking for a minimum–the minimum number of turns needed to solve any particular code, no matter what it is.

And I’m not even sure that wording is truly unambiguous. It’s a difficult thing to figure out how to say.

7

Wikipedia is your (iffy) friend. But Knuth’s 5 guess algorithm is well known.

Note also the complexity of the generalized game is NP-hard when viewed as minimizing the number of guesses to solve it given a set of previously decided guesses and answers.

Guessing an aabb type initially works really well against a random opponent. Too many people start with abcd or aaaa type guesses which are idiotic. (Note that if you start with a very fixed guess all the time, a human can ~optimize against that.) For a randomly chosen pattern, assume until proven otherwise that two pegs are the same color.

Against a computer my standards are: 3- is a win, 4 is a tie, 5+ a lose.

(I did an html-cgi version in 1994, btw. Ah, the old days on the web.)

8

Not necessarily. The proviso that your guesses must be consistent with known information prohibits some combinations.

For example:

SOLUTION abcd

  1. aaaa 1b 0w
  2. bbbb 1b 0w
  3. cccc 1b 0w
  4. dddd 1b 0w

At this point, you can’t legitimately play 5. eeee - you know there’s no possibility of any piece being an e. Any combination with e, f, or g is prohibited at this point.

Pretend this is the scenario. You’re playing the game by a bizarre set of rules. You get $100 for every more you make. But you lose all your money if you make any move which is impossible with the information you already have. What is your strategy for making the maximum amount of money?

9

I’m also in the habit of using Wikipedia. But another habit I have is reading posts before I respond to them. :smiley: Knuth’s well known solution is for 6 colors on 4 slots. I asked about 7 colors on 5 slots. (And – big hint – it happens that Knuth’s algorithm does NOT produce the Minimax strategy in that case.)

By “minimax” I mean the strategy which minimizes the maximum score. Probes which don’t fit the clues are allowed.

10

A proposed algorithm.

Base color:
Start with a base color.

  1. aaaa

You’ll either get hits or not but it doesn’t change your strategy at this point. (You can’t get any white hits.)
1a. aaaa 0b 0w
1b. aaaa 1b 0w

First test color:
Introduce a first test color. Only use one test piece.
2. aaab

If you get a black hit for the test color, you’ve found its correct position. Go to the first repeat color.

  1. aaaa 0b 0w
  2. aaab 1b 0w - you now know xxxb is correct and there are no a’s

If you get a white hit for the test color, move it one space at a time until you find its correct position. Go to the first repeat color.

  1. aaaa 0b 0w
  2. aaab 0b 1w
  3. aaba 0b 1w
  4. abaa 1b 0w - you now know xbxx is correct and there are no a’s

If you don’t get a hit for the test color, you can’t use it anymore. Go to the first repeat color.

  1. aaaa 0b 0w
  2. aaab 0b 0w - you now know there are no a’s and no b’s

First repeat color:
Repeat the procedure with a second pin of the same color.

If it’s a hit, move it until you reach the correct destination. Go to a second repeat color.

  1. aaaa 0b 0w
  2. aaab 0b 1w
  3. aaba 1b 0w - you now know xxbx is correct and there are no a’s
  4. aabb 1b 1w
  5. abba 1b 1w
  6. baba 2b - you now know bxbx is correct and there are no a’s

If it’s a miss, go to a second test color.

  1. aaaa 0b 0w
  2. aaab 0b 1w
  3. aaba 1b 0w - you now know xxbx is correct and there are no a’s
  4. aabb 1b 0w - you now know xxbx is correct, there are no a’s, and there is not a second b

Second repeat color:
Repeat the procedure with a third pin of the same color.

If you get a miss, go to the second test color.

  1. aaaa 0b 0w
  2. aaab 0b 1w
  3. aaba 1b 0w - you now know xxbx is correct and there are no a’s
  4. aabb 1b 1w
  5. abba 1b 1w
  6. baba 2b - you now know bxbx is correct and there are no a’s
  7. babb 2b - you now know bxbx is correct, there are no a’s, and there is not a third b

Second test color:
Repeat the procedure with a pin of a different color.

If you get a hit, move it until you get the correct position. Then repeat the color with a second pin.

  1. aaaa 0b 0w
  2. aaab 0b 1w
  3. aaba 1b 0w - you now know xxbx is correct and there are no a’s
  4. aabb 1b 1w
  5. abba 1b 1w
  6. baba 2b - you now know bxbx is correct and there are no a’s
  7. babb 2b - you now know bxbx is correct, there are no a’s, and there is not a third b
  8. babc 2b 1w
  9. bcba 3b - you now know bcbx is correct, there are no a’s, and there is not a third b
  10. bcbc 3b - you now know bcbx is correct, there are no a’s, there is not a third b, and there is not a second c
  11. bcbd

If you get a miss, go to a third test color.

  1. aaaa 0b 0w
  2. aaab 0b 1w
  3. aaba 1b 0w - you now know xxbx is correct and there are no a’s
  4. aabb 1b 1w
  5. abba 1b 1w
  6. baba 2b - you now know bxbx is correct and there are no a’s
  7. babb 2b - you now know bxbx is correct, there are no a’s, and there is not a third b
  8. babc 2b - - you now know bxbx is correct, there are no a’s, there is not a third b, and there are no c’s
  9. babd

Hopefully at this point, you can figure out the procedure to follow from now on.

I’ll let somebody else do the math to figure out the average number of guesses this algorithm will take.

11

Here’s an example of my algorithm, using the worst (best?) possible answer.

SOLUTION: defg

  1. aaaa
  2. aaab
  3. aaac
  4. aaad 1w
  5. aada 1w
  6. adaa 1w
  7. daaa 1b
  8. daad 1b
  9. daae 1b 1w
  10. daea 1b 1w
  11. deaa 2b
  12. deae 2b
  13. deaf 2b 1w
  14. defa 3b
  15. deff 3b
  16. defg 4b
12

Looking at my posts, I see I made an error. My algorithm does contain known false information.

If I start with a base color and get no hits, I should use a second base color. I should continue guessing base colors until I get at least one hit.

SOLUTION: defg

  1. aaaa
  2. bbbb
  3. cccc
  4. dddd 1b
  5. ddde 1b 1w
  6. dded 1b 1w
  7. dedd 2b
  8. dede 2b
  9. dedf 2b 1w
  10. defd 3b
  11. deff 3b
  12. defg 4b
13

Seems like you could leave out step 8 - you already know there’s not a “d” in the last position, based on step 4. From steps 4 - 7, you know there is exactly one “d” and it’s in the first position. Otherwise, you’d have gotten a “1b” marker sooner. (Now, if “d” was actually in, say, the third position, then I suppose you’d have to test “d” out in the 4th position as well.)

You can only leave out steps 12 and 15 for the same reason. Again, only because you “coincidentally” tried out the letters as they appear in the final combination from left to right, thereby eliminating them from fitting in any other spot as they “travel” across your guesses.

14

This violates the rule(*) that each guess must conform to prior clues.
If ‘ddde’ were correct. ‘dddd’ would score 3b not 1b.

(* ETA: A rule needed for OP’s puzzle. Of course it is not a standard Mastermind rule.)

15

Well, here, then, seems like you could leave out steps 8 and 11.

Well, and you can also leave out step 10 - if you know the “de” is in the first two spots and “d” is NOT in the third spot, then if you get a white peg for the “f” in step 9, you know it’s NOT in the last spot, so it must be in the third spot.

I propose your solution up to step 7.

  1. dedf 2b1w
  2. defg 4b.
16

This number seems way too high, could you show us an example, using your method, of a game taking more than 9 or 10 guesses? I couldn’t come up with one.

17

This seems a reasonable upper limit. But, with 6 coloured pegs and 4 spots in the code, can you come up with a game that takes 11 turns? So far, with 7 coloured pegs and 4 spots, the best I see in this thread is 10 turns (see the posts by septimus).

18

(#Colors + #Slots - 1) may happen to give the answer to OP’s question in some simple cases. For example, when #Colors = 7 and #Slots = 4, the maximum appears to be (7+4-1) = 10.

For #Colors = #Slots = 5, this formula gives 9, but I suspect a 10-score is possible (though I didn’t find a way).

However, I suspect the formula overestimates when there are many slots. At #Colors = #Slots = 6, the formula would suggest 11, but can that be achieved?

19

Well done, but as you point out, I made a mistake and had seven colours. I meant to start with the original Mastermind scenario, which was six pegs and four spots.

In that scenario, the longest game I came up with is six.



COLOURS: 6
a b c d e f

SPOTS: 4

SOLUTION ffdc

6 ffdc  4b 0w - solved
5 cede  1b 1w
4 ddaa  0b 1w
3 ccac  1b 0w
2 baef  0b 1w
1 abcd  0b 2w
20

Why can’t you learn less than one bit (i.e., rule out less than half the solution space) on some turn? [Of course, on every turn, there is the possibility of learning at least 1 bit, so no algorithm can ALWAYS take more than 11 turns, but if the actual solution happens to be favorable…]