猜數字遊戲

 多年前, 很多很多年以前, 寫了一個排7接龍的電腦撲克牌遊戲, 把自己的玩法教給了電腦. 擁有遊戲的人, 與其說是跟電腦玩, 其實是跟我玩. 自己以前也常跟自己玩, 贏的人當然通常是我自己. 看著電腦玩家一家接著一家自動順暢的出牌, 是很療癒的.

最近因為AI盛行, 想起了那個遊戲, 却遍尋不到, 但找到了1A2B猜數字遊戲. 試玩一下, 是由電腦亂數出題來讓自己猜, 也有快速運算解法協助, 當時用的解法是試誤法, 就是從小的數字逐次加1, 先檢查每個數字是否有重覆, 沒有重覆後, 再檢查與先前猜的數字的A/B數是否符合, 若符合就有可能是答案, 一直重覆直到找到正解.

這個方法很靠運氣, 若答案小, 很快就猜到. 當玩多位數時, 例如5位數, 就會玩很久, 等到答案出來都天暗了. 這樣玩, 沒有什麼樂趣, 要快速找出答案才有成就感.

這個試誤法沒有利用A/B的資訊, 浪費了很多不可能的數字的檢查, 例如 1234 若 A+B<3 的情況, 例如 2A 或 2B 或 1A1B, 接下來檢查 1235 , 1236 ...根本是浪費時間. 道理簡單易懂, 但怎麼教電腦做智慧檢查才是問題!

一般在猜數字, 就是從一組已猜測的中選出 A+B 個字, 與另一組組合後, 比對其他組是否合理, 所以就用這個方法來試. 流程, 也就是演算法, 如下:

1, 把 0 ~ 9 依某種方法猜過, 直到所有的 A, B 數加起與玩的位數一樣, 例如3位數 => 123 0A1B, 456 1A1B, 後面的 7/8/9/0 就不必猜了.

2. 從1組中選出數字, 123, 可以選出 1, 2, 3 三種情況

3. 把選出的數字做排列, 1有 1**, *1*, **1三種可能, 2與3也一樣

4. 檢查排列是否合理, 例如 456要選出2個字, 45, 排列有 45*, 4*5, 54*, *45, 5*4, *54六種可能, 但其中 45* 是不對的, 這有2A, 54*, *45, 5*4也不對, 0A, 所以只有 4*5, *54兩種可能. 同理1**是不對的.

5. 合併, *1*可以併出415/516等組合, **1可以併出461/651等, 2有 254/246/462/652, 3有354/346/435/536等組合, 這樣剩下12個可能

6.與其他組猜過的做驗證, 例如先猜了415 0A1B, 要猜516前比對 415有1A1B, 所以是不對的

7. 做完所有檢查都符合的組合就是下一個要猜的, 如246.

8. 如果沒有猜對, 對於步驟4所得到的結果先行再淘汰, 避免浪費後續合併/檢查的時間

這個方法大量減少了要算的數字, 以6位數為例, 301846, 在同一台電腦實際比較, 方法1用了30分24秒, 猜了6次, 而方法2 玩10次, 平均只用15.6秒, 猜6.6次. 如果倒霉電腦出到9*****, 就要1個半小時,方法1才會得到答案.

雖然有了重大改善, 但因增加了選字, 排列, 合併的工作, 對於少位數的5, 6個字, 或許可接受了, 但7以上的還是會等很久,例如 14分鐘, 甚至30分鐘, 當然跟運氣也有關.

檢查一下, 因為是用 EXCEL 寫的, 借用儲存格當候選字的記錄, 在把字寫入儲存格中會浪費很多時間, 加上7位數, 若前兩猜都 5B 情況下, 需要合併 14568 * 14568 次, 會有 212百萬個合併結果, 比方法1多了21倍多的檢查量, 難怪還要等很久. 雖然步驟8已經讓後續的合併大量減少了, 所以還需要再調整方法.

接下來方法3把焦點放在5位數以上, 只需預猜2次的情況. 方法2 把所有可能都排了出來, 方法3要改變作法. 方法如下. 以7位數, 3456789 2A2B, 0123456 5B為例, 可以知道 3456 內有2個(2+2+5-7=2), 因為重猜一次多了2個A或B. 這樣知道012都是有的, 排列方式只有6種. 再與 3456789 選出的2A2B排列組合做合併, 就可以大幅降低時間了. 同時, 不一一列出可能的組合再合併, 而是合併一個就檢查一個.

實測這方法7位數10次, 平均 5.5秒猜7.5次. 可以了嗎? 還得用8/9/10 位數確認. 8位數, 5次平均 47.2秒 猜9次, 還可以接受, 但9位數猜了11分鐘11秒, 還是需要再進化.

再檢查整個過程發現, 高位數的排列結果數量很多, 檢查時間當然多. 如何避免不必要的檢查呢? 就是A+B不足遊戲位數的不排. 例如8位數, 答案是 12345678 組成. 則01234567, 23456789就不要再排了, 一定不會答對.

於是, 方法4就是先確認所有的數字. 所以利用方法3的方法, 把兩組數字選出的字排列的工作移到最後, 這樣還可以節省一些時間, 但猜的次數可能會增加. 8位數大概省2/3, 9位數大概省1/2的時間.

實測方法4, 8位數10次平均花15.2秒 9次猜中, 大約是方法3的1/3時間而已. 9位數10次平均花 261秒 11.2次猜中.

平均4分20秒猜中9位數雖然快了很多, 但還是久, 倒霉時要等到8分鐘, 還是需要再精進. 從前面的幾個改進, 主要在減少合併的時間, 方法4雖又減少了排列的時間, 但對A數字的利用只在答案的檢查, 所以精進的方向就是拿A的資料來做排列的減少.

方法5 的想法是, 在排除沒有的數字過程中, 所猜的結果中, 以A的數值最大的做為基礎, 從中先選出A量個字, 這些字因為是A, 所以不必每個位置排列, 這樣就可減少排列了. 例如 答案由 123456789 組成, 在過程中 234567890 有 3A5B 是最多的A, 所以可用 234等先選3個固定數再組合156789的排列的方式來減少排列. 此例大約可以減少到剩1/9的量, 若是2A而已, 減少到剩 7/18的量. A的量越多越省時間.

實測方法5, 8位數10次平均花9.4秒 猜9.2次, 9位數10次平均花124.7秒猜10.3次. 10位數呢? 試了1次, 刻意找2A, A的位置較前的預猜, 花了25分34秒猜11次, 真的是運氣佔比高, 因為一次就會猜中所有的數字, A多就快, A少就慢; 所以不太敢再試, 約會較9位數多10倍的時間, 等9位數有進一步改善再試吧.

方法5只靠一次的A量後就進行排列猜測, 對其他或後續的A量只做檢查用, 應該還有改善方法. 只是演算法是如何, 還在思考中.

檢查選A字過程, 發現後來猜的A會減少, 但在選出A字時沒有先與猜的資訊檢查就進行排列, 結果一些不合的A字就多浪費了排列的時間, 經修正方法5, 9位數10次的平均變為79.6秒11次,又減少了1/3的時間.

測試10位數, 因為0A的機會很高, 所以預猜的部份先多做了幾次, 在找出最多A最優A的預猜後再開始遊戲的過程, 結果A為2時4次平均花298.5秒猜10次, A為3時2次平均28.5秒猜10.5次, A為4時4次平均16.5秒猜9.25次.

從以上10位數分析開發了方法6, 如果每一次的猜題所得到的A數較原來的高, 利用這個新猜結果重新開始, 應該可以大幅改善花用的時間. 測試9位數10次平均花65.5秒猜11.7次,10位數5次平均花241.8秒猜11次. 9位數有小幅改善, 10位數進到了5分鐘內.

在看程式猜字過程中發現

1. 9位數與10位數一開始猜中的A的數很低, 透過排列得到可能的答案後再猜測來取得較大A的時間要很久

2. 當再猜了一個答案, 例如 9******** 有0A10B, 因取字/排列都是利用遞迴寫法, 會一直做完所有檢查, 所以還會再把所有的 9********都檢查過, 而0A已經說9不會在第一的位置了, 所以這是浪費時間的地方

有了這個觀察, 就改成在排列下一個位置前先檢查已經排好的是否符合, 這樣, 當猜了一個答案後, 後續的排列就會檢查是否需要再往下一位置排下去, 還是要往上換不同的選字.

把有較多A就重開始的方法先停用, 只做排前先檢查, 10位數13次平均花50.2秒猜11.2次. 有了關鍵的改善. 但也看到一個現象, 個位數秒數, 甚至到1 秒, 找出答案的都是一開始是0A的; 當然秒數最多的那次也是一開始是0A. 而一開始是1A的有2次高於平均, 1次低於平均; 一開始是3A的只1次, 是低於平均.

把有較多A就重開始的方法再結合進來, 結果達到了極佳的成果, 9位數10次平均花6.9秒猜12次, 10位數10次平均花16.7秒猜11.2次.

以下是最佳成績的面, 10位數, 花不到1秒, 猜了7次就中.