I bought an old fashioned 1972 Original MasterMind on eBay in a bid to play with my kids and teach them some logical reasoning… Mind you, they are 6 months old and 2.5 years old, so there’s a bit of time until it happens.
A bit of time that can conveniently be allocated to develop a MasterMind solver in Excel and VBA! A solver and a game also, as it’s easy to generate randomly a combination and hide it with VBA: who would think at work you are not working with Excel on your screen?
It reminds me the very clever site for the purpose of slacking at work: www.cantyouseeiambusy.com. It doesn’t exist anymore… Unfortunately!
MasterMind is a very simple game, created in 1970. A player (codemaker) is creating a 4 colour code, 6 colours are available to him (he can repeat the same colour in the code as many times as he wants). There are some variant to the game but the 4 colour code out of 6 is the original game. There are therefore 1,296 permutations:
The other player (codebreaker) has 10 attempts to decode it (once again there are some variants, but 8/10 is more than enough). After every attempt, the codemaker needs to give an indication: how many colours pegs are correctly placed (without disclosing which one, symbolised by a black peg on the side of the board) and how many colour pegs are incorrectly positioned (without disclosing which one, symbolised by a white peg on the side of the board).
In case of duplicated colours, they have to work by pair. In other words, if there are two reds in the code but only one red in the attempt, code maker will award one peg:
- A black peg if the red peg in the attempt is in the position of one of the two reds in the code;
- A white per if the red peg in the attempt is not in the position of both of the two reds in the code.
In other words, no indication is provided on whether a colour is duplicated if the codebreaker is not duplicating himself a colour in his attempt. Also if the code breaker has duplicated colours while the codebreaker has not, no indication is given about which one is correctly positioned or not. The following should cover all the possibilities to avoid misunderstanding.
In Excel, rather than colours, we will use numbers from 1 to 6.
As a kid, the intuitive way to start is to ‘waste’ up to five attempts to identify all the colours by creating single-coloured attempts. Five attempts as the three first one might identify a colour, the two following not and the sixth colour would not need to be attempted as it would be obvious it is in the code (or not). In case of luck and or duplication, it can take four attempts only. This is why duplicating colours is probably not the best strategy as a codemaker.
In the below example, we know 1,2,3 and 6 will be the component of the code but there is no clue yet about their respective position.
Anyway, the issue with a such strategy is that with the 4 colours identified, there are still 24 permutations (if there is no duplicated colours), not easy by any means to crack in 5 or 6 attempts, especially we have no clue yet about any of the position of the colours in the code! Luck is actually needed to break the code in the 5 or 6 next rounds. But kids or beginners will intuitively start from there and hopefully frustration of failing will make them evolve to a more consistent approach.
Indeed, the normal evolution of a player would be to keep a colour on the code when identified to start playing with its position, this is much more effective.
Let’s assume a 1,2,3,6 code (although displayed, unknown until the end obviously). Player is starting with a full house of 1’s, he gets on black peg.
He knows there is a 1, he keeps one and complete with 2’s. Let’s assume he gets a black and white peg. It can only mean the there’s a 2 in one of the three positions and the 1 is misplaced. If the output were two whites, it would give away the position of the 2 (where the 1 is currently sitting).
Anyway, he keeps a 1, change its position, he keeps a 2 and complete with 3’s. Bad luck he gets three white pegs.
But it now means the 1 and the 2 are in the two first positions (without knowing the order yet) and there is a 3 in one of the two last positions. He carries a 3 and introduce one 4. Bad luck he keeps having three whites.
However, he now know that he will gain two blacks by inverting the 1 and 2, he knows there is no 4 (he will switch to 5) and know the 3 can only go in the third position!
Switching to a 5 is unsuccessful to identify the fourth colour but at least he got the three other in correct positions.
Therefore, last attempt can only be the good one.
It took six attempts to break the code. Including a bit of bad luck, lets say the two first attempts are not identifying any colour, that would be eight attempts worst case. Eight attempts is really the maximum any decent player should reach, decent number of attempt is six. The number of attempt will make a difference to break a tie between the players (the codbreaker and the codemaker will obviously switch, a bit like in cricket!).
Therefore, they key of the game is to use the information gathered on the previous attempt in order to succeed in a quicker manner.
A standard strategy is to run initially two colours at the same time and the next attempt should be consistent with all previous feedbacks. However, sometimes there can be an advantage to post an inconsistent attempt (in other word an attempt that cannot be the code considering attempt received on previous attempts).
Let’s start with 1,1,2,2. One black, one white. Well it means, either:
- a – Two 1’s with only one correctly positioned and no 2, or;
- b – Two 2’s with only one correctly positioned and no 1, or;
- c – One 1 and one 2, one of each being correctly positioned, the other incorrectly.
We’ll have to take assumption and progress consistently while this assumption is not proven wrong. Let’s assume we have two 1’s and no 2, assumption a, and let’s introduce 3’s.
One black and two whites: it confirms there is at least one 1 and one 3, nothing much more. Also, assumption b can be ruled out: there can still be a 2 but only one.
Let’s assume we are still under the assumption a, as it cannot bu ruled out just yet, in other words, there could only be one 3 and we therefore can introduce a 4.
We are technically decreasing the information there as we are down to only two feedback pegs: one white and one black… But what a great deal of information retrospectively! Indeed, it means:
- There will be two 3’s;
- Therefore if there are two 3’s, there is only one 1, and if there is only one 1 there is one 2 and correct assumption was assumption c;
- In other words, we have all the code components: two 3’s, one 1 and one 2;
- The 1 is not in the first position, else it would mean on attempt number two the two 3’s are white pegged and they would steal the spot of the 1.
Quite overwhelming and finally convincing for a first impression of bad luck! This is the why it is a wonderful game, played efficiently, the previous attempts will give a great amount of feedback retrospectively.
Back to attempts 1, we can still consider the black was pointing at a 1, but the other one. Therefore, the 2 could only be in the first position, and the two 3’s on the right.
Bad luck, four whites. And it shows why duplicating colours is not necessarily good. Next attempt is the good one, if the 3’s are white pegged, they can only be on the two other positions. It means on attempt two the black peg was for the 3 in the second position, therefore the 1 has to come last!
Job done! Five attempts is pretty good, but the response on the first two attempts were pretty good, so there was a bit of luck. Luck will help not solving the code but solving it in a quicker manner if first couple of attempts are lucky enough to give a lot of information. If computer algorithm is averaging 4.34 attempts (with worse case scenario at 7 attempts), 5 is good for a human being.
But these are the most consistent human strategy. A human being will fail ruling out every possibility at every turn as a universe of 1,296 possibilities would require some kind of brain power. But what about using a computer program as hinted before?
Let’s start by building the game before building the solver on it.
Generating the Code
The obvious first step will be to generate the code and hide it.
There is a random number generator in VBA. But it generates a number between 0 (included) and 1 (excluded), a uniformly distributed (it is what we want, we don’t want the tails (1 and 6) to occur less often than 3 and 4. We will check the distribution obviously!
By multiplying our random number by 6, we will have a number between 0 (included) and 6 (excluded). By adding 1 to this number, we will have a number between 1 (included) and 7 (excluding). By keeping the integer part of the generated number, it should give us an integer uniformly distributed between 1 (included) and 6 (included)Let’s generate 12,000 random numbers with this process just to double check.
It seems fair enough. The hypothesis that it is an actual uniform distribution could obviously be statistically tested but we will trust our instinct from now, empirical results are enough proof for the purpose.
We fill the cell in black (to avoid seeing the code).
We generate the 4 numbers.
We allocate them to our cells.
Generating the Feedback
It starts to be interesting there. It will be straight forward to compute the black pegs. Indeed, we will create a function and arguments will work by pair, if the pair is matching, black peg, if not, no black peg. This one is very straight forward, not much comments needed. Here is the complete formula.
The white pegs formula is more interesting. If it is also all about matching the arguments of our function, the challenge is that we must exclude situations where it would be a black peg, and we should not double count matchings. When a white peg is awarded, the colour in the code and in the attempt will be taken out of the equation.
For easiness, we will store the arguments in 2 different array variables, one for the code, one for the attempt. Array variables need to be dimensioned. We will then first check if there is some potential black pegs and if so, we will clear the variables accordingly, in order not to consider them for awarding a white peg.
Then we will try to match code colour to attempt colour, if there is a match, we increment the number of white pegs and we need to clear the variable in order the pair no to be matched again. Not too complicated after all!
And this is pretty much it! File can be downloaded here: MasterMind.xlsx
To start playing, click ‘Manual Play’, it will clear the data, create a hidden code and off you go! ‘Reveal Code’ button will show the code. ‘Clear’ button will clear the attempts (not the code) and reinitialize the database of ruled out combinations.
Automated Play and Algorithm Solving
Let’s now work on the solver.
By iteration, it is conceptually very easy to scan all the possibilities and ultimately find the good one. The most common approach was developed by Donald Knuth in 1977.
Let’s start with a first attempt, whatever it is. This combination will get a feedback like on black peg and one white peg. The program is going to rule out all combinations that would not give a such feedback considering the attempt.
Indeed, let’s assume first attempt is 1,1,1,1 and gets two blacks and no white. The algorithm will rule out any combination where if it was the code, the feedback on a 1,1,1,1 attempt would not be two black and no white.
A couple of examples:
- If 1,2,3,4 was the code, the attempt of 1,1,1,1 would give one black and no white, therefore, 1,2,3,4 cannot be the code and is ruled out;
- If 1,2,3,1 was the code, the attempt of 1,1,1,1 would give two black and no white, therefore, 1,2,3,1 can be the code and is kept in the universe of the possibilities.
On the particular example, it will keep all the combinations that contain only two 1’s. How many that is? 2 slots are still available, this is 36 possibilities, then the four pegs with one duplicated needs to rearranged. Therefore, the number of possibilities left are calculated as follows:
In other words, a single attempt is ruling out two third of the total possible codes and none of the ruled out codes should be played. In the vast majority of the cases, there is no advantage posting an inconsistent attempt (an attempt that has already been ruled out as a possible code).
For the second attempt, the program will pick a combination in the 432 remaining available and will go through the same process, eliminate codes that can’t be the good one, select a new one in the remaining, etc,… Until either there is only one code available, or until the attempt is luckily successful.
Indeed, there is a bias in a simple iteration. The order of the iteration and the first code will impact the number of attempt before success.
We have chosen a standard rotation order, from the right, to the left.
First try will therefore be 1,1,1,1. Let’s suppose 1,1,1,1 and 1,1,1,2 are ruled out, first available code in the list would be 1,1,1,3 and would therefore be the next attempt. There is nothing optimal in the approach. It does the job for sure, but it probably uses more attempt that a computer should require.
As a matter of fact, a code of 4,5,6,3 would take seven attempts to be broken by the algorithm that way!
If we force the first trial to be something cleverer like 1,1,2,2, the algorithm is doing it in 6 attempts, which is not optimal either. 1,1,2,2 gives no black or white peg, therefore, the first available code in the list becomes 3,3,3,3, not optimal either, 3,3,4,4 would be where a human goes.
But let’s focus initially on just making the job: the algorithm will find the solution with a standard iteration in the list of a standard rotation.
First, let’s write the 1,296 possibilities. It’s going a quadruple 1 to 6 For To Next imbricated loop! Sounds more complicated that it is, it is actually quite straightforward. We’re coppying the list in 2 different sheets as we’ll also need it at a later stage for optimizing the solving.
Then we will cater for 10 possible attempts (1 to 10 For To Next), look for the first not ruled out combination, use them as an attempt, checking the number of white and black pegs, and if there is 4 black pegs, the program can end, if there is no 4 black pegs, the program will continue and will obviously rule out current attempt.
Program will therefore take the current attempt and scan all combinations that have not been ruled out yet. Program will therefore compare the selected combination with the current attempt and the feedback in terms of white and black peg should be the same one, else the combination cannot be the code and will be ruled out. When process over, algorithm is going to the next attempt.
And eventually, we will get there! Not in the optimal way but it works!
Let’s take back our 4,5,6,3 code.
We can see that the first three attempts are clearly not optimal. We can easily implement a forcing of the first attempt, let’s try with 1,1,2,2. As mentioned before, it only gains a step as the first available combination in the list becomes the 3,3,3,3, still not optimal.
Sometimes it won’t even gain a step and program will actually struggle to make it below six.
Is there a way to make the program chose a better combination among st those available for testing? A Minimax approach is required.
It will take a great amount of time, probably 10 minutes, especially if program is not optimized… Which is most probably the case! One of the obvious lack of optimization is the fact our Black and White formulas are used as Excel formula and result is picked up from the Excel cell and it is using a lot of memory, it should be used as formula also inside VBA. The program can be optimized, this is a certainty, and to gain some execution time, we need to switch off the automatic calculations where not required.
The first attempt will be set to 1,1,2,2 as it could be demonstrated the pattern is the best start for optimization. And the feedback will rule out, as usual some combinations. The frist step of the algorithm is similar indeed. But to select the second attempt, we are going to compare all the remaining possibilities to select the best one. The process is as follows:
- a- We select a potential attempt among the universe of combinations that are not ruled out just yet;
- b- We compute the black and white peg feedback between the selected potential attempt and all the combinations that are not ruled out yet;
- c- We classify and count the feedbacks (like x1 number of no black / no white, x2 number of one black / zero white – there are 14 different possible feedbacks, see below, noted Black,White and for example, 3 blacks and 1 White is obviously impossible);
- d- We record the Max(x1,x2,x3…x14), as a high number indicates a high number of commonalities with the rest of the available combinations, in other words, a combination with a higher Max will eliminate less combinations and we want the program to select the attempt that is going to rule out the greatest number of possibilites;
- e- When all the Max are recorded, we pick the combination that has the minimum Max, hence the name Minimax (if there are several matching Max, some discretion has to intervene, but we will take consistently the first minimal Max available).
- f- Then we use the selected combination, check the feedback, rule out more combinations and program is looping back to step a.
The solver part of the code is barely changing, we need to set the trial one to 1,1,2,2 then the subsequent trials, another macro (MinMaxMac) is called to select it. MinMaxMac is outputting in the second sheet in cell V1 the line of the attempt to consider.
Let’s have a detailed look at MinMaxMac.
We are going to get the fedback trying all the potenital attemps with other potential attempts, a matrix really, so this is a very straight forward double loop imbricated.
We have copied the attempt in X2:AA2 and the code in X1:AA1, in AB2 and AC2 stands our formulas Blanck and White for the feedback, hence, we will create a string like 1,2 if the feedback is one black and two whites, as similar notation is used at the top of the colum of the matrix.
In the correct feedback column, we increment the code by 1.
The aim, is to know how many potential 0,0 a code will have considering all the attempts, how many 0,1, how many 0,2, etc,… The matrix is done the other way around in the program but this is irrelevant, the following is showing the output. In the following (not meant to be realistic by the way, just for illustration purpose), there are 209 attempts that have not been ruled out. The number of feedbacks against all other combinations are summed. We want to keep the one that has the minimum maximum. In this case, maximum on 1,2,3,4 is 75 (on 0,0) and maximum on 3,4,5,6 is 85 (on 0,0 as well but it’s irrelevant on which feedback it is). We will therefore chose 1,2,3,4 rather than 3,4,5,6. Why? Because this maximum means that the 0,0 feedback on 1,2,3,4 is the most probable (75/209=35.89% chances) and if this feedback occurs, it will rule out 209-75=132 combinations. On the other hand, 3,4,5,6, the most probable feedback has 85/209=40.67% chances of occurrence and would only rule out 209-85=124 combinations.
The maximum is calculated through an excel formula in U1298, is hard coded in the accurate line. Ultimately, cell V1 is looking up the minimum of the maximum to retrieve the line number of the corresponding combination (or the fist one in the list should there be identical minimums, the one that will be used for the next step.
That’s about it really!
Let’s take our 4,5,6,3 code and compare the methods.
The top one is the algorithm using at every attempt the first available non-ruled out combination (listed as a standard rotation): it is solved in 7 attempts.
The top one is the algorithm using at every attempt the first available non-ruled out combination (listed as a standard rotation), but the first attempt is forced to 1,1,2,2: it is solved in 6 attempts.
The bottom one is the algorithm starting with 1,1,2,2, with the Donald Knuth optimization for the selection of subsequent attempts: it is solved in 5 attempts.
Very useful to see the improvement! However, this is not systematic, one attempt won’t be won with every single code.
It is highly dependent on the position of the code, for example, 1,1,1,2 will be solved in 2 attempts with our 2 first methods as 1,1,1,1 will be ruled out on the first attempt, and the next available attempt is the code! The Knuth optimization is solving it in 3 attempts!
Even more obvious, if the code is 1,1,1,1 our first algorithm is getting it at attempt 1, the same algorithm forcing the first attempt at 1,1,2,2 will get it in 2 attempts and Knuth in 4 attempts!
But over a great number of runs, the Knuth optimization will be performing much better and it will take an average of 4.34 attempts to break the code and in no more than 6 attempts. There’s a lot of potential fun to have on programming and research, a few ideas:
- Chose another rotation of possibilities;
- Create an ex-aequo Minimax tie breaker algorithm;
- Try all different first attempts.
Possibilities are endless and that’s why the game is never boring!
Wikipedia – Mastermind: https://en.wikipedia.org/wiki/Mastermind_(board_game)
Wikipedia – Minimax: https://en.wikipedia.org/wiki/Minimax
Permutations with Repetition: https://brilliant.org/wiki/permutations-with-repetition/
Mastermind – Tom Davis: http://www.geometer.org/mathcircles/mastermind.pdf
An Optimal Mastermind (4,7) Strategy and More Results in the Expected Case: https://arxiv.org/pdf/1305.1010.pdf
Tactile Tools for Teaching – An Implementation of Knuth’s Algorithm for Mastering Mastermind: http://www.antonellaperucca.net/FioreLangPerucca.pdf
Selected Papers on Fun and Games: https://www-cs-faculty.stanford.edu/~knuth/fg.html
Can’t you see I’m busy, or, how to waste your company’s time at work: https://techcrunch.com/2009/10/06/cant-you-see-im-busy-or-how-to-waste-your-comapnys-time-at-work/