We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
The Exact Query Complexity of Yes-No Permutation Mastermind.
- Authors
El Ouali, Mourad; Sauerland, Volkmar
- Abstract
Mastermind is famous two-player 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, the codemaker's duty is to help the 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 the codemaker only indicates if a query contains any correct position at all. For this Mastermind version with n positions and k ≥ n colors and ℓ : = k + 1 − n , we prove a lower bound of ∑ j = ℓ k log 2 j 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 Θ (n log n) queries.
- Subjects
DUTY; NONCOOPERATIVE games (Mathematics)
- Publication
Games (20734336), 2020, Vol 11, Issue 2, p19
- ISSN
2073-4336
- Publication type
Article
- DOI
10.3390/g11020019