Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2012.441
URN: urn:nbn:de:0030-drops-34112
URL: https://drops.dagstuhl.de/opus/volltexte/2012/3411/
Doerr, Benjamin ; Winzen, Carola
Playing Mastermind With Constant-Size Memory
| pdf-format: |
|
Abstract
We analyze the classic board game of Mastermind with n holes and aconstant number of colors. The classic result of Chvatal (Combinatorica 3 (1983), 325-329) states that the codebreaker can find the secret code with Theta(n / log n) 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.
BibTeX - Entry
@InProceedings{doerr_et_al:LIPIcs:2012:3411,
author = {Benjamin Doerr and Carola Winzen},
title = {{Playing Mastermind With Constant-Size Memory}},
booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
pages = {441--452},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-35-4},
ISSN = {1868-8969},
year = {2012},
volume = {14},
editor = {Christoph D{\"u}rr and Thomas Wilke},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3411},
URN = {urn:nbn:de:0030-drops-34112},
doi = {10.4230/LIPIcs.STACS.2012.441},
annote = {Keywords: Algorithms, Mastermind, black-box complexity, memory-restricted algorithms, query complexity}
}
| Keywords: | Algorithms, Mastermind, black-box complexity, memory-restricted algorithms, query complexity | |
| Seminar: | 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012) | |
| Issue date: | 2012 | |
| Date of publication: | 24.02.2012 |
