An Optimal Strategy for Static Black-Peg Mastermind with Three Pegs

Abstract

Mastermind is a famous game played by a codebreaker against a codemaker. We investigate its static (also called non-adaptive) black-peg variant. Given c colors and p pegs, the codemaker has to choose a secret, a p-tuple of c colors, and the codebreaker asks a set of questions all at once. Like the secret, a question is a p-tuple of c colors. The codemaker then tells the codebreaker how many pegs in each question are correct in position and color. Then the codebreaker has one final question to find the secret. His aim is to use as few of questions as possible. Our main result is an optimal strategy for the codebreaker for $p=3$ pegs and an arbitrary number c of colors using $\lfloor 3c/2 \rfloor +1$ questions.

A reformulation of our result is that the metric dimension of $\mathbb {Z}_n \times \mathbb {Z}_n \times \mathbb {Z}_n$ is equal to $\lfloor 3n/2 \rfloor$.

1 Introduction

Mastermind is a board game invented by Meirowitz in 1970 with applications in cryptography [3] and bioinformatics [4]. In the original version of the game, the so-called codemaker chooses a secret code consisting of 4 pegs and 6 possible colors for each peg. The so-called codebreaker must discover this code by making a sequence of guesses, called questions, until the secret has been found, using as few questions as possible. Each answer of the codemaker consists of black and white pegs, one black peg for each peg of the question which is correct in both position and color, and one white peg for each peg which is correct only in color. For Mastermind with p pegs and c colors the decision problem to decide whether a secret exists which satisfies a given set of questions and answers is $\mathcal {NP}$-complete [14]. An analysis of optimal strategies has been presented for original Mastermind [7, 10], and for several of its variants, e.g., for the black-peg variant, where no white pegs are given in the answers [8, 11], and the AB Game, where the secret and each question must not contain any color twice [12].

Static (or Non-Adaptive) Mastermind requires the codebreaker to ask all questions at the beginning of the game. The codebreaker then receives all answers and must be able to find the secret in a final question. Goddard [6] gave a $\left\lceil 2c/3+1 \right\rceil$-strategy for two pegs, a c-strategy for three pegs and a c-strategy for four pegs¹ all of which are optimal for sufficiently large c. Here, we consider Static Black-Peg Mastermind, i.e., the codebreaker only receives black pegs as answers, and thus only gets to know how many of the positions in each question are correctly colored. We present an optimal $\left\lfloor 3c/2 \right\rfloor +1$-strategy for the case of $p=3$ pegs and an arbitrary number c of colors. This continues the work in [9], where a $\left\lceil (4c-1)/3 \right\rceil$-strategy for $p=2$ was presented, and in [5], where the static black-peg variant of the AB Game was studied and a $(\lceil 4c/3 \rceil -1)$-strategy was given for the case $p=2$² and additionally a $\mathcal O(n^{1.525})$-strategy for the case $p=c$, where the questions and secrets correspond to permutations.

Mastermind may be studied from the point of view of Game Theory, the theory that investigates the (effect of) strategic choices made by interacting opponents. While it is a one-player game, where only the codebreaker acts, it can be viewed as a two-player game by allowing the codemaker to change the secret before answering a question, in a way consistent with previous answers. To define a winning situation for each player, one may limit the number k of questions. The existence of winning strategies for either player would then depend on k. For Static Black-Peg Mastermind with 3 pegs and c colors our main result shows that the codebreaker has a winning strategy if and only if $k>\left\lfloor 3c/2 \right\rfloor$; otherwise, the codemaker has a winning strategy.

The metric dimension of an arbitrary (undirected and unweighted) graph is the minimal size of a set U such that every vertex v of the graph is uniquely determined by the vector of distances between v and the vertices in U. This concept occurred first in [1] and has since been studied in various papers. In [13] it was shown that the metric dimension of $(\mathbb {Z}_2)^{n}$ is asymptotically $\mathcal O(n/\log n)$, and in [2] that the metric dimension of $\mathbb {Z}_n \times \mathbb {Z}_n$ is $\left\lceil (4n-1)/3-1 \right\rceil$. It is easy to see that the minimal number of questions needed to win Static Black-Peg Mastermind on p pegs with c colors is equal to the metric dimension of $(\mathbb {Z}_c)^p$ plus 1. Thus, our optimal $\left\lfloor 3c/2 \right\rfloor +1$-strategy gives that the metric dimension of $\mathbb {Z}_n \times \mathbb {Z}_n \times \mathbb {Z}_n$ is $\left\lfloor 3n/2 \right\rfloor$) for all n.

2 Preliminaries

We number the pegs by $1,2\dots ,p$, and the colors by $1,2,\dots ,c$. For $r\in \mathbb {N}$, an r-strategy for Static Black-Peg Mastermind consists of $r-1$ questions $Q_1,Q_2,\dots ,Q_{r-1}\in \{1,2,\dots ,c\}^p$. Such a strategy is feasible if every possible secret S is uniquely determined by the $r-1$ answers so that the codebreaker can ask the final question S to win the game. The strategy is called optimal if r is minimal. In the following consider only the case $p=3$.

We implemented a computer program available at [15], to check for $p=3$, small $c \in \mathbb {N}$ and $r \in \mathbb {N}$ all possible strategies, i.e., all combinations of questions, for being feasible. This program serves both as a corroboration of the feasibility of the main strategy for small c, and as a part of the optimality proof for all c.

3 The Main Result: A $(\lfloor 3c/2 \rfloor +1)$-Strategy for $p=3$

We introduce a $(\lfloor 3c/2 \rfloor +1)$-strategy for each c, where we distinguish between the cases $c \equiv 0,1,2,3 \;\text {mod}\;4$. Note that for the number $k := \lfloor 3c/2 \rfloor$ of questions (without the final question) it holds that $k = 3 \cdot \frac{c}{2}$ if c is even, and that $k= 3 \cdot \frac{c-1}{2} + 1$ if c is odd. Table 1 shows examples of the four cases. Below, we use the superscript “${\times }2$” to denote a color that is repeated twice.

Strategy 1

( $\mathbf {(\lfloor 3c/2 \rfloor }+1)$ -strategy for $\mathbf {p=3}$ and $\mathbf {c>4,\ c \equiv 0~\mathbf{mod}~4}$ ) ³

Divide the k questions into three blocks $B_1$, $B_2$, $B_3$ of $k/3\,\,(=c/2)$ questions each.

• 1. Peg 1 contains the colors $1,\,2,\, \dots ,\, k/3$ in $B_1$, the colors $(k/3+1)^{\times 2},\, (k/3+2)^{\times 2},\,\dots ,\, (k/2)^{\times 2}$ in $B_2$, and the colors $(k/2+1)^{\times 2},\, (k/2+2)^{\times 2}, \, \dots ,c^{\times 2}$ in $B_3$.

• 2. Peg 2 contains the colors $(k/2+1)^{\times 2},\, (k/2+2)^{\times 2}, \, \dots ,\, (2k/3)^{\times 2}$ (i.e., $B_3$ of peg 1) in $B_1$, the colors $1,\, 2,\, \dots ,\,$ k / 3 (i.e., $B_1$ of peg 1) in $B_2$, and the colors $k/2, \, (k/3+1)^{\times 2},\, (k/3+2)^{\times 2}, \, \dots ,\, (k/2-1)^{\times 2},\, k/2$ (i.e., again $B_2$ of peg 1, but here shifted down by one question) in $B_3$.

• 3. Peg 3 contains the colors $k/2, \, (k/3+1)^{\times 2},\,(k/3+2)^{\times 2}, \, \dots ,\, (k/2-1)^{\times 2}, \, k/2$ (i.e., $B_2$ of peg 1, but shifted by one question) in $B_1$, the colors $2k/3, \, (k/2+1)^{\times 2},\, (k/2+2)^{\times 2}, \, \dots ,\, (2k/3-1)^{\times 2},\, 2k/3$ (i.e., $B_3$ of peg 1, but shifted by one question) in $B_2$, and the colors $1,\, 2,\, \dots ,\, k/3$ (i.e., $B_1$ of peg 1) in $B_3$.

The shifting of questions is essential for this strategy and the following ones. E.g., if on peg 3 of Strategy 1 in Table 1a, the first eight colors were 9, 9, 10, 10, 11, 11, 12, 12 instead of 12, 9, 9, 10, 10,  11, 11, 12, the possible secrets (1, 13, 10) and (1, 14, 9) would get the same combination of answers: 2B, 1B, 1B, 1B, $14 \times$ 0B, i.e., the strategy would not be feasible. Without this shifting there would be colors which would occur in exactly the same set of questions, e.g., color 13 on peg 2 and color 9 on peg 3 would occur in the questions 1 and 2, and color 14 on peg 2 and color 10 on peg 3 would occur in the questions 3 and 4.

Strategy 2

( $\mathbf {(\lfloor 3c/2 \rfloor }+1)$ -strategy for $\mathbf {p=3}$ and $\mathbf {c>4,\ c \equiv 1~\mathbf{mod}~4}$ ) ⁴

Divide the k questions into three blocks $B_1$, $B_2$, $B_3$ of $(k+2)/3 (=(c+1)/2)$, $(k+2)/3$ and $(k+2)/3-2$ questions, respectively.

• 1. Peg 1 contains the colors $1,\, 2,\, \dots ,\, (k+2)/3$ in $B_1$, and the colors $((k+2)/3+1)^{\times 2},\, ((k+2)/3+2)^{\times 2}, \, \dots ,\, c^{\times 2}$ in $B_2$ and continuing throughout $B_3$.

• 2. Peg 2 contains the colors $((k+1)/2+1)^{\times 2}, \, ((k+1)/2+2)^{\times 2}, \, \dots ,(2(k+2)/3-1)^{\times 2}, \, (k+1)/2$ in $B_1$, the colors $1,\, 2,\, \dots ,\, (k+2)/3$ (i.e., $B_1$ of peg 1) in $B_2$, and the colors $((k+2)/3+1)^{\times 2}, \, ((k+2)/3+2)^{\times 2}, \, \dots , \, ((k+1)/2-1)^{\times 2}, \, (k+1)/2$ in $B_3$.

• 3. Peg 3 contains the colors $(k+1)/2-2, \, ((k+2)/3-1)^{\times 2},\, ((k+2)/3)^{\times 2}, \, \dots ,((k+1)/2-3)^{\times 2}, \, (k+1)/2-2, \, (k+1)/2-1$ in $B_1$, the colors $2(k+2)/3-1, \, ((k+1)/2+1)^{\times 2}, \, ((k+1)/2+2)^{\times 2}, \, \dots , \, (2(k+2)/3-2)^{\times 2}, \, 2(k+2)/3-1, \, (k+1)/2-1$ in $B_2$, and the colors $1,\, 2,\, \dots , \, (k+2)/3-2$ in $B_3$.

Strategy 3

( $\mathbf {(\lfloor 3c/2 \rfloor })+1$ -strategy for $\mathbf {p=3}$ and $\mathbf {c \equiv 2~\mathbf{mod}~4}$ )

Divide the k questions into three blocks $B_1$, $B_2$, $B_3$ of $k/3\,\,(=c/2)$ questions each.

• 1. Peg 1 contains the colors $1,\, 2,\, \dots ,\, k/3$ in $B_1$ and the colors $(k/3+1)^{\times 2},\, (k/3+2)^{\times 2}, \, \dots ,\, c^{\times 2}$ in $B_2$ and continuing throughout $B_3$.

• 2. Peg 2 contains the colors $1,\, 2,\, \dots ,\, k/3$ (i.e., $B_1$ of peg 1) in $B_2$ and the colors $(k/3+1)^{\times 2},\, (k/3+2)^{\times 2}, \, \dots , (2k/3)^{\times 2}$ in $B_3$ and continuing throughout $B_1$.

• 3. Peg 3 contains the colors $1,\, 2,\, \dots ,\, k/3$ (i.e., $B_1$ of peg 1) in $B_3$ and the colors $(k/3+1)^{\times 2},\, (k/3+2)^{\times 2}, \, \dots ,\, (2k/3)^{\times 2}$ in $B_1$ and continuing throughout $B_2$.

Strategy 4

( $\mathbf {(\lfloor 3c/2 \rfloor })+1$ -strategy for $\mathbf {p=3}$ and $\mathbf {c \equiv 3~\mathbf{mod}~4}$ )

Divide the k questions into three blocks $B_1$, $B_2$, $B_3$ of $(k+2)/3\,\,(=(c+1)/2)$, $(k+2)/3$ and $(k+2)/3-2$ questions, respectively.

• 1. Peg 1 contains the colors $1,\, 2,\, \dots ,\, (k+2)/3$ in $B_1$ and the colors $((k+2)/3+1)^{\times 2},\, ((k+2)/3+2)^{\times 2}, \, \dots , \, c^{\times 2}$ in $B_2$ and continuing throughout $B_3$.

• 2. Peg 2 contains the colors $((k+2)/2)^{\times 2}, \, ((k+2)/2+1)^{\times 2}, \, \dots , \, (2(k+2)/3-1)^{\times 2}$ in $B_1$, the colors $1,\, 2,\, \dots ,\, (k+2)/3$ (i.e., $B_1$ of peg 1) in $B_2$, and the colors $(k+2)/2-1,\, ((k+2)/3+1)^{\times 2},\, ((k+2)/3+2)^{\times 2}, \, \dots , \, ((k+2)/2-2)^{\times 2}, \, (k+2)/2-1$ in $B_3$.

• 3. Peg 3 contains the colors $(k+2)/2-2,\, ((k+2)/3-1)^{\times 2},\, ((k+2)/3)^{\times 2}, \, \dots , ((k+2)/2-3)^{\times 2}, \, (k+2)/2-2$ in $B_1$, the colors $2(k+2)/3-1,\, ((k+2)/2)^{\times 2},\, ((k+2)/2+1)^{\times 2}, \, \dots , \, (2(k+2)/3-2)^{\times 2}, \, 2(k+2)/3-1$ in $B_2$, and the colors $1,\, 2,\, \dots ,\, (k+2)/3-2$ in $B_3$.

Table 1. Examples for Strategies 1, 2, 3 and 4 with $p=3$.

Theorem 1

Strategies 1, 2, 3 and 4 are feasible and optimal $(\lfloor 3c/2 \rfloor )+1$-strategies for $p=3$ and for the corresponding c with $c \not =1, 4$.

Recall that the AB Game corresponds to Mastermind, but with the additional condition that both in the secret and questions the colors on different pegs must be pairwise distinct. By observing that the strategies in Theorem 1 only use questions containing three different colors each, we thus obtain the following.

Corollary 1

For $c=6$ and for all $c \ge 8$, the Strategies 1, 2, 3 and 4 are also feasible strategies for the AB Game with $p=3$ and the considered c.

4 Idea of Proof of Theorem 1

Feasiblity: For a given strategy, two questions are called neighbors, and double neighbors, if they have one color in common on exactly one peg and two pegs, respectively. A question Q is called a $(a_1,a_2,a_3)$-question for $a_1,a_2,a_3 \in \mathbb {N}$, if for $i=1,2,3$, the i-th color of Q occurs $a_i$ times on the i-th peg (throughout the strategy). In Table 1a, $Q_3 = (3,14,9)$ and $Q_4 = (4,14,10)$ are neighbors (but not double neighbors), and both are (1, 2, 2) -questions,

As can be seen in Table 1, the four strategies consist only of (1, 2, 2) -questions, (2, 1, 2) -questions and (2, 2, 1)-questions, and no double neighbors exist.

In Table 1a, if the neighbors $Q_3 = (3,14,9)$ and $Q_4 = (4,14,10)$ both receive an answer $\ge 1$B, then the secret has the form (?, 14, ?) , unless one of the neighbors $Q_2=(2,13,9)$ and $Q_5=(5,15,10)$ also receives an answer $\ge 1$B, and in this case the secret has the form (4, ?, 9) or (3, ?, 10) . The detailed proof needs an extensive case distinction and the introduction of the so-called strategy graph, where the questions correspond to vertices and two questions are connected by an edge, if they are neighbors.

Optimality: This proof relies on observations regarding the feasibility of the strategy, e.g., on each peg all but one color must occur, and there can be at most one (1, 1, 1)-question. We consider the cases of odd and even c and four subcases each, depending on how many of the three pegs contain c colors. Note that in the strategies of Table 1 all colors occur at least once on each peg, except for peg 3 of Strategies 2 and 4, where the colors $(k+1)/2$ and k / 2, respectively, do not occur. This case must be excluded for Strategies 1 and 3 for even c as well, which makes the proof much more difficult for even c than for odd c. The detailed proof needs again several cases and the introduction of a new term, the so-called proof questions.

Due to the space limitation, we refer to the forthcoming full version of the paper for the feasibility and optimality proofs.