Playing Mastermind with constant-size memory

DOI10.4230/LIPICS.STACS.2012.441MaRDI QIDQ2904783zbMATH OpenOpenAlexFDO

Authors Benjamin Doerr, Carola Winzen

Publication date 23 August 2012

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

zbMATH Keywords

query complexityblack-box complexityMastermindmemory-restricted algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) 2-person games (91A05)

Abstract: We analyze the classic board game of Mastermind with $n$ holes and a constant number of colors. A result of Chv'atal (Combinatorica 3 (1983), 325-329) states that the codebreaker can find the secret code with $Theta(n/logn)$ questions. We show that this bound remains valid if the codebreaker may only store a constant number of guesses and answers. In addition to an intrinsic interest in this question, our result also disproves a conjecture of Droste, Jansen, and Wegener (Theory of Computing Systems 39 (2006), 525-544) on the memory-restricted black-box complexity of the OneMax function class.

Recommendations

• Playing mastermind with constant-size memory
• Bounding memory for Mastermind might not make it harder
• Playing several variants of Mastermind with constant-size memory is not harder than with unbounded memory

Cited in

(12)

• scientific article; zbMATH DE number 2148779 (Why is no real title available?)
• CONCUR 2005 – Concurrency Theory
• Playing several variants of Mastermind with constant-size memory is not harder than with unbounded memory
• Bounding memory for Mastermind might not make it harder
• On the query complexity of black-peg AB-mastermind
• Toward a unifying framework for evolutionary processes
• Playing mastermind with constant-size memory
• Memory-restricted black-box complexity of OneMax
• The worst case number of questions in generalized AB game with and without white-peg answers
• A framework for co-optimization algorithm performance and its application to worst-case optimization
• Reducing the arity in unbiased black-box complexity
• Unbiasedness of estimation-of-distribution algorithms

This page was built for publication: Playing Mastermind with constant-size memory

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