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。