nach oben

Theory of Computing Systems

Erschienen in:

01.11.2014

Playing Mastermind with Constant-Size Memory

verfasst von: Benjamin Doerr, Carola Winzen

Erschienen in: Theory of Computing Systems | Ausgabe 4/2014

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We analyze the classic board game of Mastermind with n holes and a constant number of colors. The classic result of Chvátal (Combinatorica 3:325–329, 1983) states that the codebreaker can find the secret code with Θ(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 Comput. Syst. 39:525–544, 2006) on the memory-restricted black-box complexity of the OneMax function class.

Vorheriger Artikel -Approximation for Graphic TSP

Nächster Artikel The Complexity of Compressed Membership Problems for Finite Automata

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

That is, we have \(\operatorname{tn}(x)=\ell+1\), ∀i≤ℓ:x _i=z _i, and \(\exists c \in \mathcal {C}\backslash \{x_{\ell}\} \forall i\geq \operatorname{tn}(x): x_{i}=c\).

Anil, G., Wiegand, R.P.: Black-box search by elimination of fitness functions. In: Proc. of Foundations of Genetic Algorithms (FOGA’09), pp. 67–78. ACM, New York (2009)

Chen, Z., Cunha, C., Homer, S.: Finding a hidden code by asking questions. In: Proc. of the Second Annual International Conference on Computing and Combinatorics (COCOON’96). Lecture Notes in Computer Science, vol. 1090, pp. 50–55. Springer, Berlin (1996)

Vasek, C.: Mastermind. Combinatorica 3, 325–329 (1983) MathSciNetCrossRef

Droste, S., Jansen, T., Wegener, I.: Upper and lower bounds for randomized search heuristics in black-box optimization. Theory Comput. Syst. 39, 525–544 (2006) MathSciNetCrossRefMATH

Doerr, B., Winzen, C.: Memory-restricted black-box complexity of OneMax. Inf. Process. Lett. 112, 32–34 (2012) MathSciNetCrossRefMATH

Doerr, B., Winzen, C.: Playing Mastermind with constant-size memory. In: Proc. of the Symposium on Theoretical Aspects of Computer Science (STACS’12), LIPIcs, vol. 14, pp. 441–452 (2012). Schloss Dagstuhl—Leibniz-Zentrum fuer Informatik

Erdős, P., Rényi, A.: On two problems of information theory. Magy. Tud. Akad. Mat. Kut. Intéz. Közl. 8, 229–243 (1963)

Goodrich, M.T.: On the algorithmic complexity of the mastermind game with black-peg results. Inf. Process. Lett. 109, 675–678 (2009) MathSciNetCrossRefMATH

Jäger, G., Peczarski, M.: The number of pessimistic guesses in generalized black-peg Mastermind. Inf. Process. Lett. 111, 933–940 (2011) CrossRefMATH

10.

Knuth, D.E.: The computer as a master mind. J. Recreat. Math. 9, 1–5 (1977) MathSciNetMATH

11.

Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995) CrossRefMATH

12.

Stuckman, J., Zhang, G.-Q.: Mastermind is NP-complete. INFOCOMP J. Comput. Sci. 5, 25–28 (2006)

13.

Wegener, I.: Simulated annealing beats metropolis in combinatorial optimization. In: Proc. of the 32nd International Colloquium on Automata, Languages and Programming (ICALP’05). Lecture Notes in Computer Science, vol. 3580, pp. 589–601. Springer, Berlin (2005) CrossRef

Titel: Playing Mastermind with Constant-Size Memory
verfasst von: Benjamin Doerr
Carola Winzen
Publikationsdatum: 01.11.2014
Verlag: Springer US
Erschienen in: Theory of Computing Systems / Ausgabe 4/2014
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-012-9438-8

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 4/2014

Preface of STACS 2012 Special Issue

-Approximation for Graphic TSP

Linear-Space Data Structures for Range Mode Query in Arrays

On the Separation Question for Tree Languages

On First-Order Logic and CPDA Graphs

Efficient Algorithms for Highly Compressed Data: The Word Problem in Generalized Higman Groups Is in P

Premium Partner