Economics at your fingertips  

On the Query Complexity of Black-Peg AB-Mastermind

Mourad El Ouali (), Christian Glazik (), Volkmar Sauerland () and Anand Srivastav ()
Additional contact information
Mourad El Ouali: Polydisciplinary Faculty Ouarzazate, University Ibn Zohr, Agadir 80000, Morocco
Christian Glazik: Department of Computer Science, Kiel University, 24118 Kiel, Germany
Volkmar Sauerland: Department of Computer Science, Kiel University, 24118 Kiel, Germany
Anand Srivastav: Department of Computer Science, Kiel University, 24118 Kiel, Germany

Games, 2018, vol. 9, issue 1, 1-12

Abstract: Mastermind is a two players zero sum game of imperfect information. Starting with Erdős and Rényi (1963), its combinatorics have been studied to date by several authors, e.g., Knuth (1977), Chvátal (1983), Goodrich (2009). The first player, called “codemaker”, chooses a secret code and the second player, called “codebreaker”, tries to break the secret code by making as few guesses as possible, exploiting information that is given by the codemaker after each guess. For variants that allow color repetition, Doerr et al. (2016) showed optimal results. In this paper, we consider the so called Black-Peg variant of Mastermind, where the only information concerning a guess is the number of positions in which the guess coincides with the secret code. More precisely, we deal with a special version of the Black-Peg game with n holes and k ≥ n colors where no repetition of colors is allowed. We present upper and lower bounds on the number of guesses necessary to break the secret code. For the case k = n , the secret code can be algorithmically identified within less than ( n − 3 ) ⌈ log 2 n ⌉ + 5 2 n − 1 queries. This result improves the result of Ker-I Ko and Shia-Chung Teng (1985) by almost a factor of 2. For the case k > n , we prove an upper bound of ( n − 2 ) ⌈ log 2 n ⌉ + k + 1 . Furthermore, we prove a new lower bound of n for the case k = n , which improves the recent n − log log ( n ) bound of Berger et al. (2016). We then generalize this lower bound to k queries for the case k ≥ n .

Keywords: Mastermind; combinatorial problem; permutation; algorithm; complexity (search for similar items in EconPapers)
JEL-codes: C C7 C70 C71 C72 C73 (search for similar items in EconPapers)
Date: 2018
References: View complete reference list from CitEc
Citations Track citations by RSS feed

Downloads: (external link) (application/pdf) (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:

Access Statistics for this article

Games is currently edited by Prof. Dr. Ulrich Berger

More articles in Games from MDPI, Open Access Journal
Bibliographic data for series maintained by XML Conversion Team ().

Page updated 2018-10-02
Handle: RePEc:gam:jgames:v:9:y:2018:i:1:p:2-:d:125079