Mastermind

Mastermind 是一款简单的双人破译密码棋盘游戏，由以色列邮政局长和电信专家 Mordecai Meirowitz 于 1970 年发明。它可能受到了 moo 的启发，moo 是 J. M. Grochow 于 1960 年代后期在麻省理工学院开发的一个程序。

在游戏中，一名玩家是密码制定者，另一名玩家是密码破译者。密码制定者秘密选择一个由四个颜色组成的有序序列 ，每个颜色从六种可能的颜色集中选择，允许重复。然后，密码破译者尝试通过重复提出颜色序列 来猜测密码。每次猜测后，密码制定者会告诉密码破译者两个数字 ：正确颜色且位置也正确的数量 () 和颜色正确但位置不正确的数量 ()。例如，如果密码是 (1,2,3,3)，密码破译者的猜测是 (3,2,4,3)，那么密码制定者的回应将是 (2,1)，因为密码破译者猜对了 2 和第二个 3，位置也正确，同时猜对了第一个 3，但位置不正确。

密码破译者继续猜测，直到他正确猜出密码，或者直到他达到最大允许猜测次数而没有正确识别出秘密密码。

有趣的是， 可以计算为

其中 是颜色 在密码中出现的次数， 是它在猜测中出现的次数。

Knuth (1976-77) 表明，密码破译者总是可以在五步或更少的步数内成功 (即，在四次猜测后知道密码)。他的技术使用了一种贪婪策略，该策略最大限度地减少了每一步剩余可能性的数量，并且平均需要 4.478 次猜测，假设代码选择的可能性均等。Irving (1978-79) 随后发现了一种平均长度稍小的策略。Koyama 和 Lai (1993) 描述了一种使平均猜测次数最小化的策略，平均需要 4.340 次猜测，尽管在最坏的情况下可能需要多达六次。Koyama 和 Lai (1993) 描述的稍作修改的策略将平均值增加到 4.341，但将所需的最大猜测次数减少到五次。

“静态” 问题，即在游戏开始时一次性找到密码破译者可以进行的最少猜测次数，而无需等待答案，然后在收到答案后，在下一次“猜测”中完全确定密码 (Chvatal 1983)，可以用六次初始猜测来解决 (Greenwell 1999-2000)。一种特定的组合，允许密码破译者在六次猜测后知道密码 (因此需要第七次来揭示他对解决方案的了解) 是 (1, 2, 2, 1), (2, 3, 5, 4), (3, 3, 1, 1), (4, 5, 2, 4), (5, 6, 5, 6), (6, 6, 4, 3)。目前尚不清楚这个数字是否可以减少到五次 (穷举检查将需要 次计算)，尽管人们认为不能。

Swaszek (1999-2000) 分析了不需要复杂的记录或使用计算机的实用策略。从剩余的候选代码序列集中随机猜测可以得出令人惊讶的短平均游戏长度 4.638，而将每次猜测解释为一个数字并使用与已知信息一致的下一个更高的数字，则游戏的平均长度为 4.758。