Publication:3177818

DOI10.1145/2987372zbMath1425.91078arXiv1207.0773OpenAlexW1923754076MaRDI QIDQ3177818

Henning Thomas, Reto Spöhel, Benjamin Doerr, Carola Doerr, Carola Winzen

Publication date: 2 August 2018

Published in: Journal of the ACM, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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 loglog n)$ bound holds for up to $n^2 loglog 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.

Full work available at URL: https://arxiv.org/abs/1207.0773

zbMATH Keywords

randomized algorithmscombinatorial gamesquery complexityMastermind

Mathematics Subject Classification ID

Randomized algorithms (68W20) Combinatorial games (91A46)

Related Items (17)

On the query complexity of black-peg AB-mastermind ⋮ Playing Several Variants of Mastermind with Constant-Size Memory is not Harder than with Unbounded Memory ⋮ Query complexity of mastermind variants ⋮ An Optimal Strategy for Static Black-Peg Mastermind with Two Pegs ⋮ Optimal schemes for combinatorial query problems with integer feedback ⋮ Unnamed Item ⋮ The exact query complexity of yes-no permutation mastermind ⋮ Bounds for the static permutation mastermind game ⋮ The query complexity of a permutation-based variant of mastermind ⋮ Playing Mastermind with Wordle-like Feedback ⋮ Playing Guess Who with your kids: code-word strategy against adversaries ⋮ Mastermind with a linear number of queries ⋮ Optimal strategies for the static black-peg AB game with two and three pegs ⋮ Solving static permutation mastermind using \(O(n \log n)\) queries ⋮ The Query Complexity of Finding a Hidden Permutation ⋮ The worst case number of questions in generalized AB game with and without white-peg answers ⋮ Bounding memory for Mastermind might not make it harder

This page was built for publication: Playing Mastermind With Many Colors