Mastermind with a Linear Number of Queries

MaRDI QIDQ6353542zbMATH OpenFDO

Authors Anders Martinsson, Pascal Su

Publication date 11 November 2020

Abstract: Since the 60's Mastermind has been studied for the combinatorial and information theoretical interest the game has to offer. Many results have been discovered starting with ErdH{o}s and R'enyi determining the optimal number of queries needed for two colors. For $k$ colors and $n$ positions, Chv'atal found asymptotically optimal bounds when $kle{n}^{1-epsilon}$. Following a sequence of gradual improvements for $kgeqn$ colors, the central open question is to resolve the gap between $Omega(n)$ and $mathcalO(nloglogn)$ 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$.

This page was built for publication: Mastermind with a Linear Number of Queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6353542)