The Exact Query Complexity of Yes-No Permutation Mastermind

Mourad El Ouali and Volkmar Sauerland
Additional contact information
Mourad El Ouali: Polydisciplinary Faculty Ouarzazate, University Ibn Zohr, Agadir 80000, Morocco
Volkmar Sauerland: Department of Mathematics, Kiel University, 24118 Kiel, Germany

Games, 2020, vol. 11, issue 2, 1-11

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.

Keywords: Mastermind; permutation; query complexity (search for similar items in EconPapers)
JEL-codes: C C7 C70 C71 C72 C73 (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2073-4336/11/2/19/pdf (application/pdf)
https://www.mdpi.com/2073-4336/11/2/19/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jgames:v:11:y:2020:i:2:p:19-:d:344780

Access Statistics for this article

Games is currently edited by Ms. Susie Huang

More articles in Games from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().