arXiv Analytics

Sign in

arXiv:2003.11538 [cs.DS]AbstractReferencesReviewsResources

The Exact Query Complexity of Yes-No Permutation Mastermind

Moura El Ouali, Volkmar Sauerland

Published 2020-03-25Version 1

Mastermind is famous two-players game. The ?rst 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-de?ned 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)+\dots+\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.

Comments: 12 pages, 2 figures, submitted to GAMES
Categories: cs.DS, math.CO
Subjects: 91A46
Related articles:
arXiv:1303.5862 [cs.DS] (Published 2013-03-23, updated 2013-03-26)
Improved Approximation Algorithm for the Number of Queries Necessary to Identify a Permutation
arXiv:1611.05907 [cs.DS] (Published 2016-11-17)
On the Query Complexity of Black-Peg AB-Mastermind
arXiv:1207.0773 [cs.DS] (Published 2012-07-03, updated 2013-01-17)
Playing Mastermind with Many Colors