人腦vs電腦-Mastermind破解技法

最近有網友瀏覽本人的Mastermind網頁,並讓我的Mastermind遊戲程式猜他出的謎底(有關本人Mastermind程式的詳細介紹,請參閱本人的人工智能MastermindMastermind遊戲說明網頁),結果我的程式發現網友提供的提示有誤。以下是網友提供的資料,首先是遊戲設定方面的資料。

顏色數目:8 (用數字0至7代表這8種顏色)
謎底長度:6
排序類型:任意次序
顏色可否重覆:每種顏色最多出現3次


接著是謎底和本人程式的猜謎過程。

回合輸入提示
 7 6 5 4 3 2(謎底)
17 7 7 5 5 01,1
25 0 0 0 0 00,1
30 7 4 4 6 31,3
40 3 7 3 3 41,2
57 4 4 3 4 51,3
67 5 6 4 3 63,3
7發現提示有誤 

上表「提示」中的第一個數字代表猜對且位置正確的顏色數目,第二個數字代表猜對但位置不正確的顏色數目。

上述資料顯示,在第6回合時,有3個顏色猜對且位置正確(即7、4和3),並有兩個顏色猜對但位置不正確(即5和6),因此這個回合的提示應為3,2,但網友提供的提示卻是3,3。由於提示有誤,程式不能繼續進行下去。

但問題是,本人的程式根本不知道網友的謎底,如何能在第6回合斷定提示有誤?這也就是該名網友感到困惑之處。答案是:本人的程式是通過有系統的推理,逐一考慮所有可能性,從而最終斷定提示有誤。以下闡述這個推理過程(以下我們將忘記上表提供的真正謎底,而僅僅根據上表六個回合中的提示嘗試繼續猜下去)。

根據第6回合的提示,程式已知謎底必然包含3、4、5、6、6、7這六個顏色,接下來只須確定這六個顏色的正確位置。確定的方法是作出一系列假設,並根據提示修正這些假設。請注意我們必須有系統地作假設,以避免遺漏任何一個可能性。

首先,根據第1回合的提示,對於「777550」這個組合,只有一個顏色猜對且位置正確,不妨假設這個顏色是左起第一個7。換句話說,假設謎底為「7*****」(其中「*」代表待定的顏色)。為方便以下討論,我們把這個假設命名為「假設1」。接著,根據第2回合的提示,可知5不能出現在左起第一個位置上,故假設它出現於第二個位置上,即假設謎底為「75****」,我們把這個假設命名為「假設11」(意思是基於「假設1」的第1個假設)。同理,根據第3回合的提示,我們假設謎底為「754***」(假設111);根據第4回合的提示,我們假設謎底為「7543**」(假設1111)。但「假設1111」與第5回合的提示相矛盾,這是因為如果「假設1111」成立,那麼第5回合便應有至少3個顏色猜對且位置正確,但第5回合的提示卻是1,3,與此不符。

由於「假設1111」不成立,我們返回「754***」(假設111),並根據第4回合的提示,重新假設謎底為「754*3*」,我們把這個新假設命名為「假設1112」。但「假設1112」同樣與第5回合的提示相矛盾。事實上,容易看到任何形式為「754***」的謎底都與第5回合的提示相矛盾,由此可知「假設111」不成立。

由於「假設111」不成立,我們返回「75****」(假設11),並根據第3回合的提示,重新假設謎底為「75*4**」,我們把這個新假設命名為「假設112」。接著根據第4回合的提示,我們假設謎底為「75*43*」(假設1121),請注意這個假設與第5回合的提示並不矛盾。由於現在只剩下兩個6尚未填入,因此在「假設1121」下,謎底必然是「756436」,但此假設與第6回合的提示不相容,由此可知「假設1121」不成立。

由於「假設1121」不成立,我們返回「75*4**」(假設112),並嘗試根據第4回合的提示作出新的假設,但我們發覺無法這樣做,由此可知「假設112」不成立。既然「假設112」不成立,我們返回「75****」(假設11),並根據第3回合的提示,重新假設謎底為「75**6*」(假設113)。接著根據第4回合的提示,我們假設謎底為「75*36*」(假設1131)。由於現在只剩下4和6尚未填入,在「假設1131」下,根據第4回合的提示,謎底只可能是「754366」,但此假設與第3回合的提示相矛盾,由此可知「假設1131」不成立。

由於「假設1131」不成立,我們返回「75**6*」(假設113),並根據第4回合的提示,重新假設謎底為「75**64」(假設1132)。由於現在只剩下3和6尚未填入,在「假設1132」下,根據第4回合的提示,謎底只可能是「753664」,但此假設與第6回合的提示不相容,由此可知「假設1132」不成立。

由於「假設1132」不成立,我們返回「75**6*」(假設113),並嘗試根據第4回合的提示作出新的假設,但我們發覺無法這樣做,由此可知「假設113」不成立。既然「假設113」不成立,我們返回「75****」(假設11),並根據第3回合的提示,重新假設謎底為「75***3」(假設114)。接著嘗試根據第4回合的提示繼續作出假設,但我們發覺無法這樣做,由此可知「假設114」不成立。既然「假設114」不成立,我們又返回「75****」(假設11),並嘗試根據第3回合的提示作出新的假設,但我們發覺已無法這樣做,由此可知「假設11」也不成立。

由於「假設11」不成立,我們返回「7*****」(假設1),並根據第2回合的提示,重新假設謎底為「7*5***」(假設12)。由於接下來我們基本重覆進行前述的推理過程,為免重覆使用繁瑣的文字,以下使用較簡略的表達法。「7*5***」(假設12) →「7*54**」(假設121) → 「7354**」(假設1211) →「735466」 → 與第3回合的提示相矛盾 → 「假設1211」不成立 → 返回「7*54**」(假設121) →「7*543*」(假設1212) →「765436」 → 與第6回合的提示相矛盾 →「假設1212」不成立 → 返回「7*54**」(假設121) → 無法繼續進行假設 →「假設121」不成立。

接著返回「7*5***」(假設12) →「7*5*6*」(假設122) →「735*6*」(假設1221) →「735466」 → 與第3回合的提示相矛盾 →「假設1221」不成立 → 返回「7*5*6*」(假設122) →「7*536*」(假設1222) →「745366」→ 與第5回合的提示相矛盾 →「假設1222」不成立 → 返回「7*5*6*」(假設122) →「7*5*64」(假設1223) → 無法繼續進行假設 →「假設1223」不成立 → 返回「7*5*6*」(假設122) → 無法繼續進行假設 →「假設122」不成立。

接著返回「7*5***」(假設12) →「7*5**3」(假設123) → 無法繼續進行假設 →「假設123」不成立 → 返回「7*5***」(假設12) → 無法繼續進行假設 →「假設12」不成立。

接著返回「7*****」(假設1) →「7****5」(假設13)。容易看到,形式為「7****5」的謎底都與第5回合的提示相矛盾,由此可知「假設13」不成立。接著再次返回「7*****」(假設1) → 無法繼續進行假設 →「假設1」不成立。

「假設1」既已被否定,我們接著根據第1回合的提示,重新假設謎底為「*7****」(假設2) →「*75***」(假設21) →「*753**」(假設211) → 無法繼續進行假設 →「假設211」不成立 → 返回「*75***」(假設21) →「*75*3*」(假設212) → 無法繼續進行假設 →「假設212」不成立 → 返回「*75***」(假設21) →「*75**4」(假設213) →「*753*4」(假設2131) →「675364」→ 與第3回合的提示相矛盾 →「假設2131」不成立 → 返回「*75**4」(假設213) → 無法繼續進行假設 →「假設213」不成立 → 返回「*75***」(假設21) → 無法繼續進行假設 →「假設21」不成立。

接著返回「*7****」(假設2) →「*7***5」(假設22) →「*7*3*5」(假設221) → 無法繼續進行假設 →「假設221」不成立 → 返回「*7***5」(假設22) →「*7**35」(假設222) → 無法繼續進行假設 →「假設222」不成立 → 返回「*7***5」(假設22) → 無法繼續進行假設 →「假設22」不成立 → 返回「*7****」(假設2) → 無法繼續進行假設 →「假設2」不成立。

「假設2」既已被否定,我們接著根據第1回合的提示,重新假設謎底為「**7***」(假設3) →「*57***」(假設31) →「*574**」(假設311) → 無法繼續進行假設 →「假設311」不成立 → 返回「*57***」(假設31) →「*57*6*」(假設312) → 無法繼續進行假設 →「假設312」不成立 → 返回「*57***」(假設31) →「*57**3」(假設313) →「*57*43」(假設3131) →「657643」→ 與第6回合的提示相矛盾 →「假設3131」不成立 → 返回「*57**3」(假設313) → 無法繼續進行假設 →「假設313」不成立 → 返回「*57***」(假設31) → 無法繼續進行假設 →「假設31」不成立。

接著返回「**7***」(假設3) →「**7**5」(假設32) →「**74*5」(假設321) → 無法繼續進行假設 →「假設321」不成立 → 返回「**7**5」(假設32) →「**7*65」(假設322) → 無法繼續進行假設 →「假設322」不成立 → 返回「**7**5」(假設32) → 無法繼續進行假設 →「假設32」不成立 → 返回「**7***」(假設3) → 無法繼續進行假設 →「假設3」不成立。

「假設3」既已被否定,我們接著根據第1回合的提示,重新假設謎底為「***5**」(假設4) →「**45**」(假設41) →「*345**」(假設411) → 無法繼續進行假設 →「假設411」不成立 → 返回「**45**」(假設41) →「**453*」(假設412) → 無法繼續進行假設 →「假設412」不成立 → 返回「**45**」(假設41) → 無法繼續進行假設 →「假設41」不成立。

接著返回「***5**」(假設4) →「***56*」(假設42) →「*3*56*」(假設421) → 無法繼續進行假設 →「假設421」不成立 → 返回「***56*」(假設42) →「***564」(假設422) → 無法繼續進行假設 →「假設422」不成立 → 返回「***56*」(假設42) → 無法繼續進行假設 →「假設42」不成立。

接著返回「***5**」(假設4) →「***5*3」(假設43) → 無法繼續進行假設 →「假設43」不成立 → 返回「***5**」(假設4) → 無法繼續進行假設 →「假設4」不成立。

「假設4」既已被否定,我們接著根據第1回合的提示,重新假設謎底為「****5*」(假設5) →「**4*5*」(假設51) →「*34*5*」(假設511) → 無法繼續進行假設 →「假設511」不成立 → 返回「**4*5*」(假設51) →「**435*」(假設512) → 無法繼續進行假設 →「假設512」不成立 → 返回「**4*5*」(假設51) → 無法繼續進行假設 →「假設51」不成立。

接著返回「****5*」(假設5) →「***45*」(假設52) →「*3*45*」(假設521) → 無法繼續進行假設 →「假設521」不成立 → 返回「***45*」(假設52) → 無法繼續進行假設 →「假設52」不成立。

接著返回「****5*」(假設5) →「****53」(假設53) → 無法繼續進行假設 →「假設53」不成立 → 返回「****5*」(假設5) → 無法繼續進行假設 →「假設5」不成立。

至此我們已考慮所有可能性,但卻找不到一個能符合全部提示的謎底,由此可以推斷,所給提示必然有誤。這個例子顯示,破解Mastermind的技法就是重覆進行上述的推理過程。在某些情況下,這個過程可以非常繁瑣,靠人腦進行可能要花很長時間,而且會有很多錯漏,而本人的程式則在電光石火間便已完成上述過程,這個例子顯示了把邏輯推理與電腦自動計算結合後所能產生的強大威力。


「周家發的數學網頁」
<script type = "text/javascript"> (function(d, w) { var x = d.getElementsByTagName('SCRIPT')[0]; var f = function() { var _id = 'lexity-pixel'; var _s = d.createElement('script'); _s.id = _id; _s.type = 'text/javascript'; _s.async = true; _s.src = "//np.lexity.com/embed/YW/be0aa169de7f441c6473361be62c9ef6?id=ddad453e7753"; if (!document.getElementById(_id)) { x.parentNode.insertBefore(_s, x); } }; w.attachEvent ? w.attachEvent('onload', f) : w.addEventListener('load', f, false); }(document, window)); </script>