On the query complexity of Black-Peg AB-mastermind

Ouali, Mourad El; Glazik, Christian; Sauerland, Volkmar; Srivastav, Anand Article On the query complexity of Black-Peg AB-mastermind Games Provided in Cooperation with: MDPI – Multidisciplinary Digital Publishing Institute, Basel Suggested Citation: Ouali, Mourad El; Glazik, Christian; Sauerland, Volkmar; Srivastav, Anand (2018) : On the query complexity of Black-Peg AB-mastermind, Games, ISSN 2073-4336, MDPI, Basel, Vol. 9, Iss. 1, pp. 1-12, https://doi.org/10.3390/g9010002 This Version is available at: https://hdl.handle.net/10419/179164 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by/4.0/ Article On the Query Complexity of Black-Peg AB-Mastermind Mourad El Ouali 1, Christian Glazik 2,*, Volkmar Sauerland 2and Anand Srivastav 2 1Polydisciplinary Faculty Ouarzazate, University Ibn Zohr, Agadir 80000, Morocco; [email protected] 2Department of Computer Science, Kiel University, 24118 Kiel, Germany; [email protected] (V.S.); [email protected] (A.S.) *Correspondence: [email protected] Received: 8 November 2017; Accepted: 28 December 2017; Published: 2 January 2018 Abstract: Mastermind is a two players zero sum game of imperfect information. Starting with Erd˝os and Rényi (1963), its combinatorics have been studied to date by several authors, e.g., Knuth (1977), Chvátal (1983), Goodrich (2009). The first player, called “codemaker”, chooses a secret code and the second player, called “codebreaker”, tries to break the secret code by making as few guesses as possible, exploiting information that is given by the codemaker after each guess. For variants that allow color repetition, Doerr et al. (2016) showed optimal results. In this paper, we consider the so called Black-Peg variant of Mastermind, where the only information concerning a guess is the number of positions in which the guess coincides with the secret code. More precisely, we deal with a special version of the Black-Peg game with n holes and k≥n colors where no repetition of colors is allowed. We present upper and lower bounds on the number of guesses necessary to break the secret code. For the case k=n , the secret code can be algorithmically identified within less than (n− 3 )dlog2ne+5 2n− 1 queries. This result improves the result of Ker-I Ko and Shia-Chung Teng (1985) by almost a factor of 2. For the case k>n , we prove an upper bound of (n− 2 )dlog2ne+k+ 1. Furthermore, we prove a new lower bound of n for the case k=n , which improves the recent n−log log(n) bound of Berger et al. (2016). We then generalize this lower bound to k queries for the case k≥n. Keywords: Mastermind; combinatorial problem; permutation; algorithm; complexity MSC: 91A46 1. Introduction In this paper, we deal with Mastermind, which is a popular board game that in the past three decades has become interesting from an algorithmic point of view. Mastermind is a two-player board game invented in 1970 by the postmaster and telecommunication expert Mordecai Meirowitz. The original version of Mastermind consists of a board with twelve (or ten, or eight) rows containing four holes and pegs of six different colors. The idea of the game is that the codemaker chooses a secret color combination of n pegs from k possible colors and the codebreaker has to identify the code by a sequence of queries and corresponding information that is provided by the codemaker. All queries are also color combinations of n pegs. Information is given about the number of correctly positioned colors and further correct colors, respectively. Mathematically, the codemaker selects a vector y∈[k]n and the codebreaker gives in each iteration a query in form of a vector x∈[k]n . The codemaker replies with a pair of two numbers, called black(x , y) and white(x , y) , respectively. The first one is the number of positions in which both vectors x and y coincide and the second one is the number of additional pegs with a right color but a wrong position: Games 2018,9, 2; doi:10.3390/g9010002 www.mdpi.com/journal/games Games 2018,9, 2 2 of 12 black(x,y) = |{i∈[n]|x(i) = y(i)}|, white(x,y) = max σ∈Sn |{i∈[n]|y(i) = x(σ(i))}| −black(x,y). The Black-Peg game is a special version of Mastermind, where answers are provided by black information only. A further version is the so-called AB game, a.k.a. Bulls and Cows, in which all colors within a code must be distinct. Actually, this version is supposed to be much older than the commercial variant of Mastermind. It is an interesting open question whether both variants are of the same complexity for the codebreaker or if one version is significantly harder because, in the AB game, the space of possible solutions as well as the space of possible queries are both restricted. In this paper, we deal with a special combination of the Black-Peg game and the AB game, where both the secret vector and the guesses must be composed of pairwise distinct colors ( k≥n ) and the answers are given by the black information only. In a breakthrough paper, Doerr et al. [ 1 ] state that k=n is the most popular case in research, where the white information is redundant for the AB game. Related Works: The study of Mastermind in its different variants has a long lasting history in combinatorial game theory. In 1963, several years before the invention of Mastermind as a commercial board game, Erd˝os and Rényi [ 2 ] analyzed the same problem with two colors. One of the earliest analyses of this game after its commercialization dealing with the case of four pegs and six colors was done by Knuth [3]. He presented a strategy that identifies the secret code in at most five guesses. For the AB game with four pegs, it is known that at least seven guesses are required in the worst case [ 4 ]. Ever since the work of Knuth, the general case of arbitrary many pegs and colors has been intensively investigated in combinatorics and computer science literature. In the field of complexity, Stuckman and Zhang [ 5 ] showed that it is N P -complete (most likely impossible in polynomial time) to determine if a sequence of queries and answers is satisfiable. Concerning the approximation aspect, there are many works regarding different methods [ 5 – 16 ]. The Black-Peg game was first introduced by Chvátal for the case k=n . He gave a deterministic adaptive strategy that uses 2 ndlog2ke+ 4 n guesses. Later, Goodrich [ 17 ] improved the result of Chvátal for arbitrary n and k to ndlog2ke+d( 2 − 1 /k)ne+k guesses. Moreover, he proved in the same paper that this kind of game is N P -complete. A further improvement to ndlog2ne+k−n+ 1 for k>n and ndlog2ne+k for k≤n was done by Jäger and Peczarski [ 18 ]. Doerr et al. [ 1 ] provided a randomized codebreaker strategy that only needs O(nlog log n) queries in expectation. They also showed that this asymptotic order even holds for up to n2log log n colors, if both black and white information is allowed. For the AB game, Jäger and Peczarski [ 19 ] proved exact worst-case numbers of guesses for fixed n∈ { 2, 3, 4 } and arbitrary k . Concerning the combination of both variants, Black-Peg game and AB game, for almost three decades, the work due to Ker-I Ko and Shia-Chung Teng [ 20 ] was the only contribution that provides an upper bound for the case k=n . They presented a strategy that identifies the secret permutation in at most 2nlog2n+7nguesses and proved that the corresponding counting problem is #P-complete. Our Contribution: In this paper, we consider the Black-Peg game without color repetition. We first present a deterministic polynomial-time algorithm that identifies the secret permutation in less than (n− 3 )dlog2ne+5 2n− 1 queries in the case k=n and in less than (n− 2 )dlog2ne+k+ 1 queries in the case k>n . In a conference version (extended abstract) “Improved Approximation Algorithm for the Number of Queries Necessary to Identify a Permutation”, upper bounds of this paper have been presented with some sketches of the proofs [ 21 ]. Our result for the case k=n improves the result of Ker-I Ko and Shia-Chung Teng [ 20 ] by almost a factor of 2. Furthermore, we analyze the worst-case performance of query strategies for both variants of the Game and give a new lower bound of n queries for the case k=n , which improves the recently presented lower bound of n−log log(n) by Berger et al. [ 22 ]. We note, however, that the corresponding asymptotic bound of O(n) is long-established. For k≥n , we generalize this lower bound to k . Both lower bounds even hold if the codebreaker is allowed to use repeated colors in his guesses. Games 2018,9, 2 3 of 12 2. Upper Bounds on the Number of Queries We first consider Black-Peg Mastermind with k=n and the demand for pairwise distinct colors in both the secret code and all queries, i.e., we deal with permutations in Sn. 2.1. Black-Peg AB-Mastermind, Case k =n For convenience, we will use the term permutation for both, a mapping in Sn and its one-line representation as a vector. Our algorithm for finding the secret permutation y∈Sn includes two main phases that are based on two ideas. In the first phase, the codebreaker guesses an initial sequence of n permutations that has a predefined structure. In the second phase, the structure of the initial sequence and the corresponding information by the codemaker enable us to identify correct components yi of the secret code one after another, each by using a binary search. Recall that, for two codes w= (w1 , . . . , wn) and x= (x1 , . . . , xn) , we denote by black(w , x) the number |{i∈[n]|wi=xi}| of components in which w and x are equal. We denote the mapping x restricted to the set {s , . . . , `} with (xi)` i=s , s , `∈[n] . Phase 1. Consider the n permutations, σ1 , . . . , σn , which are defined as follows: σ1 corresponds to the identity map and, for j∈[n− 1 ] , we obtain σj+1 from σj by a circular shift to the right. For example, if n= 4, we have σ1= ( 1, 2, 3, 4 ) , σ2= ( 4, 1, 2, 3 ) , σ3= ( 3, 4, 1, 2 ) and σ4= ( 2, 3, 4, 1 ) . Within those npermutations, every color appears exactly once at every position and, thus, we have n ∑ j=1 black(σj,y) = n. (1) The codebreaker guesses σ1 , . . . , σn−1 and obtains the additional information black(σn , y) from Equation (1). Phase 2. The strategy of the second phase identifies the values of y one after another. This is done by using two binary search routines, called FINDFIRST and FINDNEXT, respectively. The idea behind both binary search routines is to exploit the information that, for 1 ≤i , j≤n− 1, we have σj i=σj+1 i+1 , σn i=σ1 i+1 , σj n=σj+1 1 and σn n=σ1 1 , while, except for an infrequent special case, FINDFIRST is used to identify the first correct component of the secret code, and FINDNEXT identifies the remaining components in the main loop of the algorithm. Actually, FINDFIRST would also be able to find the remaining components but requires more guesses than FINDNEXT (twice as many in the worst case). On the other hand, FINDNEXT only works if at least one value of y is already known such that we have to identify the value of one secret code component in advance. Identifying the First Component: Equation (1) implies that either black(σj , y) = 1 holds for all j∈[n]or that we can find a j∈[n]with black(σj,y) = 0. In the first case, which is infrequent, we can find one correct value of y by guessing at most bn 2c+ 1 modified versions of some initial guess, say σ1 . Namely, if we define a guess σ by swapping a pair of components of σ1 , we will obtain black(σ , y) = 0, if and only if one of the swapped components has the correct value in σ1. In the frequent second case, we find the first component by FINDFIRST in at most 2 dlog2ne guesses. The routine FINDFIRST is outlined as Algorithm 1and works as follows. In the given case, we can either find a j∈[n− 1 ] with black(σj , y)> 0 but black(σj+1 , y) = 0 and set r:=j+ 1, or we have black(σn , y)> 0 but black(σ1 , y) = 0 and set j:=n and r:= 1. We call such an index j an active index. Now, for every `∈ {2, 3, . . . , n}, we define the code σj,`:=(σj i)`−1 i=1,σr 1,(σr i)n i=`+1, and call the peg at position ` in σj,` the pivot peg. Note that notations of the form (σ)b i=a substitute σa , σa+1 , . . . , σb and vanish in the case a>b . From the information σj i=σr i+1 for 1 ≤i≤n− 1, we conclude that σj,` is actually a new permutation as required. The fact that black(σr , y) = 0 Games 2018,9, 2 4 of 12 implies that the number of correct pegs up to position `− 1 in σj is either black(σj,` , y) (if y`6=σr 1 ) or black(σj,` , y)− 1 (if y`=σr 1 ). For our algorithm, we will only need to know if there exists one correct peg in σj up to position `− 1. The question is cleared up, if black(σj,` , y)6= 1. On the other hand, if black(σj,` , y) = 1, we can define a new guess ρj,` by swapping the pivot peg with a wrong peg in σj,` . We define ρj,`:=       (σj i)` i=1,σr 1,(σr i)n i=`+2, if ` < n, σr 1,(σj i)n−1 i=2,σj 1, if `=n. Algorithm 1: Routine FINDFIRST input :Code yand an active index j∈[n] output:Left most correct peg position in σj 1if j=nthen r:=1; 2else r:=j+1; 3a:=1; 4b:=n;// bis also the position to be found 5while b>ado 6`:=da+b 2e;// pivot position 7Guess σj,`:=(σj i)`−1 i=1,σr 1,(σr i)n i=`+1; 8s:=black(σj,`,y); 9if s=1then 10 if ` < nthen ρj,`:=(σj i)` i=1,σr 1,(σr i)n i=`+2; 11 else ρj,`:=σr 1,(σj i)n−1 i=2,σj 1; 12 Guess ρj,`; 13 s:=black(ρj,`,y); 14 if s>0then b:=`−1; 15 else a:=`; 16 return b; For the case `=n , we may assume that we applied our query procedure for an `0< ` already, proving that the first `0− 1 pegs in σj are wrong, particularly σj 1 . Now, we obtain black(ρj,` , y)> 0, if and only if the pivot peg had a wrong color in σj,` meaning that there is one correct peg in σj in the first `− 1 places. Thus, we can find the position m of the leftmost correct peg in σj by a binary search as outlined in Algorithm 1. Identifying a Further Component: For the implementation of FINDNEXT (Algorithm 2), we deal with a partial solution vector x that satisfies xi∈ { 0, yi} for all i∈[n] . We call the (indices of the) non-zero components of the partial solution fixed. They indicate the components of the secret code that have already been identified. The (indices of the) zero components are called open. Whenever FINDNEXT makes a guess σ, it requires knowing the number of open components in which the guess coincides with the secret code, i.e., the number black(σ,y,x):=black(σ,y)−black(σ,x). Note that the term black(σ , x) is known by the codebreaker and not greater than black(σ , y) . After the first component of y has been found and fixed in x , there exists a j∈[n] such that black(σj , y , x) = 0. As long as we have open components in x , we can either find a j∈[n− 1 ] with black(σj , y , x)> 0 but black(σj+1 , y , x) = 0 and set r:=j+ 1, or we have black(σn , y , x)> 0 but black(σ1 , y , x) = 0 and set j:=n and r:= 1. Again, we call such an index j an active index. Let j be an active index and Games 2018,9, 2 5 of 12 r its related index. Let c be the color of some component of y that is already identified and fixed in the partial solution x . With `j and `r , we denote the position of color c in σj and σr , respectively. The peg with color c serves as a pivot peg for identifying a correct position m in σj that is not fixed yet. There are two possible modes for the binary search that depend on the fact if m≤`j . The mode is indicated by a Boolean variable leftS and determined by lines 5 to 10 of FINDNEXT. Clearly, m≤`j if `j=n. Otherwise, the codebreaker guesses σj,0 :=c,(σj i)`j−1 i=1,(σj i)n i=`j+1. By the information σj i=σr i+1 we obtain that (σj i)`j−1 i=1≡(σr i)`j i=2 . We further know that every open color has a wrong position in σr. For that reason, black(σj,0,y,x) = 0 implies that m≤`j. Algorithm 2: Routine FINDNEXT input :Code y, partial solution x6=0 and an active index j∈[n] output:Position of a correct open component in σj 1if j=nthen r:=1; 2else r:=j+1; 3Choose a color cof identified peg (a value cof some non-zero component of x); 4Let `jand `rbe the positions with color cin σjand σr, respectively; 5if `j=nthen leftS :=true; 6else 7Guess σj,0 :=c,(σj i)`j−1 i=1,(σj i)n i=`j+1; 8s:=black(σj,0,y,x); 9if s=0then leftS :=true; 10 else leftS :=false; 11 if leftS then 12 a:=1; 13 b:=`j; 14 else 15 a:=`r; 16 b:=n; 17 while b>ado 18 `:=da+b 2e;// position for peg c 19 if leftS then σj,`:=(σj i)`−1 i=1,c,(σr i)`j i=`+1,(σj i)n i=`j+1; 20 else σj,`:=(σr i)`r−1 i=1,(σj i)`−1 i=`r,c,(σr i)n i=`+1; 21 Guess σj,`; 22 s:=black(σj,`,y,x); 23 if s>0then b:=`−1; 24 else a:=`; 25 return b; The binary search for the exact value of m is done in the interval [a , b] , where m is initialized as n and [a,b]as [a,b]:=([1, `j], if leftS, [`r,n], else Games 2018,9, 2 6 of 12 (lines 11 to 16 of FINDNEXT). In order to determine if there is an open correct component on the left side of the current center `of [a,b]in σj, we can define a case dependent permutation: σj,`:=       (σj i)`−1 i=1,c,(σr i)`j i=`+1,(σj i)n i=`j+1,if leftS, (σr i)`r−1 i=1,(σj i)`−1 i=`r,c,(σr i)n i=`+1, else. In the first case, the first `− 1 components of σj,` coincide with those of σj . The remaining components of σj,` cannot coincide with the corresponding components of the secret code if they have not been fixed yet. This is because the ` -th component of σj,` has the already fixed value c , components `+ 1 to `j coincide with the corresponding components of σr , which satisfies black(σr , y , x) = 0, and the remaining components have been checked to be wrong in this case (cf. former definition of leftS in line 5 and line 9, respectively). Thus, there is a correct open component on the left side of ` in σj , if and only if black(σj,` , y , x)6= 0. In the second case, the same holds for similar arguments. Now, if there is a correct open component to the left of ` , we update the binary search interval [a , b] by [a , `− 1 ] . Otherwise, we update [a,b]by [`,b]. The Main Algorithm. The main algorithm is outlined as Algorithm 3. It starts with an empty partial solution and finds the components of the secret code y one-by-one. Herein, the vector v does keep records about the number of open components in which the permutations σ1 , . . . , σn equal y and is, thus, initialized by vi:=black(σi , y) , i∈[n− 1 ] and vn:=n−∑n−1 i=1vi . As mentioned above, the main loop always requires an active index. For that reason, if v=1n in the beginning, we fix one solution peg in σ1 and update x and v , correspondingly. Every call of FINDNEXT in the main loop augments x by a correct solution value. Since one call of FINDNEXT requires at most 1 +dlog2ne guesses, Algorithm 3does not need more than (n− 3 )dlog2ne+5 2n− 1 queries for n≥ 10 (inclusive n− 1 initial guesses, bn 2c+ 1 guesses to find the first correct peg, n− 3 calls of FINDNEXT and 2 final queries) to break the secret code. Algorithm 3: Algorithm for Permutations 1Let ybe the secret code and set x:= (0, 0, . . . , 0); 2Guess the permutations σi,i∈[n−1]; 3Initialize v∈ {0, 1, . . . , n}nby vi:=black(σi,y),i∈[n−1],vn:=n−∑n−1 i=1vi; 4if v=1nthen 5j:=1; 6Find the position mof the correct peg in σ1by at most bn 2c+1 further guesses; 7else 8Call m:=FINDFIRST(y,j)for an active index j∈[n]to find the position mof the correct peg in σjby at most 2dlog2nefurther guesses; 9xm:=σj m; 10 vj:=vj−1; 11 while |{i∈[n]|xi=0}| >2do 12 Use vto choose an active index j∈[n];// (vj>0,vj+1=0) 13 m:=FINDNEXT(y,x,j); 14 xm:=σj m; 15 vj:=vj−1; 16 Make at most two more guesses to find the remaining two unidentified colors; Example 1. We consider the case n =k=8and suppose that the secret code y is 71432856. Games 2018,9, 2 7 of 12 Figure 1(upper panel) shows n possible initial queries. We illustrate the procedure FINDNEXT and further suppose that we have already identified the positions of three colors indicated in the partial solution x: ••••2•5 6. From the n3 values in Figure 1, we see that black(σ3 , y , x) = 1 and black(σ4 , y , x) = 0, so we choose 3 as our active index applying FINDNEXT with the highlighted initial queries, σ3 and σ4 . Choosing the already identified color 2 as a pivot color, FINDNEXT does its binary search to identify the next correct peg as demonstrated in the lower panel of Figure 1. Since the information n3 for query σa is 0 (cf. lines 7–9 of Algorithm 2), all correctly placed but unidentified pegs in σ3 are in the first four places. Thus, we can apply a binary search for the leftmost correct peg in the first four places of query σ3 using the pivot peg. Here, the binary search is done by queries σb and σc and identifies the peg with color 7 (in general, the peg that is left to the leftmost pivot position for which n3 is non-zero). If the response to σa would have been greater than 0, we would have found analogously a new correct peg among the last four places of σ3. σ11 2 345 6 78 σ2812345 6 7 σ3781 2 345 6 σ46781 2 345 σ55 6 781 2 34 σ645 6 781 2 3 σ7345 6 781 2 σ82345 6 781 000 202 321 110 000 000 101 101 queries n1n2n3 σa σb σc 2 7 81 782 1 7 2 81 345 6 345 6 345 6 220 321 321 queries n1n2n3 Figure 1. Upper panel: initial queries σj with associated responses n1=black(σj , y) , coincidences with a partial solution n2=black(σj , x) , and the difference of both n3 . Lower panel: binary search queries to extend the partial solution. The highlighted subsequences correspond to the subsequences of the selected initial queries. 2.2. More Colors Than Positions Now, we consider the variant of Black-Peg Mastermind where k>n and color repetition is forbidden. Let y= (y1, . . . , yn)be the code that must be found. We use the same notations as above. Phase 1. Consider the k permutations σ1 , . . . , σk , where σ1 corresponds to the identity map on [k] and for j∈[k− 1 ] , we obtain σj+1 from σj by a circular shift to the right. We define k codes σ1 , . . . , σk by σj= (σj i)n i=1 , j∈[k] . For example, if k= 5 and n= 3, we have σ1= ( 1, 2, 3 ) , σ2= ( 5, 1, 2 ) , σ3= ( 4, 5, 1 ) , σ4= ( 3, 4, 5 ) and σ5= ( 2, 3, 4 ) . Within those k codes, every color appears exactly once at every position, and, thus, we have k ∑ j=1 black(σj,y) = n, similar to Equation (1). Since k>n, this implies Games 2018,9, 2 8 of 12 Lemma 1. There is a j ∈[k]with black(σj,y) = 0. Phase 2. Having more colors than holes, we can perform our binary search for the next correct position without using a pivot peg. The corresponding simplified version of FINDNEXT is outlined as Algorithm 4. Using that version of FINDNEXT also allows to simplify our main algorithm (Algorithm 3) by adapting lines 2 and 3, and, due to Lemma 1, skipping lines 4–10, as FINDNEXT can be already applied to find the first correct peg. Thus, for the required number of queries to break the secret code, we have: the initial k− 1 guesses, a call of the modified FINDNEXT for all but the last two positions (at most dlog2ne guesses per position) and one or two final guesses. This yields the modified Mastermind Algorithm breaking the secret code in at most (n−2)dlog2ne+k+1 queries. Algorithm 4: Routine FINDNEXT for k>n input :Code y, partial solution x6=0 and an active index j∈[k] output:Position mof a correct open component in σj 1if j=nthen r:=1; 2else r:=j+1; 3a:=1, b:=n; 4while b>ado 5`:=da+b 2e;// mid position of current interval 6Guess σ:=(σr i)`−1 i=1,(σj i)n i=`; 7s:=black(σ,y,x); 8if s>0then a:=`; 9else b:=`−1; 10 return a; 3. Lower Bounds on the Number of Queries In the following, we consider the case that the secret code has no repetition but arbitrary questions are allowed. Note that the lower bounds for that case especially hold true for Black-Peg AB-Mastermind, since the codebreaker will not be able to detect a secret code with less attempts, if the set of allowed queries is restricted to the corresponding subset. Similar to the upper bounds, we prove the respective lower bounds on the necessary number of queries by construction. 3.1. Black-Peg AB-Mastermind, Case k =n In each iteration, the worst case for the code breaker is simulated by allowing the codemaker to replace his secret code with another permutation from the remaining feasible search space. For m∈N , we denote the m -th query of the code breaker with xm and the m -th secret code adaption of the codemaker with ym . The remaining feasible search space Rm consists of all permutations that agree with the first mpairs of queries and answers: R0:=Sn, Rm:={σ∈Sn|black(yj,xj) = black(σ,xj)for all j∈[m]}, for m>0. Now, a simple strategy of the codemaker is to reply every query xm , m∈N , with the smallest possible number bm:=min σ∈Rm−1 black(σ,xm), choosing his new secret code ym∈Rm−1 such that black(ym , xm) = bm . We obtain our lower bound on the necessary number of queries by proving the following Lemma. Lemma 2. It holds that bm≤m for all m <n.