# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Playing Mastermind with Many Colors

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

arXiv:1207.0773.pdf

(Preprint), 2MB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Doerr, B., Doerr, C., Spöhel, R., & Thomas, H. (2012). Playing Mastermind with Many Colors. Retrieved from http://arxiv.org/abs/1207.0773.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0015-886A-8

##### Abstract

We analyze the general version of the classic guessing game Mastermind with
$n$ positions and $k$ colors. Since the case $k \le n^{1-\varepsilon}$,
$\varepsilon>0$ a constant, is well understood, we concentrate on larger
numbers of colors. For the most prominent case $k = n$, our results imply that
Codebreaker can find the secret code with $O(n \log \log n)$ guesses. This
bound is valid also when only black answer-pegs are used. It improves the $O(n
\log n)$ bound first proven by Chv\'atal (Combinatorica 3 (1983), 325--329). We
also show that if both black and white answer-pegs are used, then the $O(n
\log\log n)$ bound holds for up to $n^2 \log\log n$ colors. These bounds are
almost tight as the known lower bound of $\Omega(n)$ shows. Unlike for $k \le
n^{1-\varepsilon}$, simply guessing at random until the secret code is
determined is not sufficient. In fact, we show that an optimal non-adaptive
strategy (deterministic or randomized) needs $\Theta(n \log n)$ guesses.