Playing Mastermind with many colors

DOI10.1145/2987372zbMATH Open1425.91078arXiv1207.0773OpenAlexW1923754076MaRDI QIDQ3177818FDOQ3177818

Authors: Benjamin Doerr, Carola Doerr, Reto Spöhel, Henning Thomas, 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 $kle{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(nloglogn)$ guesses. This bound is valid also when only black answer-pegs are used. It improves the $O(nlogn)$ 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(nloglogn)$ bound holds for up to $n^{2}loglogn$ colors. These bounds are almost tight as the known lower bound of $Omega(n)$ shows. Unlike for $kle{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(nlogn)$ guesses.

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

Recommendations

• Playing Mastermind with many colors
• On the query complexity of black-peg AB-mastermind
• The number of pessimistic guesses in generalized black-peg mastermind
• An optimal strategy for static black-peg Mastermind with two pegs
• Playing mastermind with constant-size memory

zbMATH Keywords

randomized algorithmsquery complexitycombinatorial gamesMastermind

Mathematics Subject Classification ID

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

Cited In (22)

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

This page was built for publication: Playing Mastermind with many colors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3177818)