Playing Mastermind With Many Colors
Playing Mastermind With Many Colors
复制标题
玩多种颜色的策划者
DOI：
10.1145/2987372
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Carola Doerr
中科院分区：
文献类型：
--
作者：
Benjamin Doerr;Reto Spöhel;H. Thomas;Carola Doerr
我们分析了经典猜谜游戏Mastermind的一般版本，它有n个位置和k种颜色。由于k≤n1−ε， ε >为常数的情况已被很好地理解，因此我们将重点放在更大数量的颜色上。对于最突出的情况k = n，我们的结果表明，密码破译者可以用O（nlog log n）次猜测找到密码。当只使用黑色回答钉时，此界限也有效。它改进了最初由Chvátal证明的O（nlog n）界。我们还证明，如果同时使用黑白两种答案，那么O（nlog log n）界最多适用于n2log log n种颜色。这些边界几乎是紧的，正如已知的Ω(n)的下界所示。与k≤n1−ε不同，简单地随机猜测直到密码确定是不够的。事实上，我们证明了最优的非自适应策略（确定性或随机化）需要Θ（nlog n）次猜测。
We analyze the general version of the classic guessing game Mastermind with n positions and k colors. Since the case k ≤ n1 − ε, ε > 0 a constant, is well understood, we concentrate on larger numbers of colors. For the most prominent case k = n, our results imply that Codebreaker can find the secret code with O(nlog log n) guesses. This bound is valid also when only black answer pegs are used. It improves the O(nlog n) bound first proven by Chvátal. We also show that if both black and white answer pegs are used, then the O(nlog log n) bound holds for up to n2log log n colors. These bounds are almost tight, as the known lower bound of Ω(n) shows. Unlike for k ≤ n1 − ε, simply guessing at random until the secret code is determined is not sufficient. In fact, we show that an optimal nonadaptive strategy (deterministic or randomized) needs Θ(nlog n) guesses.