2018年7月8日 星期日

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