You’re right. I think the basic idea is still sound but it wouldn’t take as many steps as I said.
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.
No, I’m looking for a maximum.
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.
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.
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.
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.
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:
- aaaa
- 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.
- aaaa
- aaab 1w
- aaac
- aaad
- aaae 1w
- aaaf
- 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
- aaaa
- aaab 1w
- aaac
- aaad
- aaae 1w
- aaaf
- aaag 1b
- aabg 1b 1w
- aaeg 2b - found the third position and now I’ll work on the second
- abeg 3b
- bbeg 3b
- ebeg 3b
- gbeg 4b
Thinking further, I should apply my base color rule as well.
solution: bgeg
- aaaa
- bbbb 1b
- bbbc 1b
- bbbd 1b
- bbbe 1b 1w
- bbbf 1b
- bbbg 2b
- bbeg 3b
- beeg 3b
- bgeg 4b
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:
- aabb 1w
- 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.
I should emphasize that “may happen … in some simple cases” are the operative words here. The “true formula” may be much more complicated.
Here’s how I define “wrong guess” - each guess should be a possible solution based on the information you already have.
With this:
- aaaa
- bbbb
- cccc
- dddd 1b
- 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”.
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.)
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.)
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:
- aaaa
- bbbb
- 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.
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.
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.
- AABB 1b
- 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.
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.
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?