1A2B 猜數字遊戲

我很喜歡 1A2B 這個遊戲，想要寫一個小程式讓電腦出題，平常無聊時就可以猜電腦出的數字。

1A2B 遊戲規則

1A2B 這個遊戲在國外叫 mastermind 或 cows and bulls，玩法是選個 4 位數的數字，這 4 位數中的數字不能重覆，比方說 1231 這樣是不行的，因為 1 重覆使用了。另外，我自己玩的時候最高位數不能為 0，比方說 0123 這樣是不行的，但我看其他人在玩的時候最高位數還是可以為 0。

假設我選的數字是 1234，對手猜 9801，那對手猜中 1 這個數字，但是位子不對，這樣的情況稱為 B。因為對手沒有猜中其他數字，所以總計起來就是 1 個 B 而已，所以我會回報對手 『0A1B』，告訴他：『你猜中了一個數字，但這數字不在正確的位子上。』

如果對手猜 1987，那麼 1 被它猜中了，而且位子也在正確的地方，這樣的情況稱為 A, 因為對手沒有猜中其他數字，所以總計起來就是 1 個 A 而已，所以我會回報 『1A0B』，告訴他：『你猜中了一個數字，而且這數字在正確的位子。』

下次對手猜 4201，4 這個數字猜中了，但位子不對，1 個 B；2 這個數字猜中了，而且位子也正確，1 個 A；1 這個數字猜中了，但位子不對，1 個 B，總計就是 1 個 A 還有 2 個 B，所以我回報給對手：『1A2B』，遊戲的目標就是要達到 4A -- 4 位數都猜中，而且數字都在正確的位置上。

1A2B 猜數字遊戲的演算法

因為身邊的其他人對這遊戲沒什麼興趣，所以想要寫個小程式平時自娛，然後又想，嗯，如果要寫這樣的程式的話，除了人猜電腦的部份，那最好也寫個能夠讓電腦猜人的功能吧？不過這一方面的演算法實在不太清楚要怎麼進行。

我玩 1A2B 時常常用的是直觀法，看看之前猜的結果，綜合歸納後就：『啊，答案應該是這個！！』當中有不少『靈機一動』的感覺。但人類能用『靈機一動』來猜測，電腦沒辦法這麼做啊！所以還是得看看別人怎麼設計演算法讓電腦來猜人。

查了之後才發現好多高中生 & 資工系學生做過研究，分析 1A2B 這個遊戲如果是人想個 4 位數的數字讓電腦猜，電腦最少要猜幾次才能猜中。大家使用的演算法就是先列出所有可能性，再逐一排除不可能的答案，利用這樣的演算法電腦平均要猜 5.x 次才能猜中，目前還沒有一個演算法能讓平均值少於 5。

嗯，要列出所有可能，然後逐一刪去不可能的答案？好吧，那如果最高位數如果可以為 0 的話，可能的答案有幾種呢？

最高位數有 0~9 這 10 種可能，第二位數跟最高位數不能重覆，所以祇剩下 9 種可能，第三位數剩 8 種可能，第四位剩 7 種可能，所以總共有 10*9*8*7 = 5040 種可能性 (是的，不是 0000~9999 共 10000 種可能，而是 5040 個可能的答案)。看到的演算法都是讓電腦最多猜 7 次，就能從這 5040 個可能的答案裡找到正確的結果 (平均要猜 5.x 次)。

4 位數我自己玩大概也是猜 5~6 次可以猜到對手的數字，因為太沒有挑戰性，所以我平常玩都是玩 5 位數的，這個我就要計算一下子了；我挑戰過 6、7 位數的，結果後來翻臉不玩！ XDDD

重點是，我找到有人寫過可以猜 10 位數的程式！！

10 位數？那答案有多少種可能啊？嗯，不是 0000000000~9999999999 共 100 億種可能，而是 10! 。

『10 種？怎麼可能？你剛剛說 4 位數就已經有 5040 種可能了，怎麼 10 位數的反而才 10 種可能？你是不是在亂講？！！』

ㄟ，別急啦，我是說有 10! 種可能，而不是說 10 種，仔細看一下， 10 的後面有多一個驚嘆號，這是 10 的階乘。

10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 3,628,800

然後呢，你覺得 4 位數電腦就要猜 5.x 次了，10 位數電腦要猜多久？結果很讓人訝異，我試玩了一下，電腦祇要 13 次左右就可以猜到我設的數字。不過很遺憾作者沒有提供程式碼，所以不知道他的程式是怎麼運作的，光是把 3,628,800 種可能性存檔查表都要花點時間啊，但程式運作的很快。

繼續努力研究怎麼寫這個程式。 :)

參考資料：

1. 猜數字遊戲最佳解的討論
2. 猜數字遊戲的AI