Anzeige
Erschienen in:
2018 | OriginalPaper | Buchkapitel
An Optimal Strategy for Static Black-Peg Mastermind with Three Pegs
verfasst von : Gerold Jäger, Frank Drewes
Erschienen in: Algorithmic Game Theory
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
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 \( \lfloor 3c/2 \rfloor +1\) questions.
A reformulation of our result is that the metric dimension of \( \mathbb {Z}_n \times \mathbb {Z}_n \times \mathbb {Z}_n\) is equal to \( \lfloor 3n/2 \rfloor \).