香港新浪網 MySinaBlog
« 上一篇 | 下一篇 »
kafat | 1st Aug 2014 | 我的網站介紹 | (191 Reads)

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

顏色數目:8 (用數字0至7代這8種顏色) 

謎底長度:6

排序類型:任意次序

顏色可否重覆:每種顏色最多出現3

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

回合

 輸入提示
 7 6 5 4 3 2(謎底)
17 7 7 5 5 01,1
25 0 0 0 0 0 0,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個顏色猜對且位置正確(743),並有兩個顏色猜對但位置不正確(56),因此這個回合的提示應為3,2,但網友提供的提示卻是3,3。由於提示有誤,程式不能繼續進行下去。

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

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

首先,根據第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)。由於現在只剩下46尚未填入,在「假設1131」下,根據第4回合的提示,謎底只可能是「754366」,但此假設與第3回合的提示相矛盾,由此可知「假設1131」不成立。

由於「假設1131」不成立,我們返回「75**6*(假設113),並根據第4回合的提示,重新假設謎底為「75**64(假設1132)。由於現在只剩下36尚未填入,在「假設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」不成立。

 請繼續閱讀《人腦vs電腦-Mastermind破解技法(下)》


[1] Carlos Rowland

These insect steroids for bronchitis float crown. Hard drank buy testosterone enanthate usa stir brick?! Peep walk steroids 2013 bodybuilding by rub?! Growth front steroids urine test prod.


[引用] | 作者 buy finasteride | 28th Sep 2016 | [舉報垃圾留言]