先說明題目，就是有 n(通常是4，後面就以4討論之)位數，其
數字不可重複，你可以先猜一個4位數，然後它會告訴你，幾A幾B，
然後你可以再根據提示輸入一個4位數，它再告訴你幾A幾B，直
至你答到4A。
這個問題之前已有很多人討論過，但精華區卻都沒收錄，我便自把
我所能看到的舊信，整理一下，和大家討論。
目前最常用，也是最容易 implement 的方法，就以建 answer
list 的方法，就是把所有的可能的答案(5040個)建成一個
list，每次從可能答案的 list 中，「隨便」選一個來猜，再由
所得的提示，把不可能的答案去除，再由可能的答案中再「隨便」
選一個來猜，直至4A為止，一般這個方法「平均」 6-7 次就可以
猜出答案，但最糟的時候會有8次，但不常見。
但這個方法只是由答案中「隨便」選一個來猜，並不能保證是最佳
的猜法，也不能確保worse case 舉例來說，
若是 答案是 1230，你一開始(運氣很好，第一次就3A)猜
1234 -> 3A
若是用上面的演算法，運氣又很不好時，可能會有
1235 -> 3A
1236 -> 3A
1237 -> 3A
1238 -> 3A
1239 -> 3A
1230 -> 4A
共要猜 7 次，
但若是先猜一次 5678，無論是得到 0A0B, 1A, 或 1B，
都能保證在"6次"內猜出來。
再舉另一個例子，要猜0-100中的一個數字，猜了後，它會給你
有答案比猜的數大或小的提示，我們知道用二分法來做，一定能
保證7 次內一定可以猜中此數字 (2^7=128>101)，但若是用
上面的演算法，「可能」(雖然機率不大)會出現
50 -> small
49 -> small
48 -> small
:
:
0 -> YOU GOT IT
共猜 51 次，
當然實際上不會這麼極端，平均仍在 7-9 次之間就可猜出，
但其 WORSE CASE 就十分不好。
所以上面的演算法，隨便猜一個四位數，幾A幾B的，就有可
能到 8 次。
所以到底怎麼猜是最佳的演算法，目前可以看到是AI(人工
智慧)的方法，把問題看成game search，雖然 search
space 只有 5040，但 branch factor 的分很
大，(隨便猜只是其中的一個分枝)，其中我看吳慶鴻
(woju@bbs.ee.ntu.edu.tw)同學有較詳細的 implement
，如下：
> 1. 猜對方的數字時儘量例用「所有已知資料」，從中找出最
佳的幾個解，並計算 (模擬)出那個答案會讓對方作弊
的機會降到最低，模擬深度只有一層，也就是 local
optimal，類似象棋推測對方下一步棋一樣。
> 2. 儘可能的做弊，並使用類似 Step 1 的方法找出最佳做
弊解，儘可能讓對方猜中的可能降低
> 3. 當對方做出「不合理的弊」時，可以抓包...
> 此程還有改進的空間，比如說，把 local optimal 擴展至
global optimal，不過這樣大概得用更快的電腦了...
但他的不沒有列出他的方法「平均要猜幾次」，「最糟要猜幾次」。
還有一位同學(夜 就是我的全部，Willy.bbs@cis.nctu.edu.tw)
> 當初想這演算法的原因是班上有一位同學，玩猜數字遊戲幾乎
不超過五次的。在屢戰屢敗下受了刺激，才進而一步步的想，
數字該怎麼取比較好，慢慢歸納出十幾項規則，最後便依照這
些「鐵則」寫成 pseudo-code，無奈正逢高三要考聯考，家
裡電腦被封機，就沒能完成程式。
等考完，那心血就不知道夾到那本書中賣掉了﹍﹍
三次找出正確數字、五次排出順序看似不可能，但當初確是經過
多位同學以人工方式依虛擬碼一步步操作，而得出的結果。也曾
經不先決定數字，而取最差的狀況，結果仍然一樣五次內解出。
如今每當見到大家討論這問題，都不禁令我心中欷噓，怎會丟掉呢
？唉﹍﹍
這位同學，加了許多自已的heuristic, 可惜演算法不見了，十分可
惜，不過三次要找到正確字，的確十分不可能，若是第一次猜1234，
得到1B，第二次大概只能猜5678，又得到2B，我無法知道(想像)，
能在第三次就能知道1234中的那一個，5678中的那二個，和90中的那
一個 :< 。 不過我覺得可能會有一種猜法，平均 5-6 次，最糟只要
6次。
討論這麼多，希望有作出較好的方法的同學們，甚至已用數學(程式)
推導最佳解的天才，能給一些意見，或是一起討論一下，再AI中可以
用那些方法找出較好的猜法，或是有較好的 heuristic可以用在
implement 上.
--
蘇明信 simon@iis.sincia.edu.tw