Open access
Date
2024-03Type
- Journal Article
ETH Bibliography
yes
Altmetrics
Abstract
Since the 1960s Mastermind has been studied for the combinatorial and information-theoretical interest the game has to offer. Many results have been discovered starting with Erdos and Renyi determining the optimal number of queries needed for two colours. For $k$ colours and $n$ positions, Chvatal found asymptotically optimal bounds when $k \le n<^>{1-\varepsilon }$. Following a sequence of gradual improvements for $k\geq n$ colours, the central open question is to resolve the gap between $\Omega (n)$ and $\mathcal{O}(n\log \log n)$ for $k=n$. In this paper, we resolve this gap by presenting the first algorithm for solving $k=n$ Mastermind with a linear number of queries. As a consequence, we are able to determine the query complexity of Mastermind for any parameters $k$ and $n$. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000647235Publication status
publishedExternal links
Journal / series
Combinatorics, Probability & ComputingVolume
Pages / Article No.
Publisher
Cambridge University PressSubject
Mastermind; Coin-weighing; Information theory; Combinatorial games; Query complexityFunding
200021_156011 - Hierarchical carbon-fiber composites with tailored interphase obtained via electrophoretic deposition of magnetized and funtionalized carbon nanotubes (SNF)
169242 - Saturation Games and Robust Random Structures (SNF)
More
Show all metadata
ETH Bibliography
yes
Altmetrics