umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Playing several variants of mastermind with constant-size memory is not harder than with unbounded memory
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
Institute of Informatics, University of Warsaw, Poland.
2015 (English)In: Combinatorial Algorithms: 25th International Workshop, IWOCA 2014, Duluth, MN, USA, October 15-17, 2014, Revised Selected Papers / [ed] Kratochvíl Jan, Mirka Miller, Dalibor Froncek, Springer Berlin/Heidelberg, 2015, 188-199 p.Conference paper, Published paper (Refereed)
Abstract [en]

We investigate a version of the Mastermind game, where the codebreaker may only store a constant number of questions and answers, called Constant-Size Memory Mastermind, which was recently introduced by Doerr and Winzen. We concentrate on the most difficult case, where the codebreaker may store only one question and one answer, called Size-One Memory Mastermind. We consider two variants of the game: the original one, where the answer is coded with white and black pegs, and the simplified one, where only black pegs are used in the answer. We show that for two pegs and an arbitrary number of colors, the number of questions needed by the codebreaker in an optimal strategy in the worst case for these games is equal to the corresponding number of questions in the games without a memory restriction. In other words, for these cases restricting the memory size does not make the game harder for the codebreaker. This is a continuation of a result of Doerr and Winzen, who showed that this holds asymptotically for a fixed number of colors and an arbitrary number of pegs. Furthermore, by computer search we determine additional pairs (p, c), where again the numbers of questions in an optimal strategy in the worst case for Size-One Memory Mastermind and original Mastermind are equal.

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2015. 188-199 p.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 8986
Keyword [en]
Game theory, Logic game, Mastermind, Space complexity
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-100113DOI: 10.1007/978-3-319-19315-1_17ISI: 000365044500017ISBN: 978-3-319-19314-4 (print)ISBN: 978-3-319-19315-1 (print)OAI: oai:DiVA.org:umu-100113DiVA: diva2:790217
Conference
25th International Workshop, IWOCA 2014, Duluth, MN, USA, October 15-17, 2014
Available from: 2015-02-23 Created: 2015-02-23 Last updated: 2015-12-11Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Jäger, Gerold
By organisation
Department of Mathematics and Mathematical Statistics
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 101 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf