Playing Mastermind with constant-size memory

DOI10.4230/LIPICS.STACS.2012.441zbMATH Open1245.68144arXiv1110.3619OpenAlexW2504769075MaRDI QIDQ2904783FDOQ2904783

Authors: Benjamin Doerr, Carola Winzen 

Publication date: 23 August 2012

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.

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

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

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)

Cited In (12)

• 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
• Title not available (Why is that?)

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)