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