umu.sePublikasjoner
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
An Optimal Strategy for Static Black-Peg Mastermind with Three Pegs
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap. (Foundations of Language Processing)ORCID-id: 0000-0001-7349-7693
2018 (engelsk)Inngår i: SAGT: International Symposium on Algorithmic Game Theory: 11th International Symposium, SAGT 2018, Beijing, China, September 11-14, 2018, Proceedings / [ed] Xiaotie Deng, Springer, 2018, Vol. 11059, s. 261-266Konferansepaper, Publicerat paper (Fagfellevurdert)
Abstract [en]

Mastermind is a famous game played by a codebreaker against a codemaker. We investigate its static (also called non-adaptive) black-peg variant. Given c colors and p pegs, the codemaker has to choose a secret, a p-tuple of c colors, and the codebreaker asks a set of questions all at once. Like the secret, a question is a p-tuple of c colors. The codemaker then tells the codebreaker how many pegs in each question are correct in position and color. Then the codebreaker has one final question to find the secret. His aim is to use as few of questions as possible. Our main result is an optimal strategy for the codebreaker for p=3 pegs and an arbitrary number c of colors using ⌊3c/2⌋+1questions.

A reformulation of our result is that the metric dimension of ℤn×ℤn×ℤnis equal to ⌊3n/2⌋.

sted, utgiver, år, opplag, sider
Springer, 2018. Vol. 11059, s. 261-266
Serie
Lecture Notes in Computer Science
Emneord [en]
Mastermind, winning strategy, optimality
HSV kategori
Identifikatorer
URN: urn:nbn:se:umu:diva-151844DOI: 10.1007/978-3-319-99660-8_25OAI: oai:DiVA.org:umu-151844DiVA, id: diva2:1248094
Konferanse
11th International Symposium on Algorithmic Game Theory, Beijing, China, September 11-14, 2018
Tilgjengelig fra: 2018-09-13 Laget: 2018-09-13 Sist oppdatert: 2019-06-19bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

Forlagets fulltekst

Personposter BETA

Jäger, Gerold

Søk i DiVA

Av forfatter/redaktør
Jäger, GeroldDrewes, Frank
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric

doi
urn-nbn
Totalt: 314 treff
RefereraExporteraLink to record
Permanent link

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