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 Erd\H{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 $k \le n^{1-\epsilon}$. Following a sequence of gradual improvements for $k \geq n$ colors, 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$.
翻译：60 的 Mastermind 已经为该游戏提供的组合和信息理论兴趣进行了研究。 从 Erd\ H{o}s 和 R\'enyi 开始, 已经发现了许多结果, 确定两种颜色所需的最佳查询次数。 对于 $k$ 颜色和 $n$ 位置, Chv\'atal 在 $k\ le n ⁇ 1-\\ epsilon}$k\ geq n$ 的逐渐改进之后, 发现非同步的最佳界限。 在对 $ k\ geq n$ 颜色进行一系列的逐步改进之后, 中心未决问题是解决 $\ Omega (n) 和$\ mathcal{O} (n\log\ log n) 美元与 $k= n$. 美元之间的差额。 在本文中, 我们通过提出第一个计算 $k=n mastermind 和 线性查询次数的算法来解决这一差距。 因此, 我们能够确定万 的查询复杂度是 $ 和 $ $ 。
相关内容
微信扫码咨询专知VIP会员