umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Bounds for Static Black-Peg AB Mastermind
Christian-Albrechts Universität Kiel.
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
Christian-Albrechts Universität Kiel.
Christian-Albrechts Universität Kiel.
2017 (Engelska)Ingår i: COCOA 2017: Combinatorial Optimization and Applications, Springer Berlin/Heidelberg, 2017, s. 409-424Konferensbidrag, Publicerat paper (Refereegranskat)
Abstract [en]

Mastermind is a famous two-player game introduced by M. Meirowitz (1970). Its combinatorics has gained increased interest over the last years   for different variants.

In this paper we consider a version known as the Black-Peg AB Game, where one player creates a secret code consisting of c colors on p <= c pegs, where each color is used at most once. The second player tries to guess the secret code with as few questions as possible. For each question he receives the number of correctly placed colors. In the static variant the second player doesn't receive the answers one at a time,  but all at once after asking the last question.  There are several results both for the AB and the static version, but the combination of both versions has not been considered so far. The most prominent case is n:=p=c, where the secret code and all questions are permutations. The main result of this paper is an upper bound of O(n^{1.525}) questions for this setting. With a slight modification of the arguments of Doerr et al. (2016) we also give a lower bound of \Omega(n\log n). Furthermore, we complement the upper bound for p=c  by an optimal (\lceil 4c/3 \rceil -1)-strategy for the special case p=2 and arbitrary c >= 2 and list optimal strategies for six additional pairs (p,c) .

Ort, förlag, år, upplaga, sidor
Springer Berlin/Heidelberg, 2017. s. 409-424
Serie
Lecture Notes in Computer Science ; 10628
Nyckelord [en]
Mastermind, Game Theory, Upper Bound, Game Theory
Nationell ämneskategori
Diskret matematik
Identifikatorer
URN: urn:nbn:se:umu:diva-139844DOI: 10.1007/978-3-319-71147-8_28ISBN: 978-3-319-71146-1 (tryckt)ISBN: 978-3-319-71147-8 (digital)OAI: oai:DiVA.org:umu-139844DiVA, id: diva2:1143852
Konferens
The 11th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2017), Shanghai, China, December 16-18, 2017
Tillgänglig från: 2017-09-22 Skapad: 2017-09-22 Senast uppdaterad: 2019-06-26Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltext

Personposter BETA

Jäger, Gerold

Sök vidare i DiVA

Av författaren/redaktören
Jäger, Gerold
Av organisationen
Institutionen för matematik och matematisk statistik
Diskret matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetricpoäng

doi
isbn
urn-nbn
Totalt: 141 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf