On the query complexity of black-peg AB-mastermind (Q1651863)

Summary: Mastermind is a two-player zero-sum game of imperfect information. Starting with \textit{P. Erdős} and \textit{C. Rényi} [``On two problems in information theory'', Publ. Math. Inst. Hung. Acad. Sci. 8, 229--242 (1963)], its combinatorics have been studied to date by several authors, e.g. by \textit{D. E. Knuth} [J. Recreat. Math. 9, 1--6 (1977; Zbl 0358.90075)], \textit{V. Chvátal} [Combinatorica 3, 325--329 (1983; Zbl 0717.05002)], \textit{M. T. Goodrich} [Inf. Process. Lett. 109, No. 13, 675--678 (2009; Zbl 1197.91063)]. 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, \textit{B. Doerr} et al. [``Playing mastermind with many colors'', J. ACM 63, Paper No. 42, 23 p. (2016; \url{doi:10.1145/2987372})] 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 \geq 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) \lceil \log_2 n \rceil + \frac{5}{2} n - 1\) queries. This result improves the result of \textit{K.-I Ko} and \textit{S.-C. Teng} [J. Algorithms 7, 449--462 (1986; Zbl 0631.68059)] by almost a factor of 2. For the case \(k > n\), we prove an upper bound of \((n - 2) \lceil \log_2 n \rceil + 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 \textit{A. Berger} et al. [Discrete Math. 341, No. 3, 665--671 (2018; Zbl 1410.91125)]. We then generalize this lower bound to \(k\) queries for the case \(k \geq n\).