# Maximum number of "guesses" in Mastermind **URL:** \ **Category:** Factual Questions\ **Created:** [July 24, 2012, 1:03am UTC](https://boards.straightdope.com/t/maximum-number-of-guesses-in-mastermind/629190 "2012-07-24T01:03:55Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![Arnold\_Winkelried](https://avatars.discourse-cdn.com/v4/letter/a/3d9bf3/32.png) [@Arnold\_Winkelried](https://boards.straightdope.com/u/Arnold_Winkelried)\ **Post date:** [July 24, 2012, 1:03am UTC](https://boards.straightdope.com/t/maximum-number-of-guesses-in-mastermind/629190/1 "2012-07-24T01:03:55Z")
I assume that most of us are familiar with the board game [Mastermind](http://en.wikipedia.org/wiki/Mastermind_(board_game)). 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.) ```auto 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 ``` ---
**Author:** ![Saint\_Cad](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/saint_cad/32/18907_2.png) [@Saint\_Cad](https://boards.straightdope.com/u/Saint_Cad)\ **Post date:** [July 24, 2012, 1:47am UTC](https://boards.straightdope.com/t/maximum-number-of-guesses-in-mastermind/629190/2 "2012-07-24T01:47:46Z")
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. ---
**Author:** ![Pasta](https://avatars.discourse-cdn.com/v4/letter/p/ecccb3/32.png) [@Pasta](https://boards.straightdope.com/u/Pasta)\ **Post date:** [July 24, 2012, 3:06am UTC](https://boards.straightdope.com/t/maximum-number-of-guesses-in-mastermind/629190/3 "2012-07-24T03:06:18Z")
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… ---
**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\ **Post date:** [July 24, 2012, 5:36am UTC](https://boards.straightdope.com/t/maximum-number-of-guesses-in-mastermind/629190/4 "2012-07-24T05:36:45Z")
I can improve on OP’s example (which is actually for 7 colours, not 6) from 9 to 10. ```auto 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.) ---
**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\ **Post date:** [July 24, 2012, 9:47am UTC](https://boards.straightdope.com/t/maximum-number-of-guesses-in-mastermind/629190/5 "2012-07-24T09:47:10Z")
These maximax Masterminds seem fun. Here’s another 10: ```auto 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? ---
**Author:** ![BigT](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/bigt/32/12044_2.png) [@BigT](https://boards.straightdope.com/u/BigT)\ **Post date:** [July 24, 2012, 12:23pm UTC](https://boards.straightdope.com/t/maximum-number-of-guesses-in-mastermind/629190/6 "2012-07-24T12:23:59Z")
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. ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [July 24, 2012, 2:01pm UTC](https://boards.straightdope.com/t/maximum-number-of-guesses-in-mastermind/629190/7 "2012-07-24T14:01:31Z")
Wikipedia is your (iffy) [friend](http://en.wikipedia.org/wiki/Mastermind_(board_game)). 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.) ---
**Author:** ![Little\_Nemo](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/little_nemo/32/3120_2.png) [@Little\_Nemo](https://boards.straightdope.com/u/Little_Nemo)\ **Post date:** [July 24, 2012, 2:07pm UTC](https://boards.straightdope.com/t/maximum-number-of-guesses-in-mastermind/629190/8 "2012-07-24T14:07:19Z")
> [@BigT](#): > > 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. 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? ---
**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\ **Post date:** [July 24, 2012, 2:36pm UTC](https://boards.straightdope.com/t/maximum-number-of-guesses-in-mastermind/629190/9 "2012-07-24T14:36:55Z")
> [@septimus](#): > > I don’t think Minimax Mastermind is trivially solved. > What score can be guaranteed using 7 colors on 5 spots? > [@ftg](#): > > Wikipedia is your (iffy) [friend](http://en.wikipedia.org/wiki/Mastermind_(board_game)). But Knuth’s 5 guess algorithm is well known. I’m also in the habit of using Wikipedia. But another habit I have is reading posts before I respond to them. 😃 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. ---
**Author:** ![Little\_Nemo](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/little_nemo/32/3120_2.png) [@Little\_Nemo](https://boards.straightdope.com/u/Little_Nemo)\ **Post date:** [July 24, 2012, 2:40pm UTC](https://boards.straightdope.com/t/maximum-number-of-guesses-in-mastermind/629190/10 "2012-07-24T14:40:29Z")
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. ---
**Author:** ![Little\_Nemo](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/little_nemo/32/3120_2.png) [@Little\_Nemo](https://boards.straightdope.com/u/Little_Nemo)\ **Post date:** [July 24, 2012, 2:48pm UTC](https://boards.straightdope.com/t/maximum-number-of-guesses-in-mastermind/629190/11 "2012-07-24T14:48:38Z")
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 ---
**Author:** ![Little\_Nemo](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/little_nemo/32/3120_2.png) [@Little\_Nemo](https://boards.straightdope.com/u/Little_Nemo)\ **Post date:** [July 24, 2012, 2:55pm UTC](https://boards.straightdope.com/t/maximum-number-of-guesses-in-mastermind/629190/12 "2012-07-24T14:55:04Z")
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 ---
**Author:** ![yearofglad](https://avatars.discourse-cdn.com/v4/letter/y/b782af/32.png) [@yearofglad](https://boards.straightdope.com/u/yearofglad)\ **Post date:** [July 24, 2012, 2:59pm UTC](https://boards.straightdope.com/t/maximum-number-of-guesses-in-mastermind/629190/13 "2012-07-24T14:59:49Z")
> [@Little\_Nemo](#): > > 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 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. ---
**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\ **Post date:** [July 24, 2012, 3:00pm UTC](https://boards.straightdope.com/t/maximum-number-of-guesses-in-mastermind/629190/14 "2012-07-24T15:00:12Z")
> [@Little\_Nemo](#): > > 1. dddd 1b > 2. ddde 1b 1w 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.) ---
**Author:** ![yearofglad](https://avatars.discourse-cdn.com/v4/letter/y/b782af/32.png) [@yearofglad](https://boards.straightdope.com/u/yearofglad)\ **Post date:** [July 24, 2012, 3:03pm UTC](https://boards.straightdope.com/t/maximum-number-of-guesses-in-mastermind/629190/15 "2012-07-24T15:03:29Z")
> [@Little\_Nemo](#): > > 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 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. ---
**Author:** ![Arnold\_Winkelried](https://avatars.discourse-cdn.com/v4/letter/a/3d9bf3/32.png) [@Arnold\_Winkelried](https://boards.straightdope.com/u/Arnold_Winkelried)\ **Post date:** [July 24, 2012, 3:30pm UTC](https://boards.straightdope.com/t/maximum-number-of-guesses-in-mastermind/629190/16 "2012-07-24T15:30:13Z")
> [@Saint\_Cad](#): > > 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. 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. ---
**Author:** ![Arnold\_Winkelried](https://avatars.discourse-cdn.com/v4/letter/a/3d9bf3/32.png) [@Arnold\_Winkelried](https://boards.straightdope.com/u/Arnold_Winkelried)\ **Post date:** [July 24, 2012, 3:32pm UTC](https://boards.straightdope.com/t/maximum-number-of-guesses-in-mastermind/629190/17 "2012-07-24T15:32:00Z")
> [@Pasta](#): > > 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… 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). ---
**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\ **Post date:** [July 24, 2012, 3:42pm UTC](https://boards.straightdope.com/t/maximum-number-of-guesses-in-mastermind/629190/18 "2012-07-24T15:42:05Z")
(#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? ---
**Author:** ![Arnold\_Winkelried](https://avatars.discourse-cdn.com/v4/letter/a/3d9bf3/32.png) [@Arnold\_Winkelried](https://boards.straightdope.com/u/Arnold_Winkelried)\ **Post date:** [July 24, 2012, 3:42pm UTC](https://boards.straightdope.com/t/maximum-number-of-guesses-in-mastermind/629190/19 "2012-07-24T15:42:23Z")
> [@septimus](#): > > I can improve on OP’s example (which is actually for 7 colours, not 6) from 9 to 10. 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. ```auto 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 ``` ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [July 24, 2012, 3:42pm UTC](https://boards.straightdope.com/t/maximum-number-of-guesses-in-mastermind/629190/20 "2012-07-24T15:42:26Z")
> [@Pasta](#): > > 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… 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…] [Next page](https://boards.straightdope.com/t/maximum-number-of-guesses-in-mastermind/629190.md?page=2)