Score Distributions for Mastermind Games

SCORE DISTRIBUTIONS FOR MASTERMIND GAMES

Balmoral Software
7/21/18
Revised 6/4/23

Table of Contents

Introduction

In a generalized Mastermind-style game, a guess pattern of a specified length is drawn from an alphabet of possible symbols, colors, numbers or letters. The objective of the game is to match an unknown secret code of the same length, drawn from the same alphabet, in the least number of moves. At each move, a score is provided that gives an indication of how close the guess is to the secret code. This paper explores some of the characteristics of scores in Mastermind-style games.

Let C be the length of the secret code and of the guesses the codebreaker provides, and let N be the size of the alphabet from which each element of a code can be drawn. We use the notation (C,N) to refer to a particularly-sized game. For example, in the standard Mastermind game, each code is four colors chosen from six possibilities, so we have C = 4 and N = 6, and use the notation (4,6) to denote it.

We use the term population to describe all possible codes of the specified length that can be created from the given alphabet. The symbol Q is used to describe the size of the population.

We will consider two types of scoring: Perfect-match (P) and Mastermind-type (M). With Perfect-match scoring, one point is awarded for each symbol in a guess code if and only if it occurs in the same position as in the secret code. For example, the Perfect-match score of the codes (3,4,1,1) and (3,2,1,4) is 2, corresponding to the digits 3 and 1 that occur in the first and third positions, respectively, in each code.

With Mastermind-type scoring, 10 points are awarded for every symbol of the guess code that is found in the same position as in the secret code, plus 1 point for every other symbol that is found in the secret code, but in an incorrect position. If a match occurs, the matching symbol in each code is removed from consideration for any further matches. Perfect matches are processed first. For example, the Mastermind-type score of the codes (3,4,1,1) and (3,2,1,4) is 21, with 10 points given for each of the digits 3 and 1 that occur in the first and third positions in each code, and 1 point for the digit 4 that occurs in each code, but not in the same position.

We also consider two classes of Mastermind-style games, those with symbols that are allowed to be repeated in the secret and guess codes (Y), and those with symbols that cannot be repeated (N). We can describe a game by its scoring type and whether or not repeated symbols are allowed. For example, MY refers to a game with Mastermind-type scoring and repeated symbols, and PN denotes a game with Perfect-match scoring and non-repeated symbols. The abbreviations PY, PN, MY and MN refer to the four scoring/repetition types considered here.

Repeated symbols

When the same alphabet symbol is allowed to appear more than once in a code, each element of the code is selected from the alphabet of N symbols (sampling with replacement). Each of the C code elements has the same N possibilities, so the total number of possible codes is

For example, in the standard (4,6) game with repeated symbols, the population size is 64 = 1296.

Non-repeated symbols

When repeated symbols are not allowed, we must have N ≥ C, in order for there to be enough symbols in the alphabet from which to draw C different ones (sampling without replacement). The first symbol in a code can be chosen from any of the N alphabet symbols. The second symbol cannot be the same as the first symbol, so it can be chosen from the remaining N - 1 alphabet symbols. Similarly, the third symbol cannot be the same as either of the first two symbols, so it can be selected in N - 2 ways. Continuing in this fashion for all C symbols, the number of possible codes is

using factorial notation. For example, in the standard (4,6) game with non-repeated symbols, the population size is 6!/2! = 360. Note that the population size is usually much smaller than when repeated symbols are allowed.

Since all symbols in a code are distinct, we can remap the alphabet symbols to an arbitrary sequence, and so without loss of generality, we can take the alphabet as the first N positive integers and assume that the reference (secret code) for score computations is the sequence (1,2,...,C).

Score Probabilities and Ranges

The scores for Perfect-match scoring can take on values from 0 to C, so in each case there are C + 1 possible scores. Mastermind-type scores vary from 0 to 10C, with some gaps in the sequence in the cases where the sum of the digits exceeds C.

Each of the four scoring/repetition types can be considered to have a discrete probability distribution of scores over all of the Q2 possible pairs of codes. We can use the two-letter scoring/repetition abbreviation to denote a random variable taking on the possible scores for that particular type of game. For example, the probabilities for the (4,6) PN game can be determined by tabulating how many of the 3602 = 129,600 pairs of codes have each of the scores between 0 and 4. It can be determined that 46,080 pairs have a score of 1, so we have

Pr{PN = 1} = 46,080/129,600 = 35.5% for the (4,6) game
A Mastermind-type score of 10(C-1) + 1 (e.g., 31 in the standard game) is impossible since having exactly C - 1 symbols in the correct locations implies that the final symbol would also be in the correct position, producing a score of 10C instead. Therefore, regardless of whether repeated symbols are allowed or not, we have
Pr{MY = 10C - 9} = Pr{MN = 10C - 9} = 0
In Mastermind-type scoring, the sum of the tens and units digits of the score can between 0 and C, inclusive, as can be the tens digit. Therefore, when the tens digit is i, the possible units digits are 0,...,C-i, which is C - i + 1 values. Since the one score 10(C-1) + 1 is impossible, the number of Mastermind-type scores is
For example, in the standard (4,6) game, Mastermind-type scores can take any of the following 4(4 + 3)/2 = 14 values:
0, 1, 2, 3, 4, 10, 11, 12, 13, 20, 21, 22, 30, 40
Depending on the relative sizes of C and N, some impossible scores can be predicted when repeated symbols are not allowed. If N < 2C, then every two subsets of C distinct symbols drawn from a population of N symbols have at least 2C - N symbols in common. That is to say, two disjoint subsets of C symbols drawn from N can occur only if N is large enough to populate both subsets (N ≥ 2C). This fact establishes certain zero scores for Mastermind-type scoring:
Pr{MN = 10A + B} = 0 whenever the sum of digits A + B < 2C - N
For example, in the standard (4,6) game with non-repeated symbols, we have 2C - N = 2, so
Pr{MN = 0} = Pr{MN = 1} = Pr{MN = 10} = 0 (indicated in bold in the list above)
Finally, we note that in the particular case N = C, the entire alphabet is consumed in every code, and so it is impossible to have C - 1 perfect matches without the last one too:
Pr{PN = C - 1} = 0 if N = C

Graphs

Interesting graphs of score distributions can be created by using a grayscale for the score values and allocating one pixel for each pair of possible codes. Each such graph will have dimensions NC x NC pixels, and will have symmetry along the diagonal axis since the score of any pair of codes is a commutative operation. To avoid gaps in the graphs, we consider only the case where repeated symbols are allowed.

To assign pixels to codes, let the pixel index range from 0 to NC - 1, and let the alphabet consist of N consecutive digits beginning with 0. Then each code is the base-N representation of the pixel index; for example, in the standard (4,6) game, the code associated with index 0 is 0 0 0 0, with index 5 is 0 0 0 5, with index 6 is 0 0 1 0, with index 216 is 1 0 0 0, and with index 1295 is 5 5 5 5.

With the origin at lower left, the intensity of the pixel at position (x,y) is the score associated with code indexes x and y. A black pixel corresponds to a score of 0, and a white pixel is used for the maximum possible score (which depends on the scoring type). Proportionally-varying shades of gray are used for intermediate scores. The diagonal of the plot is all white since the score of a code combined with itself is always the maximum score.

There typically are lighter diagonal lines and squares throughout the graph where the pixel indexes differ by a constant amount due to the associated codes having multiple digits in agreement; for example, points (x,y) where |x - y| is a multiple of N. More detail can be shown in close-up using a bitmap display application such as Microsoft Paint. Following are 1296 x 1296 pixel graphs for the standard (4,6) game:

Perfect-match scoring (relatively few gray levels due to only 5 possible scores):

Click image for full resolution

Mastermind-style scoring (more details resulting from 14 gray levels):

Click image for full resolution

The corresponding pixel graphs for other game sizes have a similar appearance.

PY: Perfect-match scoring with repeated symbols

In Perfect-match scoring, a point is awarded for each element in a guess code if and only if the corresponding element in the reference code is the same. The question of interest is: out of all possible code pairs, how many have a certain score using Perfect-match scoring? Equivalently, if all patterns are equally likely, what is the probability distribution of the scores?

When codes are allowed to have repeated elements, the score distribution is based on sampling individual symbols with replacement, and a binomial probability distribution is applicable. We assume that the alphabet of symbols in a game is the positive integers. Considering the scoring of one symbol at a time as a Bernoulli trial, the probability of a success (1 point earned) is simply the chances of a randomly-selected number from the alphabet 1,...,N matching its ordinal position in the code pattern being constructed, or 1/N. Each trial is independent of the others, so the score probabilities follow the binomial distribution

The mean of this score distribution is C/N [1].

For example, in the standard (4,6) game with repeated symbols and Perfect-match scoring, the scores have the following probabilities:

(4,6) PY

ScoreProbability
0625/129648.23%
1500/129638.58%
2150/129611.57%
320/12961.54%
41/12960.08%

Mean score: 4/6 = 0.67

PN: Perfect-match scoring with non-repeated symbols

In Perfect-match scoring with non-repeated symbols, the score is computed as the quantity of numbers in the selected code that occur in their natural order; for example, the number 1 in the first position and the number 3 in the third position, for a score of 2 (or more). The score probabilities are
(1)
where fm is an mth-degree polynomial function of N-C ≥ 0. The first few functions fm are:
f0(n) = 1

f1(n) = n

f2(n) = n2 + n + 1

f3(n) = n3 + 3n2 + 5n + 2

f4(n) = n4 + 6n3 + 17n2 + 20n + 9

f5(n) = n5 + 10n4 + 45n3 + 100n2 + 109n + 44

f6(n) = n6 + 15n5 + 100n4 + 355n3 + 694n2 + 689n + 265

for n ≥ 0 (OEIS A094791).

If gm(n) denotes the mth forward difference of the factorial numbers:

gm+1(n) = gm(n+1) - gm(n), g0(n) = n!,
then fm(n) is related to gm(n) by
fm(n) = gm(n)/n!
It follows that fm(n) obeys the difference equation
fm+1(n) = (n+1)fm(n+1) - fm(n), f0(n) = 1.(2)
Interestingly, in the probabilities above, the polynomial functions fm are evaluated only for the difference N-C, so many of the same results can be applied for multiple game sizes.

Now assume for the moment that N = C. Then all alphabet symbols are consumed in creating each of the C! possible codes, and the number of codes with a given score s in the range 0,1,...,C is simply the number of code elements occurring in their ordered position, known as the partial derangement

where !(C-s) is the subfactorial of C-s. The associated score probability is the ratio of R(C,s) to the number of possible codes:
Noting that N!/(N-C)! = C! in this case, we can combine (1) with the immediately preceding results to obtain
from which we can see that fm(0) = !m for all m.

Lemma 3 shows by a simple induction argument that the probabilities (1) sum to unity. An analogous approach is used in Lemma 4 to determine that the mean of the score probability distribution is C/N, which is the same mean as in the repeated-symbols case PY.

For example, in the standard (4,6) game with non-repeated symbols and Perfect-match scoring, the scores have the following probabilities:

(4,6) PN

ScoreProbability
0181/36050.28%
1128/36035.56%
242/36011.67%
38/3602.22%
41/3600.28%

Mean score: 4/6 = 0.67

Comparison of Score Distributions

Whether by using the closed-form expressions above or by enumeration of all possible pairs of codes, the probability distribution of scores can be derived. For example, the following table summarizes score distributions for the standard game with C = 4 and N = 6:
Symbols:RepeatedNon-repeated
Scoring:Mastermind type
(T)		Perfect Match
(CF)		Mastermind type
(T)		Perfect Match
(CF)
Score:07.24%48.23%50.28%
118.66%38.58%35.56%
217.15%11.57%23.33%11.67%
34.89%1.54%24.44%2.22%
40.28%0.08%2.50%0.28%
1013.93%
1117.49%13.33%
126.82%20.00%
130.34%2.22%
208.10%3.33%
213.09%6.67%
220.39%1.67%
301.54%2.22%
400.08%0.28%
Mean score:7.710.678.670.67

(T): Tabulated
(CF): Closed form

In contrast to the grayscale representations shown earlier, the score probability distribution function (pdf) can be plotted in the usual way. The following graph shows the score pdfs for the standard (4,6) game with Mastermind-type scoring. There is some skew toward higher scores for non-repeated symbols (blue) as compared to repeated symbols (red).

The level of pdf skew between the two types of repetition varies for other game sizes and scoring types.

Summary of Closed-form Mean Scores

AbbreviationScoringSymbolsPopulation sizeMean
PYPerfect matchRepeatedNCC/N
PNPerfect matchNon-repeatedN!/(N-C)!C/N

Score Distributions of Common Games

The score distributions of some common games are listed vertically as follows:
ScoreMastermind
(4,6) MY		Bulls and Cows
(4,10) MN		Super Mastermind
(5,8) MY		Jotto variant
(5,9) PN
07.2392%7.1429%4.8198%56.5079%
118.6614%28.5714%16.1431%33.1019%
217.1539%25.0000%19.4595%8.8624%
34.8868%5.2381%9.3007%1.3889%
40.2840%0.1786%1.5195%0.1323%
50.0482%0.0010%0.0066%
1013.9318%9.5238%8.2602%
1117.4897%14.2857%16.1769%
126.8158%4.2857%10.1997%
130.3429%0.1587%1.9276%
140.0720%
208.1019%3.5714%4.8299%
213.0864%1.4286%4.4460%
220.3858%0.1190%1.1516%
230.0401%
301.5432%0.4762%1.1482%
310.3204%
320.0267%
400.0772%0.0198%0.1068%
500.0031%
Mean
score		7.71445.20007.64170.50

Five Dice Game

The Five Dice game consists of arranging five ordinary 6-sided dice to match a secret dice pattern (without regard to order), such as two 5's and three 2's. Its Mastermind-style game parameters are a code length C = 5, an alphabet size N = 6 and repeated symbols. Scoring is simply the number of correct dice in the set of five. For example, if the secret dice are {3,3,4,4,5} and the guess is {1,2,3,4,6}, the resulting score is 2 for the 3 and 4 that occur in each set of dice. An example of the Five Dice Game is included in the computer game Nostradamus: The Last Prophecy.

In many game implementations, the total of pips on the five secret dice is provided, which considerably reduces the number of feasible patterns at each move, as well as increases the average score (as would be expected since more information on the secret pattern is provided). The sum of the dice ranges from 5 to 30, or in the general case, from C to CN. For each dice sum, there is a separate distribution of scores ranging from 0 to C. However, a score of C-1 will never occur since knowing all of the die values but one, as well as the sum of the dice, implies that the remaining die value is also known.

Consider a dice pattern having sum T. Each die's value is of the form 1 + ai, where the integers ai satisfy

0 ≤ ai ≤ N-1, i=1,...,C
and
which can be written
Therefore, at most T - C of the ai's are nonzero, or equivalently, at least C - (T - C) = 2C - T of the ai's are zero. It follows that all dice patterns with sum T must contain at least 2C - T ones (occurring when the corresponding ai's are zero), and the score of any two such patterns is at least 2C - T. Since all scores are nonnegative, the minimum score is max{2C - T,0}. The only exception to this minimum score formula is when T = C + 1, in which case the dice pattern must consist of C - 1 ones and a two, and the only possible score is C.

Analogously, each die is also of the form N - bi, where the integers bi satisfy

0 ≤ bi ≤ N-1, i=1,...,C
and
which can be written
Therefore, at most CN - T of the bi's are nonzero, or equivalently, at least C - (CN - T) = T - C(N-1) of the bi's are zero. It follows that all dice patterns with sum T must contain at least T - C(N-1) ones, and the score of any two such patterns is at least T - C(N-1). Since all scores are nonnegative, the minimum score is max{T - C(N-1),0}. The only exception to this minimum score formula is when T = CN - 1, in which case max{T - C(N-1),0} = C - 1, but the pattern must consist of C - 1 values of N and one value of N-1, and the only possible score is C.

In general, the minimum score is

For the (5,6) Five Dice game, the 26 possible score distributions are listed horizontally as follows:
ScoreMean
score
Sum01235
5100.0000%5.0000
6100.0000%5.0000
744.4444%55.5556%4.1111
88.1633%48.9796%42.8571%3.7755
93.0612%10.2041%57.1429%29.5918%3.4286
100.3149%1.8896%14.2353%64.4999%19.0602%3.1916
110.2380%5.4729%14.9911%63.0577%16.2403%3.0583
120.6450%5.4824%19.3496%62.0263%12.4966%2.9274
130.8787%8.9569%18.0839%61.5646%10.5159%2.8240
141.3032%8.7963%22.4280%58.6420%8.8306%2.7373
150.8636%13.4780%19.2166%57.8762%8.5656%2.6837
161.2958%12.6059%21.4540%56.8097%7.8347%2.6512
171.0930%13.3629%21.4826%56.5746%7.4869%2.6349
181.0930%13.3629%21.4826%56.5746%7.4869%2.6349
191.2958%12.6059%21.4540%56.8097%7.8347%2.6512
200.8636%13.4780%19.2166%57.8762%8.5656%2.6837
211.3032%8.7963%22.4280%58.6420%8.8306%2.7373
220.8787%8.9569%18.0839%61.5646%10.5159%2.8240
230.6450%5.4824%19.3496%62.0263%12.4966%2.9274
240.2380%5.4729%14.9911%63.0577%16.2403%3.0583
250.3149%1.8896%14.2353%64.4999%19.0602%3.1916
263.0612%10.2041%57.1429%29.5918%3.4286
278.1633%48.9796%42.8571%3.7755
2844.4444%55.5556%4.1111
29100.0000%5.0000
30100.0000%5.0000
Some of these distributions are plotted below:

The probability distribution of the dice sum itself is known in piecewise form; see [2] and this reference. The dice sum distribution is symmetric about its mode(s), and its mean is C(N+1)/2, which is the midpoint of the minimum and maximum possible sums. Since each of the N die values is equiprobable and is determined independently of the other dice (repeated symbols), the dice sum distribution approaches the normal as C increases, by the Central Limit Theorem [3].

Appendix: Mathematical Results

Lemma 1.
Proof. Let a = -1 and b = 1 in the Binomial Theorem:
Lemma 2.
for nonnegative integers n, where ! k is the subfactorial of k.

Proof by induction.

so the formula holds for n = 0. Assume the formula holds for n. Then using Euler's recurrence relation
(OEIS A000166), we have
Lemma 3.

Let x = N - C ≥ 0 in (1) and let S(C,x) denote the sum of score probabilities

after reversing the summation on k. When x = 0 (N = C), we have
For proof by induction, assume S(C,x) = 1 for all C. Then
(5)
 
by Pascal's Rule. The first term in braces
by the induction hypothesis. Similarly, the second term in braces in (5)
so
Lemma 4.

An analogous approach to Lemma 3 is used to determine the mean of the probability distribution S(C,x). Again let x = N - C ≥ 0 in (1). Then

References

[1] Hoel, Port & Stone, Introduction to Probability Theory (Boston: Houghton Mifflin, 1971), p. 83.

[2] Uspensky, J. V., Introduction to Mathematical Probability (New York: McGraw-Hill, 1937), pp. 23-24.

[3] Hoel, Port & Stone, op. cit., p. 185.


Table of Contents

Home

Copyright © 2023 Balmoral Software (http://www.balmoralsoftware.com). All rights reserved. Republication, redistribution or conversion is expressly prohibited without the prior written consent of Balmoral Software.