算法實(shí)現(xiàn)自動(dòng)掃雷游戲

1.游戲的構(gòu)思
2.算法偽代碼的實(shí)現(xiàn)
3.算法的實(shí)現(xiàn)

1.首先需要建立起游戲的整個(gè)框架（棋盤的繪制，地雷的生成，基本函數(shù)的實(shí)現(xiàn)等）
2.構(gòu)思AI算法的大概樣貌（先嘗試寫偽碼）

void AI() //AI算法if（First）SelectRandomPos()//游戲開始隨機(jī)選擇一處位置翻開SelectPos()//根據(jù)已有條件選擇最佳翻開位置if(!GameOver)AI()//遞歸繼續(xù)進(jìn)行選擇，直到游戲結(jié)束

3.簡(jiǎn)單的偽碼寫好后，接下來應(yīng)該來思考如何具體實(shí)現(xiàn)這一算法
3.1對(duì)于SelectRandomPos()實(shí)現(xiàn)隨機(jī)位置，我們可以使用

Col = (rand())%ColNum;Row = (rand())%RowNum;//Col,Row為隨機(jī)翻開的行列坐標(biāo)//ColNum和RowNum為總的行列數(shù) //注意這里的隨機(jī)為偽隨機(jī)，要想真正接近隨機(jī)可以使用下面這段代碼srand((unsigned int)(time(NULL)));int k = (rand())%25;int l = (rand())%14;

參考：用時(shí)間做種子生成隨機(jī)數(shù)
實(shí)現(xiàn)這一函數(shù)功能
3.2對(duì)于函數(shù)SelectPos()，這是我們的重頭戲，這個(gè)函數(shù)我們的作用是實(shí)現(xiàn)選擇最佳翻開位置，在我們不知道當(dāng)前位置是否有雷的情況下，那么我們?nèi)ミx擇呢？我們需要將問題數(shù)字化，定義一個(gè)指數(shù)來判斷，是否應(yīng)該翻開當(dāng)前位置，而概率則可充當(dāng)這一任務(wù)。
我們知道當(dāng)?shù)谝淮畏_時(shí)，我們是隨機(jī)的，那么第二次我們就可以根據(jù)我們已知的條件來判斷了，例如當(dāng)前如圖（1）
對(duì)于當(dāng)前情況我們需要分析當(dāng)前點(diǎn)周圍出現(xiàn)地雷的概率如圖（2）

周圍有Count個(gè)點(diǎn)未被翻開，而周圍顯示有N個(gè)地雷，所以我們可以知道
P=N%Count，得到概率為0.25，注意此處N，P，Count應(yīng)該定義為浮點(diǎn)型。
現(xiàn)在我們應(yīng)該翻開它周圍點(diǎn)嗎？我們還需要思考能不能翻開它周圍以外的點(diǎn)，我稱它為冒險(xiǎn)博弈GetRisk（）；
由于我們已經(jīng)知道，被掀開點(diǎn)周圍有2個(gè)地雷Mine，（如果）地雷(MineNum)和行(Col)列(Row)數(shù)目是已知的，那我們就可以得到除了它周圍以外的點(diǎn)是地雷Mine的風(fēng)險(xiǎn)risk,P=（MineNum-已知地雷數(shù)目）%（Col*Row-9）
將得到的概率相互一比較，得到最優(yōu)選擇。
當(dāng)區(qū)域內(nèi)多點(diǎn)被掀開，我們應(yīng)該如何去考慮它的概率？如圖（3）

但我們掀開周圍點(diǎn)后，發(fā)現(xiàn)另一個(gè)點(diǎn)周圍有三個(gè)地雷，那么如何確定這兩個(gè)點(diǎn)周圍點(diǎn)是地雷的概率呢？
首先我們需要確定新掀開的點(diǎn)周圍有雷的概率，然后再更新前一個(gè)點(diǎn)的概率，注意概率的更新只影響到被掀開點(diǎn)周圍的點(diǎn)。
然后將兩掀開點(diǎn)周圍的點(diǎn)納入一個(gè)數(shù)組MineAround[]中，再計(jì)算被掀開點(diǎn)周圍有雷的概率，注意，這一步的計(jì)算和前面不同，我們先將區(qū)域劃分如圖（4）

計(jì)算區(qū)域1的概率時(shí)，我們暫時(shí)不考慮區(qū)域2，區(qū)域1中右上角的點(diǎn)已經(jīng)被掀開，那么說明確定那一點(diǎn)沒有雷，那么剩下的點(diǎn)是雷的概率是P1=1%7;
同樣對(duì)于區(qū)域二來說它中心點(diǎn)周圍點(diǎn)為雷的概率是：P2=3%7；
然后我們來考慮兩者結(jié)合的情況，對(duì)于兩區(qū)域?yàn)楸幌崎_的點(diǎn)來說它們是雷的概率由它周圍點(diǎn)來確定，例如我們簡(jiǎn)單的舉出兩個(gè)點(diǎn)，如圖（5）
對(duì)于點(diǎn)b的區(qū)域來說，它自身是沒有被掀開的，我們計(jì)算點(diǎn)b是雷的概率就需要通過它周圍的被掀開的點(diǎn)來確定，對(duì)于b來說，在它周圍只有左下角點(diǎn)被掀開，所以我們認(rèn)為點(diǎn)b是雷的概率為Pb=P2=3%7，也就是顯示3的點(diǎn)的周圍點(diǎn)概率。
那么如何確定點(diǎn)a是雷的概率呢？
對(duì)于點(diǎn)a，它周圍有兩個(gè)點(diǎn)被掀開，我們就基于這兩個(gè)點(diǎn)來確定它是雷的概率Pa：
Pa1一定是雷的概率 = （1%7）（3%7）
Pa2一定不是雷的概率 = （6%7）（4%7）
對(duì)于這里我們的目的是知道a不是雷的概率，所以我們?nèi)a = 1-Pa1；
（雖然對(duì)于該點(diǎn)來說只有是雷和不是雷的情況，但是這里只討論可能性）
這樣，當(dāng)我們計(jì)算得到所有周圍點(diǎn)的概率后，比較出一個(gè)最好的概率情況（概率相同時(shí)任意取），然后再與Risk比較，得出最后最優(yōu)選擇點(diǎn)位。

--------------------------------2020/12/17-機(jī)房-----------------------------------------------

顯然在實(shí)際情況中，我們遇到的情況將不會(huì)只有這些，如果單純應(yīng)用上面的算法，那么你掃雷的效率（正確率）是不高的，這是為什么呢？我們需要結(jié)合實(shí)際情況來分析：
如圖（6）：

當(dāng)程序運(yùn)行到這一步的時(shí)候，如圖所示我標(biāo)出的紅色線框
，按照我們的邏輯，對(duì)于紅色線框中的未被掀開點(diǎn)，我們可以確定它不是雷的（因?yàn)樗車奈ㄒ灰活w雷已經(jīng)被發(fā)現(xiàn)-標(biāo)上了旗幟），但是當(dāng)程序?qū)嶋H運(yùn)行的時(shí)候程序會(huì)怎么做呢？如圖（7）
可以看到程序并沒有選擇我們認(rèn)為的最優(yōu)點(diǎn)，這是為什么呢？我們來嘗試通過我們的算法計(jì)算一下最優(yōu)點(diǎn)不是雷的概率：P 1= （3%4）1（1%3）=1%12
對(duì)于走錯(cuò)的那個(gè)點(diǎn)（踩到雷的點(diǎn)），我們計(jì)算一下它不是雷的概率：P2 = （1-2%7）=5%7>P1
程序走得沒錯(cuò)，完全按照了我們的算法來執(zhí)行，但是出現(xiàn)了錯(cuò)誤，說明我們算法還有改進(jìn)的空間，我們忽略了這一種特殊情況，所以我們將它添加上：

for i in MineAround[](已經(jīng)被掀開的點(diǎn)組成的數(shù)組，不包括旗幟，空點(diǎn)和地雷)if i.Prob==0(i周圍為雷的概率為0)then open i.around #在這里，我們加入了一種特殊情況，當(dāng)已經(jīng)被掀開的點(diǎn)中，存在周圍點(diǎn)是雷概率為0的特殊情況是，我們不再比較最優(yōu)選擇（概率），直接打開它的周圍點(diǎn)。

添加代碼后，實(shí)現(xiàn)效果如圖（7）

筆者最近有點(diǎn)忙，更新可能會(huì)很慢。
未完待續(xù)。。。。。。。。

當(dāng)然在實(shí)際調(diào)試情況中，我們不僅僅將只是遇到這些情況，例如： 1.當(dāng)我們遇到確認(rèn)是地雷的點(diǎn)該怎么辦？ 2.當(dāng)我們遇到的所有點(diǎn)周圍是雷的概率都很高（但不確定是雷或者不是雷）怎么辦？ 3.等等等等。。。還需要我們慢慢去探討。

2020/12/15

總結(jié)

以上是生活随笔為你收集整理的算法实现自动扫雷游戏的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。