# 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:** 17\ **Page:** 2
**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, 3:42pm UTC](https://boards.straightdope.com/t/maximum-number-of-guesses-in-mastermind/629190/21 "2012-07-24T15:42:32Z")
> [@yearofglad](#): > > 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’re right. I think the basic idea is still sound but it wouldn’t take as many steps as I said. ---
**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:44pm UTC](https://boards.straightdope.com/t/maximum-number-of-guesses-in-mastermind/629190/22 "2012-07-24T15:44:59Z")
> [@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 if you follow the rule that each guess has to be consistent with the information obtained in the other guesses. If you omit the consistency rule, the maximum would be infinity, as said in the OP. > [@](#): > > 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. No, I’m looking for a maximum. ---
**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:46pm UTC](https://boards.straightdope.com/t/maximum-number-of-guesses-in-mastermind/629190/23 "2012-07-24T15:46:03Z")
> [@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 Looking at this, step 5 is wrong. In step 4 we learn that there is only one “d” in the solution. But in step 5, you include three "d"s. ---
**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:49pm UTC](https://boards.straightdope.com/t/maximum-number-of-guesses-in-mastermind/629190/24 "2012-07-24T15:49:32Z")
> [@septimus](#): > > (#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? At first glance, this looks like a good estimate with simple examples, but I can’t believe that this would be the answer for an arbitrary game with N colours and M slots. In the original Mastermind scenario (6+4), that would mean that you should be able to come up with a 6-color 4-slot game that would take 6 + 4 - 1 = 9 guesses to solve. I defy anyone to come up with a game that requires 9 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:52pm UTC](https://boards.straightdope.com/t/maximum-number-of-guesses-in-mastermind/629190/25 "2012-07-24T15:52:22Z")
> [@Arnold\_Winkelried](#): > > In the original Mastermind scenario (6+4), that would mean that you should be able to come up with a 6-color 4-slot game that would take 6 + 4 - 1 = 9 guesses to solve. I defy anyone to come up with a game that requires 9 guesses. 😕 Just take any of the solutions for (7,4) posted, eliminate ‘a’ as a color, eliminate the first guess (always ‘aaaa’) and get a solution one less than before. ---
**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, 4:00pm UTC](https://boards.straightdope.com/t/maximum-number-of-guesses-in-mastermind/629190/26 "2012-07-24T16:00:15Z")
> [@septimus](#): > > 😕 Just take any of the solutions for (7,4) posted, eliminate ‘a’ as a color, eliminate the first guess (always ‘aaaa’) and get a solution one less than before. :smack: You’re right of course. I’m not thinking straight this morning. ```auto COLOURS: 6 a b c d e f g SPOTS: 4 SOLUTION efdc 9 efdc 4b 0w 8 dcef 0b 4w 7 cdfe 0b 4w 6 fecd 0b 4w 5 fcde 1b 3w 4 cedf 1b 3w 3 cccc 1b 0w 2 bbbb 0b 0w 1 aaaa 0b 0w ``` ETA: So, for 8 colours and five spots, the maximum number of guesses would be 8 + 5 - 1 = 12? I’ll try with that, but as we’ve seen, I’m not the best at finding the longest possible game. ---
**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, 4:02pm UTC](https://boards.straightdope.com/t/maximum-number-of-guesses-in-mastermind/629190/27 "2012-07-24T16:02:57Z")
Another, more fundamental, problem with my algorithm - I acted as though you had to follow up on the information you received. That’s not true. You can’t directly contradict information you have but you can essentially ignore it temporarily while you search for unrelated information. For example: 1. aaaa 2. aaab 1w Now at this point, I moved the b until I found its correct position. But I could have just noted the information that there is a b present and tried other guesses. That’s not contradicted by the presence of the b. 1. aaaa 2. aaab 1w 3. aaac 4. aaad 5. aaae 1w 6. aaaf 7. aaag 1b At this point, I know the fourth position is a g and that two of the other positions are a b and an e. The fourth position must be a second b, e, or g. So I’ll work on the third position using the information I have: solution: gbeg 1. aaaa 2. aaab 1w 3. aaac 4. aaad 5. aaae 1w 6. aaaf 7. aaag 1b 8. aabg 1b 1w 9. aaeg 2b - found the third position and now I’ll work on the second 10. abeg 3b 11. bbeg 3b 12. ebeg 3b 13. gbeg 4b Thinking further, I should apply my base color rule as well. solution: bgeg 1. aaaa 2. bbbb 1b 3. bbbc 1b 4. bbbd 1b 5. bbbe 1b 1w 6. bbbf 1b 7. bbbg 2b 8. bbeg 3b 9. beeg 3b 10. bgeg 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, 4:07pm UTC](https://boards.straightdope.com/t/maximum-number-of-guesses-in-mastermind/629190/28 "2012-07-24T16:07:21Z")
> [@Arnold\_Winkelried](#): > > Looking at this, step 5 is wrong. In step 4 we learn that there is only one “d” in the solution. But in step 5, you include three "d"s. I’m not sure that counts as a “wrong” guess. I know there’s only one d but I don’t know its position. So I can legitimately surmise it might be in any of the three positions I place it in step 5 - I just haven’t pinned it down yet. It’s hard to think this way - deliberately avoiding probably evidence on the basis that it’s only probable at this point without crossing the line into evidence that’s undeniable. An example of how this would apply in a real game: 1. aabb 1w 2. ccaa 1b - at this point I’m trying to confirm whether it was the a’s or the b’s that got a hit in my first guess. I’m using tow a’s even though I know there can’t be more than one. ---
**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, 4:08pm UTC](https://boards.straightdope.com/t/maximum-number-of-guesses-in-mastermind/629190/29 "2012-07-24T16:08:40Z")
> [@septimus](#): > > (#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. I should emphasize that “may happen … in some simple cases” are the operative words here. The “true formula” may be much more complicated. ---
**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, 4:13pm UTC](https://boards.straightdope.com/t/maximum-number-of-guesses-in-mastermind/629190/30 "2012-07-24T16:13:58Z")
> [@Little\_Nemo](#): > > I’m not sure that counts as a “wrong” guess. I know there’s only one d but I don’t know its position. So I can legitimately surmise it might be in any of the three positions I place it in step 5 - I just haven’t pinned it down yet Here’s how I define “wrong guess” - each guess should be a possible solution based on the information you already have. With this: 1. aaaa 2. bbbb 3. cccc 4. dddd 1b 5. ddde 1b 1w There is no way that guess 5 could be a possible solution. Because we know that the solution only has one “d”. ---
**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, 4:21pm UTC](https://boards.straightdope.com/t/maximum-number-of-guesses-in-mastermind/629190/31 "2012-07-24T16:21:16Z")
An alternative problem would be to allow “wrong guesses” in that sense, but still demand that one never make a guess to which they know the response they will get. This will still prevent the game from going on infinitely, and make finding the maximum nontrivial, but it would allow such things as guess 5 above, on the grounds that the response could be 1b 1w, 2b, or 2w. (However, for the sake of not confusing the thread, we need not discuss this alternative problem… I’m just noting its existence.) ---
**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, 5:20pm UTC](https://boards.straightdope.com/t/maximum-number-of-guesses-in-mastermind/629190/32 "2012-07-24T17:20:35Z")
> [@Indistinguishable](#): > > Why can’t you learn less than one bit? You can. Indeed, I realized my limit was bogus as soon as I posted, but the cry of “Please turn off your electronic devices for landing” kept me from fixing it. (An obvious counterexample is a game where you only learn if you have the complete right answer or not. That can take 6[sup]4[/sup]\>\>log[sub]2/sub guesses.) ---
**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, 7:14pm UTC](https://boards.straightdope.com/t/maximum-number-of-guesses-in-mastermind/629190/33 "2012-07-24T19:14:32Z")
> [@Arnold\_Winkelried](#): > > Here’s how I define “wrong guess” - each guess should be a possible solution based on the information you already have. > > With this: > > 1. aaaa > 2. bbbb > 3. cccc > 4. dddd 1b > 5. ddde 1b 1w > > There is no way that guess 5 could be a possible solution. Because we know that the solution only has one “d”. I guess I’m looking at it more as a piece-by-piece point of view rather than an overall point of view. For example: 1. aaaa 2. bbbb 3. cccc 1b Now at this point, I’d accept that aabb is a blatantly wrong guess. I know that axxx, xaxx, xxbx, and xxxb are all impossible, so there’s no way I’m going to learn anything from this. But if I posted ccaa, I’d say that’s an acceptable possibility. Yes, I know there can’t be two c’s. But cxxx and xcxx are both possible and my guess is a combination of those two possibilities. And it’s a guess that will give me real information. Depending on what the answer is, I’ll either eliminate the first and second spots or the third and fourth spots as possible locations for c. ---
**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, 7:20pm UTC](https://boards.straightdope.com/t/maximum-number-of-guesses-in-mastermind/629190/34 "2012-07-24T19:20:37Z")
> [@Little\_Nemo](#): > > I guess I’m looking at it more as a piece-by-piece point of view rather than an overall point of view. You’re using the rules as outlined by Indistinguishable in post 31, but not the rules as I described in my OP and post 30. (In case it’s not clear for some of the readers, I’m not trying to find the best algorithm for solving a Mastermind problem - I’m trying to find the maximum number of moves necessary when each guess is consistent with the previous guesses, i.e. each guess is a possible solution according to the information you have so far.) I was trying to find the maximum number of moves necessary following the rule described in post 30. Finding the maximum number of moves necessary following the rule described in post 31 would be a different question, and something that seems to me to be more difficult. Using the rules in post 31 the number of guesses can be much higher before you arrive at a solution. ---
**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, 7:24pm UTC](https://boards.straightdope.com/t/maximum-number-of-guesses-in-mastermind/629190/35 "2012-07-24T19:24:42Z")
I like Indistinguishable’s point. Rather than holding to a standard of no contradictory guesses, we’d probably be better off using a standard of no known answers guesses. An answer is acceptable as long as it provides new information (including reducing possibilities) even if it contradicts previous information. For example, let’s use a real game. 1. AABB 1b 2. CCDD 1b Now, I might use a strategy like this in a real game and both of my guesses gave me real information. (The first told me there was on A or B, the second told me there was one C or D.) But under a “no wrong guesses” rule, the second guess would have been prohibited. ETA: Ninja’d while I was writing this post. ---
**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, 7:29pm UTC](https://boards.straightdope.com/t/maximum-number-of-guesses-in-mastermind/629190/36 "2012-07-24T19:29:38Z")
I’m not asking you to use the method in the OP to solve games. I’m asking, if you use that method, what is the maximum number of guesses. ---
**Author:** ![md2000](https://avatars.discourse-cdn.com/v4/letter/m/73ab20/32.png) [@md2000](https://boards.straightdope.com/u/md2000)\ **Post date:** [July 24, 2012, 7:50pm UTC](https://boards.straightdope.com/t/maximum-number-of-guesses-in-mastermind/629190/37 "2012-07-24T19:50:47Z")
IIRC from way back in college, there is no way to code the colours so the solution cannot be derived with the 10(?) slots provided. The way to play I learned was to make an assumption based on previous guesses and seem if it lead to a contradiction. “If this blue peg earned the black pin, then… I should have gotten a white one here… therefore the blue peg is not responsible for the black pin.” Instead of starting with 1 colour, start with 2. Are we allowed to construct a maximal solution knowing the answer? That would give a worst case scenario. Again start with 2 colours, not the 1 that some examples here have. that allows you to constrct examples not contradictory - just because aabb earned me a white pin, does not prohibit me from using aacc or bbcc. This is where knowing the solution to “construct” worst case is needed. You can construct collections abcd abcc aabc etc. so that you have a massive variety of permutations and combinations while not contradicting the information “one/two of these colours are correct”. Not every guess adds a bit of data to the solution, or even narrows down the correct answer. Whereas, “aaaa” tells me a lot that narrows down my future options. If abcd earns me two whites, I can do all combinations of that without contradicting the first result; some will earn a black or two. Worst case, I can create 6^4 solutions, and then arrange them so that they are ascending order of score, number whites, number blacks. However, if aaaa earns me zero score, can I use an “a” again, Vanna, at all? Does that contradict what I’ve learned? [Previous page](https://boards.straightdope.com/t/maximum-number-of-guesses-in-mastermind/629190.md?page=1)