Bounds for Static Black-Peg AB Mastermind

Abstract

Mastermind is a famous two-player game introduced by M. Meirowitz (1970). Its combinatorics has gained increased interest over the last years for different variants.

In this paper we consider a version known as the Black-Peg AB Game, where one player creates a secret code consisting of c colors on $p \le c$ pegs, where each color is used at most once. The second player tries to guess the secret code with as few questions as possible. For each question he receives the number of correctly placed colors. In the static variant the second player doesn’t receive the answers one at a time, but all at once after asking the last question. There are several results both for the AB and the static version, but the combination of both versions has not been considered so far. The most prominent case is $n:=p=c$, where the secret code and all questions are permutations. The main result of this paper is an upper bound of $\mathcal {O}(n^{1.525})$ questions for this setting. With a slight modification of the arguments of Doerr et al. (2016) we also give a lower bound of $\varOmega (n\log n)$. Furthermore, we complement the upper bound for $p=c$ by an optimal $(\lceil 4c/3 \rceil -1)$-strategy for the special case $p=2$ and arbitrary $c\ge 2$ and list optimal strategies for six additional pairs (p, c) .

1 Introduction

Mastermind is a two players board game invented by Mordecai Meirowitz in 1970. In the original version the first player, called codemaker, chooses a secret code, consisting of four pegs, each with one of six possible colors. The second player, called codebreaker, tries to guess the secret code. Therefore, he asks questions, also in the form of four pegs in six colors. For each question, he receives an answer in the form of black and white pegs. The number of black pegs represents the number of correctly placed colors, whereas the number of white pegs represents the number of colors occurring both in the question and the secret code, but on different positions. This game can be generalized for p pegs and c colors with $p,c \in {\mathbb N}$. In the Black-Peg Game, the codebreaker only receives the number of black pegs. AB Game is a restriction, where the secret code and each question contain every color at most once. This implies that $p \le c$. For the case $p = c$, the secret codes and questions can be thought of as permutations. Here, every color is used exactly once, so the number of white pegs is the difference between p and the number of black pegs. Hence, this can be considered as a Black-Peg Game. In the static variant the second player doesn’t receive the answers one at a time, but all at once after asking the last question. After that, he only has one more try to guess the code correctly.

1.1 Previous Work

Besides its popularity as board game, Mastermind has been of large interest also in theory (see the $\mathcal {NP}$-hardness proof in [14]) and practice (see an application in cryptography [6] and string and vector databases [1]).

Much research has been done in recent years in the area of Mastermind and its variants. The generalized version of Mastermind has been investigated in [9] and [4], in the latter a strategy with $\mathcal {O}(n \log \log n)$ questions is presented for the case $p=c=n$ and is also adaptable to the Black-Peg variant. In [10], exact formulas are given for small p in Black-Peg Mastermind.

The best strategy known for AB Game with $p=c=n$ needs $\mathcal {O}(n\log n)$ questions and is presented in [5]. They also give a lower bound of n questions for this setting. In [11] exact values and tight bounds for small p are presented.

Doerr et al. [4] also give an asymptotically tight bound of $\varOmega (n\log n)$ questions for general Static Black-Peg Mastermind using probabilistic methods.

For $p=2$ an optimal number of $\lceil (4c-1)/3 \rceil$ questions is proven in [3] and an according strategy is presented in [8].

In this paper we consider a combination of these three variants, namely the Static Black-Peg AB Game, which, to the best of our knowledge, previously has not been considered in literature. For an overview of previous results about Classic and Static Mastermind for the case $p=c=n$ see Table 1. Note that all known bounds equal the ones for the Black-Peg version.

Table 1. Known lower and upper bounds for Classic and Static Mastermind for $p=c=n$.

1.2 Our Contribution

As the main result of this paper we show that for $n \in \mathbb N$ there is a feasible strategy for the Static Black-Peg AB Game on n pegs with n colors that uses $\mathcal O(n^{1.525})$ questions. A modification of the arguments of Doerr et al. [4] gives a lower bound of $\varOmega (n \log n)$ questions. For the proof of the upper bound, we define the term “separation”. Let $S_n$ be the set of permutations of the set $\{1,\ldots ,n\}$. We say that a question Q separates two possible secret codes (secrets) $X_1, X_2 \in S_n$ if Q yields different answers for them. A set of questions, called strategy, is feasible if every pair of possible secrets is separated by at least one question of the set.

First we show that there is a set of $\mathcal O(n^{1.525})$ questions such that every pair of possible secrets with Hamming distance of at most $\sqrt{n}$ is separated by at least one question. For a prime n, we construct a set of $\mathcal O(n^{1.5})$ questions for that matter. If n is not a prime, the problem gets slightly more complicated. Here we start with a fairly simple feasible $(2n^2/3)$-strategy. We then modify this strategy to get a set of $\mathcal O(n^{1.525})$ questions that for a secret gives us the placement of the last $n^{0.525}$ colors and the colors of the last $n^{0.525}$ pegs. A result of Baker et al. [2] for the difference between consecutive primes reveals that for sufficiently large n there is a prime $p(n) \in [n-n^{0.525}, n]$, so we can use the mentioned $\mathcal O(p(n)^{1.5})$ questions to get the information of the first p(n) colors and pegs. Altogether for this part we use $\mathcal O(n^{1.525})$ questions.

For pairs of possible secrets with Hamming distance of at least $\sqrt{n}$ there are considerably more separating questions, so we can use a different approach. We give a non-constructive proof that for every set of pairs of possible secrets with large Hamming distance, there is a question that separates at least a fraction of $\frac{1}{18\sqrt{n}}$ of it. So iteratively we can choose such a question and consider the set of pairs of possible secrets not yet separated. After $\mathcal O(n^{1.5}\log n)$ iteration steps every pair of possible secrets is separated by at least one question.

We complement the upper bound for $p=c$ by an optimal $(\lceil 4c/3 \rceil -1)$-strategy for the special case $p=2$ and arbitrary $c\ge 2$. Furthermore, for small p and c, we have computed tighter upper bounds and exact values via randomized resp. brute force algorithms.

1.3 Organization of the Article

In Sect. 2, we introduce the basic definitions. A $(2n^2/3)$-strategy is presented in Sect. 3. Section 4 contains a non-constructive proof of the upper bound of $\mathcal O(n^{1.525})$. We give a lower bound of $\varOmega (n\log n)$ for $p=c=n$ in Sect. 5. Section 6 is dedicated to our optimal strategies for 2 pegs. Finally, in Sect. 7, we present upper bounds and exact values for small p and c. We defer the proofs of some lemmata and examples to the full version of the paper.

2 Preliminaries

Let p denote the number of pegs and c the number of colors. In the AB Game, it holds that $p\le c$. If p and c are fixed, we call the game (p, c) -Static Black-Peg AB Game. The code chosen by the codemaker is called secret. The possible answers are written as 0B, 1B, 2B, $\dots$, pB. For calculation purposes we often write i instead of iB when the context is clear. Each strategy for Static Black-Peg AB Game starts with $r-1$ main questions which the codebreaker has to ask at the beginning of the game, and one final question, which has to be correct. We distinguish between a feasible strategy, where after the $r-1$ main questions the secret is uniquely determined and an infeasible strategy, where after the $r-1$ main questions at least two secrets are possible. A strategy is called optimal if there is no feasible strategy with fewer questions. For fixed $p, c \in \mathbb N$, define sa(p, c) as the number of questions of an optimal strategy of (p, c) -Static Black-Peg AB Game. For a strategy we say that a peg contains $l\le c$ colors if there are exactly l colors that occur in at least one main question on that peg. In the following let the pegs be numbered by $1,2,\dots ,p$ and the colors by $1,2,\dots ,c$.

In our context, secrets and questions are functions, i.e., mappings of the pegs $1,\ldots ,p$ to the colors $1,\ldots ,c$. Let Q be a question and X a possible secret. We write $C(Q,X)=i$ if question Q would receive the answer iB for the secret X. Let $X_1, X_2$ be possible secrets. We say that a question Q separates $X_1$ and $X_2$ if $C(Q,X_1) \ne C(Q,X_2)$. For $n \in \mathbb N$ let $[n]:=\{1,\ldots ,n\}$. The Hamming distance $\varDelta (X_1, X_2)$ of $X_1$ and $X_2$ is the number of pegs at which the corresponding colors are different. So $\varDelta (X_1, X_2) = \left| \left\{ i \in [p]\mid X_1(i) \ne X_2(i) \right\} \right|$. Note that in the following we consider the case $p=c=:n$. In this case the secrets and questions are permutations on [n]. We use the common one-line notation for permutations in the form $(b_1,b_2,\ldots , b_p)$, which means that 1 is mapped to $b_1$, 2 is mapped to $b_2$ and so on. For $k \in \{0,\ldots ,n\}$ the Rencontres number $D_{n,k}$ denotes the number of permutations in $S_n$ with exactly k fixpoints and has the form

$$\begin{aligned} D_{n,k} = \frac{n!}{k!}\sum \limits _{i=0}^{n-k} \frac{(-1)^i}{i!}&\quad \text { (see e.g.}~ {[12])}. \end{aligned}$$

3 A Feasible $\mathcal O(n^2)$-Strategy for the Case $n=p=c$

We start presenting a feasible strategy with $\mathcal O(n^2)$ questions. The technique developed here will later be used to fill some gaps in the main strategy. We use the following questions.

Definition 1

For $n \in \mathbb N_{\ge 3}$ define the following questions by starting with the identity function and only changing the mapping of two or three elements: Let $i,j,k \in [n]$ be pairwise distinct.

$$\begin{aligned} P^{(2)}_{i,j}:[n] \longrightarrow [n], x \mapsto {\left\{ \begin{array}{ll} j, &{}\text { if } x=i,\\ i, &{}\text { if } x=j,\\ x, &{}\text { otherwise.}\\ \end{array}\right. } \end{aligned}$$

$$\begin{aligned} P^{(3)}_{i,j,k}:[n] \longrightarrow [n], x \mapsto {\left\{ \begin{array}{ll} j, &{}\text { if } x=i,\\ k, &{}\text { if } x=j,\\ i, &{}\text { if } x=k,\\ x, &{}\text { otherwise.}\\ \end{array}\right. } \end{aligned}$$

Let I denote the identity function on [n].

Keep in mind that $P^{(3)}_{i,j,k} = P^{(3)}_{j,k,i} = P^{(3)}_{k,i,j}$.

When changing the mapping of two elements of a question, the difference of the answers is at most 2, so there are five cases to consider. It is easy to see the conditions of each case. We denote the exclusive disjunction of events A and B by $A \oplus B:= (A \wedge \lnot B) \vee (\lnot A \wedge B)$.

Observation 1

Let $n \in \mathbb N_{\ge 3}$ and $i,j \in [n]$ be distinct. Let Q, X be permutations on [n].

• (i) $C\left( P^{(2)}_{Q(i),Q(j)} \circ Q, X\right) = C(Q,X)+2 \Longleftrightarrow Q(i)=X(j) \wedge Q(j)=X(i)$

• (ii) $C\left( P^{(2)}_{Q(i),Q(j)} \circ Q, X\right) = C(Q,X)+1 \Longleftrightarrow Q(i)=X(j) \oplus Q(j)=X(i)$

• (iii) $C\left( P^{(2)}_{Q(i),Q(j)} \circ Q, X\right) = C(Q,X)+0 \Longleftrightarrow Q(i),Q(j)\notin \{X(i),X(j)\}$

• (iv) $C\left( P^{(2)}_{Q(i),Q(j)} \circ Q, X\right) = C(Q,X)-1 \Longleftrightarrow Q(i)=X(i) \oplus Q(j)=X(j)$

• (v) $C\left( P^{(2)}_{Q(i),Q(j)} \circ Q, X\right) = C(Q,X)-2 \Longleftrightarrow Q(i)=X(i) \wedge Q(j)=X(j)$

We will show that with the questions of Definition 1 a feasible strategy can be constructed. The next lemmata provide some criteria to determine for given i, j whether peg i has color j.

Lemma 1

Let $n \in \mathbb N$ and $i \in [n]$. Let X be a possible secret on [n]. Then, $X(i)=i$ if and only if $C(P^{(2)}_{i,j},X) < C(I,X)$ for all $j \in [n]\backslash \{i\}$.

Lemma 2

Let $n \in \mathbb N_{\ge 3}$ and $i,j,k \in [n]$ be pairwise distinct. Let X be a possible secret on [n]. Then, $X(i) = j$ if and only if one of the following conditions holds:

• (i) $C(P^{(2)}_{i,j},X) = C(I,X) + 2$,

• (ii) $C(P^{(2)}_{i,j},X) = C(I,X) + 1$ and $C(P^{(3)}_{i,j,k},X) \ge C(P^{(2)}_{i,j},X)$,

• (iii) $C(P^{(2)}_{i,j},X) = C(I,X) + 1$, $C(P^{(3)}_{i,j,k},X) = C(P^{(2)}_{i,j},X) - 1$ and $C(P^{(2)}_{i,k},X) < C(I,X)$.

In the following lemma we show that the same result can be achieved with the question $P^{(3)}_{j,i,k}$ instead of the question $P^{(3)}_{i,j,k}$.

Lemma 3

Let $n \in \mathbb N_{\ge 3}$ and $i,j,k \in [n]$ be distinct. Let X be a possible secret on [n]. Then, $X(i) = j$ if and only if one of the following conditions holds:

• (i) $C(P^{(2)}_{i,j},X) = C(I,X) + 2$,

• (ii) $C(P^{(2)}_{i,j},X) = C(I,X) + 1$ and $C(P^{(3)}_{j,i,k},X) = C(P^{(2)}_{i,j},X) - 2$,

• (iii) $C(P^{(2)}_{i,j},X) = C(I,X) + 1$, $C(P^{(3)}_{j,i,k},X) = C(P^{(2)}_{i,j},X) - 1$ and $C(P^{(2)}_{i,k},X) \ge C(I,X)$.

Combining Lemmata 2 and 3 we construct a first feasible strategy.

Theorem 1

For $n \in \mathbb N_{\ge 5}$ there is a feasible strategy with at most $2n^2/3$ questions, so $\mathrm {sa}(n,n) \le 2n^2/3$.

Proof

If for every distinct $i,j \in [n]$ the permutation $P^{(2)}_{i,j}$ is a question and there is a $k \in [n]\backslash \{i,j\}$ such that $P^{(2)}_{i,k}$ and $P^{(3)}_{i,j,k}$ $\left( \text {or }P^{(3)}_{j,i,k}\right)$ are questions, this set of questions together with I forms a feasible strategy, because for every secret X and every $i \in [n]$ we get X(i) by Lemmata 1, 2 and 3. Hedlund and Fort [7] showed that for every $n \in \mathbb N_{\ge 3}$ there is a set $\{T_1,\ldots ,T_t\}$ with $t\le n^2/6 + 1/3$ and $|T_{\tilde{t}}| = 3$ for all $1 \le {\tilde{t}} \le t$ such that for every pair $\{i,j\} \subset [n]$ there is a ${\tilde{t}} \in [t]$ with $\{i,j\} \subset T_{\tilde{t}}$. So, there is a set T of questions with $|T| \le n^2/6 + 1/3$ such that for every $i,j \in [n]$ there is a $k \in [n]\backslash \{i,j\}$ with $P^{(3)}_{i,j,k} \in T$ or $P^{(3)}_{j,i,k} \in T$. Combined with the final question, the identity function I and the $n(n-1)/2$ questions $P^{(2)}_{i,j}$, we get a feasible r-strategy with $r \le 1+1+n(n-1)/2 + n^2/6 + 1/3 \le 2n^2/3$, where $n \ge 5$.    $\square$

Remark 1

Such a set T and thus the strategy can be easily drafted. For further details on how to construct the question set we refer to Theorem 1 of [7].

4 A Feasible $\mathcal O(n^{1.525})$-Strategy for the Case $n=p=c$

For improving the upper bound of $\mathcal O(n^2)$, we use this strategy just for a fraction of the number of colors and pegs. Lemmata 2 and 3 give clues about the colors of specific pegs. Since we need the concept of “separating pairs of possible secrets” in the following lemmata, we modify the result accordingly.

Remark 2

Let $n, r \in \mathbb N$ and $T=(Q_1,\ldots ,Q_r) \in (S_n)^r$ be a strategy. There exist $X_1, X_2 \in S_n$ with $X_1 \ne X_2$ such that $C(Q_i,X_1) = C(Q_i,X_2)$ for all $i \in [r]$ if and only if the strategy is infeasible. Hence, we can prove $T$ to be a feasible r-strategy by showing that for every $X_1, X_2 \in S_n$ with $X_1 \ne X_2$ there is an $i \in [r]$ such that $Q_i$ separates $X_1$ and $X_2$.

Lemma 4

Let $n \in \mathbb N_{\ge 3}$ and $t \in [n]$. Let $T^{(2)}:=\Big \{P^{(2)}_{i,j}\mid i \in \{t+1,\ldots ,n\}, j \in [n], i\ne j \Big \}$, $T^{(3)}:=\left\{ P^{(3)}_{i,j,1}\mid i \in \{t+1,\ldots ,n\}, j \in \{2,\ldots ,n\}, i\ne j \right\}$ and $T:=\{I\} \cup T^{(2)} \cup T^{(3)}$. Let $X_1, X_2 \in S_n$ with at least one of the following properties:

• (i) There is an $i \in \{t+1,\ldots ,n\}$ with $X_1(i) \ne X_2(i)$.

• (ii) There is a $j \in \{t+1,\ldots ,n\}$ with $X_1^{-1}(j) \ne X_2^{-1}(j)$.

Then at least one question of $T$ separates $X_1$ and $X_2$.

4.1 Possible Secrets with Low Hamming Distance

In this subsection we depict how to separate pairs of possible secrets with low Hamming distance, i.e. a Hamming distance $\le \sqrt{n}$. Let $t \in \{0,\ldots ,n-1\}$ be a prime.

Definition 2

For $m,n \in \mathbb N$ with $m\ge n$ we denote by $\mathrm {rem}_n(m)$ (remainder) the unique integer $r \in \{0,\ldots ,n-1\}$ such that there exists $q \in \mathbb N$ with $m = q\cdot n + r$. Let $n \in \mathbb N$, $t \le n$ be a prime, $k \in [t-1]$ and $l \in [t]$. Define the question $P(n,t,k,l): [n] \longrightarrow [n]$ as

$$\begin{aligned} P(n,t,k,l)(b) = {\left\{ \begin{array}{ll} \mathrm {rem}_{t} (k\cdot b+ l) + 1, &{} \text { if } b\le t\\ b, &{} \text { if } b> t.\\ \end{array}\right. } \end{aligned}$$

Lemma 5

For n, t, k, l as above, P(n, t, k, l) is a bijective function, i.e., a permutation.

The separation of a pair of possible secrets will be achieved as follows:

Lemma 6

Let $n \in \mathbb N$ and $X_1, X_2 \in S_n$ be possible secrets with $h:=\varDelta (X_1, X_2)$. Let $a_1,\ldots ,a_h$ be the pegs on which $X_1$ and $X_2$ have different colors. Let $Q \in S_n$ be a question with $Q(a_1) = X_1(a_1)$ and $Q(a_i) \ne X_2(a_i)$ for all $i \in [h]$. Then Q separates $X_1$ and $X_2$.

If we have a pair of possible secrets $X_1$, $X_2$ with low Hamming distance and a prime $t \le n$ such that no condition of Lemma 4 is fulfilled, there is a suitable P(n, t, k, l) that separates $X_1$ and $X_2$.

Lemma 7

Let $n \in \mathbb N$, $t \in \{\lceil \sqrt{n} \rceil ,\ldots ,n\}$ be a prime and $X_1, X_2 \in S_n$ be possible secrets with $2 \le h:=\varDelta (X_1, X_2) \le \sqrt{n}$. If $X_1^{-1}(b)=X_2^{-1}(b)$ for every $b\in \{t+1,\ldots ,n\}$ and there is a peg $a\in [t]$ with $X_1(a) \ne X_2(a)$, then there exist $k \in \left[ \lceil \sqrt{n}\rceil \right]$ and $l \in [t]$ such that P(n, t, k, l) separates $X_1$ and $X_2$.

With the questions from Definitions 1 and 2 we can construct a strategy for separating pairs of possible secrets with low Hamming distance.

Strategy 1

(for n $\varvec{\in \mathbb N}$ sufficiently large)

• 1. Determine the largest prime p(n) in [n].

• 2. Take the identity function I as question.

• 3. For every $i \in \{ p(n)+1,\ldots ,n\}, j \in [i-1]$ take question $P^{(2)}_{i,j}$.

• 4. For every $i \in \{p(n)+1,\ldots ,n\}, j \in \{2,\ldots ,i-1\}$ take question $P^{(3)}_{i,j,1}$.

• 5. For every $k \in \left[ \lceil \sqrt{n}\rceil \right]$ and $l \in [p(n)]$ take question P(n, p(n), k, l).

Lemma 8

Let $n \in \mathbb N$ be sufficiently large. Let $p(n) \in [n]$ be the largest prime in [n]. Then Strategy 1 has $\mathcal O\left( \max \{\sqrt{n}\cdot p(n),n\cdot (n-p(n))\}\right)$ questions and every pair $X_1, X_2 \in S_n$ with $2 \le \varDelta (X_1,X_2) \le \sqrt{n}$ is separated by at least one question.

Proof

In steps 2–4 of Strategy 1 we use less than $1+(n-p(n))\cdot 2n$ questions. In step 5 we add $\lceil \sqrt{n}\rceil \cdot p(n)$ questions. Overall the number of questions is in $\mathcal O\left( \max \{\sqrt{n}\cdot p(n),n\cdot (n-p(n))\}\right)$. The claimed property of the strategy follows by Lemmata 4 and 7: Let $X_1, X_2$ be a pair of possible secrets with $2 \le \varDelta (X_1,X_2) \le \sqrt{n}$. There are two cases: If there is an $i \in \{p(n)+1,\ldots ,n\}$ with $X_1(i) \ne X_2(i)$ or $X_1^{-1}(i) \ne X_2^{-1}(i)$, by Lemma 4 the questions of steps 2–4 are sufficient. Otherwise, there exists a color $a\in [p(n)]$ with $X_1(a) \ne X_2(a)$, because $X_1 \ne X_2$. So, $X_1$ and $X_2$ fulfill the properties of Lemma 7. Hence, at least one question of step 5 separates $X_1$ and $X_2$.    $\square$

For further specifying the bound mentioned in Lemma 8 we need an upper bound on the difference of consecutive primes. For the next theorem we use the following result of Baker et al.

Lemma 9

[2]. There exists an $x_0$ such that for all $x \ge x_0$ the interval $[x - x^{0.525}, x]$ contains at least one prime number.

Theorem 2

Let $n \in \mathbb N$ be sufficiently large.

• a) There exists a set $T$ of $\mathcal O(n^{1.525})$ questions such that every pair $X_1, X_2 \in S_n$ with $2 \le \varDelta (X_1,X_2) \le \sqrt{n}$ is separated by at least one question from $T$.

• b) If n is a prime, $T$ has $\mathcal O(n^{1.5})$ questions.

Proof

Lemma 8 shows that Strategy 1 contains $\mathcal O\Big (\max \big \{\sqrt{n}\cdot p(n),n (n-p(n))\big \}\Big )$ questions. If n is a prime, we have $n-p(n)=0$, so there are $\mathcal O\left( n^{1.5}\right)$ questions. In general, $\sqrt{n}\cdot p(n) \le n^{1.5}$ and $n\cdot (n-p(n)) \le n^{1.525}$ because of Lemma 9.    $\square$

4.2 Possible Secrets with High Hamming Distance

We have yet to separate pairs of possible secrets with Hamming distance of $h \ge \sqrt{n}$. We depict this case as a problem on hypergraphs.

A hypergraph is a pair $\mathcal H = (V, \mathcal E)$, where V is a finite set and $\mathcal E$ is a set of subsets of V. We call elements of V vertices and the elements of $\mathcal E$ edges. A vertex cover is a subset $U \subseteq V$ such that every edge $e \in \mathcal E$ contains at least one vertex of U. For a detailed description see e.g. [13].

We start by showing that for every pair $X_1, X_2$ there is a relatively large number of separating questions. Let $n \in \mathbb N$. We define the hypergraph $\mathcal H=(V,\mathcal E)$ as follows:

• V is the set of questions, so $V:=S_n$.

• For every pair of possible secrets $X_1, X_2$ with $\varDelta (X_1, X_2) \ge \sqrt{n}$, we create an edge called $H_{X_1,X_2}$. So, $\mathcal E:=\left\{ H_{X_1, X_2}\mid X_1, X_2 \in S_n, \varDelta (X_1, X_2) \ge \sqrt{n}\right\}$.

• An edge $H_{X_1, X_2}$ consists of all questions Q separating $X_1$ and $X_2$. So, for all $H_{X_1,X_2} \in \mathcal E$ we have $H_{X_1,X_2}=\{Q\in S_n \mid C(Q,X_1)\ne C(Q,X_2)\}$.

Lemma 10

Let $n \ge 6$. Let $X_1, X_2 \in S_n$ with $\varDelta (X_1, X_2) \ge \sqrt{n}$ and $e:=H_{X_1,X_2} \in \mathcal E$. Then $|e| \ge n!\cdot \frac{1}{18\sqrt{n}}$.

Similarly, there is always a question that separates a relatively large number of pairs of possible secrets with large Hamming distance.

Lemma 11

Let $n \ge 6$. For every subset $\emptyset \ne \mathcal F \subseteq \mathcal E$, there is a vertex $Q \in V$ with $\left| \{ e \in \mathcal F \mid Q \in e\}\right| \ge \frac{1}{18\sqrt{n}}\cdot \left| \mathcal F\right|$.

We can iteratively pick such questions to separate as many pairs of possible secrets as possible. After $\mathcal O(n^{1.5} \log n)$ iteration steps every pair with high Hamming distance is separated.

Theorem 3

Let $n \ge 6$. There exists a set of $\mathcal O(n^{1.5} \log n)$ questions such that every pair $X_1, X_2 \in S_n$ with $\varDelta (X_1,X_2) \ge \sqrt{n}$ is separated by at least one question.

Proof

We prove that a vertex cover $T$ of $\mathcal H$ with $\mathcal O(n^{1.5} \log n)$ vertices exists. This translates to a set $\tilde{T}$ of questions with the needed property, because for every distinct pair $X_1, X_2 \in S_n$ there is a vertex $Q \in T$ that covers the edge $H_{X_1,X_2} \in \mathcal E$, so the corresponding question separates $X_1$ and $X_2$. With Lemma 11, for every subset $\emptyset \ne \mathcal F \subseteq \mathcal E$ there is a vertex $Q \in V$ with $\left| \{ e \in \mathcal F \mid Q \in e\}\right| \ge \frac{1}{18\sqrt{n}}\cdot \left| \mathcal F\right|$. Hence, for every subset $\emptyset \ne \mathcal F \subseteq \mathcal E$ we can pick a vertex $Q \in V$ that leaves at most $\left( 1-\frac{1}{18\sqrt{n}}\right) \cdot \left| \mathcal F\right|$ uncovered. Now we can start with the empty set $T=\emptyset$, and iteratively add vertices to $T$, which at the time are in at least a fraction of $\frac{1}{18\sqrt{n}}$ of the uncovered edges. After t steps the fraction of uncovered edges is at most $\left( 1-\frac{1}{18\sqrt{n}}\right) ^t$. With $t:=36\ln (n)\cdot n^{1.5}$, the fraction of uncovered edges after t steps is at most

$$\begin{aligned} \left( 1-\frac{1}{18\sqrt{n}}\right) ^{36\ln (n)\cdot n^{1.5}}&= \left( 1-\frac{1}{18\sqrt{n}}\right) ^{18\sqrt{n}\cdot \left( 2\ln (n)\cdot n\right) }\\&\le \left( \frac{1}{e}\right) ^{2\ln (n)\cdot n}\\&= \left( \frac{1}{n}\right) ^{2n} \le \frac{1}{(n!)^2}. \end{aligned}$$

Since $\left| \mathcal E\right| < (n!)^2$, after about t iteration steps $T$ is a vertex cover of $\mathcal H$. So, $\mathcal O(n^{1.5} \log (n))$ questions suffice for separating every pair $X_1, X_2 \in S_n$ with $\varDelta (X_1,X_2) \ge \sqrt{n}$.    $\square$

Finally, we can prove our main result.

Theorem 4

Let $n \in \mathbb N$ be sufficiently large. There exists a set $T$ of $\mathcal O(n^{1.525})$ questions such that every pair $X_1, X_2 \in S_n$ is separated by at least one question from $T$. Therefore, $T$ is a feasible strategy.

Proof

Remark 2 states that a strategy is feasible if every pair of possible secrets is separated by at least one question. Theorem 2 implies that there are $\mathcal O(n^{1.525})$ questions separating every pair of possible secrets with low Hamming distance. Because of Theorem 3, $\mathcal O(n^{1.5}~\log n)$ questions are sufficient for separating pairs of possible secrets with high Hamming distance. Altogether, there exists a feasible strategy with $\mathcal O(n^{1.525})$ questions.    $\square$

5 A Lower Bound of $\varOmega (n\log N)$ for the Case $n=p=c$

In this section we present a lower bound of $\varOmega (n\log n)$ questions for Static Black-Peg AB Game for $n=p=c$. The technique is based on information theory and adopted from [4]. Note that in the following we use the logarithm to the base 2 and denote it by “$\log$”.

We introduce a few notions and results from information theory.

Definition 3

Let X be a discrete random variable on a domain D. The entropy of X is defined as

$$H(X):=\sum \limits _{x\in D}{} \textit{Pr}[X=x]\log \left( \frac{1}{\textit{Pr}[X=x]}\right) .$$

Intuitively speaking, the entropy is a measure on how much information X will reveal in expectation.

We need the following well-known properties of entropy:

Lemma 12

Let X, Y be discrete random variables.

• (i) $H((X,Y))\le H(X)+H(Y)$.

• (ii) If $X=f(Y)$ for some deterministic function f, then $H(X)\le H(Y)$.

Consider a possible secret $X\in S_n$ chosen uniformly at random (so $H(X)=\log (|S_n|)=\log (n!)$). Let s be the size of a feasible strategy. For $i\in [s]$ let $Y_i$ be the answer to the i-th question. Since our strategy is feasible, the sequence $Y=(Y_1,\ldots ,Y_s)$ determines X and hence we have $H(Y)\ge H(X)$ by Lemma 12 (ii). On the other hand, $H(Y)=H(Y_1,\ldots ,Y_s)\le \sum \limits _{i=1}^{s}H(Y_i)$ by Lemma 12 (i). Recalling the definition of the Rencontres number $D_{n,k}$, for any $i\in [s]$ we have $H(Y_i)=\sum \limits _{k=0}^{n}\frac{D_{n,k}}{n!}\log \left( \frac{n!}{D_{n,k}}\right)$. Note that

$$\begin{aligned} D_{n,k}=\frac{n!}{k!}\sum \limits ^{n-k}_{i=0}\frac{(-1)^i}{i!}\le \frac{n!}{2k!} \text { for any }k<n \end{aligned}$$

(1)

and on the other hand

$$\begin{aligned} D_{n,k}\ge \frac{n!}{3k!} \text { for any } k<n-1. \end{aligned}$$

(2)

Moreover $D_{n,n}=1$ and $D_{n,n-1}=0$, so for any $i\in [s]$ and $n\ge 4$ we get

So altogether we have $\log (n!)=H(X)\le H(Y)\le \frac{3se}{2}$ and hence $s\ge 2\log (n!)/3e=\varOmega (n\log n)$.

6 An Optimal $\left( \left\lceil 4c/3 \right\rceil -1\right)$-Strategy for $p=2$

In this section we present a $\left( \left\lceil 4c/3 \right\rceil -1\right)$-strategy for the case of $p=2$ pegs and arbitrarily many colors $c \ge 2$. In the following let $p=2$. Observe that a feasible strategy for Static Black-Peg Mastermind is automatically also a feasible strategy for the Static Black-Peg AB Game if in each question no color occurs twice. The idea of the following strategies for the Static Black-Peg AB Game and arbitrarily many colors $c \ge p=2$ is to use the strategy for Static Black-Peg Mastermind for $p=2$ pegs from [8] as basis, apply it to $c-2$ colors and add two further main questions to this strategy, namely the questions $(c-2,c-1)$ and $(c-1,c)$. In the following we introduce a $\left( \left\lceil 4c/3 \right\rceil -1\right)$-strategy for each $c\ge 3$ except $c=4,5$. We distinguish between the cases , , . For the number $k := \left( \left\lceil 4c/3 \right\rceil -2\right)$ of main questions it holds that

$$\begin{aligned} k= & {} \left\{ \begin{array}{cccccc} \displaystyle \frac{4}{3} \cdot c - 2 &{} = &{} \displaystyle 4 \, \cdot \, \frac{c}{3}-2 &{} \equiv &{} 2 \! \! \! \mod 4 &{} \text{ for }\ c \equiv 0 \! \! \! \mod 3 \\ [0.7em] \displaystyle \frac{4}{3} \cdot c - \frac{4}{3} &{} = &{} \displaystyle 4 \, \cdot \, \frac{c-1}{3} &{} \equiv &{} 0 \! \! \! \mod 4 &{} \text{ for }\ c \equiv 1 \! \! \! \mod 3 \\ [0.7em] \displaystyle \frac{4}{3} \cdot c - \frac{5}{3} &{} = &{} \displaystyle 4 \, \cdot \, \frac{c-2}{3} + 1 &{} \equiv &{} 1 \! \! \! \mod 4 &{} \text{ for }\ c \equiv 2 \! \! \! \mod 3 \end{array} \right. \end{aligned}$$

(3)

Strategy 2

$(\left( \left\lceil 4c/3 \right\rceil -1\right)$-strategy for $p=2$ and arbitrary

• 1. Divide the k main questions into three blocks of questions, the first $(k-2)/2$ questions and the second $(k-2)/2$ questions, and two additional questions $(c-2,c-1)$ and $(c-1,c)$.

• 2. The first peg contains the colors $1,\, 2,\dots ,\, (k-2)/2$ in the first block and the colors $(k-2)/2+1,\, (k-2)/2+1,\, (k-2)/2+2,\, (k-2)/2+2\dots ,\, 3(k-2)/4,\, 3(k-2)/4(=c-3)$ in the second block.

• 3. In the first two blocks, the second peg is received from the first peg by switching the role of the two blocks.

• 4. Finally, the secret has to be asked as final question $Q_{k+1}$.

Strategy 3

$(\left( \left\lceil 4c/3 \right\rceil -1\right)$-strategy for $p=2$ and arbitrary

• 1. Divide the k main questions into three blocks of questions, the first $(k-2)/2$ questions and the second $(k-2)/2$ questions, and two additional questions $(c-2,c-1)$ and $(c-1,c)$.

• 2. The first peg contains the colors $1,\, 2,\dots ,\, (k-2)/2$ in the first block and the colors $(k-2)/2+1,\, (k-2)/2+1,\, (k-2)/2+1,\, (k-2)/2+2,\, (k-2)/2+2\dots ,\, 3(k-4)/4+1, 3(k-4)/4+1(=c-3)$ in the second block (note that the first number $(k-2)/2 + 1$ occurs three times, not only twice).

• 3. In the first two blocks, the second peg is received from the first peg by switching the role of the two blocks.

• 4. Finally, the secret has to be asked as final question $Q_{k+1}$.

Strategy 4

$(\left( \left\lceil 4c/3 \right\rceil -1\right)$-strategy for $p=2$ and arbitrary

• 1. Divide the k main questions into three blocks of questions, the first $(k-3)/2$ questions and the second $(k-1)/2$ questions, and two additional questions $(c-2,c-1)$ and $(c-1,c)$.

• 2. The first peg contains the colors $1,\, 2,\, \dots ,\, (k-3)/2$ in the first block and the colors $(k-1)/2,\, (k-1)/2,\, (k-1)/2+1,\, (k-1)/2+1,\, \dots ,\, 3(k-1)/4-1, \, 3(k-1)/4-1 (=c-3)$ in the second block.

• 3. The second peg contains the colors $(k-1)/2+1,\, (k-1)/2+1,\, (k-1)/2+1,\, (k-1)/2+2,\, (k-1)/2+2, \dots ,\, 3(k-1)/4-1, \, 3(k-1)/4-1$ in the first block and the colors $1,\, 2,\, \dots ,\, (k-1)/2$ in the second block (note that the first number $(k-1)/2 + 1$ occurs three times, not only twice).

• 4. Finally, the secret has to be asked as final question $Q_{k+1}$.

Remark 3

Note that in all three strategies the colors c and $c-2$ are not used in the first peg and second peg, respectively, of the main questions at all.

As examples, the main questions of Strategy 2 for $p=2$ and $c=12$ with $k=14$ questions (the first 12 questions can be found in Table 1(b) of [8]), Strategy 3 for $p=2$ and $c=13$ with $k=16$ questions (the first 14 questions can be found in Table 1(c) of [8]), and Strategy 4 for $p=2$ and $c=11$ with $k=13$ questions (the first 11 questions can be found in Table 1(a) of [8]) are listed in Tables 2a, b and c, respectively.

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

This idea works for all $c \ge 2$ except for $c=2,4,5$. The case $c=2$ is trivial. Regarding the case $c=4$, one optimal strategy for Static Black-Peg Mastermind for $c-2=2$ contains the main question (1, 1) which is forbidden in the AB Game. Analogously, regarding the case $c=5$, one optimal strategy for Static Black-Peg Mastermind for $c-2=3$ contains the forbidden main question (2, 2) . These cases are considered in the following observation.

Observation 2

 

(a) :

For $c=2$, the strategy which consists only of the main question (1, 2) is a feasible strategy which needs $\left( \left\lceil 4 \cdot c/3 \right\rceil -1\right) = 2$ questions.

(b) :

For $c=4$, the strategy which consists of the four main questions (1, 2) , (1, 3) (2, 1) , (3, 1) is a feasible strategy for Static Black-Peg AB Game. It needs $\left( \left\lceil 4 \cdot c/3 \right\rceil -1\right) =5$ questions.

(c) :

For $c=5$, the strategy which consists of the five main questions (1, 2) , (1, 3) , (2, 1) , (3, 1) , (4, 5) is a feasible strategy for Static Black-Peg AB Game. It needs $\left( \left\lceil 4 \cdot c/3 \right\rceil -1\right) =6$ questions.

 

Theorem 5

The strategy of [8] for Static Black-Peg Mastermind for $c-2$ colors plus the additional main questions $(c-2,c-1)$, $(c-1,c)$ is a feasible and optimal $\left( \left\lceil 4c/3 \right\rceil -1\right)$-strategy for $p=2$ and for the corresponding $c\ge 3$, $c \not = 4,5$. I.e., $sa(2,c) = \left( \left\lceil 4c/3 \right\rceil -1\right)$ for arbitrary $c \ge 2$.

We obtain the following interesting relations in comparison to the strategies of [8].

Remark 4

 

(a) :

For , the strategies of Theorem 5 for the Static Black-Peg AB Game need one question less than Strategy 1 from [8] for Static Black-Peg Mastermind.

(b) :

For , the strategies of Theorem 5 and Observation 2 for the Static Black-Peg AB Game need the same number of questions as Strategy 2 from [8] for Static Black-Peg Mastermind.

(c) :

For , the strategies of Theorem 5 and Observation 2 need one question less than Strategy 3 from [8] for Static Black-Peg Mastermind.

 

7 Optimal and Random Strategies and Future Work

In Sect. 6 we computed exact values for sa(2, c) for all $c \ge 2$ by giving optimal strategies. However, for pairs (p, c) with $3 \le p \le c$ it seems rather difficult to construct strategies that are optimal, or at least close to optimum with sensible computing effort. We tackled this problem using random strategies, i.e. strategies, where each main question is chosen randomly and uniformly distributed over all possible questions to compute tighter upper bounds on sa(p, c) for pairs (p, c) with larger p, c.

For this purpose we used a computer program which for small p, c finds optimal strategies by brute-force search and for larger p, c generates a random strategy of a given length and checks, whether the computed strategy is feasible. The program was implemented in the programming language C++, and all experiments were done on a standard desktop in a Unix-based system. Its source code is available online at [15].

The results for $1 \le p \le c \le 8$ can be found in Table 3.

Table 3. Summary of results for values sa(p, c) for $p \le c \le 8$

In addition to the values for $p=2$ we were able to compute exact values for sa(pc) for six additional pairs and upper bounds for several other cases.

Further, note that for all pairs (p, c) , where we could (theoretically or by the program) validate exact values, at least one of 10, 000 tested random strategies were optimal. The computed upper bounds turn out to be remarkably smaller than the strategy constructed in Sect. 3 (e.g. 18 questions vs. 41 questions for $p=c=8$).

Regarding future work, this motivates both to theoretically investigate the behavior of random strategies and to improve the known upper bounds for the case $p=c$, but also for the case $p<c$.