Decoding Mastermind
Mastermind is a code-breaking board game for 2 players. It was invented by an Israeli postmaster and telecommunications expert named Mordecai Meirowitz in 1970 (note 1). The most prevailing modern version has introduced a set of new rules for 3–5 players taking turns to be either the codemaker or the codebreaker (note 2).
[This is the English translation of the author’s article in Traditional Chinese published on 6 May 2020. Apologies for any grammatical mistakes or inaccurate expressions in this article.]
Game Rules
In a 2-player game, the codemaker picks a pattern of 4 pegs in different colours out of 8 colours (including red, green, blue, yellow, orange, pink, grey and white) to make the code, while the codebreaker has to guess the code within 12 turns. The codemaker has to provide a feedback to the codebreaker in each turn, using a red scale from 1 to 4 (R) to indicate any pegs in both correct colour and correct position, and a white scale from 1 to 4 (W) to indicate any pegs in correct colour but wrong position (note 3).
e.g. The codemaker picked 🔴🟢🔵🟡 (RGBY) as the answer and the codebreaker guessed ⚪🟠🟢🟡 (WOGY) in the 1st turn. Since the codebreaker got 2 correct colours 🟢🟡 (GY) but only 1 correct position 🟡 (Y) in this turn, the codemaker would give 1R1W as the feedback.
A game will end once the codebreaker either successfully breaks the code or fails to break the code within 12 turns. Each of the 2 players takes turns to be the codemaker or the codebreaker. The codebreaker should aim to break the code with the least possible number of turns. I have created a scoring scale for a 2-player game for readers’ reference and experiment (note 4).
I would like to focus on the analysis of the decoding process for the rest of this article.
Game Analysis
When I firstly experienced Mastermind, I thought of those flash games on Neopets including Codebreaker and Time Tunnel. All those games have similar rules that the codebreaker needs to break the code within a limited number of turns. The decoding process involves logical thinking and knowledge in combinations and permutations, and thus it is worth studying.
The codemaker picks a pattern of 4 pegs in different colours out of 8 colours, which involves the concepts of combinations and permutations as below:
1. Picking 4 colours out of 8, number of combinations = 8C4 = 8! / (4! 4!) = 70
2. Arranging positions of 4 colours, number of permutations = 4P4 = 4! = 24
Aggregating the 2 points above, we have the number of permutations for arranging positions of 4 colours picked from 8 = 70 * 24 = 1680 (or 8P4 = 8! / 4! = 1680)
The codebreaker’s target in this game is to find out the only 1 correct permutation out of 1680 within 12 turns. As the number of permutations is huge comparing to the maximum number of turns, the codebreaker has to utilize every feedback provided by the codemaker in order to strategize his guesses in the remaining turns. My strategy is to prioritize solving the 70 combinations over solving the 24 permutations, which appears to be less complicated than the other way round.
There are 14 different types of feedback provided by the codemaker: 0R0W, 0R1W, 0R2W, 0R3W, 0R4W, 1R0W, 1R1W, 1R2W, 1R3W, 2R0W, 2R1W, 2R2W, 3R0W, 4R0W (note 5)
5 out of the 14 types of feedback are more favourable to the codebreaker. The remaining 9 are less favourable and the codebreaker needs to pay more effort to solve. The 14 types of feedback can be further divided into 3 sets:
- Set A {4R0W}
The codebreaker breaks the code and ends the game. - Set B {0R0W, 0R4W, 1R3W, 2R2W}
The set can be split into Set B1 {0R0W} and Set B2 {0R4W, 1R3W, 2R2W} with identical characteristics.
Set B1 {0R0W} — None of the 4 pegs are in correct colour or position. Thus, the remaining 4 colours must be included in the code, and the codebreaker only needs to find out the correct permutation of the 4 pegs.
Set B2 {0R4W, 1R3W, 2R2W} — All of the 4 pegs are in correct colour, but at least 2 of them are in wrong position. Thus, the codebreaker only needs to find out the correct permutation of the 4 pegs. - Set C {0R1W, 0R2W, 0R3W, 1R0W, 1R1W, 1R2W, 2R0W, 2R1W, 3R0W}
Not all of the 4 pegs are in correct colour. Thus, the codebreaker needs to find out the 4 correct colours first and then the correct permutation.
The codebreaker should aim to reach Set A to end the game. Typically, the codebreaking process should go through Set C -> Set B -> Set A.
After each turn, the codebreaker will either stay in the same set or proceed to the next set. There is a trivial chance to reach Set A right from Set C. If the codebreaker reaches Set B1, he must reach either Set B2 or Set A in the next turn.
When the codebreaker reaches Set C, he should aim to find out the 4 correct colours and then the correct permutation, R+W=4 will be the checkpoint in the middle of the game. Also, the codebreaker should compare the guess and feedback in each turn carefully to make the next guess. I will give an example to illustrate (Set C -> Set B).
When the codebreaker reaches Set B, the riddle will be simplified into the correct permutation of the 4 pegs with a total of 24 permutations. However, the codebreaker has only 12 turns to break the code, so it is hard to win the game using exhaustive method. Instead, the codebreaker has to utilize each feedback from the codemaker to minimize the code range. I will give 2 examples to illustrate (Set B -> Set A).
I will let ABCDEFGH represent the 8 colours in the following examples.
Case 1 (Set C -> Set B)
The codemaker made the code ABCD. The codebreaker guessed AEFG in the 1st turn and got the feedback 1R0W.
The codebreaker assumed that G is in the code while AEF are not (please note that G should be maintained in the same position for verification purpose) and then chose 3 out of BCDH. He guessed BCHG in the 2nd turn and got the feedback 0R2W.
The codebreaker noted that the 1R in the 1st feedback did not exist in the 2nd feedback, so he inferred that G was not in the code, the 1R should refer to 1 of AEF and the 2W should refer to 2 of BCH. Besides, the codebreaker included 7 colours in the 2 guesses but only 3 colours are correct, so the remaining correct colour must be the unknown D.
The codebreaker then chose E out of AEF, BH out of BCH and D. He guessed DEBH in the 3rd turn and still got the same feedback 0R2W.
As the number of correct colours remained unchanged even the codebreaker added a correct colour D and removed a wrong colour G, the codebreaker deduced that he might have removed a correct colour in this turn, which is C. Also, the codebreaker noted that the 1R in the 1st feedback did not exist in the 3rd feedback, so he inferred that E was not in the code. At this point, the codebreaker knew that 1 of AF is correct and 1 of BH is correct and he could reveal all the 4 correct colours within 2 trials (or 3 turns maximum to actually state the correct colours).
The codebreaker chose F out of AF and B out of BH to form CBFD in the 4th turn. He got the feedback 2R1W.
It could not be assured whether AB/AH/BF/BH are the remaining 2 correct colours until the codebreaker either switched B to H or switched F to A in the 5th turn. Finally, the codebreaker got all 4 correct colours ABCD in either the 5th or 6th turn.
Case 2 (Set B -> Set A)
The codemaker made the code ABCD. The codebreaker guessed BCDA in the 1st turn and got the feedback 0R4W.
The codebreaker should make good use of the hint 0R4W by screening out all permutations of BXXX / XCXX / XXDX / XXXA which had at least 1 colour in the same position with BCDA.
Only 9 out of 24 permutations were left after screening: ABCD, ADBC, ADCB, CABD, CBAD, CDAB, DABC, DACB, DBAC.
Assuming the codebreaker guessed CDAB in the 2nd turn and still got the same feedback 0R4W.
The codemaker would screen out all permutations of CXXX / XDXX / XXAX / XXXB which had at least 1 colour in the same position with CDAB. As there were only 2 permutations left — ABCD / DABC, the codebreaker would break the code within 2 turns.
Case 3 (Set B -> Set A)
The codemaker made the code ABCD. The codebreaker guessed DBCA in the 1st turn and got the feedback 2R2W.
The codebreaker could reach 4R0W from 2R2W by switching the wrongly positioned 2 pegs. Thus, he should screen out all permutations that could not be formed by only switching 2 pegs in DBCA for once.
Only 6 out of 24 permutations were left after screening: ABCD, BDCA, CBDA, DACB, DBAC, DCBA.
The codebreaker assumed that DB were correctly positioned, switched CA and guessed DBAC in the 2nd turn. He got the feedback 1R3W with 1R less than the last feedback.
The codebreaker then assumed that DA in DBCA (the guess in 1st turn) were correctly positioned, switched BC and guessed DCBA in the 3rd turn. He got the feedback 0R4W with 1R less than the last feedback.
The codebreaker would screen out all permutations of DXXX / XCXX / XXBX / XXXA which had at least 1 colour in the same position with DCBA.
Only ABCD was left as the correct permutation. Thus, the codebreaker broke the code in the next turn.
Cracking Set C and Set B
Referring to the codebreaking process Set C -> Set B -> Set A, it is essential to reach Set B as early as possible and then screen out the wrong permutations in order to break the code.
The 24 permutations can be divided into 0R4W * 9, 1R3W * 8, 2R2W * 6 and 4R0W * 1.
From Case 2 and Case 3 we can know that:
1. If the codebreaker gets the feedback 0R4W, he can screen out the wrong permutations with 9 permutations left (0R4W * 2, 1R3W * 4, 2R2W * 2 and 4R0W * 1), screening efficiency = 15/24 = 62.5%;
2. If the codebreaker gets the feedback 2R2W, he can screen out the wrong permutations with 6 permutations left (0R4W * 1, 1R3W * 4, 2R2W * 0 and 4R0W * 1), screening efficiency = 18/24 = 75%;
3. It has been experimented that if the codebreaker gets the feedback 1R3W, he can screen out the wrong permutations with 14 permutations left (0R4W * 6, 1R3W * 4, 2R2W * 3 and 4R0W * 1), screening efficiency = 10/24 = 41.67%.
Screening efficiency in descending order: 2R2W > 0R4W > 1R3W
Let the maximum number of turns required for the codebreaker to screen out all wrong permutations be n.
24 * (1–41.67%)^n = 1
n = 5.90 = 6 (rounded up to the nearest integer)
Let the average number of turns required for the codebreaker to screen out all wrong permutations be m.
P(break the code in 1 turn) = 1/24 = 4.17%
P(break the code in 2 turns) = 9/24 * 1/9 + 8/24 * 1/14 + 6/24 * 1/6 = 10.71%
P(break the code in 3 to 6 turns) = 85.12%, I picked 4.5 turns to estimate the weighted average of m.
m = 1 * 4.17% + 2 * 10.71% + 4.5 * 85.12% = 4.09
Based on the above estimation, it takes 6 turns at most and around 4 turns in average to reach Set A from Set B.
Hence, what is the maximum number of turns required for the codebreaker to reach Set B from Set C?
It is difficult to illustrate the screening process from 70 colour combinations in Set C to only 1 colour combination in Set B. I just take Case 1 as an example.
1. In the 2nd turn, the codebreaker realized that D was correct and G was wrong. The number of possible combinations was reduced from 8C4 to 6C3 = 20.
2. In the 3rd turn, the codebreaker realized that C was correct and E was wrong. Also, only 1 of AF was correct and only 1 of BH was correct. The number of possible combinations was reduced from 6C3 to 2C1 * 2 = 4.
3. In the 5th turn, the codebreaker realized that AB were correct and FH were wrong. Only ABCD was left as the correct colour combination and was arrived in the 6th turn.
Practically, the codebreaker obtains different feedbacks from the codemaker in every game. It may take slightly more or less than 6 turns to reach Set B from Set C.
Based on the above, it is highly possible for the codebreaker to break the code within 12 turns if the codebreaker carefully reviews all available feedbacks from the codemaker.
Notes
3. It was amazing to discover that red stands for right and white stands for wrong.
4. Custom scoring for a 2-player game
No. of trials required — Score for codebreaker — Score for codemaker
1–100–0, 2–80–20, 3–70–30, 4–60–40, 5–55–45, 6–50–50, 7–45–55, 8–40–60, 9–35–65, 10–30–70, 11–25–75, 12–20–80, unsuccessful–0–100
The codebreaker can get 1 point for each peg with correct colour (W) and 2 points for each peg with both correct colour and correct position (R).
Whenever the codebreaker discovers any misleading feedback from the codemaker, the codemaker must correct the feedback immediately and 20 points would be deducted for each misleading feedback at the end of the game (the maximum deduction in each game is all positive points earned by the codemaker).
5. Based on the characteristics of permutations, there is no permutation with 3R1W. It is impossible that 3 pegs are correctly positioned while the rest peg is not.
