AI strategies for a mastermind codebreaker
Author
I am designing a program that will break a mastermind code (4 colours now for simplicity''s sake) I would like the AI to break it in 6 turns.
Codebreaker will guess a combination of 4 colours in four positions. And depending and what you guess you get a black peg which means one colour is correct and in the correct column. White peg means one colour is correct but in the incorrect column. And any holes left means wrong colour wrong position.
I have played it somewhat extensively with 4 colours and am able to break it always by the 6th line if not sooner. However sometimes it requires a lot of thinking.
I am wondering what strategies I should use to code so the AI will break it by the 6th time.
I have thought about doing a line for 3 colours and to determine
how many of each colour there is. But that will only leave me two guesses to get it right by the sixth guess.
I am not sure that this will be enough though and maybe have to interchanging colours earlier. I will have less of a history to store in the array though this way once I have all colours sorted out. Thanks
I am going to code it into C.
Es Quatro
AU
So let me get this right... rather than using the typical 6 colors in 4 slots, you are only using 4 colors? That would help, I''m sure! When I first saw you saying you would normally get it in 6 moves, my BS detector went off! Anyway, I can understand now how you would do it in 6.
As for programming, there are two ways you can go about it. First would be to select the starting pegs at random and just play it from there. Second, as you mentioned, would be to have a sort of "playbook" on how you are going to narrow things down in the first few moves. Programming the game the first way is rather straight forward if you aren''t using a playbook. Programming it with a playbook requires that you come up with the playbook on your own and then script those first few moves for the computer.
One flaw in your "try the four colors theory" is that you won''t have to ever try the fourth color. By determining the correct counts of the first three, you would automatically know what the count of the fourth color is. Next, you don''t have to put all 4 pegs of the same color to determine how many there are necessarily. It is worth exploring the patterns of how you could approach the problem by perhaps doing 2/2 of 2 colors, then 2/2 of the next two, then 2/2 of a cross-hatch of the first 2 lines, etc. However, that sounds a bit haphazard.
Back to the first method. One way of doing it would be to "score" the pegs by color and position until you reach a level of certainty. (By the way, I''m pulling this out of my AIss as I type, so I may wander a bit.) Declare an array that is 4 colors wide by 4 positions deep. For each move, you could increment ALL the array positions a little bit for a white peg (right color, wrong spot) and increment them all a little more for a black peg. As the values increase, you are more certain that those pegs are likely to be in the final solution.
As you progress to the next move, you would need to come up with an algorithm that analyzes the scores compared to the past plays and decide what pegs should stay, which should go, and which should be swapped around a bit. That seems like a starting point, anyway.
Dave Mark - President and Lead Designer
Intrinsic Algorithm - "Reducing the world to mathematical equations!"
As for programming, there are two ways you can go about it. First would be to select the starting pegs at random and just play it from there. Second, as you mentioned, would be to have a sort of "playbook" on how you are going to narrow things down in the first few moves. Programming the game the first way is rather straight forward if you aren''t using a playbook. Programming it with a playbook requires that you come up with the playbook on your own and then script those first few moves for the computer.
One flaw in your "try the four colors theory" is that you won''t have to ever try the fourth color. By determining the correct counts of the first three, you would automatically know what the count of the fourth color is. Next, you don''t have to put all 4 pegs of the same color to determine how many there are necessarily. It is worth exploring the patterns of how you could approach the problem by perhaps doing 2/2 of 2 colors, then 2/2 of the next two, then 2/2 of a cross-hatch of the first 2 lines, etc. However, that sounds a bit haphazard.
Back to the first method. One way of doing it would be to "score" the pegs by color and position until you reach a level of certainty. (By the way, I''m pulling this out of my AIss as I type, so I may wander a bit.) Declare an array that is 4 colors wide by 4 positions deep. For each move, you could increment ALL the array positions a little bit for a white peg (right color, wrong spot) and increment them all a little more for a black peg. As the values increase, you are more certain that those pegs are likely to be in the final solution.
As you progress to the next move, you would need to come up with an algorithm that analyzes the scores compared to the past plays and decide what pegs should stay, which should go, and which should be swapped around a bit. That seems like a starting point, anyway.
Dave Mark - President and Lead Designer
Intrinsic Algorithm - "Reducing the world to mathematical equations!"
mm.. I think I did it like this, way back:
1. Start by making a random guess
2. Look at the scores of all guesses, take the "best" guess so far (up to you how to decide
)
3. Make a new guess building on this guess: if it has two totally correct ones, copy two to the same place, if it has two "correct color, but wrong place", copy two (previously uncopied) colors to different places
4. Fill the rest of the empty holes with random colors
5. Check that this guess is consistent with ALL previous guesses - this is easy to do, by simply comparing EACH old guess with the new one, get a scoring from that comparison, and check that you get the Exact same scoring here as you got when the old guesses were compared to the secret code - If the new guess CAN be correct, it has to pass the test of all the old guesses
6. Did it pass? Fine - guess, and go back to 2 if it's not totally right yet, otherwise:
7. It didn't pass these tests - go to 3 without submitting guess
Voila - solves it very quickly and easily
If you're into Mastermind you might want to check out my online game Theorem: www.toblo.net/games/theorem, and please tell me if you have any feedback on it
[edited by - toblo on August 26, 2003 10:10:32 AM]
1. Start by making a random guess
2. Look at the scores of all guesses, take the "best" guess so far (up to you how to decide
)3. Make a new guess building on this guess: if it has two totally correct ones, copy two to the same place, if it has two "correct color, but wrong place", copy two (previously uncopied) colors to different places
4. Fill the rest of the empty holes with random colors
5. Check that this guess is consistent with ALL previous guesses - this is easy to do, by simply comparing EACH old guess with the new one, get a scoring from that comparison, and check that you get the Exact same scoring here as you got when the old guesses were compared to the secret code - If the new guess CAN be correct, it has to pass the test of all the old guesses
6. Did it pass? Fine - guess, and go back to 2 if it's not totally right yet, otherwise:
7. It didn't pass these tests - go to 3 without submitting guess
Voila - solves it very quickly and easily
If you're into Mastermind you might want to check out my online game Theorem: www.toblo.net/games/theorem, and please tell me if you have any feedback on it
[edited by - toblo on August 26, 2003 10:10:32 AM]
I never thought about Mastermind AI before, but this is very simple. I just wrote a program which solves the 4-colour problem in 5 or fewer steps and the 6-colour problem in 6 or fewer steps.
The strategy is pretty brute-force. Just keep a boolean per possible configuration. Initially, they are all `true', meaning that the hidden configuration could be any of them. A configuration selected as the next guess will classify the possible configurations in 14 classes, according to the two matching numbers. Just peek the guess that minimizes the size of the largest class.
I can post code if someone wants it.
[edited by - Alvaro on August 27, 2003 3:06:28 PM]
The strategy is pretty brute-force. Just keep a boolean per possible configuration. Initially, they are all `true', meaning that the hidden configuration could be any of them. A configuration selected as the next guess will classify the possible configurations in 14 classes, according to the two matching numbers. Just peek the guess that minimizes the size of the largest class.
I can post code if someone wants it.
[edited by - Alvaro on August 27, 2003 3:06:28 PM]
quote:Original post by alvaro
I never thought about Mastermind AI before, but this is very simple. I just wrote a program which solves the 4-colour problem in 5 or fewer steps and the 6-colour problem in 6 or fewer steps.
What happens if your initial guess contains no correct results, either by number of colour or position (this is certainly possible in the 6 colour version of the problem).
Timkin
quote:Original post by Timkin
What happens if your initial guess contains no correct results, either by number of colour or position (this is certainly possible in the 6 colour version of the problem).
You get a lot of information from that. It means that only the remaining colours are involved. For example, if your initial guess is 1 2 0 0 (with colours from 0 to 5) and there are no correct results, it means that the code consists only of 3''s, 4''s and 5''s. There are only 81 possibilities to differentiate.
Yes, but in a worst case scenario, you randomly choose 0 0 0 0 as your first guess... there are now 625 remaining cases to consider... and now you only have 5 moves left (since you state you can do it in 6). How did you manage this? I''m genuinely curious!
Timkin
Timkin
Timkin, there are only 105 remaining cases if after 1 2 0 0 you tell me that there are two exact matches and no inexact matches, at least according to my program. Actually, I counted it by hand and got to the same result.
The next guess from my program is 2 1 3 1, which narrows it down to 9 cases. The next guess is 0 0 0 0. So that''s not a particularly difficult case for my program. Try it!
The next guess from my program is 2 1 3 1, which narrows it down to 9 cases. The next guess is 0 0 0 0. So that''s not a particularly difficult case for my program. Try it!
#include <iostream>#include <vector>const int nc=6;const int nc4=nc*nc*nc*nc;struct Set{ std::vector<bool> v; Set(){ v=std::vector<bool>(nc4,true); }};int count(const Set &s){ int result=0; for(int i=0;i<nc4;++i) if(s.v[i]) result++; return result;} int classify(int real, int guess){ int g1=guess%nc; guess/=nc; int r1=real%nc; real/=nc; int g2=guess%nc; guess/=nc; int r2=real%nc; real/=nc; int g3=guess%nc; int g4=guess/nc; int r3=real%nc; int r4=real/nc; int result=0; if(g1==r1) result+=5,r1=-1; if(g2==r2) result+=5,r2=-1; if(g3==r3) result+=5,r3=-1; if(g4==r4) result+=5,r4=-1; if(r1!=-1 && (g1==r2 || g1==r3 || g1==r4)) result++; if(r2!=-1 && (g2==r1 || g2==r3 || g2==r4)) result++; if(r3!=-1 && (g3==r1 || g3==r2 || g3==r4)) result++; if(r4!=-1 && (g4==r1 || g4==r2 || g4==r3)) result++; return result;}int biggest_class_size(const Set &s, int guess){ int class_count[21]={0}; for(int i=0;i<nc4;++i) if(s.v[i]) class_count[classify(i,guess)]++; int maximum=0; for(int i=0;i<21;i++) if(maximum<class_count[i]) maximum=class_count[i]; return maximum;}void print_conf(std::ostream &o, int guess){ int g1=guess%nc; guess/=nc; int g2=guess%nc; guess/=nc; int g3=guess%nc; int g4=guess/nc; o << g1 << g2 << g3 << g4;}int evaluate(const Set &s){ int best_value=nc4+1; int best_guess; for(int i=0;i<nc4;++i) if(s.v[i]){ int value = biggest_class_size(s,i); if(best_value>value){ best_value=value; best_guess=i; } } return best_guess;}void filter(Set &s, int guess, int class_number){ for(int i=0;i<nc4;++i) if(s.v[i] && classify(i,guess)!=class_number) s.v[i]=false;}int main(void){ Set s; while(1){ std::cout << "There are " << count(s) << " possibilities left." << std::endl; int guess=evaluate(s); std::cout << "My guess is "; print_conf(std::cout, guess); std::cout << std::endl; int exact, inexact; std::cout << "Enter the number of exact and inexact matches, separated by a space: " << std::flush; std::cin >> exact >> inexact; int class_number=exact*5+inexact; if(class_number==20){ std::cout << "Solved!" << std::endl; break; } filter(s,guess,class_number); switch(count(s)){ case 0: std::cout << "That''s impossible! Check your answers." << std::endl; exit(0); case 1: std::cout << "I narrowed it down to as single possibility!" << std::endl; break; } } return 0;}quote:Original post by alvaro
Timkin, there are only 105 remaining cases if after 1 2 0 0 you tell me that there are two exact matches and no inexact matches
Sorry, I probably wasn't very clear about what I was asking... although I think I know the answer now. You're notion of taking 6 moves is based on getting at least a minimal amount of information from each move. Presumably, once you have some information, you can then make the choice that offers the highest Value Of Information (VOI) - you might want to look that up if you're not already familiar with it... it's very common to probabilistic decision methods.
Of course, this presumes that you obtain information with your first guess, which is what I was trying to get at in my last post, but I didn't express very clearly. I take it then, that your assessment of 6 moves is actually '5 moves after the move that first gives information about the solution'. Is that correct? Is 6 moves always the shortest path to the solution, or will it depend on the specific information you obtain. If you can't answer that one off the top of your head, you could run the program with all possible starting combinations for a given solution and measure the minimum number of moves it takes for each starting combination, then collect them into groups based on what information was given about that combination, relative to the solution. Make sense?
By the way, for those that are interested, Mastermind is a great puzzle that relates to the problem of asking sequential questions to obtain information, where you want to minimise the number of questions asked and maximise the information obtained. This crops up a lot in a variety of application fields.
Hece my interest in your solution method and its performance.
Cheers,
Timkin
[edited by - Timkin on September 2, 2003 10:44:20 PM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
