The Exact Query Complexity of Yes-No Permutation Mastermind

Abstract

Mastermind is famous two-players game. The first player (codemaker) chooses a secret code which the second player (codebreaker) is supposed to crack within a minimum number of code guesses (queries). Therefore, codemaker's duty is to help codebreaker by providing a well-defined error measure between the secret code and the guessed code after each query. We consider a variant, called Yes-No AB-Mastermind, where both secret code and queries must be repetition-free and the provided information by codemaker only indicates if a query contains any correct position at all. For this Mastermind version with n positions and $k\le n$ colors we prove a lower bound of ${\log }_2(k+1-n)+{\log }_2(k+2-n)+\cdots +{\log }_2(k)$ and an upper bound of $n{\log }_2(n)+k$ on the number of queries necessary to break the secret code. For the important case $k=n$, where both secret code and queries represent permutations, our results imply an exact asymptotic complexity of $\Theta (n{\log }_2(n))$ queries.

12 pages, 2 figures, submitted to GAMES