Umeå University's logo

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
Optimal strategies for the static black-peg AB game with two and three pegs
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
Umeå University, Faculty of Science and Technology, Department of Computing Science. (Foundations of Language Processing)ORCID iD: 0000-0001-7349-7693
2023 (English)In: Discrete Mathematics, Algorithms and Applications (DMAA), ISSN 1793-8309, E-ISSN 1793-8317Article in journal (Refereed) Epub ahead of print
Abstract [en]

The AB Game is a game similar to the popular game Mastermind. We study a version of this game called Static Black-Peg AB Game. It is played by two players, the codemaker and the codebreaker. The codemaker creates a so-called secret by placing a color from a set of c colors on each of p ≤ c pegs, subject to the condition that every color is used at most once. The codebreaker tries to determine the secret by asking questions, where all questions are given at once and each question is a possible secret. As an answer the codemaker reveals the number of correctly placed colors for each of the questions. After that, the codebreaker only has one more try to determine the secret and thus to win the game. 

For given p and c, our goal is to find the smallest number k of questions the codebreaker needs to win, regardless of the secret, and the corresponding list of questions, called a (k + 1)-strategy. We present a (⌈4c/3⌉ − 1)-strategy for p = 2 for all c ≥ 2, and a ⌊(3c − 1)/2⌋-strategy for p = 3 for all c ≥ 4 and show the optimality of both strategies, i.e., we prove that no (k + 1)-strategy for a smaller k exists. 

Place, publisher, year, edition, pages
World Scientific, 2023.
Keywords [en]
Game theory, mastermind, AB game, optimal strategy
National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-210346DOI: 10.1142/s1793830923500490ISI: 001034748600002Scopus ID: 2-s2.0-85165934499OAI: oai:DiVA.org:umu-210346DiVA, id: diva2:1771561
Funder
The Kempe Foundations, JCK-2022.1Available from: 2023-06-20 Created: 2023-06-20 Last updated: 2023-09-08

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Jäger, GeroldDrewes, Frank

Search in DiVA

By author/editor
Jäger, GeroldDrewes, Frank
By organisation
Department of Mathematics and Mathematical StatisticsDepartment of Computing Science
In the same journal
Discrete Mathematics, Algorithms and Applications (DMAA)
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 107 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