How We Made Computers Play Mastermind

Introduction
A game of Mastermind being played.
One player creates a secret code consisting
of 4 pegs that can each take on one of 6 colors.
The other player tries to guess that code;
the code maker responds to each guess with
one black pin for every peg in the correct spot
and one white pin for every peg with the right
color, but in the wrong spot.

    How complex are simple strategy games? Though that question may seem pointless to ask, mankind’s development of artificial intelligences may be the single most effective method by which to understand just how complicated our own human minds are. In this project, we have taken a popular one-on-one hidden code game— Mastermind— and implemented three separate algorithms, each programmed to play and attempt to win against an automated (non-AI) opponent. Each algorithm assumes a different approach to playing the game. Knuth’s Algorithm, developed based off of Donald Knuth’s optimal Mastermind strategy, utilizes a pattern by which it is consistently able to guess the correct hidden code in five turns or less. Our Genetic Algorithm makes use of search heuristics, common in the field of AI, to narrow down future possibilities and close in on the correct answer. Our final algorithm— which was custom-made for this project— attempts to mimic human logic and reasoning, to a fair degree of success. 
    Each of these algorithms differs from the others in unique ways, and each emphasizes a strength and a weakness in artificial intelligences. In comparing the effectiveness and efficiency of each of these algorithms, we can begin to understand the disparity between different techniques for strategy games— be it mathematically optimal, the mathematically streamlined, or the human.

The Donald Knuth 5-Guess Algorithm

    One of our first approaches was the algorithm designed by Donald E. Knuth to always guess the winning code in 5 guesses or less. This algorithm followed a 7-step process for selecting a guess, using the response to that guess to narrow down the remaining possible codes, and then scoring the codes in such a way as to select the next best guess. The steps went as follows:
  1. Create the set S of all 1296 possible codes.
  2. Start with the initial guess of “red red orange orange” (numerical equivalent being 1122), as this code is optimal for finding the correct code in 5 guesses or less.
  3. Play the guess to get a response of black and white pegs.
  4. If the response is four black pegs, the game is won and the algorithm can terminate.
  5. Otherwise, remove from S any code that, if it were the hidden code, would not give the same number of black and white pegs in response to the most recent guess.
  6. Apply the minimax technique to score the codes. For every possible guess, not just those still in S but every possible unused code of the 1296, calculate how many possibilities in S would be eliminated for each possible black and white peg response. This calculation is done in a similar manner to step 5. The score of a guess is the minimum number of possible codes which that guess might eliminate from S. A single pass through S for each unused code of the 1296 will provide a hit count for each coloured/white peg score found; the coloured/white peg score with the highest hit count will eliminate the fewest possibilities; calculate the score of a guess by using "minimum eliminated" = "count of elements in S" - (minus) "highest hit count". From the set of guesses with the maximum score, select one as the next guess, choosing a member of S whenever possible.
  7. Repeat from Step 3.
A minimax algorithm.

This approach also required removing a previously guessed code from both the set S and the set of all 1296 possible codes. In terms of speed, this algorithm was somewhere between the other two, being faster than the genetic algorithm but slightly slower than Felix. The first one or two guesses were always the slowest and accounted for the bulk of the time required to play the game, as it was during those initial guesses that the set of possible solutions was largest. In terms of efficiency, however, this algorithm was the best, as the average number of guesses required by it to win is approximately 4.3403, with a worst-case number of guesses equal to 5. It also required the fewest lines of code to implement, with about 126 lines of functional code in its final iteration.

The Genetic Algorithm

At this point, you may (quite justifiably) be wondering why we’re even bothering to study other Mastermind algorithms. After all, Knuth’s algorithm is provably optimal: It is impossible to create an algorithm that is guaranteed to win Mastermind in a fewer number of moves than Knuth’s algorithm does. And furthermore, the algorithm doesn’t run in an unreasonable amount of time; in our experience, it rarely takes more than a few seconds. So if Knuth’s algorithm is, it seems, pretty much perfect in every way, what is the point of trying to create a new one? How is “playing Mastermind with a genetic algorithm even though Knuth’s algorithm already exists” fundamentally different from some patently absurd proposal like “using machine learning to find minimum flows even though the Ford-Fulkerson algorithm already exists”? Why are we trying to build a better mousetrap?
As it happens, there are two reasons. The first reason is that Knuth’s algorithm is technically only optimal according to one performance metric: the worst-case metric. Knuth’s algorithm, yes, will always win in 5 guesses or less, and no algorithm exists that will always be able to win in 4 guesses or less. So, if we rate our algorithms based on the maximum number of guesses they can possibly make before finding the code, then Knuth’s algorithm indeed comes out on top. However, if we instead rank our algorithms based on how many guesses they take on average to find the code, then Knuth’s algorithm fails to be the best: It needs an average of 4.478 guesses to beat the game, being handily beaten by, among many others, Barteld Kooi’s “Most Parts” algorithm, which needs 4.373 guesses on average. While a Mastermind algorithm that is optimal according to the average-case metric has been found by Koyama and Lai (requiring an average of 4.340 guesses), that algorithm was only found through what amounted to an exhaustive search of all possible deterministic Mastermind algorithms, and extending their results to Mastermind variants with larger color pools and peg lengths is not an easy task (Ville). As such, research surrounding Mastermind algorithms generally attempts to improve average-case performance via algorithms that apply simple, intuitive, and efficient heuristics -- even if those algorithms only approximate optimality.
The second reason why we might try and go beyond Knuth’s algorithm is simply efficiency. Because Knuth’s algorithm has to, with each guess past the first, check how each member of some arbitrary subset of all the possible Mastermind codes interacts with nearly every other possible Mastermind code, it has a runtime of O((KP)2)=O(K2P), where K is the number of colors a peg can be (usually 6) and P is the number of pegs contained in a code (usually 4). However, one of the fundamental principles behind the genetic algorithm we implemented is that because guesses are constructed using evolutionary search methods and never by explicitly enumerating every possible code, its runtime is solidly sublinear with respect to the number of possible codes. Admittedly, it might seem a little rich to suggest that the genetic algorithm is more efficient than Knuth’s algorithm when, as discussed above, our implementation of the genetic algorithm takes as much or more time to run than our implementation of Knuth’s algorithm (Knuth’s algorithm takes around 4.23 seconds to run, while depending on the parameters, the genetic algorithm can take anywhere from 4.24 to 9.08 seconds). However, we mustn't be too hard on the genetic algorithm. After all, even though our implementation of it is slow, that slowness may just be the fault of the highly object-oriented way we coded it; the original paper that introduced this algorithm claims that it can run in around 0.6 seconds, and an implementation of the algorithm by GitHub user sp4ke that doesn’t use object-oriented programming has a similar level of efficiency (Berghman). Furthermore, Berghman, Goossens, and Leus themselves admit that “[their] new algorithm is more time-consuming for low values of P and [K], but the computational effort rises only slightly for larger instances, while the other algorithms are clearly less preferable for higher P and [K],” which is to say that their algorithm is designed to scale easily to more complicated Mastermind variants, and not to be more efficient on simpler variants like the 6-color, 4-peg one we’re studying. And indeed, for the Mastermind variant with 8 colors and 5 pegs, the genetic algorithm takes around 20-30 seconds to win, while Knuth’s algorithm has to run for around 15 minutes.
With the motivation for the genetic algorithm out of the way, we may finally begin discussing how it works. From our research, it seems that in general, the heuristics underlying Mastermind algorithms seem to follow one or both of the following principles:
  • Every guess made should be compatible with the clues provided from the previous guesses.
  • Every guess made should give as much information as possible concerning what the code is.
Knuth’s algorithm is, in a way, the result of a direct application of the second of these principles -- in fact, it could be said that the key innovation of Knuth’s algorithm is the fact that it abandons the first principle and sometimes makes guesses that are inconsistent with the results of previous clues in order to gain more information (Ville). Other strategies primarily following this second principle include Neuwrith’s entropy strategy and Kooi’s most-parts algorithm. However, it is the first principle that motivates Berghman, Goossens, and Leus’s genetic algorithm. Many heuristics derived from the first principle (such as those of Rosu, Shapiro, and Swaszek) involve rather crude and time-consuming (though not totally ineffective, based on our testing) strategies to find guesses that are compatible with the previous clues, such as randomly generating clues until a compatible one is found, or running through a list of all possible codes in alphabetical order until a compatible one is found (Berghman). The basic idea of the genetic algorithm, then, is to search for compatible guesses not by scouring the entire space of possible codes, but by appealing to the local search techniques our class studied in Unit 2 of this course -- evolutionary algorithms, specifically.
The broad outline of the genetic algorithm is as follows:
  1. Guess a predetermined starting code (“red red orange yellow” by default) and obtain feedback. (If the feedback is “4 black pegs,” the game is won and the algorithm can terminate.)
  2. For each following guess:
    1. Generate a starting population of random codes. (By default, the population has 150 members.)
    2. While the number of generations that have passed has not reached a certain limit (100 by default) and the number of eligible codes (i.e., codes that are consistent with previous guesses) that have been found has not reached a certain limit (60 by default):
      1. Create a new population:
        1. Crossover:
          1. Find fitness values for all of the codes in the current population.
          2. Use roulette selection based on those fitness values to choose parents for the new generation.
          3. One-point versus two-point crossover.
            Each pair of parents creates two children for the new population using either one-point or two-point crossover (the method is picked randomly, each one having a 50% probability to be chosen).
        2. Mutation:
          1. Each code in the new population has a 3% chance of a random one of its pegs being changed to a random different color.
          2. Each code in the new population has a 3% chance of having two of its pegs (chosen randomly) switch position.
          3. And finally, each code in the new population has a 2% chance of having the sequence of the pegs from one randomly-chosen peg to another be reversed.
      2. If there are any codes in the new population that are consistent with the previous guesses, add them to the set of eligible codes.
    3. Choose one of the eligible codes that was found as your next guess and obtain feedback. (If the feedback is “4 black pegs,” the game is won and the algorithm can terminate.)
An astute reader might notice that we have actually underspecified a few aspects of this algorithm; these underspecifications were intentional, as by addressing each of these deficiencies in the above description in turn, we will be able to remark on particularly interesting or odd qualities of the algorithm.
    To wit, one may note that we have not actually specified how we choose one an eligible code out of the ones found with the evolutionary search. The Berghman paper actually describes multiple strategies for doing so; the one that the authors recommend given their testing, though, is one that is heavily inspired by the second principle described above, with the added twist of “assum[ing] that the set [of eligible codes found by the algorithm] is a good representation” the set of all codes that are compatible with the previous guesses. In order to approximate how many possible codes a given guess would eliminate, this technique goes through each of the other eligible codes that were found, pretends that that code is the actual secret code chosen by the other player, and sees how many of the other found eligible codes would be eliminated by the given guess in that case. Whichever code eliminates the most other eligible codes on average in this way is chosen as the next guess. Compared to simpler ways of choosing a guess (like just picking a random eligible code out of the ones that were found), this strategy results in an algorithm with better average-case performance (in experiments we performed, over 100 trials, the recommended strategy required 4.45 guesses on average, but the random strategy required an average of 4.55) but significantly worse runtime (in those same experiments, the random strategy took 4.24 seconds on average to run, but the recommended strategy took 9.08 seconds). Perhaps this slowness is to be expected, though -- the recommended strategy does require us to iterate through a list using a nested loop three layers deep!
    Of course, we also haven’t specified what happens when the genetic search doesn’t find any eligible codes, and thus there are no eligible codes to choose from in the first place. The paper, in fact, does not actually state what the algorithm should do in this case. In my implementation, I give the user the option to make the algorithm default to choosing random codes until an eligible one is found, or to make the algorithm continue more generations until an eligible code is found. Overall, though, it seems that the best way to deal with this ambiguity is to make the population size and number of generations large enough so that this situation rarely comes up. Finally, we have not specified the fitness function. While the exact fitness function is a bit too complicated to describe in detail here, suffice it to say that it checks “how consistent” a code is with the previous guesses and clues. If the clues that the previous guesses would engender -- if a particular code were the actual secret code -- contain very different numbers of white and black pegs than the real clues do, then that code is given a high fitness value. Meanwhile, if the clues that the previous guesses would engender if that particular code were the real code are identical to the real clues, then the code has a fitness of 0, and it is considered eligible. However, this fitness function has a problem: It gives lower fitness values to more desirable population members, even though high-fitness codes are more likely to “pass on their genes.” We tried modifying the fitness function so that more eligible codes have higher fitness (the new fitness function, in effect, was the reciprocal of the old fitness function plus one), and the results were drastic: not only did the average-case performance of the algorithm improve slightly, but the algorithm became much better at finding eligible codes (running into the aforementioned “no codes found” scenario significantly less often). It feels as though we misread the Berghman paper somewhere (surely professors at the Katholieke Universiteit Leuven wouldn’t make such an obvious mistake in their research!), but we don’t see how.
    Suffice it to say, from the unspecified edge cases to the backwards fitness function to the deeply-ingrained inefficiencies in our implementation of the game Mastermind, we ran into a few technical hiccups as we coded this genetic algorithm. But at the end of the day, this genetic algorithm is nonetheless a wonderful demonstration of the importance of specifying a performance metric, the eternal trade-off between optimality and efficiency, and the power of even the slowest local search algorithm to asymptotically reduce the amount of time needed to hunt down something as elusive as an eligible code.

The Custom-Made AI (“Felix”)

    Our final approach to developing an artificial intelligence was an attempt to imitate a human playstyle as closely as reasonably possible. The result of this attempt was Felix, an AI which uses pseudo-reasoning to determine what it believes to be the simplest path forward when guessing the opponent’s hidden code. The strategy our custom AI utilizes was loosely based on the strategy used by one of our (human) team members. Rather than simulate future probabilities or run through long lists of pre-generated codes— which a computer can do with ease in a very short amount of time-- our third AI runs through a sequence of if-statements designed to corral each game towards one of a series of “final moves.” 
    Each guess the AI makes attempts to elicit a response that it can recognize as a certain state of the game’s progress; similarly to how a person may have developed a routine response to certain situations, Felix is programmed with several methods that each handle a scenario from which it knows it can eventually win. These methods are labeled appropriately— “handleTwoUnknowns” and “handleOneUnknown” for when it is closing in on the correct answer, or “handleThreeBlack” for the surprise scenario when the AI has made a lucky guess and nearly gotten it right. Other methods simulate basic strategies a human would use to gather more information, such as “test,” which takes two pins— one which is in the correct spot, one that isn’t— and figures out which is which.
    Yet another strain of functions at Felix’s disposal are those that are specifically designed to analyze information after a certain action has been complete. “analyzeFirstPhases” takes the information gained from the first few experimental guesses of the game and uses the given clues to decide whether it can confirm if any colors belong in any specific locations, or if further testing needs to be completed. On the other hand, “finalAnalysis” handles any situation where a large amount of information has been gathered, but no one clue has been provided that the AI can latch onto and reach an ultimate conclusion from.
Understandably, Felix relies on a large amount of code to properly function in comparison with his peers. While the Genetic Algorithm and Knuth’s Approach each take less than 250 lines of code, our custom-AI is written with nearly 1000 lines. Still, Felix only really scratches the surface of human strategy. There are several things that a person can do— patterns that they can recognize, or actions they can take to attain more data— that Felix cannot. While there are a considerable number of things that our AI can accomplish in pursuit of identifying the right code and winning the game, there are yet many more that were too complex to implement in time available to us.
    In terms of success, Felix is also handicapped by the methods by which he approaches the game. While the other algorithms that we programmed make use of a computer’s strengths to quickly and effectively win, our custom AI depends on a limited number of human strategies for gathering information. It is, by design, not allowed to run through hundreds of probabilities or keep track of lists of thousands of codes. Because of this limitation, our AI averages 10 guesses to find the correct code in a single game of Mastermind. When given twenty guesses total, the algorithm will win 80% of games, and run out of guesses in the remaining 20%. However, the lack of for-loops, data mining and list searching that the algorithm takes part in allows it to run through hundreds of games in the span of a few seconds. So, at the very least, Felix can accomplish being a little slow very quickly.

Conclusion

Compared with one another, each of the algorithms implemented in our project interact in a unique way with the Mastermind environment, and do so with differing levels of speed, efficiency, and effectiveness. The Knuth algorithm was indeed always able to successfully guess the correct code within five turns or less, making it both the most efficient and the most effective of the three approaches. It is also the second fastest of the three algorithms, taking a few seconds to run through a single game, though the bulk of this time was spent on the first one or two guesses. Most often Knuth would find the correct code in 4 guesses, with 5 guesses being the second most frequent outcome, and 3 guesses being the rarest. Our genetic algorithm, which predicts which future guesses will eliminate the most possibilities (in other words, provide the most information), performs at a similar level of efficiency, taking on average five guesses to find the correct code — usually requiring a few more or a few less. This puts it on equal footing with the Knuth algorithm in terms of average and best-case scenario number of guesses, and far above Felix in those categories as well. However, it is the slowest of our three algorithms in terms of time and the least resource-efficient, taking on average upwards of thirty seconds to complete a single game. It is also the least resource-efficient (though not much worse than Knuth) due to having to generate and then modify successive populations of genetic code. That being said, like the Knuth algorithm, this approach always manages to find the correct hidden code, and it could be made much faster if we were to rewrite portions of our Mastermind environment to be more compatible with a genetic algorithm.
    Our custom-designed algorithm (nicknamed “Felix”) is by far the least effective and the least efficient of the three algorithms. In attempting to mimic human logic and natural approaches to playing the game, it can take as many as fourteen or fifteen guesses to correctly find the code, and only wins about four in five games (sometimes more, sometimes less). Given its noticeably lower efficiency, however, Felix is incredibly fast, capable of playing through hundreds of games in the span of a couple of seconds. Though it cannot predict future outcomes or calculate with numerical precision the best guesses to make, where the Knuth and genetic algorithms can only successfully complete one game, Felix can finish hundreds, if not thousands. This is accomplished through a logic which is far more efficient than the other two algorithms, consisting of a series of if-statements rather than time-intensive for-loops, memory-guzzling lists, and painstakingly slow and complex selection and scoring methods. This makes Felix by far the fastest and most resource-efficient algorithm of the three. 
    Regardless of their success, all three algorithms accomplish the same goal: showcasing the strengths, weaknesses, and potential of artificial intelligence in strategic reasoning. The three algorithms we created all demonstrate different approaches to making strategic AI. There’s the mathematical approach embodied in the Knuth algorithm, which is overall the best of the three algorithms across the different categories mentioned above, but is also the least practical for a general artificial intelligence. Being optimized specifically for Mastermind makes the range of applications for which the Knuth algorithm can be utilized very limited, and it would doubtlessly be difficult to come up with similar algorithms for every possible scenario an AI might encounter which requires strategic thinking. The genetic algorithm is similarly effective and efficient, but, like evolution itself, is frustratingly slow. However, if one is willing to be patient, then the genetic algorithm would be much more optimal for a general AI as the approach of genetic algorithms can be applied far more generally than the mathematical logic of Knuth. In other words, it is more adaptable, though the issue of speed may always be a factor as, unlike the code for Mastermind, not every environment can be modified to fit the algorithm, rather than the other way around. Felix demonstrates, in a way, the ultimate goal of AI: to think like a human. But Felix shows both the promise and the disappointment of this goal. Felix was able to replicate human logic in a very fast manner and in a way which was recognizably human. However, Felix also required by far the most lines of code and was less effective at winning the game than the other two algorithms. Felix raises the question then of could we replicate human thinking right now, if we are only willing to tolerate a human-level of inaccuracy and dedicate the copious lines of code and work-hours it would require to encapsulate the workings of a human mind?

References

Berghman, Lotte, Dries Goossens, and Roel Leus. 2009. “Efficient Solutions for Mastermind Using Genetic Algorithms.” Computers & Operations Research 36 (6): 1880–85. https://doi.org/10.1016/j.cor.2008.06.004.

Knuth, Donald. 1976. “The Computer as Master Mind.” Journal of Recreational Mathematics 9 (1). http://www.cs.uni.edu/~wallingf/teaching/cs3530/resources/knuth-mastermind.pdf.

Kooi, Barteld. 2005. “YET ANOTHER MASTERMIND STRATEGY.” ICGA Journal 28 (1): 13–20. https://doi.org/10.3233/icg-2005-28105.

Ville, Geoffroy. 2013. “An Optimal Mastermind (4,7) Strategy and More Results in the Expected Case,” March. https://arxiv.org/pdf/1305.1010.pdf.






Comments

Post a Comment