Playing Mastermind with Constant-Size Memory

Abstract

We analyze the classic board game of Mastermind with n holes and a constant number of colors. The classic result of Chvátal (Combinatorica 3:325–329, 1983) states that the codebreaker can find the secret code with Θ(n/logn) questions. We show that this bound remains valid if the codebreaker may only store a constant number of guesses and answers. In addition to an intrinsic interest in this question, our result also disproves a conjecture of Droste, Jansen, and Wegener (Theory Comput. Syst. 39:525–544, 2006) on the memory-restricted black-box complexity of the OneMax function class.

1 Introduction

The original Mastermind game is a board game for two players invented in the seventies by Mordecai Meirowitz. It has pegs of six different colors. The goal of the codebreaker, for brevity called Paul here, is to find a color combination made up by the codemaker, called Carole in the following. He does so by guessing color combinations and receiving information on how close his guess is to Carole’s secret code. Paul’s aim is to use as few guesses as possible.

For a more precise description, let us call the colors 1 to 6. Write [n]:={1,…,n} for any n∈ℕ. Carole’s secret code is a length-4 string of colors, that is, a z∈[6]⁴. In each iteration, Paul guesses a string x∈[6]⁴ and Carole replies with a pair $(\operatorname{eq}(z,x),\pi(z,x))$ of numbers. The first number, $\operatorname{eq}(z,x)$, which is usually indicated by black answer-pegs, is the number of positions in which Paul’s and Carole’s string coincide. The other number, π(z,x), usually indicated by white answer-pegs, is the number of additional pegs having the right color, but being in the wrong position. Formally $\operatorname{eq}(z,x):=|\{i \in [4] \mid z_{i}=x_{i} \}|$ and $\pi(z,x):=\max_{\rho \in S_{4}}|\{i \in [4] \mid z_{i}=x_{\rho(i)}\}|-\operatorname{eq}(z,x)$, where S ₄ denotes the set of all permutations of the set [4]. Paul “wins” the game if he guesses Carole’s string, that is, if Carole’s answer is (4,0).

We are interested in strategies for Paul that guarantee him to find the secret code with few questions. We thus adopt a worst-case view with respect to Carole’s secret code. This is equivalent to assuming that Carole may change her hidden string at any time as long as it remains consistent with all previous answers (devil’s strategy).

Previous Results

Mathematics and computer science literature has produced a plethora of results on the Mastermind problem. For the original game with 6 colors and 4 positions, Knuth [10] showed that Paul needs at most four queries until being able to identify Carole’s string (which he may query in the fifth iteration to win the game).

Chvátal [3] studied a general version of this game with k colors and n positions, that is, the secret code is a length-n string z∈[k]ⁿ. Denote by d(n,k) the minimum number of guesses that enable Paul to win the game for any secret code. Chvátal proved that for any arbitrarily small constant ε>0 and for k<n ^1−ε colors we have $d(n,k)=O(\tfrac{n \log k}{\log n-\log k})$. More precisely, he showed that for any ε>0, n sufficiently large and for any k≤n ^1−ε, a number of $(2+\varepsilon)\frac{n(1+2 \log k)}{\log n-\log k}$ guesses chosen from [k]ⁿ independently and uniformly at random, with high probability, leads to a different sequence of answers for each possible code, which implies that the answers uniquely determine the secret code. In particular, this probabilistic construction shows the existence of such a sequence of guesses, and thus, of a strategy determining the secret code with $(2+\varepsilon)\frac{n(1+2 \log k)}{\log n-\log k}$ guesses. This remains true if Carole replies only with black answer-pegs, that is, if for any of Paul’s guesses x she reveals to him only $\operatorname{eq}(z,x)$; the number of bits in which her and Paul’s string coincide.

For larger values of k, the following is known. For n≤k≤n ², Chvátal proved d(n,k)≤2nlogk+4n and for k=ω(n ²logn) he showed (k−1)/n≤d(n,k)≤⌈k/n⌉+d(n,n ²). These results have subsequently been improved. Chen, Cunha, and Homer [2] showed that d(n,k)≤2n⌈logn⌉+2n+⌈k/n⌉+2 for k≥n. Goodrich [8] proved d(n,k)≤n⌈logk⌉+⌈(2−1/k)n⌉+k for arbitrary k. This was again improved by Jäger and Peczarski [9], who showed an upper bound of n⌈logn⌉−n+k+1 for the case k>n and n⌈logk⌉+k for the case k≤n.

For k=2 colors, the Mastermind problem is related to the well-studied coin weighing problem. For this reason, first results on this problem date back to years as early as 1963, when Erdős and Rényi [7] showed that d(n,2)=Θ(n/logn).

Concerning the computational complexity, Stuckman and Zhang [12] showed that it is $\mathcal {NP}$-hard to decide whether a given sequence $(x^{(i)}, (\operatorname{eq}^{(i)},\pi^{(i)}))_{i=1}^{t}$ of queries x ⁽ⁱ⁾ and answers $(\operatorname{eq}^{(i)},\pi^{(i)})$ of black and white answer-pegs has a secret code leading to these answers, i.e., whether there exists a string z∈[k]ⁿ such that $\operatorname{eq}(z,x^{(i)})=\operatorname{eq}^{(i)}$ and π(z,x ⁽ⁱ⁾)=π ⁽ⁱ⁾ for all i∈[t]. Goodrich [8] proved that this is already $\mathcal {NP}$-hard if we only ask for consistence with the black answer-peg replies $\operatorname{eq}^{(i)}$.

Our Results

Originally motivated by a conjecture on black-box complexities (cf. Sect. 2), we study a memory-restricted version of the Mastermind problem. Since this original motivation asks for the case of two colors only, we restrict ourselves to the number k of colors being constant.

The memory-restriction can be briefly described as follows. Given a memory of size m∈ℕ, Paul can store up to m guesses and Carole’s corresponding replies. Based only on this information, Paul decides on his next guess. After receiving Carole’s reply, based only on the content of the memory, the current guess, and the current answer, he decides which m out of the m+1 strings and answers he keeps in the memory. Note that our memory restriction means that Paul truly has no other memory, in particular, no separate iteration counters and boolean variables (possibly hidden as case distinctions) may be used. So formally Paul’s strategy consists of a guessing strategy which can be fully described by a mapping from m-sets of guesses and answers to strings x∈[k]ⁿ, and a forgetting strategy which maps (m+1)-sets of guesses and answers to m-subsets thereof.

Clearly, a memory-restriction does not make Paul’s life easier. The O(n/logn) strategies by Erdős and Rényi [7] and by Chvátal [3] do use the full history of guesses and answers and thus only work with a memory of size Θ(n/logn). Surprisingly, this amount of memory is not necessary. In fact, one single memory cell suffices.

Theorem 1

Let k∈ℕ_≥2. For all n∈ℕ, Paul has a size-one memory strategy winning the Mastermind game with k colors and n positions in O(n/logn) guesses. This remains true if we allow Carole to play a devil’s strategy and she only reveals the number of fully correct pegs $\operatorname{eq}(x,z)$ (“black answer-peg version of Mastermind”).

The bound in Theorem 1 is asymptotically tight. A lower bound of Ω(n/logn) is already true without memory restrictions. This follows easily from an information-theoretic argument, cf. [7] or [3]. Our result disproves a conjecture of Droste, Jansen, and Wegener [4], who believed that a lower bound of Ω(nlogn) should hold for the 2-color black answer-peg Mastermind problem with memory-restriction one.

The proof of Theorem 1 is quite technical. For a clearer presentation of the ideas, we first consider the size-two memory-restricted model, cf. Sect. 3. The proof of Theorem 1 is given in Sect. 4. Before going into the proofs, in the following section we sketch the connection between Mastermind games and black-box complexities.

2 Mastermind and Black-Box Complexities

In this section, we describe the connection between the Mastermind game and black-box complexity. The reader only interested in the Mastermind result may skip this section without loss.

Roughly speaking, the black-box complexity of a set of functions is the number of function evaluations needed to find the optimum of an unknown member from that set. Since problem-unspecific search heuristics such as randomized hill-climbers, evolutionary algorithms, simulated annealing etc. do optimize by repeatedly generating new search points and evaluating their objective values (“fitness”), the black-box complexity is a lower bound on the efficiency of such general-purpose heuristics [4].

Black-Box Complexity

Let $\mathcal {S}$ be a finite set. A (randomized) algorithm following the scheme of Algorithm 1 is called black-box optimization algorithm for functions $\mathcal {S}\to \mathbb {R}$.

Algorithm 1

Scheme of a black-box algorithm for optimizing $f:\mathcal{S} \rightarrow \mathbb {R}$

For such an algorithm A and a function $f : \mathcal {S}\to \mathbb {R}$, let T(A,f)∈ℝ∪{∞} be the expected number of fitness evaluations until A queries for the first time some x∈argmaxf. We call T(A,f) the runtime of A for f. For a class $\mathcal {F}$ of functions $\mathcal {S}\to \mathbb {R}$, the A-black-box complexity of $\mathcal {F}$ is $T(A,\mathcal {F}):=~\sup_{f \in \mathcal {F}}{T(A,f)}$, the worst-case runtime of A on $\mathcal {F}$. Let $\mathcal {A}$ be a class of black-box algorithms for functions $\mathcal {S}\to \mathbb {R}$. Then the $\mathcal {A}$ -black-box complexity of $\mathcal {F}$ is $T(\mathcal {A},\mathcal {F}) := \inf_{A\in \mathcal {A}}{T(A,\mathcal {F})}$. If $\mathcal {A}$ is the class of all black-box algorithms, we also call $T(\mathcal {A},\mathcal {F})$ the unrestricted black-box complexity of $\mathcal {F}$.

As said, the unrestricted black-box complexity is a lower bound for the efficiency of randomized search heuristics optimizing $\mathcal {F}$. In fact, it is a lower bound for the efficiency of any randomized black-box algorithm. Unfortunately, often this lower bound is not very useful. For example, Droste, Jansen, and Wegener [4] observed that the $\mathcal {NP}$-complete MaxCliqueproblem on graphs of n vertices has a black-box complexity of only O(n ²).

Black-Box Algorithms with Bounded Memory

As a possible solution to this dilemma, Droste, Jansen, and Wegener suggested to restrict the class of algorithms considered from all black-box optimization algorithms to a reasonably large subset. A natural restriction is to forbid the algorithm to exploit the whole history of search points evaluated. This is motivated by the fact that many heuristics, e.g., evolutionary algorithms, only store a bounded size population of search points. Simple hill-climbers, the Metropolis algorithm or simulated annealing (see, e.g., [13] and the references therein) even store only one single search point.

Algorithm 2 is the scheme of a black-box algorithm with bounded memory of size μ. It is important to note that a black-box algorithm with bounded memory is not allowed to access any information other than the one stored in the μ pairs (x ⁽¹⁾,f(x ⁽¹⁾)),…,(x ^(μ),f(x ^(μ))) which are currently stored in the memory and, in the selection step, also the information provided by (x ^(μ+1),f(x ^(μ+1))).

Algorithm 2

Scheme of a black-box algorithm with memory of size μ for optimizing function $f:\mathcal{S} \rightarrow \mathbb {R}$

Mastermind and the OneMaxFunction Class

A test function often regarded to analyze how the randomized search heuristic under investigation progresses in easy parts of the search space, is the simple OneMaxfunction $\textsc {OneMax}: \{0,1\}^{n} \to \mathbb {R}, x \mapsto \sum_{i = 1}^{n} x_{i}$. Note that $\textsc {OneMax}(x) = \operatorname{eq}((1, \ldots, 1),x)$ for all x∈{0,1}ⁿ. In fact, for any z∈{0,1}ⁿ, $\operatorname{eq}(z,\cdot)$ yields an equivalent optimization problem. Let us denote by $\textsc {OneMax}_{n} := \{\operatorname{eq}(z, \cdot) \mid z \in \{0,1\}^{n}\}$ the class of all these functions.

Many classical randomized search heuristics like randomized local search or the (μ+λ) evolutionary algorithm (with μ,λ constants) need Θ(nlogn) function evaluations to optimize OneMax _n . This stems from the fact in a typical run of such an algorithm, new solutions are obtained from flipping mostly a constant number of bits in an existing solution. By the coupon collector theorem (see, e.g., [11]), Ω(nlogn) such modifications are necessary to ensure that each bit is touched at most once.

As a moments thought reveals, black-box algorithms optimizing OneMax _n correspond to strategies for Paul in the Mastermind game (without memory restriction) with two colors and only black answer-pegs used. Hence the unrestricted black-box complexity of OneMax _n is Θ(n/logn) by the results of Erdős and Rényi [7] and Chvátal [3].

This connection was apparently overlooked so far in the randomized search heuristics community, where Droste, Jansen, and Wegener [4] proved an upper bound of O(n) and later Anil and Wiegand [1] proved the asymptotically correct bound of O(n/logn). Since already the first bound is lower than what many randomized search heuristics achieve, Droste, Jansen, and Wegener suggested to investigate the memory-restricted black-box complexity of OneMax _n . They conjectured in [4, Sect. 6] that a memory restriction of size one leads to a black-box complexity of order Θ(nlogn).

Again, clearly, the memory-restricted black-box complexity of OneMax _n and optimal strategies for Mastermind with two colors, black answer-pegs only, and a corresponding memory restriction are equivalent questions. Consequently, our result can be rephrased to saying that the black-box complexity of OneMax _n even with the memory restricted to one is Θ(n/logn). This disproves the conjecture of Droste, Jansen, and Wegener.

From the view-point of building a useful complexity theory for randomized search heuristics, Theorem 1 indicates that a memory restriction alone does not suffice to overcome the drawbacks of the unrestricted black-box model.

3 The Mastermind Game with Memory of Size Two

Since the proof of Theorem 1 is quite technical, we shall give in this section a simpler proof showing that with a memory of size two Paul can win the game using only O(n/logn) guesses. Already this proof contains many ingredients needed to prove Theorem 1; e.g., the use of the random guessing strategy with limited memory, the block-wise determination of the secret code, and the simulation of iteration counters in the memory.

Let k≥2 be the number of colors used. In particular for k=2, it will be convenient to label the colors from 0 to k−1. Let us denote the set of colors by $\mathcal {C}:=[0\,..\,k-1]:=\{0,1,\ldots,k-1\}$. We assume that k is a constant and that the number n of positions in the string is large, that is, all asymptotic notation is with respect to n.

Theorem 2

Paul has a size-two memory strategy winning the black answer-peg version of the Mastermind game with k colors and n positions in O(n/logn) guesses. This remains true if we allow Carole to play a devil’s strategy.

As many previous works, the proof of Theorem 2 heavily relies on random guessing. For the case of k=2 colors, already Erdős and Rényi [7] showed that there is a t=Θ(n/logn) such that t guesses x ⁽¹⁾,…,x ^(t) chosen from {0,1}ⁿ independently and uniformly at random, together with Carole’s black answer-peg answers, uniquely define the hidden code. This was generalized by Chvátal [3] to the following result.

Theorem 3

(From [3])

Let ε>0, let n>n(ε) be sufficiently large and let k<n ^1−ε. Let x ⁽¹⁾,…,x ^(t) be  $t\ge (2+\varepsilon)\frac{n(1+2 \log k)}{\log n-\log k}$ samples chosen from  $\mathcal {C}^{n}$ independently and uniformly at random. Then for all $z \in \mathcal {C}^{n}$, the set

satisfies $\operatorname{E}[|\mathcal {S}^{\mathit{consistent}}|]\leq 1+1/n$.

Since the strategy implicit in Theorem 3 needs a memory of size Θ(n/logn), we cannot apply it directly in our setting. We can, however, adapt it to work on smaller portions (“blocks”) of the secret code, and this with much less memory.

Let $y \in \mathcal {C}^{n}$ and let B⊆[n] be a block (i.e., an interval) of size $s:=\lceil \sqrt{n} \rceil$. As we shall see, by t=O(s/logs) times guessing a string obtained from y by replacing the colors in B by randomly chosen ones (and guessing k additional reference strings), we can determine z _|B , the part of the secret code z in block B.

We can do so with a memory of size two only. We store the string obtained from y by altering it on B (sampling string) in one cell. Note that we do not need to remember y, as we only need to ensure that our guesses agree in the positions [n]∖B. We use the other memory cell (storage string, in the following typically denoted by x) to store the random substrings of length s substituted into y at B, and Carole’s answers. Note that each such answer can be encoded in binary using ℓ _n =O(logn) entries of the string. Hence the t guesses and answers can be memorized using a total number of t(s+ℓ _n )=O(n/logn) positions. Let us remark that we do need to query the scores $\operatorname{eq}(z,x)$ of the storage strings only in order to be able to add the pair $(x, \operatorname{eq}(z,x))$ to the memory $\mathcal {M}$ (here and henceforth we denote by $\mathcal {M}$ the memory, which is a set containing pairs $(x,\operatorname{eq}(z,x))$ of a previous query x and its answer $\operatorname{eq}(z,x)$). The answers $\operatorname{eq}(z,x)$ themselves, however, are irrelevant to us.

This approach allows us to determine s positions of z using t=O(s/logs) guesses. Hence we can determine the secret code z with t⌈n/s⌉=O(n/logn) guesses as desired.

In Algorithm 3 (notation used will be introduced below) we make this strategy more precise by giving it in pseudo-code. Note, however, that this algorithm does not fully satisfy the size-two memory restriction. The reason is that the queries do not only depend on the current state of the memory, but also on iteration counters and, e.g. in lines 9 and 11, on the program counter. Further below, in Algorithm 4 we shall remove this shortcoming with a few additional technicalities, which we are happy to spare for the moment.

Algorithm 3

An almost size-two memory-restricted algorithm winning the k-color black answer-peg only Mastermind game in O(n/logn) guesses. Remark: x denotes the unique string in $\mathcal {M}$ with x _n =1 and y denotes the unique string in $\mathcal {M}$ with y _n =0.

Algorithm 4

A size-two memory-restricted algorithm winning the k-color black answer-peg only Mastermind game in O(n/logn) guesses. Remark: x denotes the unique string in $\mathcal {M}$ with x _n =1 and y denotes the unique string in $\mathcal {M}$ with y _n =0.

Before we argue for the correctness of Algorithm 3, let us fix the notation. For a string $x \in \mathcal {C}^{n}$ we also write x=[x ₁…x _n ]. To ease reading, we allow ourselves to indicate different structural components of x by vertical bars, e.g., x=[x ₁…x _p |x _p+1…x _n ]. For i∈[⌈(n−1)/s⌉] let B _i :={(i−1)s+1,…,is}∩[n−1], the positions of the ith block. Set

the ith block of x. For any string $r \in \mathcal {C}^{|B_{i}|}$ we define

the string x with the ith block substituted by r. Similarly, let substitute(y,{n},c):=[y ₁…y _n−1|c]. Note that we do not assign the nth position to any of the blocks. We do so because in Algorithms 3 and 4 we shall use the nth position to indicate which one of the two strings in the memory $\mathcal {M}$ is the storage string (the unique $x \in \mathcal {M}$ with x _n =1) and which one is the sampling string (the unique string $y \in \mathcal {M}$ with y _n =0).

Let p ₁(x):=max{i∈[n−1]∣x _i =1}, the largest position i<n of x with entry “1”. As mentioned above, we encode Carole’s answers $\operatorname{eq}(z,y)\in [0\,..\,n]$ in binary, using ℓ _n :=⌈logn⌉+1 positions, and we denote this binary encoding of length ℓ _n by $\texttt {binary}_{\ell_{n}}(\operatorname{eq}(z,y))$. By Δ _i (y) we denote the contribution of the ith block to the value $\operatorname{eq}(z,y)$; i.e., Δ _i (y) is the number of positions in the ith block in which Paul’s guess y and Carole’s secret code z coincide. Formally, $\Delta_{i}(y):=\operatorname{eq}(z_{|B_{i}}, y_{|B_{i}})$. Lastly, let $\mathcal {S}^{\text{consistent}}_{i}$ be the set of strings w of length |B _i | such that substitute(z,B _i ,w) is consistent with all of Carole’s replies (formal definition follows). We shall see below that both Δ _i (y) and $\mathcal {S}^{\text{consistent}}_{i}$ can be computed solely from the content of the memory cells (lines 12–14).

We now argue for the correctness of Algorithm 3. Let us consider the state of the memory after having sampled all t random samples for the ith block (that is, we are in lines 12–14). We show that, based on the information given in the memory, we can restore the full history of guesses for the ith block. To this end, first note that for any guess y done in line 9, we used s+ℓ _n +1 positions in x for storing its information (line 10; we add the additional “1” at the end to ease determining via p ₁(x) the positions in x which have not yet been used for storing information). In lines 6–11 we first asked and stored k non-random guesses x ^c=substitute(y,B _i ,[c…c]) and we stored these reference strings together with Carole’s replies $\operatorname{eq}(z,x^{c})=\sum_{h=1}^{\ell_{n}}{2^{h-1} x_{c(s+\ell_{n}+1)-h}}$, c∈[0 .. k−1]. Therefore, for j∈[t], the jth random sample is $r^{(j)}=[x_{(k+j-1)(s+\ell_{n}+1)+1} \ldots x_{(k+j-1)(s+\ell_{n}+1)+|B_{i}|}]$ and the corresponding query was y ^(j)=substitute(y,B _i ,r ^(j)). We have stored Carole’s reply to this guess in binary, and we can infer $\operatorname{eq}(z,y^{(j)})=\sum_{h=1}^{\ell_{n}}{2^{h-1}x_{(k+j)(s+\ell_{n}+1)-h}}$. This shows how to regain the full guessing history.

Next we show how to compute the contributions Δ _i (y ^(j)) of the entries in the ith block. To this end, note that the constant substrings [c…c] in the reference strings x ^c in total contribute exactly |B _i | to the sum $\operatorname{eq}(z,x^{0})+\cdots+\operatorname{eq}(z,x^{k})$. Formally, $\sum_{c=0}^{k-1}{\operatorname{eq}([z_{(i-1)s+1} \ldots z_{\min\{is,n-1\}}],[c \ldots c])}=|B_{i}|$. Since all other positions of the sampling string y are not changed during the phase in which we determine the ith block, each of them either contributes 0 to the sum $\sum_{c=0}^{k-1}{\operatorname{eq}(z,x^{c})}$, or it contributes k. We thus infer that

Consequently, in lines 12–14, the algorithm can compute Δ _i (y ^(j)) for all j∈[t]. From this it can infer

the set of possible code segments in B _i . By Theorem 3, the expected size of $\mathcal {S}^{\text{consistent}}_{i}$ is bounded from above by 1+1/|B _i |. Thus, in lines 12–14 we need an expected number of 1+1/|B _i | samples w chosen from $\mathcal {S}^{\text{consistent}}_{i}$ uniformly at random until we find a y=substitute(y,B _i ,w) with Δ _i (y)=s (which implies that the ith block of y coincides with Carole’s secret code). This shows how we determine the entries of the ith block in an expected total number of t=O(s/logs) guesses.

When Algorithm 3 executes line 15, all but the last entry of y coincide with Carole’s secret code. Hence trying random colors in the nth position finds the hidden code z with an additional expected number of k=Θ(1) guesses.

To turn Algorithm 3 into a size-two memory-restricted one, we use the first ℓ _n entries of x to store in binary the iteration counter i, which indicates the index of the block currently being under consideration. This will move the storage space for the guesses and answers by ℓ _n positions to the right. Formally, we define $i(x):=\sum_{h=0}^{\ell_{n}-1}{2^{h}x_{\ell_{n}-h}}$. The inner for loop needs no additional memory to be simulated, because we can learn from p ₁(x) how many guesses q(x) have been queried already. More precisely, since storing each guess requires s+ℓ _n +1 positions and the first ℓ _n positions are used for indicating the number of already determined entries, we have q(x):=(p ₁(x)−ℓ _n )/(s+ℓ _n +1).

Lastly, we need to replace the sequential queries in lines 9 and 11 of Algorithm 3 (as this exploits information stored in the program counter). Fortunately, again we can deduce from the memory alone the state of the algorithm. We define a function Part(y,x) which equals 1 if the information of y has been added to the storage string x already and which equals 0 otherwise. That is, we set

Note that Part(y,x)=1 indicates that the information of y has been stored in x also in the case that our current sample equals the previous one. This is no problem as then the current guess does not give any new information. Hence the use of Part modifies the algorithm to sample t random guesses without immediate repetition. Note that the probability to sample the same string $r \in \mathcal {C}^{|B_{i(x)}|}$ twice in a row is at most 1/2 (if the last block consists only of one position and k=2) and is typically much smaller. Hence, occurrences of this event have no influence on the asymptotic number of guesses needed to win the game.

With these modifications, Algorithm 3 becomes the truly size-two memory-restricted Algorithm 4.

4 Reducing the Memory to Size One

Compared to the situation in Sect. 3, Paul faces two additional challenges in the size-one memory-restricted setting. The obvious one is that he has less memory available, in particular, after a large part of the code has been determined and needs to be stored. The more subtle one is that he cannot any longer query a search point and then store whatever is worth storing in the second memory cell. With one memory cell, all he can do is to guess a new string and keep or forget it.

4.1 Linear Time Strategies

Before we give a proof of Theorem 1, let us discuss a linear time winning strategy; i.e., a strategy that allows Paul to find Carole’s secret code in a linear expected number of guesses; using one memory cell only. This linear time strategy will be used in the proof of Theorem 1 to determine the last Θ(n/logn) entries of the secret code.

The basic idea of the linear time strategy is to test each position one by one, from left to right. Since we have just one memory cell, we need to indicate in this one string which entries have been determined already. We do so by keeping all not yet determined entries at one identical value different from the one of the entry determined last. To this end we set, for all $x \in \mathcal {C}^{n}$,

the tail number of x. The way to make progress from x is to randomly change the $\operatorname{tn}(x)$th entry of x to a random other value, or to change the entries in positions $\operatorname{tn}(x)+1$ to n to the same random other value. The latter is a successful move if $x_{\operatorname{tn}(x)}$ is already correct, but is not marked as determined by being different from the other tail entries.

The following lemma describes the linear time strategy.

Lemma 4

Let $x \in \mathcal {C}^{n}$. Furthermore, let us denote Carole’s secret code by $z \in \mathcal {C}^{n}$. Let us assume that the first $\operatorname{tn}(x)-1$ entries of z have been determined (i.e., Carole can no longer change the entries of $[z_{1} \ldots z_{\operatorname{tn}(x)-1}]$). Further assume that x _i =z _i for all $i < \operatorname{tn}(x)$ and that $\mathcal {M}=\{(x,\operatorname{eq}(z,x))\}$ is the current content of the memory cell.

There is a size-one memory-restricted guessing procedure NextEntry that—even if Carole plays a devil’s strategy—after an expected constant number of successive calls modifies the memory such that the string y now in the memory satisfies y _i =z _i for all $i \leq \operatorname{tn}(x)$ and $\operatorname{tn}(y)=\operatorname{tn}(x)+1$. Every call of NextEntry requires only one guess.

Interestingly, for the definition of NextEntry, we need to distinguish between the cases of k=2 and k≥3 colors, as certain arguments exploit particular properties of these cases. For k=2 colors and Carole not playing a devil’s strategy but choosing a random secret z∈{0,1}ⁿ, we have analyzed this algorithm already in [5].

4.1.1 The Case of k=2 Colors $\mathcal {C}=\{0,1\}$

In this section we prove that for k=2 colors $\mathcal {C}=\{0,1\}$, NextEntry is a procedure that requires, in expectation, three calls to modify the memory content by replacing the current string x that is assumed to satisfy the conditions of Lemma 4, by a string y with $\operatorname{tn}(y)=\operatorname{tn}(x)+1$ and y _i =z _i for all $i \leq \operatorname{tn}(x)$.

For all i∈[n] let $e^{n}_{i}$ be the ith unit vector of length n.

Proposition 5

For k=2 colors, Algorithm  5 verifies Lemma 4. In expectation, three calls to routine NextEntry suffice.

Algorithm 5

Routine NextEntry for k=2 colors

Proof

Let x∈{0,1}ⁿ be a bit string with $\operatorname{tn}(x)<n$ and x _i =z _i for all $i <\operatorname{tn}(x)$.

Algorithm 5 samples with probability 1/2 the string $y=x\oplus e^{n}_{\operatorname{tn}(x)}$, and with probability 1/2 it samples $y=x \oplus \sum_{i=\operatorname{tn}(x)+1}^{n}{e^{n}_{i}}$. That is, either it flips only the $\operatorname{tn}(x)$th bit of x or it flips all “tail bits” but the $\operatorname{tn}(x)$th one.

If $y=x\oplus e^{n}_{\operatorname{tn}(x)}$, clearly we have $z_{\operatorname{tn}(x)}=y_{\operatorname{tn}(x)}$ if and only if $\operatorname{eq}(z,y)>\operatorname{eq}(z,x)$.

Therefore, let us assume that Algorithm 5 samples $y=x \oplus \sum_{i=\operatorname{tn}(x)+1}^{n}{e^{n}_{i}}$. We show that $z_{\operatorname{tn}(x)}=y_{\operatorname{tn}(x)}(=x_{\operatorname{tn}(x)})$ holds if and only if $\operatorname{eq}(z,x)+\operatorname{eq}(z,y)= n+\operatorname{tn}(x)$. By definition we have y _i =x _i =z _i for all $i <\operatorname{tn}(x)$. Thus, the first $\operatorname{tn}(x)-1$ bits of x and y contribute $2(\operatorname{tn}(x)-1)$ to the sum $\operatorname{eq}(z,x)+\operatorname{eq}(z,y)$; formally,

On the other hand, for all $i>\operatorname{tn}(x)$ either have z _i =x _i or z _i =1−x _i =y _i . Thus, the last $n-\operatorname{tn}(x)$ bits of x and y contribute exactly $n-\operatorname{tn}(x)$ to the sum $\operatorname{eq}(z,x)+\operatorname{eq}(z,y)$; formally,

By definition we also have $y_{\operatorname{tn}(x)}=x_{\operatorname{tn}(x)}$ and, thus,

This shows that $\operatorname{eq}(z,x)+\operatorname{eq}(z,y)=n + \operatorname{tn}(x)$ if and only if $\operatorname{eq}(z_{\operatorname{tn}(x)},x_{\operatorname{tn}(x)})=1$; i.e., if and only if $z_{\operatorname{tn}(x)}=x_{\operatorname{tn}(x)}(=y_{\operatorname{tn}(x)})$.

It is immediate that for a secret code z taken from {0,1}ⁿ uniformly at random, the probability to obtain, in one call of NextEntry, a string y with $\operatorname{tn}(y)=\operatorname{tn}(x)+1$ and y _i =z _i for all $i<\operatorname{tn}(y)$ is 1/2. This shows that, if Carole does not play a devil’s strategy and if her string is taken from {0,1}ⁿ uniformly at random, we need, on average, two successive calls to procedure NextEntry until we obtain a string y as desired.

Proposition 5 follows from the easy observation that it takes, on average, three iterations until both $y=x\oplus e^{n}_{\operatorname{tn}(x)}$, and $y=x \oplus \sum_{i=\operatorname{tn}(x)+1}^{n}{e^{n}_{i}}$ have been sampled. That is, even if Carole plays a devil’s strategy, three calls of Algorithm 5, on average, force her to accept one entry $z_{\operatorname{tn}(x)}\in \{0,1\}$. □

To win the two-color Mastermind game in a linear number of guesses, Paul may just start with querying the string [0,…,0] and then calling Algorithm 5 sufficiently often.

4.1.2 The Case of k≥3 Colors $\mathcal {C}=[0\,..\,k-1]$

The main argument of Proposition 5, namely that $\sum_{c=0}^{k-1}{\operatorname{eq}(z,[c\ldots c])=n}$, seems hard to extend to more than two colors with no additional memory. However, having more than two colors can be exploited in a different way as it gives more than one possibility to mark the tail $[x_{\operatorname{tn}(x)} \ldots x_{n}]$ of a search point x.

Proposition 6

For k≥3 colors, Algorithm  6 satisfies the claims of Lemma 4.

Algorithm 6

Routine NextEntry for k≥3 colors

Proof

Let $x \in \mathcal {C}^{n}$ with $\operatorname{tn}(x)<n$ and x _i =z _i for all $i<\operatorname{tn}(x)$. If $y=[x_{1} \ldots x_{\operatorname{tn}(x)-1} |j|x_{\operatorname{tn}(x)+1} \ldots x_{n}]$, then clearly we have $\operatorname{eq}(z,y)>\operatorname{eq}(z,x)$ if and only if $y_{\operatorname{tn}(x)}=j=z_{\operatorname{tn}(x)}$. Therefore, all we need to show is that, using the strategy of Algorithm 6, it takes a constant number of guesses until for each $j \in \mathcal {C}$ there exists an $i_{j} \in \mathcal {C}\backslash \{j\}$ such that we have queried both $x=[z_{1} \ldots z_{\operatorname{tn}(x)-1}|i_{j} \ldots i_{j}]$ and $y=[z_{1} \ldots z_{\operatorname{tn}(x)-1}|j|i_{j} \ldots i_{j}]$ in two subsequent guesses. This follows essentially from the fact that k is constant.

More precisely—regardless of the current search point x—for any bitstring $y=[z_{1} \ldots z_{\operatorname{tn}(x)-1}|j|i_{j} \ldots i_{j}]$ the probability to sample y in the second of two subsequent calls to Algorithm 6 is constant. Therefore, the expected number of calls to Algorithm 6 until y is sampled is constant. The claim follows by the linearity of expectation. □

4.2 Proof of Theorem 1

Building on NextEntry and the block-wise random guessing strategy introduced in Sect. 3, we can now prove Theorem 1. That is, we present Paul’s O(n/logn) winning strategy for the setting with one single memory cell.

Proof of Theorem 1

The structure of this proof is as follows. First we sketch the main ideas and give a high-level pseudo-code for the size-one memory-restricted strategy winning the black answer-peg only Mastermind game with k colors in O(n/logn) guesses. After fixing some notation, we then present more details for the different phases, in particular for the random guessing phase, which is the most critical part of this proof. We present here the details of Paul’s strategy for the case of k=2 colors. The generalization to k≥3 colors is pretty much straightforward. Some remarks on the differences between the case of k=2 and k≥3 colors are given at the end of this proof.

Let us begin with the rough overview of Paul’s strategy. He determines the first n−Θ(n/logn) positions using random guessing, where he manages to store the random substrings and Carole’s answers in the yet undetermined part of his one string in the memory. As in the proof of Theorem 2, he does so by iteratively determining blocks of length $s:=\lceil \sqrt{n} \rceil$. The number of blocks determined this way will be $b:=\lfloor \tfrac{n-2}{s}(1-\tfrac{K}{\log n})\rfloor$, where K is a suitably large constant.

This is the first phase of the strategy. In the second phase, using the linear time strategy from Lemma 4, he determines the missing Θ(n/logn) entries in O(n/logn) guesses.

To distinguish between the sampling and the linear time phase, Paul uses the last two entries suffix(x):=[x _n−1 x _n ] of his string x. He has suffix(x)=[01] when he is in the random guessing phase, and he uses suffix(x)=[cc] for some $c\in \mathcal {C}$ to indicate that he applies calls to NextEntry. Once Paul has determined all but the last two entries (visible from $\operatorname{tn}(x)=n-1$), he simply needs to sample uniformly at random from the set of all k ²−1 remaining possible strings. This clearly determines z in a constant expected number of additional queries (phase 3).

The total expected number of guesses can be bounded by

A non-trivial part is the random guessing phase. As in the proof of Theorem 2, after guessing t+k strings, we want to be able to regain the full guessing history. If we simply stored the random substring and Carole’s reply in some unused part of x, then this changed memory would influence Carole’s next answer and we would be unable to deduce information on the next guess from it. We solve this difficulty as follows. We store Carole’s latest reply (i.e., value $\operatorname{eq}(z,x)$ currently in the memory) and we sample new (random) substrings for the current block at the same time. Here we store the value $\operatorname{eq}(z,x)$ in a part of x for which we know the entries of Carole’s hidden code. By this, we can separate in Carole’s next answer the influence of the just stored information from the one of the random guess. The precise description of this Sampling strategy is presented below.

To gain the storage space, for which we know the hidden code, we need to add another phase, phase 0, in which we apply O(logn) calls to the NextEntry procedure until we have determined the first ℓ:=ℓ _n +1 positions of z (cf. Lemma 4). This does not change the overall asymptotic number of queries Paul needs to win the game.

The pseudo-code for this size-one memory-restricted strategy is given in Algorithm 7. Similar to the notation in the proof of Theorem 2, we denote for any h∈[0 .. n] its binary encoding of length ℓ _n by $\texttt {binary}_{\ell_{n}}(h)$ and for h∈[0 .. s] we denote its binary encoding of length ℓ _s :=⌈logs⌉+1 by $\texttt {binary}_{\ell_{s}}(h)$. The current block of interest i(x) is encoded in positions {n−ℓ _s −1,…,n−2}; i.e., we have $i(x):=\sum_{h=0}^{\ell_{s}-1}{2^{h} x_{n-2-h}}$ and B _i(x):={ℓ+(i(x)−1)s+1,…,ℓ+i(x)s}, and, consequently, BLOCK _i(x)(x):=[x _{ℓ+(i(x)−1)s+1}…x _ℓ+i(x)s ]. The number of random guesses for each block is $t:=\lceil (2+\varepsilon) \tfrac{s(1+2 \log k)}{\log s -\log k} \rceil$ where ε>0 is an arbitrarily small constant. Lastly, the actual number of already sampled guesses for block B _i(x) is denoted by q(x). As in the proof of Theorem 2, q(x) can be computed via p ₁(x):=max{i∈[n−ℓ _s −3]∣x _i =1}, the largest position i<n−2−ℓ _s with entry x _i =1. Details on how q(x) can be computed are given in the description of the OptimizeBlockroutine, which, after t random samples have been sampled via the Samplingroutine, determines BLOCK _i(x)(z), stores it in B _i(x), and increases the block counter i(x) by one.

Algorithm 7

A size-one memory-restricted algorithm winning the k-color black answer-peg only Mastermind game in O(n/logn) guesses.

Let us now present a more detailed description of Algorithm 7.

As in the proof of Theorem 2 let us assume that Carole has chosen a fix code $z\in \mathcal {C}^{n}$, which she does not change during the game; i.e., to any of Paul’s guesses x she replies $\operatorname{eq}(z,x)$. By adopting a worst-case view below, we implicitly still allow Carole to change z as long as the new choice is consistent with all previous replies.

If in any iteration we find an x with $\operatorname{eq}(z,x)=n$, we have x=z and all we need to do is to output x. Thus, in what follows we always assume $\operatorname{eq}(z,x)<n$.

Initialization of Algorithm 7, Lines 1–4

For initialization, Paul picks a $c \in \mathcal {C}$ uniformly at random and guesses the all-“c”s string of length n, x=[c…c]. He updates the memory $\mathcal {M}\leftarrow \{(x,\operatorname{eq}(z,x))\}$ accordingly. This memory satisfies all conditions of line 1 of routine NextEntry (Algorithms 5 and 6) with $\operatorname{tn}(x)=1$.

Phase 0 of Algorithm 7, Lines 5–6

To this string, Paul applies successive calls to the routine NextEntry. By Lemma 4 he finds a string $y \in \mathcal {C}^{n}$ with y _i =z _i , i≤ℓ, and $\operatorname{tn}(y)=\ell+1$ in an expected number of O(ℓ) guesses. As mentioned above, Paul runs this first phase until he has determined the first

entries. This is the number

of entries needed to store in binary any integer value h∈[0 .. n] plus 1. These bits shall be used in phase 1 of Algorithm 7 to indicate the status of the Sampling routine (first position) and for storing Carole’s latest reply $\operatorname{eq}(z,x)\in [0\,..\,n]$ (positions {2,…,ℓ}). We shall describe this in more detail below.

First Phase of Algorithm 7, Lines 7–13

After Paul has determined the first ℓ entries, he first needs to prepare the string for the random guessing phase. This is done in lines 7–9. Since we want to use the first ℓ entries to store reference values, we need to make a copy of the prefix (which, by construction, coincides with Carole’s hidden code). To this end, we query in line 8 the string

where x is the string that is currently in the memory (i.e., the string we obtained through phase 0)¹ and bs=n−Θ(n/logn) is the number of positions Paul determines using random guessing. As mentioned in the overview, the last two entries suffix(x)=[x _n−1 x _n ]=[01] indicate that we are entering the second phase. In positions {n−ℓ _s −1,…,n−2} we indicate in binary the block which we are currently trying to determine. That is, whenever x is the current string in the memory with suffix(x)=[01], then the block currently of interest is B _i(x) with $i(x)=\sum_{i=0}^{\ell_{s}-1}{2^{i} x_{n-2-i}}$. We initialize i(x)=1.

After guessing y and updating the memory by replacing the current one with $\{(y,\operatorname{eq}(z,y))\}$, Paul enters the first phase (as indicated by suffix(x)). The overall expected number of queries needed until this point is O(ℓ)=O(logn).

After lines 7–9 have been executed, Paul determines all but n−Θ(n/logn) entries by iteratively determining blocks of length $s=\lceil \sqrt{n} \rceil$ via random guessing. In total, he determines $b=\lfloor \frac{n}{s}(1-\frac{K}{\log n})\rfloor$ such blocks in this phase. The description of the routines Sampling (in which k reference strings and t random samples are queried for the i(x)th block B _i(x)) and OptimizeBlock (in which we use the reference strings and the random guesses to determine BLOCK _i(x)(z), the i(x)th block of the secret code z) is quite technical. We present the details after the description of the remaining phases.

Second Phase of Algorithm 7, Lines 14–18

In the second phase of Algorithm 7 we again apply successive calls to routine NextEntry to determine all but the last two remaining entries. To this end, we first need to prepare the string. This is done in lines 14–16 of Algorithm 7. It follows from the correctness of the first phase that the string x queried in line 16 satisfies x _i =z _i for all 1≤i≤ℓ+bs. And, by definition, it also satisfies $x_{\operatorname{tn}(x)-1} \neq x_{\operatorname{tn}(x)}$ with $\operatorname{tn}(x)=\ell + bs +1$.

From Lemma 4 we infer that via routine NextEntry we find a string x with $\operatorname{tn}(x)=n-1$ and x _i =z _i for all 1≤i≤n−2 in an expected number of O(n−2−(ℓ+bs))=O(n/logn) queries. These are lines 17 and 18 of Algorithm 7.

Third Phase of Algorithm 7, Lines 19–22

Similarly to the last step of Algorithm 4, all we need to do in the last phase of Algorithm 7 is to determine the last two entries. This is done by sampling y uniformly at random from the set of possible target strings

and we find y=z after a constant expected number of queries. This phase is recognized by the algorithm by the fact that $\operatorname{tn}(x)=n-1$. Note that we have $\operatorname{tn}(x)\leq n-2$ in the NextEntry phases—phases 0 and 2—and that we have $\operatorname{tn}(x)=n$ in phase 1.

Summing up the expected number of queries needed for each phase, we have shown that Paul needs, on average,

queries until he has identified Carole’s hidden code z.

In the remainder of this proof we present the details of the first phase of Algorithm 7, the random sampling routine Sampling, and the OptimizeBlock routine. As mentioned above, this description requires some technicalities. Therefore, we split it into the following parts:

• In Part I we present the general structure of the guesses Paul queries in the sampling phase. Here, we shall also show that the n positions are indeed sufficient to store, for any of the b blocks of length s, all necessary information about the samples.

• Part II provides further notation used in the pseudo-code of Algorithm 8.

  Algorithm 8

  

  The Sampling routine for k=2 colors.

• In Part III we show how the contributions Δ _i(x)(r)∈[0 .. s] of the random samples $r \in \mathcal {C}^{s}$ can be computed solely from the content in the memory. This also shows that indeed after sampling the t random guesses for the current block of interest, it is possible to regain the full query history using only the information that has been stored in the memory.

• We conclude the description of phase 1 in Part IV, where we explain how the memory is being updated once the entries BLOCK _i(x)(z) of the secret code z in the i(x)th block have been determined.

Part I The general structure of a random query x for determining block B _i(x) is the following.

(1)

where we use

• (1) the first entry x ₁∈{0,1} to indicate whether we are sampling a new random substring (x ₁=1) or whether we are doing a storage operation by which we add to x all necessary information from the previous guess (x ₁=0). An explanation of these operations follows below;

• (2) ℓ _n entries for encoding the value $\operatorname{eq}(z,y) \in [0\,..\,n]$ of the string y that is currently stored in the memory cell (serves as reference value),

• (3) (i(x)−1)s entries for the already determined blocks B ₁,…,B _i(x)−1,

• (4) s entries for the current block B _i(x) of interest. If we are sampling new information (i.e., if x ₁=1), then the substring r is a string taken from $\mathcal {C}^{s}$ uniformly at random and r is the all-zeros string [0,…,0] of length s otherwise;

• (5) (b−i(x))s zeros for the yet untouched blocks B _b′ with i(x)<b′≤b,

• (6) ℓ entries for storing the length-ℓ prefix that coincides with Carole’s hidden code (obtained through phase 0),

• (7) 2ℓ _n +1 entries for storing the values $\operatorname{eq}(z,x^{0})$ and $\operatorname{eq}(z,x^{1})$ of the two reference strings x ⁰ and x ¹ (explanation follows),

• (8) t′(ℓ _n +s+ℓ _s +1), t′≤t, entries for storing, for each random sample,

  • (i) the value $\operatorname{eq}(z,\texttt {ref})$ for a reference string ref (in binary, requires ℓ _n positions),

  • (ii) the random sample $r \in \mathcal {C}^{s}$ itself,

  • (iii) its contribution Δ _i(x)(r)∈[0 .. s] to Carole’s reply (in binary, requires ℓ _s positions), and

  • (iv) one additional “1” (to ease the computation of the number of guesses q(x) via p ₁(x); details follow),

• (9) ℓ _s entries for encoding in binary which block we are currently trying to determine, and

• (10) the last two entries, suffix(x), for indicating the current phase of the algorithm.

Clearly, one critical part is the limited storage capacity. For this reason, let us show that we have enough positions to store all the information needed to compute $\mathcal {S}^{\text{consistent}}_{i(x)}$, the set of all strings consistent with Carole’s replies for the random guesses in the i(x)th block B _i(x).

Recall that, by Theorem 3, for determining the i(x)th block BLOCK _i(x)(z) of z, we need $t=(2+\varepsilon)\frac{s(1+2 \log k)}{\log s-\log k}=\varTheta(s/\log n)$ random guesses (ε>0 being an arbitrarily small constant). In addition, equivalently to the proof of Theorem 2, we need again 2 reference strings x ⁰ and x ¹ (reference (7) in Eq. (1)). These two reference strings will be needed to infer the contributions Δ _i(x)(r) of the random samples $r\in \mathcal {C}^{s}$ in the i(x)th block.

From the structure of the guesses presented in Eq. (1) above, we infer that the total storage requirement can be bounded from above by

for sufficiently large, but constant K and sufficiently large n. This shows that, for sufficiently large n, Paul indeed can store all information needed to compute $\mathcal {S}^{\text{consistent}}_{i(x)}$ in one single string of length n.

Part II Let us now fix the notation used in the pseudo-code of routine Sampling (Algorithm 8). For all b′<i(x) we set

the entries of x in the b′th block. The notation “opt” is justified by the fact that we shall have opt(B _b′)=BLOCK _b′(z) for all b′<i(x). Furthermore, let

where the references in the expression above are the same as the ones used in Eq. (1) and where (∗) is simply a copy of the last entries of x. That is, the AddReferenceStringInfo(x) operation adds to x the values $\operatorname{eq}(z,x^{0})$ and $\operatorname{eq}(z,x^{1})$ and each of these values is stored in binary notation of length ℓ _n . Lastly, we denote by $\texttt {Add}(\operatorname{eq}(z,x))$ the operation

(2)

which adds (in substring (†)) to the memory

• a copy of the value $\operatorname{eq}(z,\texttt {ref})$ of a reference string ref (which was previously stored in positions {2,…,ℓ}),

• the random sample BLOCK _i(x)(x) of the last guess,

• the contribution Δ _i(x)(BLOCK _i(x)(x)) of the random sample BLOCK _i(x)(x) to $\operatorname{eq}(z,x)$, and

• the one additional “1” that shall ease the computation of q(x), the number of already queried samples.

All but the first ℓ entries (which are set to zero) are copied from x. The references in Eq. (2) are again the same as in Eq. (1).

Part III Let us now show in detail how to infer the contributions Δ _i(x)(r) of the random guesses. For clarity, we show how to do this for the first block; i.e., for the positions {ℓ+1,…,ℓ+s}. The procedure is similar for all other blocks and we shall comment on this case at the end of this part.

First note that after executing lines 7 to 9 of Algorithm 7, Paul enters the routine Sampling with $\mathcal {M}=\{(x^{0},\operatorname{eq}(z,x^{0}))\}$ where

and he queries in the first sampling iteration (lines 2–4 of Algorithm 8)

with the entries in the first block replaced by the all-ones substring [1,…,1] and the first ℓ entries updated. We can compute the contribution of the first ℓ entries $[1|\texttt {binary}_{\ell_{n}}(\operatorname{eq}(z,x^{0}))]$ to the value $\operatorname{eq}(z,x^{1})$ via

and, by the same reasoning, the contribution of the first ℓ entries in x ⁰ to $\operatorname{eq}(z,x^{0})$ via $\tilde{f}(x^{0})=\operatorname{eq}([x^{0}_{\ell+bs+1} \ldots x^{0}_{2\ell+bs}],[0 \ldots 0])$. Let us, for a moment, assume that we now had $\mathcal {M}=\{(x^{1}, \operatorname{eq}(z,x^{1}))\}$ and that we had another string

for some random substring $r \in \mathcal {C}^{s}$. Then we could compute the contribution of the random entries r in the first block B ₁ of y via

Key to this equality is the fact that the first ℓ entries of y contribute ℓ to Carole’s response $\operatorname{eq}(z,y)$ to guess y, whereas the first ℓ entries of x ⁰ and x ¹ contribute $\tilde{f}(x^{0})+\tilde{f}(x^{1})$ to the sum $\operatorname{eq}(z,x^{0})+\operatorname{eq}(z,x^{1})$, and the fact that the entries in the first block—[0…0] and [1…1], respectively—contribute in total s towards $\operatorname{eq}(z,x^{0})+\operatorname{eq}(z,x^{1})$. All other entries x _i ,y _i ,i>ℓ+s contribute either 2 or 0 to the sum $\operatorname{eq}(z,x^{0})+\operatorname{eq}(z,x^{1})$ and every entry contributes 2 if and only if it contributes 1 to the value $\operatorname{eq}(z,y)$.

Note, however, that we would now have to choose which of the strings to keep in the memory and we would eventually loose the information $\operatorname{eq}(z,x^{1})$. Therefore, in lines 6 and 7 in Algorithm 8, we first query the reference string

This query is needed only to store the values $\operatorname{eq}(z,x^{0})$ and $\operatorname{eq}(z,x^{1})$ of both reference strings. Since adding the substring $[\texttt {binary}_{\ell_{n}}(\operatorname{eq}(z,x^{0}))|\texttt {binary}_{\ell_{n}}(\operatorname{eq}(z,x^{1}))|1]$ to the memory string again changes the number of positions in which the guess and Carole’s hidden string coincide, we need to store this information in the next query as well. More precisely, we have that x ⁰ and x ² differ in exactly the substring $[\texttt {binary}_{\ell_{n}}(\operatorname{eq}(z,x^{0}))|\texttt {binary}_{\ell_{n}}(\operatorname{eq}(z,x^{1}))|1]$, and the contribution of this substring (compared to the all-zeros substring which it replaces) is $\operatorname{eq}(z,x^{2})-\operatorname{eq}(z,x^{0})$.

Furthermore, we need to indicate that we are sampling a new random substring. This is the first position in the string and the next ℓ−1 entries are needed to encode in binary the value $\operatorname{eq}(z,x^{2})$. That is, instead of querying y as above we query (lines 9 and 10 in Algorithm 8)

where the substring $r^{(1)} \in \mathcal {C}^{s}$ in B ₁ is taken uniformly at random. The number of zeros in the first all-zeros substring is again (b−1)s and in the second all-zeros substring it is n−(2ℓ+bs+2ℓ _n +1+ℓ _s +2). Now, in the same fashion as above, we can compute the contribution $\Delta_{1}(r^{(1)})= \operatorname{eq}([z_{\ell+1} \ldots z_{\ell+s}])$ of the substring $r^{(1)} \in \mathcal {C}^{s}$ via

(3)

Note that all the information needed for this computation is contained in the string x ³ itself.

Since later we want to be able to regain the full guessing history, in the next guess we store both the reference value $\operatorname{eq}(z,x^{2})$ as well as the contribution Δ₁(r ⁽¹⁾). And, of course, we also need to store the random guess r ⁽¹⁾=BLOCK ₁(x ³) itself. Therefore, we query (lines 12 and 13 in Algorithm 8) in the next iteration of Algorithm 7

Note that, since Δ₁(r ⁽¹⁾)∈[0 .. s], we can encode this value using ℓ _s positions only.

By continuing like this we are able to compute, in any iteration of the first phase, the contributions Δ _i(x)(r) of the random substrings $r \in \mathcal {C}^{s}$.

As in the proof of Theorem 2 we need to be able to compute how many random guesses have been queried already for the current block of interest. As indicated above, this can be derived from p ₁(x) as follows. For any random guess $r \in \mathcal {C}^{s}$ we use ℓ _n +s+ℓ _s +1 entries for storing all information that will be needed later to regain the full guessing history. Furthermore, we used 2ℓ _n +1 entries for storing the values $\operatorname{eq}(z,x^{0})$ and $\operatorname{eq}(z,x^{1})$ of the two reference strings x ⁰ and x ¹, and we store information only in positions i>2ℓ+bs. Hence, the number of guesses for block B _i(x) can be computed as

After querying t random guesses (i.e., after querying a total number of t+k guesses) for the first block, we regain the full guessing history from the string x currently in the memory as follows. The ith random sample $r^{(i)}\in \mathcal {C}^{s}$ which we guessed for the first block is

and the corresponding query was

We have stored in binary the contribution Δ₁(r ⁽ⁱ⁾) of r ⁽¹⁾ to the overall function value $\operatorname{eq}(z, y^{(i)})$ in positions

and thus we have

By Theorem 3, the expected size of

is bounded from above by 1+1/s. That is, we can now identify BLOCK ₁(z) in a constant number of guesses. These are lines 3–5 of routine OptimizeBlock (Algorithm 9).

Algorithm 9

The OptimizeBlock routine.

As mentioned above, determining the other blocks 2,…,b is similar. In these iterations, the (i(x)−1)s entries in positions {ℓ+1,…,ℓ+(i(x)−1)s} are already optimized, that is, they coincide with Carole’s hidden string z. Thus, they are not changed in any further iteration of Algorithm 9.

Part IV Once BLOCK _i(x)(z)=[z _{ℓ+(i(x)−1)s+1}…z _ℓ+i(x)s ] has been determined, we need to update the memory such that we can start determining the entries of the next block. These are lines 7 and 8 in Algorithm 9. Here we abbreviate

where

• (a) the first ℓ entries are set to zero,

• (b) we now have i(x) already determined blocks,

• (c) the new block of interest, block i(x)+1, as well as all blocks b′>i(x)+1 are (still) set to zero,

• (d) we keep the copy of the prefix [z ₁…z _ℓ ] in positions {ℓ+bs+1,…,2ℓ+bs},

• (e) all information that we have used in the previous query to determine block B _i(x) is removed (and set to zero),

• (f) the index for the current block of interest is increased by one, and

• (g) the last two entries still indicate the second phase.

The Case of k≥3 Colors

For the general case, the main strategy as given by Algorithm 7 remains the same. What needs to be changed is the Sampling routine where instead of sampling only two reference strings x ⁰ and x ¹, we need to sample k reference strings x ⁰,x ¹,…,x ^k−1 with BLOCK _i(x)(x ^c)=[c…c] for all c∈[0 .. k−1].

Algorithm 10 shows the generalized sampling routine. Here we define

where

(1)–(7):

are the same references as in Eq. (1),

(7’):

are the additional positions needed for storing the values $\operatorname{eq}(z,x^{j})$ of the already queried reference strings x ²,…,x ^q(x)−1 (requiring 2ℓ _n +1 positions each),

(†):

we add the information of the q(x)th reference string x ^q(x) to the memory (again requiring 2ℓ _n +1 positions), and

(∗):

is simply a copy of the last entries of the previous guess.

The substring [x ₂…x _ℓ ] is needed again to infer the contribution of the positions in which we added the information of the previous reference string x ^q(x)−1. The reasoning is the same as in the case of k=2 colors.

Algorithm 10

The Sampling routine for k≥3 colors.

Since we added more reference string information, we need to adjust the definition of q(x) accordingly. Since we need 2ℓ _n +1 additional bits for each reference string x ^j, 2≤j≤k−1, and we use ℓ _n +s+ℓ _s +1 entries for storing the information of each random guess, we have

It is easily verified that all statements made in the above proof for k=2 colors remain correct if we consider the general case of k≥3 colors. Only the computation of the contributions Δ _i(x)(BLOCK _i(x)(x)), Eq. (3), becomes a bit more tedious. However, all calculations are straightforward.  □