自動(dòng)掃雷——概率分析之程序?qū)崿F(xiàn)
說到自動(dòng)游戲，即用程序自動(dòng)去玩某個(gè)游戲。這主要會(huì)涉及到三個(gè)部分：獲取游戲數(shù)據(jù)，分析數(shù)據(jù)、得到有用數(shù)據(jù)，控制游戲。
mineTerminator中用分析游戲窗口像素信息得到游戲數(shù)據(jù)，而控制游戲而是用SendMessage給游戲窗口發(fā)送按鍵消息。現(xiàn)在的難點(diǎn)既是分析游戲數(shù)據(jù)：通過下面幾部分來說明如何利用數(shù)學(xué)之美，成功地解決問題。
先來分析一下掃雷中可以存在的情況，總結(jié)出了四種不同的模型：
第一種、第二種模型
分析右上角的的2，其周圍的未知塊a,b兩塊，等于其周圍雷數(shù)，故可判斷出a,b都是雷；接下來，分析下面的2，其周圍共有3個(gè)未顯示的塊a,b,c，其中a,b已判斷出為雷，即周圍已判斷的雷數(shù)等于其雷數(shù)時(shí)，則可判斷剩下的塊都不是雷，即c塊不是雷。
這兩種模型，一種是判斷出雷、一種是判斷出沒有雷，這是地球人都知道的掃雷方法。而接下來的模型或許只有掃雷高手或者數(shù)學(xué)高手才知道~~
第三種模型
我先做一個(gè)大膽的判斷，c塊沒有雷！！且聽我慢慢道來~
根據(jù)兩個(gè)顯示為1的塊，可得如下的式子：
a+b=1 (1)
d+e=1 (2)
表示a,b中有且只有一個(gè)雷，d,e有且只有一個(gè)雷，
根據(jù)顯示為2的塊，可得：
a+b+c+d+e=2 (3)
表示abcde中有且只有兩個(gè)雷
根據(jù)(1)(3)，可得
c+d+e=1 (4)
根據(jù)(2)(4)可得， c=0 ，所以c塊肯定無雷，可放心地揭開。
這種模型可以說在掃雷中應(yīng)用得最精妙，看似無法判斷的情況，通過這樣的計(jì)算就可確定出哪里是雷或者哪里不是雷。
第四種模型
上面三種模型都屬于可確定判斷的范疇，而在掃雷中經(jīng)常會(huì)遇到無法確定判斷的死局。這時(shí)就得用到數(shù)學(xué)工具——概率，來進(jìn)行最優(yōu)判斷。
如圖所示顯示為3周圍有雷的概率很容易計(jì)算出：3/8（這是比較簡(jiǎn)單的情況）。再看下面的圖
當(dāng)點(diǎn)開兩個(gè)"8鄰接"距離小于等于2的塊時(shí)，它們周圍有雷的概率就不那么容易判斷了（上面a,b,c有雷的概率分別是多少），這種情況留在后文詳細(xì)分析�！毒幊讨馈返淖詈笠活}也就是這個(gè)問題， 三年前自己一直在想這個(gè)概率如何來求，以及如何用程序?qū)崿F(xiàn)。現(xiàn)在總算是想明白了~~~
這篇將介紹如何使用數(shù)學(xué)中的概率知識(shí)來玩掃雷游戲，也正是本人最想介紹的地方，即《前言》中所說的第四種掃雷模型的分析。
先看游戲界面，如下：
在游戲開始時(shí)，如何出現(xiàn)這樣的情況，我們可以認(rèn)為游戲中未顯示塊按概率相等可分為四個(gè)區(qū)域，其中a,b,c是其中的三個(gè)區(qū)域（a區(qū)域指上面的5個(gè)塊，b區(qū)域指中間的3個(gè)塊，c區(qū)域指下面的5個(gè)塊），再加上不與已揭開塊相鄰的所有塊構(gòu)成一個(gè)區(qū)域d（d區(qū)域含有465塊）。那么這四個(gè)區(qū)域中哪個(gè)區(qū)域有雷的概率最小呢？
這里直接說明所使用的數(shù)學(xué)方法叫做——條件概率和全概率公式。
條件概率可以說是計(jì)算機(jī)領(lǐng)域的一個(gè)功臣，由其發(fā)展而來的“統(tǒng)計(jì)語言模型”實(shí)現(xiàn)了機(jī)器翻譯、語音識(shí)別、漢字識(shí)別等一系列的用傳統(tǒng)方法很難解決的問題。而以其為基礎(chǔ)的“貝葉斯公式”在圖像處理、決策支持系統(tǒng)和博弈論中有著廣泛的應(yīng)用。
維基百科中給的定義是：條件概率就是事件A在另外一個(gè)事件B已經(jīng)發(fā)生條件下的發(fā)生概率。條件概率表示為P（A|B），讀作“在B條件下A的概率”。
而全概率為：
假設(shè){ Bn : n = 1, 2, 3, ... } 是一個(gè)概率空間的有限或者可數(shù)無限的分割，且每個(gè)集合Bn是一個(gè)可測(cè)集合，則對(duì)任意事件A有全概率公式：
又因?yàn)?/p>
此處Pr(A | B)是B發(fā)生后A的條件概率，所以全概率公式又可寫作：
用自己的話說，條件概率是在某件事發(fā)生的情況下，另一件事的概率；全概率是將所有情況的概率加起來。
而在掃雷游戲中有什么“所有情況”呢？
看上面的游戲場(chǎng)景，a,b,c所占的13個(gè)塊，如果僅僅根據(jù)上面所顯示的"1","2"，可以說這13個(gè)塊中，雷的總數(shù)可以有2個(gè)，也可以有3個(gè)�。〔⑶矣�2個(gè)或者3個(gè)的概率分別是1/2。
那么其情況如下：
上表說明當(dāng)雷數(shù)為2時(shí)，abc有雷的概率分別為0,1/3,1/5；當(dāng)雷數(shù)為3時(shí)，abc有雷的概率分別為1/5,0,2/5。
可算出
a區(qū)域有雷的概率為0*1/2+(1/5)*(1/2)=1/10
b區(qū)域有雷的概率為(1/2)*(1/3)+0*1/2=1/6
c區(qū)域有雷的概率為(1/2)*(1/5)+(1/2)*(2/5)=3/10
而d區(qū)域的概率同理也算出為(1/2)*(97/465)+(1/2)*(96/465)=193/930
可知，a區(qū)域有雷的概率最小，故可以在此5塊中隨機(jī)選一塊點(diǎn)擊了，然后一切就交給上蒼了~~（在不用類似查看內(nèi)存的方法的情況下，人做的就只有這么多了）
到此，數(shù)學(xué)原理已介紹完畢，用一句話總結(jié)，即，先找出按區(qū)域劃分的未顯示塊，然后分類討論這些區(qū)域中雷的總個(gè)數(shù)。接下來的一篇博文（也是本系列最后一篇），將介紹如何將上面的數(shù)學(xué)運(yùn)算用程序代碼實(shí)現(xiàn)。
批注：從自己想到數(shù)學(xué)實(shí)現(xiàn)到想明白如何用程序代碼實(shí)現(xiàn)，應(yīng)該有兩年之多，當(dāng)然只是偶爾無聊時(shí)才思考一下。不過，在思考這個(gè)實(shí)現(xiàn)過程中，自己開始一直在用數(shù)學(xué)的思路而沒有用代碼的思路去思考，故一直行不通。當(dāng)自己用代碼實(shí)現(xiàn)后，感覺自己的思維又有了新的提高~~
下載 
下載 
下載 
下載 
下載 
下載 
喜歡 
頂
難過
囧
圍觀
無聊
