https://stackoverflow.com/questions/1185634/how-to-solve-the-mastermind-guessing-game Stack Overflow 1. About 2. Products 3. For Teams 1. Stack Overflow Public questions & answers 2. Stack Overflow for Teams Where developers & technologists share private knowledge with coworkers 3. Talent Build your employer brand 4. Advertising Reach developers & technologists worldwide 5. Labs The future of collective knowledge sharing 6. About the company [ ] Loading... 1. current community + Stack Overflow help chat + Meta Stack Overflow your communities Sign up or log in to customize your list. more stack exchange communities company blog 2. 3. Log in 4. Sign up 1. 1. Home 2. Questions 3. Tags 4. 5. Users 6. Companies 7. Collectives 8. Explore Collectives 9. Labs 10. Discussions 2. Teams Stack Overflow for Teams - Start collaborating and sharing organizational knowledge. [teams-illo-free-si] Create a free Team Why Teams? 3. Teams 4. Create free Team Collectives(tm) on Stack Overflow Find centralized, trusted content and collaborate around the technologies you use most. Learn more about Collectives Teams Q&A for work Connect and share knowledge within a single location that is structured and easy to search. Learn more about Teams Get early access and see previews of new features. Learn more about Labs How to solve the "Mastermind" guessing game? Ask Question Asked 14 years, 5 months ago Modified 3 years, 7 months ago Viewed 45k times 44 How would you create an algorithm to solve the following puzzle, "Mastermind"? Your opponent has chosen four different colours from a set of six (yellow, blue, green, red, orange, purple). You must guess which they have chosen, and in what order. After each guess, your opponent tells you how many (but not which) of the colours you guessed were the right colour in the right place ["blacks"] and how many (but not which) were the right colour but in the wrong place ["whites"]. The game ends when you guess correctly (4 blacks, 0 whites). For example, if your opponent has chosen (blue, green, orange, red), and you guess (yellow, blue, green, red), you will get one "black" (for the red), and two whites (for the blue and green). You would get the same score for guessing (blue, orange, red, purple). I'm interested in what algorithm you would choose, and (optionally) how you translate that into code (preferably Python). I'm interested in coded solutions that are: 1. Clear (easily understood) 2. Concise 3. Efficient (fast in making a guess) 4. Effective (least number of guesses to solve the puzzle) 5. Flexible (can easily answer questions about the algorithm, e.g. what is its worst case?) 6. General (can be easily adapted to other types of puzzle than Mastermind) I'm happy with an algorithm that's very effective but not very efficient (provided it's not just poorly implemented!); however, a very efficient and effective algorithm implemented inflexibly and impenetrably is not of use. I have my own (detailed) solution in Python which I have posted, but this is by no means the only or best approach, so please post more! I'm not expecting an essay ;) * python * algorithm Share Improve this question Follow edited Sep 1, 2009 at 11:08 alicederyn asked Jul 26, 2009 at 21:43 alicederyn's user avatar alicederynalicederyn 12.9k66 gold badges5151 silver badges5757 bronze badges 10 * 8 Get a blog maybe? - shoosh Jul 26, 2009 at 22:29 * 5 @shoosh: you can be alittle nicer than that. :D @chrispy: I completely appreciate what you are doing in posting a tutorial on SO. I love the idea, and other sites have extensive tutorial sections. I've actually tried posting tuts here, but people usually tell me not to, SO is better for Q and A. I will address the issue on meta. You tutorial will get more views on a different site for tutorials than here as a question probably. I would reccomend dreamincode.net for posting tutorials. :D (but its up to you, do whatever you like) - Gordon Gustafson Jul 27, 2009 at 0:06 * @CrazyJugglerDrummer: I wouldn't say that this would necessarily get less views - if someone were to type in to google "how to solve mastermind" (which would probably be quite a common search term for this problem) than this question ranks on the first page - not too shabby. If they refine their search terms to "how to solve mastermind in python" then this question is the top ranked result - because the site consistently ranks highly, tutorials posted on here will rank quite high in search results. - a_m0d Aug 29, 2009 at 9:59 * 1 When studying I remember a fellow student constructing the evil mastermind opponent playing the "other" player in mastermind. So instead of pre-selecting a hidden position according to the rules, it cheats and dynamically answers in order to maximize the number of needed guesses; randomly selecting among the worst alternatives. Should the generalized solver be able to handle that as well? - Hans Olsson Feb 7, 2018 at 16:02 * @hans-olsson Yep, please cover that with a standard worst-case analysis - alicederyn Feb 8, 2018 at 21:31 | Show 5 more comments 9 Answers 9 Sorted by: Reset to default [Highest score (default) ] 44 Key tools: entropy, greediness, branch-and-bound; Python, generators, itertools, decorate-undecorate pattern In answering this question, I wanted to build up a language of useful functions to explore the problem. I will go through these functions, describing them and their intent. Originally, these had extensive docs, with small embedded unit tests tested using doctest; I can't praise this methodology highly enough as a brilliant way to implement test-driven-development. However, it does not translate well to StackOverflow, so I will not present it this way. Firstly, I will be needing several standard modules and future imports (I work with Python 2.6). from __future__ import division # No need to cast to float when dividing import collections, itertools, math I will need a scoring function. Originally, this returned a tuple (blacks, whites), but I found output a little clearer if I used a namedtuple: Pegs = collections.namedtuple('Pegs', 'black white') def mastermindScore(g1,g2): matching = len(set(g1) & set(g2)) blacks = sum(1 for v1, v2 in itertools.izip(g1,g2) if v1 == v2) return Pegs(blacks, matching-blacks) To make my solution general, I pass in anything specific to the Mastermind problem as keyword arguments. I have therefore made a function that creates these arguments once, and use the **kwargs syntax to pass it around. This also allows me to easily add new attributes if I need them later. Note that I allow guesses to contain repeats, but constrain the opponent to pick distinct colours; to change this, I only need change G below. (If I wanted to allow repeats in the opponent's secret, I would need to change the scoring function as well.) def mastermind(colours, holes): return dict( G = set(itertools.product(colours,repeat=holes)), V = set(itertools.permutations(colours, holes)), score = mastermindScore, endstates = (Pegs(holes, 0),)) def mediumGame(): return mastermind(("Yellow", "Blue", "Green", "Red", "Orange", "Purple"), 4) Sometimes I will need to partition a set based on the result of applying a function to each element in the set. For instance, the numbers 1..10 can be partitioned into even and odd numbers by the function n % 2 (odds give 1, evens give 0). The following function returns such a partition, implemented as a map from the result of the function call to the set of elements that gave that result (e.g. { 0: evens, 1: odds }). def partition(S, func, *args, **kwargs): partition = collections.defaultdict(set) for v in S: partition[func(v, *args, **kwargs)].add(v) return partition I decided to explore a solver that uses a greedy entropic approach. At each step, it calculates the information that could be obtained from each possible guess, and selects the most informative guess. As the numbers of possibilities grow, this will scale badly (quadratically), but let's give it a try! First, I need a method to calculate the entropy (information) of a set of probabilities. This is just -[?]p log p. For convenience, however, I will allow input that are not normalized, i.e. do not add up to 1: def entropy(P): total = sum(P) return -sum(p*math.log(p, 2) for p in (v/total for v in P if v)) So how am I going to use this function? Well, for a given set of possibilities, V, and a given guess, g, the information we get from that guess can only come from the scoring function: more specifically, how that scoring function partitions our set of possibilities. We want to make a guess that distinguishes best among the remaining possibilites -- divides them into the largest number of small sets -- because that means we are much closer to the answer. This is exactly what the entropy function above is putting a number to: a large number of small sets will score higher than a small number of large sets. All we need to do is plumb it in. def decisionEntropy(V, g, score): return entropy(collections.Counter(score(gi, g) for gi in V).values()) Of course, at any given step what we will actually have is a set of remaining possibilities, V, and a set of possible guesses we could make, G, and we will need to pick the guess which maximizes the entropy. Additionally, if several guesses have the same entropy, prefer to pick one which could also be a valid solution; this guarantees the approach will terminate. I use the standard python decorate-undecorate pattern together with the built-in max method to do this: def bestDecision(V, G, score): return max((decisionEntropy(V, g, score), g in V, g) for g in G)[2] Now all I need to do is repeatedly call this function until the right result is guessed. I went through a number of implementations of this algorithm until I found one that seemed right. Several of my functions will want to approach this in different ways: some enumerate all possible sequences of decisions (one per guess the opponent may have made), while others are only interested in a single path through the tree (if the opponent has already chosen a secret, and we are just trying to reach the solution). My solution is a "lazy tree", where each part of the tree is a generator that can be evaluated or not, allowing the user to avoid costly calculations they won't need. I also ended up using two more namedtuples, again for clarity of code. Node = collections.namedtuple('Node', 'decision branches') Branch = collections.namedtuple('Branch', 'result subtree') def lazySolutionTree(G, V, score, endstates, **kwargs): decision = bestDecision(V, G, score) branches = (Branch(result, None if result in endstates else lazySolutionTree(G, pV, score=score, endstates=endstates)) for (result, pV) in partition(V, score, decision).iteritems()) yield Node(decision, branches) # Lazy evaluation The following function evaluates a single path through this tree, based on a supplied scoring function: def solver(scorer, **kwargs): lazyTree = lazySolutionTree(**kwargs) steps = [] while lazyTree is not None: t = lazyTree.next() # Evaluate node result = scorer(t.decision) steps.append((t.decision, result)) subtrees = [b.subtree for b in t.branches if b.result == result] if len(subtrees) == 0: raise Exception("No solution possible for given scores") lazyTree = subtrees[0] assert(result in endstates) return steps This can now be used to build an interactive game of Mastermind where the user scores the computer's guesses. Playing around with this reveals some interesting things. For example, the most informative first guess is of the form (yellow, yellow, blue, green), not (yellow, blue, green, red). Extra information is gained by using exactly half the available colours. This also holds for 6-colour 3-hole Mastermind -- (yellow, blue, green) -- and 8-colour 5-hole Mastermind -- (yellow, yellow, blue, green, red). But there are still many questions that are not easily answered with an interactive solver. For instance, what is the most number of steps needed by the greedy entropic approach? And how many inputs take this many steps? To make answering these questions easier, I first produce a simple function that turns the lazy tree of above into a set of paths through this tree, i.e. for each possible secret, a list of guesses and scores. def allSolutions(**kwargs): def solutions(lazyTree): return ((((t.decision, b.result),) + solution for t in lazyTree for b in t.branches for solution in solutions(b.subtree)) if lazyTree else ((),)) return solutions(lazySolutionTree(**kwargs)) Finding the worst case is a simple matter of finding the longest solution: def worstCaseSolution(**kwargs): return max((len(s), s) for s in allSolutions(**kwargs)) [1] It turns out that this solver will always complete in 5 steps or fewer. Five steps! I know that when I played Mastermind as a child, I often took longer than this. However, since creating this solver and playing around with it, I have greatly improved my technique, and 5 steps is indeed an achievable goal even when you don't have time to calculate the entropically ideal guess at each step ;) How likely is it that the solver will take 5 steps? Will it ever finish in 1, or 2, steps? To find that out, I created another simple little function that calculates the solution length distribution: def solutionLengthDistribution(**kwargs): return collections.Counter(len(s) for s in allSolutions(**kwargs)) For the greedy entropic approach, with repeats allowed: 7 cases take 2 steps; 55 cases take 3 steps; 229 cases take 4 steps; and 69 cases take the maximum of 5 steps. Of course, there's no guarantee that the greedy entropic approach minimizes the worst-case number of steps. The final part of my general-purpose language is an algorithm that decides whether or not there are any solutions for a given worst-case bound. This will tell us whether greedy entropic is ideal or not. To do this, I adopt a branch-and-bound strategy: def solutionExists(maxsteps, G, V, score, **kwargs): if len(V) == 1: return True partitions = [partition(V, score, g).values() for g in G] maxSize = max(len(P) for P in partitions) ** (maxsteps - 2) partitions = (P for P in partitions if max(len(s) for s in P) <= maxSize) return any(all(solutionExists(maxsteps-1,G,s,score) for l,s in sorted((-len(s), s) for s in P)) for i,P in sorted((-entropy(len(s) for s in P), P) for P in partitions)) This is definitely a complex function, so a bit more explanation is in order. The first step is to partition the remaining solutions based on their score after a guess, as before, but this time we don't know what guess we're going to make, so we store all partitions. Now we could just recurse into every one of these, effectively enumerating the entire universe of possible decision trees, but this would take a horrifically long time. Instead I observe that, if at this point there is no partition that divides the remaining solutions into more than n sets, then there can be no such partition at any future step either. If we have k steps left, that means we can distinguish between at most n^k-1 solutions before we run out of guesses (on the last step, we must always guess correctly). Thus we can discard any partitions that contain a score mapped to more than this many solutions. This is the next two lines of code. The final line of code does the recursion, using Python's any and all functions for clarity, and trying the highest-entropy decisions first to hopefully minimize runtime in the positive case. It also recurses into the largest part of the partition first, as this is the most likely to fail quickly if the decision was wrong. Once again, I use the standard decorate-undecorate pattern, this time to wrap Python's sorted function. def lowerBoundOnWorstCaseSolution(**kwargs): for steps in itertools.count(1): if solutionExists(maxsteps=steps, **kwargs): return steps By calling solutionExists repeatedly with an increasing number of steps, we get a strict lower bound on the number of steps needed in the worst case for a Mastermind solution: 5 steps. The greedy entropic approach is indeed optimal. Out of curiosity, I invented another guessing game, which I nicknamed "twoD". In this, you try to guess a pair of numbers; at each step, you get told if your answer is correct, if the numbers you guessed are no less than the corresponding ones in the secret, and if the numbers are no greater. Comparison = collections.namedtuple('Comparison', 'less greater equal') def twoDScorer(x, y): return Comparison(all(r[0] <= r[1] for r in zip(x, y)), all(r[0] >= r[1] for r in zip(x, y)), x == y) def twoD(): G = set(itertools.product(xrange(5), repeat=2)) return dict(G = G, V = G, score = twoDScorer, endstates = set(Comparison(True, True, True))) For this game, the greedy entropic approach has a worst case of five steps, but there is a better solution possible with a worst case of four steps, confirming my intuition that myopic greediness is only coincidentally ideal for Mastermind. More importantly, this has shown how flexible my language is: all the same methods work for this new guessing game as did for Mastermind, letting me explore other games with a minimum of extra coding. What about performance? Obviously, being implemented in Python, this code is not going to be blazingly fast. I've also dropped some possible optimizations in favour of clear code. One cheap optimization is to observe that, on the first move, most guesses are basically identical: (yellow, blue, green, red) is really no different from (blue, red, green, yellow), or (orange, yellow, red, purple). This greatly reduces the number of guesses we need consider on the first step -- otherwise the most costly decision in the game. However, because of the large runtime growth rate of this problem, I was not able to solve the 8-colour, 5-hole Mastermind problem, even with this optimization. Instead, I ported the algorithms to C++, keeping the general structure the same and employing bitwise operations to boost performance in the critical inner loops, for a speedup of many orders of magnitude. I leave this as an exercise to the reader :) Addendum, 2018: It turns out the greedy entropic approach is not optimal for the 8-colour, 4-hole Mastermind problem either, with a worst-case length of 7 steps when an algorithm exists that takes at most 6! Share Improve this answer Follow edited Mar 16, 2018 at 9:05 answered Jul 26, 2009 at 21:44 alicederyn's user avatar alicederynalicederyn 12.9k66 gold badges5151 silver badges5757 bronze badges 4 * Read up on collecctions.defaultdict class. Your partition function could be written with collections.defaultdict(set). Your multiset is collections.defaultdict(int). Excellent solution. - hughdbrown Jul 26, 2009 at 22:23 * Nice. Thanks for sharing. :) It would nice to see this on RosettaCode.org as well. - ars Jul 26, 2009 at 22:29 * @hugh: Good point on the defaultdict class. I did use that at one point, but profiling showed it was somewhat slower. It's much clearer with it, so I've stitched it back in above. Thanks. - alicederyn Aug 26, 2009 at 10:41 * 2 Whoa. That seems like a lot of work! Years ago I spend hours one night thinking about the problem on pencil and paper and felt like an idiot when I finally came to the realization that the scoring function is symmetrical. After that epiphany the coding is actually pretty simple. - Jim Dennis Aug 30, 2009 at 7:47 Add a comment | 12 I once wrote a "Jotto" solver which is essentially "Master Mind" with words. (We each pick a word and we take turns guessing at each other's word, scoring "right on" (exact) matches and "elsewhere" (correct letter/color, but wrong placement). The key to solving such a problem is the realization that the scoring function is symmetric. In other words if score(myguess) == (1,2) then I can use the same score() function to compare my previous guess with any other possibility and eliminate any that don't give exactly the same score. Let me give an example: The hidden word (target) is "score" ... the current guess is "fools" --- the score is 1,1 (one letter, 'o', is "right on"; another letter, 's', is "elsewhere"). I can eliminate the word "guess" because the `score("guess") (against "fools") returns (1,0) (the final 's' matches, but nothing else does). So the word "guess" is not consistent with "fools" and a score against some unknown word that gave returned a score of (1,1). So I now can walk through every five letter word (or combination of five colors/letters/digits etc) and eliminate anything that doesn't score 1,1 against "fools." Do that at each iteration and you'll very rapidly converge on the target. (For five letter words I was able to get within 6 tries every time ... and usually only 3 or 4). Of course there's only 6000 or so "words" and you're eliminating close to 95% for each guess. Note: for the following discussion I'm talking about five letter "combination" rather than four elements of six colors. The same algorithms apply; however, the problem is orders of magnitude smaller for the old "Master Mind" game ... there are only 1296 combinations (6**4) of colored pegs in the classic "Master Mind" program, assuming duplicates are allowed. The line of reasoning that leads to the convergence involves some combinatorics: there are 20 non-winning possible scores for a five element target (n = [(a,b) for a in range (5) for b in range(6) if a+b <= 5] to see all of them if you're curious. We would, therefore, expect that any random valid selection would have a roughly 5% chance of matching our score ... the other 95% won't and therefore will be eliminated for each scored guess. This doesn't account for possible clustering in word patterns but the real world behavior is close enough for words and definitely even closer for "Master Mind" rules. However, with only 6 colors in 4 slots we only have 14 possible non-winning scores so our convergence isn't quite as fast). For Jotto the two minor challenges are: generating a good world list (awk -f 'length($0)==5' /usr/share/dict/words or similar on a UNIX system) and what to do if the user has picked a word that not in our dictionary (generate every letter combination, 'aaaaa' through 'zzzzz' --- which is 26 ** 5 ... or ~1.1 million). A trivial combination generator in Python takes about 1 minute to generate all those strings ... an optimized one should to far better. (I can also add a requirement that every "word" have at least one vowel ... but this constraint doesn't help much --- 5 vowels * 5 possible locations for that and then multiplied by 26 ** 4 other combinations). For Master Mind you use the same combination generator ... but with only 4 or 5 "letters" (colors). Every 6-color combination (15,625 of them) can be generated in under a second (using the same combination generator as I used above). If I was writing this "Jotto" program today, in Python for example, I would "cheat" by having a thread generating all the letter combos in the background while I was still eliminated words from the dictionary (while my opponent was scoring me, guessing, etc). As I generated them I'd also eliminate against all guesses thus far. Thus I would, after I'd eliminated all known words, have a relatively small list of possibilities and against a human player I've "hidden" most of my computation lag by doing it in parallel to their input. (And, if I wrote a web server version of such a program I'd have my web engine talk to a local daemon to ask for sequences consistent with a set of scores. The daemon would keep a locally generated list of all letter combinations and would use a select.select() model to feed possibilities back to each of the running instances of the game --- each would feed my daemon word/score pairs which my daemon would apply as a filter on the possibilities it feeds back to that client). (By comparison I wrote my version of "Jotto" about 20 years ago on an XT using Borland TurboPascal ... and it could do each elimination iteration --- starting with its compiled in list of a few thousand words --- in well under a second. I build its word list by writing a simple letter combination generator (see below) ... saving the results to a moderately large file, then running my word processor's spell check on that with a macro to delete everything that was "mis-spelled" --- then I used another macro to wrap all the remaining lines in the correct punctuation to make them valid static assignments to my array, which was a #include file to my program. All that let me build a standalone game program that "knew" just about every valid English 5 letter word; the program was a .COM --- less than 50KB if I recall correctly). For other reasons I've recently written a simple arbitrary combination generator in Python. It's about 35 lines of code and I've posted that to my "trite snippets" wiki on bitbucket.org ... it's not a "generator" in the Python sense ... but a class you can instantiate to an infinite sequence of "numeric" or "symbolic" combination of elements (essentially counting in any positive integer base). You can find it at: Trite Snippets: Arbitrary Sequence Combination Generator For the exact match part of our score() function you can just use this: def score(this, that): '''Simple "Master Mind" scoring function''' exact = len([x for x,y in zip(this, that) if x==y]) ### Calculating "other" (white pegs) goes here: ### ... ### return (exact,other) I think this exemplifies some of the beauty of Python: zip() up the two sequences, return any that match, and take the length of the results). Finding the matches in "other" locations is deceptively more complicated. If no repeats were allowed then you could simply use sets to find the intersections. [In my earlier edit of this message, when I realized how I could use zip() for exact matches, I erroneously thought we could get away with other = len([x for x,y in zip(sorted(x), sorted(y)) if x==y]) - exact ... but it was late and I was tired. As I slept on it I realized that the method was flawed. Bad, Jim! Don't post without adequate testing! * (Tested several cases that happened to work)]. In the past the approach I used was to sort both lists, compare the heads of each: if the heads are equal, increment the count and pop new items from both lists. otherwise pop a new value into the lesser of the two heads and try again. Break as soon as either list is empty. This does work; but it's fairly verbose. The best I can come up with using that approach is just over a dozen lines of code: other = 0 x = sorted(this) ## Implicitly converts to a list! y = sorted(that) while len(x) and len(y): if x[0] == y[0]: other += 1 x.pop(0) y.pop(0) elif x[0] < y[0]: x.pop(0) else: y.pop(0) other -= exact Using a dictionary I can trim that down to about nine: other = 0 counters = dict() for i in this: counters[i] = counters.get(i,0) + 1 for i in that: if counters.get(i,0) > 0: other += 1 counters[i] -= 1 other -= exact (Using the new "collections.Counter" class (Python3 and slated for Python 2.7?) I could presumably reduce this a little more; three lines here are initializing the counters collection). It's important to decrement the "counter" when we find a match and it's vital to test for counter greater than zero in our test. If a given letter/symbol appears in "this" once and "that" twice then it must only be counted as a match once. The first approach is definitely a bit trickier to write (one must be careful to avoid boundaries). Also in a couple of quick benchmarks (testing a million randomly generated pairs of letter patterns) the first approach takes about 70% longer as the one using dictionaries. (Generating the million pairs of strings using random.shuffle() took over twice as long as the slower of the scoring functions, on the other hand). A formal analysis of the performance of these two functions would be complicated. The first method has two sorts, so that would be 2 * O(n log(n)) ... and it iterates through at least one of the two strings and possibly has to iterate all the way to the end of the other string (best case O(n), worst case O(2n)) -- force I'm mis-using big-O notation here, but this is just a rough estimate. The second case depends entirely on the perfomance characteristics of the dictionary. If we were using b-trees then the performance would be roughly O(nlog(n) for creation and finding each element from the other string therein would be another O(n*log(n)) operation. However, Python dictionaries are very efficient and these operations should be close to constant time (very few hash collisions). Thus we'd expect a performance of roughly O(2n) ... which of course simplifies to O(n). That roughly matches my benchmark results. Glancing over the Wikipedia article on "Master Mind" I see that Donald Knuth used an approach which starts similarly to mine (and 10 years earlier) but he added one significant optimization. After gathering every remaining possibility he selects whichever one would eliminate the largest number of possibilities on the next round. I considered such an enhancement to my own program and rejected the idea for practical reasons. In his case he was searching for an optimal (mathematical) solution. In my case I was concerned about playability (on an XT, preferably using less than 64KB of RAM, though I could switch to .EXE format and use up to 640KB). I wanted to keep the response time down in the realm of one or two seconds (which was easy with my approach but which would be much more difficult with the further speculative scoring). (Remember I was working in Pascal, under MS-DOS ... no threads, though I did implement support for crude asynchronous polling of the UI which turned out to be unnecessary) If I were writing such a thing today I'd add a thread to do the better selection, too. This would allow me to give the best guess I'd found within a certain time constraint, to guarantee that my player didn't have to wait too long for my guess. Naturally my selection/ elimination would be running while waiting for my opponent's guesses. Share Improve this answer Follow edited Nov 28, 2016 at 6:24 answered Aug 30, 2009 at 7:41 Jim Dennis's user avatar Jim DennisJim Dennis 17.2k1313 gold badges6868 silver badges117117 bronze badges Add a comment | 7 Have you seem Raymond Hettingers attempt? They certainly match up to some of your requirements. I wonder how his solutions compares to yours. Share Improve this answer Follow answered Jul 26, 2009 at 22:47 David Raznick's user avatar David RaznickDavid Raznick 18.1k22 gold badges3636 silver badges2727 bronze badges 1 * Nice link, thanks! He's also gone with the entropy approach, but with random sampling. Unfortunately, he's also limited his guesses to the set of remaining possibilities, which some work I did initially suggests he's limited to at best 6 minimum steps. (4 whites on the first step gets you in a lot of trouble, IIRC.) - alicederyn Jul 27, 2009 at 8:10 Add a comment | 4 There is a great site about MasterMind strategy here. The author starts off with very simple MasterMind problems (using numbers rather than letters, and ignoring order and repetition) and gradually builds up to a full MasterMind problem (using colours, which can be repeated, in any order, even with the possibility of errors in the clues). The seven tutorials that are presented are as follows: * Tutorial 1 - The simplest game setting (no errors, fixed order, no repetition) * Tutorial 2 - Code may contain blank spaces (no errors, fixed order, no repetition) * Tutorial 3 - Hints may contain errors (fixed order, no repetition ) * Tutorial 4 - Game started from the middle (no errors, fixed order, no repetition) * Tutorial 5 - Digits / colours may be repeated (no errors, fixed order, each colour repeated at most 4 times) * Tutorial 6 - Digits / colours arranged in random order (no errors, random order, no repetition) * Tutorial 7 - Putting it all together (no errors, random order, each colour repeated at most 4 times) Share Improve this answer Follow answered Aug 27, 2009 at 7:54 a_m0d's user avatar a_m0da_m0d 12.1k1515 gold badges5757 silver badges8080 bronze badges 2 * 3 Nice links, thanks. Unfortunately, he's built his whole strategy up on the idea that "each [guess] only the least possible modification is made to the previous assumptions". (I used to play that way, too.) One of the things my solver showed me was that you get less information if you stick to old assumptions; better to challenge your assumptions as frequently as possible to squeeze the most information out of each guess. - alicederyn Aug 27, 2009 at 8:40 * Okay - that's a good point. I have been using his method to solve it methodically, but I will start looking at other ways now as well. - a_m0d Aug 27, 2009 at 21:47 Add a comment | 1 Just thought I'd contribute my 90 odd lines of code. I've build upon @Jim Dennis' answer, mostly taking away the hint on symetric scoring. I've implemented the minimax algorithm as described on the Mastermind wikipedia article by Knuth, with one exception: I restrict my next move to current list of possible solutions, as I found performance deteriorated badly when taking all possible solutions into account at each step. The current approach leaves me with a worst case of 6 guesses for any combination, each found in well under a second. It's perhaps important to note that I make no restriction whatsoever on the hidden sequence, allowing for any number of repeats. from itertools import product, tee from random import choice COLORS = 'red ', 'green', 'blue', 'yellow', 'purple', 'pink'#, 'grey', 'white', 'black', 'orange', 'brown', 'mauve', '-gap-' HOLES = 4 def random_solution(): """Generate a random solution.""" return tuple(choice(COLORS) for i in range(HOLES)) def all_solutions(): """Generate all possible solutions.""" for solution in product(*tee(COLORS, HOLES)): yield solution def filter_matching_result(solution_space, guess, result): """Filter solutions for matches that produce a specific result for a guess.""" for solution in solution_space: if score(guess, solution) == result: yield solution def score(actual, guess): """Calculate score of guess against actual.""" result = [] #Black pin for every color at right position actual_list = list(actual) guess_list = list(guess) black_positions = [number for number, pair in enumerate(zip(actual_list, guess_list)) if pair[0] == pair[1]] for number in reversed(black_positions): del actual_list[number] del guess_list[number] result.append('black') #White pin for every color at wrong position for color in guess_list: if color in actual_list: #Remove the match so we can't score it again for duplicate colors actual_list.remove(color) result.append('white') #Return a tuple, which is suitable as a dictionary key return tuple(result) def minimal_eliminated(solution_space, solution): """For solution calculate how many possibilities from S would be eliminated for each possible colored/white score. The score of the guess is the least of such values.""" result_counter = {} for option in solution_space: result = score(solution, option) if result not in result_counter.keys(): result_counter[result] = 1 else: result_counter[result] += 1 return len(solution_space) - max(result_counter.values()) def best_move(solution_space): """Determine the best move in the solution space, being the one that restricts the number of hits the most.""" elim_for_solution = dict((minimal_eliminated(solution_space, solution), solution) for solution in solution_space) max_elimintated = max(elim_for_solution.keys()) return elim_for_solution[max_elimintated] def main(actual = None): """Solve a game of mastermind.""" #Generate random 'hidden' sequence if actual is None if actual == None: actual = random_solution() #Start the game of by choosing n unique colors current_guess = COLORS[:HOLES] #Initialize solution space to all solutions solution_space = all_solutions() guesses = 1 while True: #Calculate current score current_score = score(actual, current_guess) #print '\t'.join(current_guess), '\t->\t', '\t'.join(current_score) if current_score == tuple(['black'] * HOLES): print guesses, 'guesses for\t', '\t'.join(actual) return guesses #Restrict solution space to exactly those hits that have current_score against current_guess solution_space = tuple(filter_matching_result(solution_space, current_guess, current_score)) #Pick the candidate that will limit the search space most current_guess = best_move(solution_space) guesses += 1 if __name__ == '__main__': print max(main(sol) for sol in all_solutions()) Should anyone spot any possible improvements to the above code than I would be very much interested in your suggestions. Share Improve this answer Follow edited May 23, 2017 at 12:17 Community's user avatar CommunityBot 111 silver badge answered Oct 19, 2011 at 22:03 Tim's user avatar TimTim 19.9k99 gold badges7171 silver badges9595 bronze badges 1 * It looks and could be an interesting MM "solver" (the most promising up to this point), but still it's far from a real MM solver! It uses the solution ('actual') to generate guesses! And, BTW, it's not about 5-6 guesses ... we are talking about thousand ones (as I found out by the number of calls to the 'score()' function. Also, I replaced this function by another, which gets user input as a "reply" (as it should normally be) and returns it in exactly the same form as 'score()' does. Well, guess what: It never ends! Guesses pass very close to the solution and then they move away!! - Apostolos Feb 26, 2021 at 9:00 Add a comment | 1 Here's a link to pure Python solver for Mastermind(tm): http:// code.activestate.com/recipes/496907-mastermind-style-code-breaking/ It has a simple version, a way to experiment with various guessing strategies, performance measurement, and an optional C accelerator. The core of the recipe is short and sweet: import random from itertools import izip, imap digits = 4 fmt = '%0' + str(digits) + 'd' searchspace = tuple([tuple(map(int,fmt % i)) for i in range(0,10**digits)]) def compare(a, b, imap=imap, sum=sum, izip=izip, min=min): count1 = [0] * 10 count2 = [0] * 10 strikes = 0 for dig1, dig2 in izip(a,b): if dig1 == dig2: strikes += 1 count1[dig1] += 1 count2[dig2] += 1 balls = sum(imap(min, count1, count2)) - strikes return (strikes, balls) def rungame(target, strategy, verbose=True, maxtries=15): possibles = list(searchspace) for i in xrange(maxtries): g = strategy(i, possibles) if verbose: print "Out of %7d possibilities. I'll guess %r" % (len(possibles), g), score = compare(g, target) if verbose: print ' ---> ', score if score[0] == digits: if verbose: print "That's it. After %d tries, I won." % (i+1,) break possibles = [n for n in possibles if compare(g, n) == score] return i+1 def strategy_allrand(i, possibles): return random.choice(possibles) if __name__ == '__main__': hidden_code = random.choice(searchspace) rungame(hidden_code, strategy_allrand) Here is what the output looks like: Out of 10000 possibilities. I'll guess (6, 4, 0, 9) ---> (1, 0) Out of 1372 possibilities. I'll guess (7, 4, 5, 8) ---> (1, 1) Out of 204 possibilities. I'll guess (1, 4, 2, 7) ---> (2, 1) Out of 11 possibilities. I'll guess (1, 4, 7, 1) ---> (3, 0) Out of 2 possibilities. I'll guess (1, 4, 7, 4) ---> (4, 0) That's it. After 5 tries, I won. Share Improve this answer Follow edited Dec 22, 2013 at 2:54 answered Dec 22, 2013 at 2:39 Raymond Hettinger's user avatar Raymond HettingerRaymond Hettinger 219k6565 gold badges392392 silver badges487487 bronze badges 4 * I'm afraid someone already posted an answer linking to your recipe in 2009! See my comment on that post for my response. - alicederyn Dec 27, 2013 at 15:41 * 1 I simplified the presentation above for StackOverflow. - Raymond Hettinger Dec 28, 2013 at 1:58 * You haven't actually presented it as a solution to the question, though :( - alicederyn Dec 28, 2013 at 18:13 * Interesting, but this is not how a MM game is solved. The target (solution) must be unknown, not provided to be compare to and create guesses!! - Apostolos Feb 26, 2021 at 9:53 Add a comment | 0 To work out the "worst" case, instead of using entropic I am looking to the partition that has the maximum number of elements, then select the try that is a minimum for this maximum => This will give me the minimum number of remaining possibility when I am not lucky (which happens in the worst case). This always solve standard case in 5 attempts, but it is not a full proof that 5 attempts are really needed because it could happen that for next step a bigger set possibilities would have given a better result than a smaller one (because easier to distinguish between). Though for the "Standard game" with 1680 I have a simple formal proof: For the first step the try that gives the minimum for the partition with the maximum number is 0,0,1,1: 256. Playing 0,0,1,2 is not as good: 276. For each subsequent try there are 14 outcomes (1 not placed and 3 placed is impossible) and 4 placed is giving a partition of 1. This means that in the best case (all partition same size) we will get a maximum partition that is a minimum of (number of possibilities - 1)/13 (rounded up because we have integer so necessarily some will be less and other more, so that the maximum is rounded up). If I apply this: After first play (0,0,1,1) I am getting 256 left. After second try: 20 = (256-1)/13 After third try : 2 = (20-1)/13 Then I have no choice but to try one of the two left for the 4th try. If I am unlucky a fifth try is needed. This proves we need at least 5 tries (but not that this is enough). Share Improve this answer Follow edited Oct 28, 2012 at 2:29 jogojapan's user avatar jogojapan 69k1111 gold badges103103 silver badges132132 bronze badges answered Mar 1, 2012 at 11:28 Alain Faure's user avatar Alain FaureAlain Faure 1 Add a comment | 0 Here is a generic algorithm I wrote that uses numbers to represent the different colours. Easy to change, but I find numbers to be a lot easier to work with than strings. You can feel free to use any whole or part of this algorithm, as long as credit is given accordingly. Please note I'm only a Grade 12 Computer Science student, so I am willing to bet that there are definitely more optimized solutions available. Regardless, here's the code: import random def main(): userAns = raw_input("Enter your tuple, and I will crack it in six moves or less: ") play(ans=eval("("+userAns+")"),guess=(0,0,0,0),previousGuess=[]) def play(ans=(6,1,3,5),guess=(0,0,0,0),previousGuess=[]): if(guess==(0,0,0,0)): guess = genGuess(guess,ans) else: checker = -1 while(checker==-1): guess,checker = genLogicalGuess(guess,previousGuess,ans) print guess, ans if not(guess==ans): previousGuess.append(guess) base = check(ans,guess) play(ans=ans,guess=base,previousGuess=previousGuess) else: print "Found it!" def genGuess(guess,ans): guess = [] for i in range(0,len(ans),1): guess.append(random.randint(1,6)) return tuple(guess) def genLogicalGuess(guess,previousGuess,ans): newGuess = list(guess) count = 0 #Generate guess for i in range(0,len(newGuess),1): if(newGuess[i]==-1): newGuess.insert(i,random.randint(1,6)) newGuess.pop(i+1) for item in previousGuess: for i in range(0,len(newGuess),1): if((newGuess[i]==item[i]) and (newGuess[i]!=ans[i])): newGuess.insert(i,-1) newGuess.pop(i+1) count+=1 if(count>0): return guess,-1 else: guess = tuple(newGuess) return guess,0 def check(ans,guess): base = [] for i in range(0,len(zip(ans,guess)),1): if not(zip(ans,guess)[i][0] == zip(ans,guess)[i][1]): base.append(-1) else: base.append(zip(ans,guess)[i][1]) return tuple(base) main() Share Improve this answer Follow edited Dec 19, 2012 at 5:03 Himanshu's user avatar Himanshu 32.1k3131 gold badges113113 silver badges135135 bronze badges answered Dec 19, 2012 at 4:45 Kyle Siopiolosz's user avatar Kyle SiopioloszKyle Siopiolosz 1111 bronze badge Add a comment | 0 My friend was considering relatively simple case - 8 colors, no repeats, no blanks. With no repeats, there's no need for the max entropy consideration, all guesses have the same entropy and first or random guessing all work fine. Here's the full code to solve that variant: # SET UP import random import itertools colors = ('red', 'orange', 'yellow', 'green', 'blue', 'indigo', 'violet', 'ultra') # ONE FUNCTION REQUIRED def EvaluateCode(guess, secret_code): key = [] for i in range(0, 4): for j in range(0, 4): if guess[i] == secret_code[j]: key += ['black'] if i == j else ['white'] return key # MAIN CODE # choose secret code secret_code = random.sample(colors, 4) print ('(shh - secret code is: ', secret_code, ')\n', sep='') # create the full list of permutations full_code_list = list(itertools.permutations(colors, 4)) N_guess = 0 while True: N_guess += 1 print ('Attempt #', N_guess, '\n-----------', sep='') # make a random guess guess = random.choice(full_code_list) print ('guess:', guess) # evaluate the guess and get the key key = EvaluateCode(guess, secret_code) print ('key:', key) if key == ['black', 'black', 'black', 'black']: break # remove codes from the code list that don't match the key full_code_list2 = [] for i in range(0, len(full_code_list)): if EvaluateCode(guess, full_code_list[i]) == key: full_code_list2 += [full_code_list[i]] full_code_list = full_code_list2 print ('N remaining: ', len(full_code_list), '\n', full_code_list, '\n', sep='') print ('\nMATCH after', N_guess, 'guesses\n') Share Improve this answer Follow answered Mar 15, 2018 at 6:24 dirk's user avatar dirkdirk 1 1 * "All guesses have the same entropy" On the first round, yes, but afterwards? - alicederyn Mar 16, 2018 at 9:06 Add a comment | Your Answer Reminder: Answers generated by artificial intelligence tools are not allowed on Stack Overflow. Learn more [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] Thanks for contributing an answer to Stack Overflow! * Please be sure to answer the question. Provide details and share your research! But avoid ... * Asking for help, clarification, or responding to other answers. * Making statements based on opinion; back them up with references or personal experience. To learn more, see our tips on writing great answers. Draft saved Draft discarded [ ] Sign up or log in Sign up using Google Sign up using Facebook Sign up using Email and Password Submit Post as a guest Name [ ] Email Required, but never shown [ ] Post as a guest Name [ ] Email Required, but never shown [ ] Post Your Answer Discard By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy. Not the answer you're looking for? Browse other questions tagged * python * algorithm or ask your own question. * The Overflow Blog * Maximum Glitch: How to break Tetris * How to build a role-playing video game in 24 hours * Featured on Meta * Sites can now request to enable a banner to warn about their policy on... * Temporary policy: Generative AI (e.g., ChatGPT) is banned Linked 0 Choosing permutations with constraints 4 Whats the name of this game? 2 Generate two lists at once 0 python script for Mastermind solving stops unexpectedly (also gives error after increasing range) Related 22 Applying machine learning to a guessing game? 2 Mastermind solver guessing problems 2 Python- Stuck on a guessing game's program? 4 Mastermind in python 0 Python: Guessing game gone wrong 0 Mastermind Game Code in Python 2 how to make a guessing game in python I am struggling 0 Simple Guessing Game in Python that doesn't work 1 Mastermind game, Choosing what colour to guess 1 Mastermind Game, Pygame, Adding the guess Indicators Hot Network Questions * Could a low quality SSD enclosure prevent the TRIM functionality on my SSD? * Whether the series converges uniformly on [0,1] * Why did my coworker see a "painting-ified" version of my background image on a Zoom call? * Is there an absolute geometry that underlies spherical, Euclidean and hyperbolic geometry? * Arithmetic-progression-free sequences * Unidentified symbol in music notation * Validate a CPF number * Why was this move a miss? * Will the interference pattern still be observed with gamma rays in double slit experiment? * Why do some journals want to send the manuscript to arXiv before submission? * Half of my iCloud storage is full of nothing! (backups) * is there a program that automatically convert old printings into TeX files? * Should I push my fledgling programming work out of the development nest myself? * Virial Theorem for Gas Particles * Significant Mann Whitney, and significant t-test, but in the other direction * Did the Dutch eat their Prime Minister? * If everyone in the Senate is drunk, does that invalidate their actions? * Are umbral moonshine and umbral calculus connected? * Mesh Topology Nodes - Edges of Vertex - How to work with the weights input? * Is This a Fake Bank? * Why escape pods can't be opened from the inside? * How to motivate that Newton's method is useful? * Asking a professor for materials before the course * How do Latter-day Saints address the claim that all unique teachings of The Church of Jesus Christ of Latter-day Saints depend solely on Joseph Smith? more hot questions Question feed Subscribe to RSS Question feed To subscribe to this RSS feed, copy and paste this URL into your RSS reader. [https://stackoverflo] * lang-py Stack Overflow * Questions * Help Products * Teams * Advertising * Collectives * Talent Company * About * Press * Work Here * Legal * Privacy Policy * Terms of Service * Contact Us * Cookie Settings * Cookie Policy Stack Exchange Network * Technology * Culture & recreation * Life & arts * Science * Professional * Business * API * Data * Blog * Facebook * Twitter * LinkedIn * Instagram Site design / logo (c) 2024 Stack Exchange Inc; user contributions licensed under CC BY-SA. rev 2024.1.10.3270 Your privacy By clicking "Accept all cookies", you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy. Accept all cookies Necessary cookies only Customize settings