2012/07/03 by Doerr, Benjamin, Doerr, Carola, Spöhel, Reto +1
#Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1207.0773
We analyze the general version of the classic guessing game Mastermind with n positions and k colors. Since the case k ≤ n1-ε, ε>0 a constant, is well understood, we concentrate on larger numbers of colors. For the most prominent case k = n, our results imply that Codebreaker can find the secret code with O(n log log n) guesses. This bound is valid also when only black answer-pegs are used. It improves the O(n log n) bound first proven by Chvátal (Combinatorica 3 (1983), 325--329). We also show that if both black and white answer-pegs are used, then the O(n loglog n) bound holds for up to n2 loglog n colors. These bounds are almost tight as the known lower bound of Ω(n) shows. Unlike for k ≤ n1-ε, simply guessing at random until the secret code is determined is not sufficient. In fact, we show that an optimal non-adaptive strategy (deterministic or randomized) needs Θ(n log n) guesses.