猜數字（又稱 Bulls and Cows）是一種源自20世紀中期英國的密碼破譯類益智游戲，其現代數字化衍生版本通過界面設計、難度分級和機制融合（如數獨、掃雷）擴展了傳統玩法，形成涵蓋邏輯訓練、瞬時記憶和策略拓展的多樣化產品體系。游戲通常由兩人或多個人參與，也可一人與電腦對戰，旨在通過猜測對方隱藏的數字序列，逐步逼近正確答案。
游戲規則
猜數字游戲的標準規則是由兩人參與，其中一人為出題人，另一人為猜謎人。出題人預先選定一個無重復數字的四位數，而不讓猜謎人知曉。猜謎人則開始猜測數字，每次猜測后，出題人會根據猜測數字提供一組“幾A幾B”的反饋，其中“A”代表位置正確的數字數量，“B”代表數字正確但位置錯誤的數量。例如，若正確答案為5234，而猜謎人猜測5346，則出題人的反饋應為1A2B，表明有一個5的位置正確，而3和4這兩個數字雖然正確，但位置不對應。
標準的猜數字游戲由10個數碼（0-9）和4個數位組成。可以通過變化數碼或數位來豐富游戲，例如使用9個數碼玩4個數位的游戲。
當猜謎人收到“A-B”反饋后，可以根據反饋調整自己的猜測，直至猜中全部四個數字（即4A0B）為止。游戲中通常設定了一定的猜測次數上限，根據計算機模擬，采用嚴謹的猜測策略，任何數字都可以在不超過七次的嘗試中被猜中。需要注意的是，有時即使已經確定了數字，仍可能需要額外的一次猜測才能達到4A0B的結果。
變體規則
猜數字游戲的一種變體允許重復的數碼。這種規則的游戲被稱為 Mastermind。在這種規則下，如果猜測數字或正確答案中有重復的數字，重復的數字每個僅能計數一次，且按照最優原則判斷。例如，當正確答案為5543，而猜謎人猜測5255時，根據最優原則和每個數字僅能計數一次的規定，反饋應為1A1B，因為第一個5的位置正確，記為1A，而猜測數字中的第三個5或第四個5與答案中的第二個5匹配，記為1B。
解法
猜數字游戲的解決方法通常有兩種目標：一種是保證在限定次數內獲勝，另一種則是盡可能減少猜測次數。前者追求的是最差情況下的最少猜測次數，后者則關注平均情況下的最少猜測次數。然而，對于特定的數字和位數組合，這兩種目標可能會有所沖突。例如，對于4個數位、6個數碼的Mastermind游戲，平均猜測次數最少的策略平均需要4.340次，但在最差情況下需要6次猜測；如果限制猜測次數至5次，則平均猜測次數最少的策略平均需要4.341次。
解法最少需要7次猜測，平均次數最少的解法由田中哲朗于1996年提出，平均次數為5.213次。系統化的猜測策略可分為三種類型：簡單策略、啟發式策略和最優策略。這三種策略均適用于不同的游戲規則變體。以下以標準規則（10個數碼，4個數位，不含重復數字）為例，介紹這幾類策略。
簡單策略
簡單策略是一種直截了當的方法，每次猜測都選擇可能答案中的最小值。例如，首次猜測1234，如果得到2A0B的反饋，則下次猜測可選擇1256、1257、5236等可能的答案，其中1256是所有可能答案中最小的數字。簡單策略的優點是速度非常快，缺點是所需猜測次數很多。在標準規則下，簡單策略最多需要9次猜測，平均需要5.560次。
啟發式策略
啟發式策略是猜數字游戲中最常見的解法。它的基本流程包括：
1. 首次猜測1234，獲取初始反饋（xAyB）。
2. 從所有數字中，根據反饋篩選出所有可能的答案集合，稱為“可能集”。
3. 對于所有數字（而不僅限于篩選出來的可能集），評估其優劣并給予分數，然后選擇得分最高者進行猜測。如果多個數字得分相等，則優先選擇可能集中的數字。
4. 重復步驟2-3，直到猜中4A0B為止。
啟發式策略的關鍵是如何評估數字的好壞程度。常見的評價指標包括：
- 最壞情況指標（Knuth,1977）：給定一個數字，考慮這個數字所帶來的不同反饋分區內元素的個數，并選擇最大反饋分區內元素個數最少的數字作為下一個猜測。在標準規則下，這種方法最多需要7次猜測，平均需要5.385次。
- 平均情況指標（Irving,1978）：選擇能使可能集預期大小最小的數字進行猜測。在標準規則下，這種方法最多需要7次猜測，平均需要5.268次。
- 預期步數指標（Neuwirth,1982）：也稱“熵”指標，選擇能使下一步猜測所需的預計步數最小的數字進行猜測。在標準規則下，這種方法最多需要7次猜測，平均需要5.265次。
- 反饋個數指標（Kooi,2005）：選擇能帶來最多不同反饋的數字進行猜測。在標準規則下，這種方法最多需要8次猜測，平均需要5.308次。
值得一提的是，啟發式策略的表現也可能受到數字排列的影響，但這通常不會產生顯著差異。
最優策略
最優策略是通過計算機窮舉所有可能的猜測方案來尋找最佳策略。由于每次猜測的選擇范圍有限（因為總共的數字組合個數有限），而且我們確信能在有限次數內猜中所有答案，因此計算機能夠遍歷所有的猜測方法，從而找到最優策略。此外，還有一些研究采用了遺傳算法等技術來解決猜數字問題，這里不再贅述。
不同規則下的表現
下面是幾種解法在不同規則下的表現。這些數據都是通過計算機程序計算得出的。
參考資料 >