猜數字[興起於英國的益智類小遊戲]

猜數字（又稱 Bulls and Cows ）是一種古老的的密碼破譯類益智類小遊戲，起源於20世紀中期，一般由兩個人或多人玩，也可以由一個人和電腦玩。

遊戲規則

先解釋標準規則，再介紹幾種變體。

通常由兩個人玩，一方出數字，一方猜。出數字的人要想好一個沒有重複數字的4個數，不能讓猜的人知道。猜的人就可以開始猜。每猜一個數字，出數者就要根據這個數字給出幾A幾B，其中A前面的數字表示位置正確的數的個數，而B前的數字表示數字正確而位置不對的數的個數。

如正確答案為 5234，而猜的人猜 5346，則是 1A2B，其中有一個5的位置對了，記為1A，而3和4這兩個數字對了，而位置沒對，因此記為 2B，合起來就是 1A2B。

接著猜的人再根據出題者的幾A幾B繼續猜，直到猜中（即 4A0B）為止。

猜數字遊戲通常設有猜測次數的上限。根據計算機測算，如果採用嚴謹的猜測策略，任何數字最多7次就可猜出（即達到 4A0B）。值得注意的是，在有些地方把次數上限定義為最多幾次猜測以後就可以肯定數字是幾，但這時或還需要再猜一次才能得到 4A0B 的結果。

標準的猜數字遊戲由10個數碼（0-9）和4個數位組成。可以通過變化數碼或數位來豐富遊戲。例如，可以使用9個數碼玩4個數位的遊戲。

猜數字遊戲的一種變體允許重複的數碼。這種規則的遊戲被稱為 Mastermind 。其規則大致為：

除了上面的規則外，如果有出現重複的數字，則重複的數字每個也只能算一次，且以最優的結果為準。例如，如正確答案為5543，猜的人猜5255，則在這裡不能認為猜測的第一個5對正確答案第二個，根據最優結果為準的原理和每個數字只能有一次的規則，兩個比較後應該為1A1B，第一個5位子正確，記為1A；猜測數字中的第三個5或第四個5和答案的第二個5匹配，只能記為1B。當然，如果有猜5267中的第一個5不能與答案中的第二個5匹配，因此只能記作1A0B。

解法

求解猜數字遊戲的策略通常有兩個目標：一是保證在猜測次數限制下贏得遊戲，二是使用儘量少的猜測次數。第一個目標追求的是最壞情況下的猜測次數最少，第二個目標追求的是平均情況下猜測次數最少。對於某些數碼和數位的規則組合，這兩個目標不能同時實現。例如，對於4個數位、6個數碼的 Mastermind 遊戲，平均猜測次數最少的策略需要平均 4.340 次，但最壞需要6次猜測；如果限制猜測次數最多為5次，則平均猜測次數最少的策略需要平均 4.341 次。

目前解法最少需要7次猜測，平均次數最少的解法由田中哲朗與1996年提出，平均次數為5.213次。

系統的猜測策略可分為三類：簡單策略、啟發式策略和最優策略。下面以標準規則（10個數碼，4個數位，不含重複數字）為例，介紹這幾類策略。這些策略也適用於其它規則變體。

這種策略非常直接——每次都猜可能答案中的第一個。例如，首先猜測1234，如果得到的反饋是 2A0B，那么可能的答案包括1256，1257，5236，等等。根據簡單策略，下一次就猜1256，因為1256是所有可能答案中最小的數字。

簡單策略的優點是速度非常快，缺點是所需猜測次數很多。對於標準規則，簡單策略最多需要9次猜測，而平均需要5.560次。

這類策略是猜數字遊戲最常用的解法。其算法步驟如下：

a. 首先猜 1234，得到第一個反饋（xAyB）。

b. 從所有數字中，篩選出滿足已知反饋的所有可能數字，稱之為“可能集”。

c. 對於所有數字（而不僅限於篩選出來的可能集），逐一評估每個數字的“好壞”，並給其打分。選取得分最高的那個數字猜。如果有多個數字的評分一樣高，則優先選取可能集中的數字。

d. 重複步驟 b-c，直到猜出 4A0B 為止。

顯然，啟發式策略的重點在於如何評估一個數字的“好壞”？人們提出了多種直觀的評價指標。簡介如下：

最壞情況指標(Knuth, 1977) ：給定一個數字，考慮這個數字所帶來的不同反饋分區內元素的個數，並選擇最大反饋分區內元素個數最少的數字作為下一個猜測。對於標準規則，這一評價指標最多需要7次猜測，平均需要5.385次。

平均情況指標(Irving, 1978)：這是一個相當直觀的指標，在各種規則變體下均有較好的效果。給定一個數字，如果猜這個數字，那么接下來我的“可能集”平均會縮小到多大？選取使可能集的預期大小最小的那個猜測。對於標準規則，這一評價指標最多需要7次猜測，平均需要 5.268 次。

預期步數指標(Neuwirth, 1982)：又稱“熵”指標。給定一個數字，這個指標計算如果猜測這個數字，那么接下來估計還需要多少步才能猜到答案。當然，這個步數只是一個粗略的估計，它假設每次猜測可以將可能集縮小一半（或縮小某一個常數倍k），於是估計步數就是可能集大小的對數函式，即估計步數=log(可能集中元素的個數)。對於標準規則，這一評價指標最多需要7次猜測，平均需要 5.265 次。

反饋個數指標(Kooi, 2005) ：給定一個數字，這個指標計算該數字所可能帶來的不同反饋的個數。反饋越多的越好。對於標準規則，這一評價指標最多需要8次猜測，平均需要 5.308 次。

此外，值得注意的是，啟發式策略的效果也經常取決於所有數字的排列。不過影響一般不大。

猜數字遊戲的最優策略需要由計算機用窮舉法獲得。其思路是，由於每次猜測的選擇是有限的（因為總共的數字組合個數有限），並且我們知道一定可以在有限次數內猜出所有答案，那么計算機可以窮舉所有猜法，從中找出最佳的策略。

此外，也有一些文獻採用遺傳算法等求解猜數字問題，在此不詳述。

以下列出上述幾種解法套用於不用規則時的猜測效果，供參考。這些結果由電腦程式算出。

標準規則

對於標準規則（4 數位、10 數碼、不含重複數字），下表列出了各種策略的最多猜測次數、平均猜測次數、以及每個猜測次數所對應的答案個數。例如，採用“平均情況指標”最多需要7次猜測，平均需要 5.268 次猜測，有 1885 個數字需要用6次猜出。

算法	平均次數	1次	2次	3次	4次	5次	6次	7次	8次	9次
簡單策略	5.560	1	13	108	596	1668	1768	752	129	5
最壞情況指標	5.385	1	3	44	515	2124	2151	202	-	-
平均情況指標	5.268	1	4	59	574	2430	1885	87	-	-
預期步數指標	5.265	1	4	53	560	2515	1796	111	-	-
反饋個數指標	5.308	1	11	80	556	2277	1929	183	3	-

Mastermind規則

下表列出各種算法套用於Mastermind規則（4數位、6數碼、可重複）時的效果。

算法	平均次數	1次	2次	3次	4次	5次	6次	7次	8次	9次
簡單策略	5.765	1	4	25	108	305	602	196	49	6
最壞情況指標	4.476	1	6	62	533	694	-	-	-	-
平均情況指標	4.395	1	10	54	645	583	3	-	-	-
預期步數指標	4.424	1	4	70	611	590	20	-	-	-
反饋個數指標	4.373	1	12	72	635	569	7	-	-	-