年輕時，很容易手癢、想寫程式來解一些益智問題。
AB-game 也算是頗有趣的遊戲。因而，我在很久以前，就曾寫一支程式來（和使用者、或電腦自己）玩 AB-game。雖然那時自己其實對程式設計懂得很少，但最後還是能用 BASIC 語言，笨笨地、很暴力地 (ad hoc) 寫出「還算能夠玩」的程式。
回想起來，雖然頗覺得當時「不知天高地厚」，但心裏仍不免懷念那段年少輕狂的過去。也是因為最近試圖整理「從前感興趣的問題」，讓我回想起 AB-game。
從遊戲規則來看，要寫一支程式來檢查使用者的猜測，是相當容易的。程式可先依亂數選定一個數字，然後檢查使用者輸入的數字，回答幾 A 幾 B；直到使用者猜到程式所選的數字（回答 4A0B）為止。另一方面，要寫一支程式（扮演甲的角色來猜乙所選的數字），自動猜測使用者心裡所想的數字，似乎就不是那麼容易。
稍微分析一下，我們知道，在還沒有猜測前，乙選的數字有 10 x 9 x 8 x 7 = 5040 種可能。所以，即使乙並不需要回答幾 A 幾 B （僅需回答「是否猜中」），最糟的狀況下，我們也可以將這些可能的數字一個一個地拿來詢問「是這個數字嗎」，而在 5040 步內，猜中乙的答案。
而我們現在有乙所回答的「幾 A 幾 B」資訊，該如何利用它呢？最直接的方式，就是利用這項回答，從 5040 種可能（或者稱作「可能性空間」，possibilities space）裡，將不符合的數字刪掉。例如，如果猜測 1234 而得到回答 0A1B，那我們知道，答案不可能是 1234 （否則，回答應該是 4A0B)、不可能是 1567（若答案是 1567，猜 1234 的回答應為 1A0B）、也不可能是 8912 （回答會是 0A2B 而不是 0A1B）...。
因此，甲每猜測一次，就可以藉由乙的回答，從「可能性空間」裡，刪除一些「不可能是答案」的數字（也就是說，每一步都可以縮減可能性空間的大小）。於是，還保留在可能性空間裡的數字，就是「經過一連串猜測與回答後，仍有可能是答案」的那些數字。而我從前的程式，就是任意地從可能性空間中挑選出一個數字，來當作下個回合的猜測。
接下來的問題是：若演算法是任意由可能性空間裡，挑選一個數字，那麼最壞的情況下，需要猜測多少次呢？或者，更進一步：平均起來，需要猜幾次才能得到答案？還有：雖然可能性空間裡的數字，都有可能是答案；是否會有一些數字，它比其他的數字「更有可能」是答案？
雖然經過了這些年、似乎累積了更多電腦相關的知識；但我除了對從前的程式實作，有些改良的意見外，竟然也沒能想出更好的演算法與結果呢！
4 則留言:
雖然小時候也玩過像Mastermind這類遊戲, 不過對於這種組合加上機率/統計分析的東西, 向來缺乏直覺. 稍微整理了幾個關於這個問題的性質以後, 還是放棄了.....
這個網址提供了關於Mastermind問題的相關性質與演算法的例子:
http://www.delphiforfun.org/Programs/MasterMind.htm
這個網址提到猜測超過七次的例子:
http://www.cut-the-knot.org/ctk/Mastermind.shtml
另外還舉出一些必定可以解出答案的固定猜測patterns (static Mastermind), 都是有趣的變形
引用別人的一段文字:
Knuth outlines a mastermind strategy that is very close to being optimal, and which guarantees a win at most five guesses. His idea is to create a solution pool P that contains all of the codes that are still possible. Each guess G is chosen from the original 1296 possibilities in order to minimize the current size of P. This strategy is interesting because it is sometimes the case that the guess that minimizes the size of P is not a member of P. That is, it is necessary to make a guess that we know no longer a possibility in order to guarantee a win in five moves! The drawback of this strategy is that it requires a lot of computer time. For each guess the program must compare the original possibilities to each member of the solution pool P.
.....
Knuth shows that the pattern xxyy where x<>y is the optimal first guess (for Mastermind game)
.....
原文 by Richard Zaccone;
另一個採用Genetic Algorithm 解的例子:
http://geneura.ugr.es/~jmerelo/newGenMM/newGenMM.html
哎，Ankh 一下子就找出一堆 Mastermind 的相關文章了。我本來還想花一點篇幅介紹這個遊戲呢...
我根本沒有 "整理" 相關的資訊, 只是引用而已. 閱讀學長整理過的東西, 感受是完全不同的.
對我自己來說, 光是發現處理一個問題可以分為被 "solve", 也可以用 "search" , 就已經覺得夠古里古怪地有趣.
而很多策略要耗用電腦不少memory resources, 並進行comparisons, 這種策略似乎都不像人的處理方式. 我當初就不太會玩這種遊戲, 而現在雖然可以"猜測, 設計"出一些讓電腦能夠處理的策略, 真要我再去玩, 恐怕也還是很糟.
張貼留言