十四步實(shí)現(xiàn)擁有強(qiáng)大AI的五子棋游戲

博主按：在看到這篇文章的時(shí)候有很深刻的體會(huì)了，畢竟我的大學(xué)第一個(gè)C語(yǔ)言作品就是五子棋，時(shí)隔十多年我用Java在Android重新設(shè)計(jì)了手機(jī)版五子棋游戲，這篇文章對(duì)于五子棋算法的分析有很強(qiáng)的實(shí)用性，有點(diǎn)相見恨晚的感覺(jué)啊，我要接著改進(jìn)AI了。

想做個(gè)好的人機(jī)對(duì)弈的五子棋，可以說(shuō)需要考慮的問(wèn)題還是很多的，我們將制作擁有強(qiáng)大AI五子棋的過(guò)程分為十四步，讓我來(lái)步步介紹。

第一步，了解禁手規(guī)則

做一個(gè)五子棋的程序，自然對(duì)五子棋需要有足夠的了解，現(xiàn)在默認(rèn)大家現(xiàn)在和我研究五子棋之前了解是一樣多的。以這個(gè)為基礎(chǔ)，介紹多數(shù)人不大熟悉的方面。五子棋的規(guī)則實(shí)際上有兩種：有禁手和無(wú)禁手。由于無(wú)禁手的規(guī)則比較簡(jiǎn)單，因此被更多人所接受。其實(shí)，對(duì)于專業(yè)下五子棋的人來(lái)說(shuō)，有禁手才是規(guī)則。所以，這里先對(duì)“有禁手”進(jìn)行一下簡(jiǎn)單介紹：

五子棋中“先手必勝”已經(jīng)得到了論證，類似“花月定式”和“浦月定式”，很多先手必勝下法雖然需要大量的記憶，但高手確能做到必勝。所以五子棋的規(guī)則進(jìn)行了優(yōu)化，得到了 “有禁手”五子棋。五子棋中，黑棋必然先行。因此“有禁手”五子棋競(jìng)技中對(duì)黑棋有以下“禁手”限制:“三三禁”:黑棋下子位置同時(shí)形成兩個(gè)以上的三；“四四禁”:黑棋下子位置同時(shí)形成兩個(gè)以上的四；“長(zhǎng)連禁”:六子以上的黑棋連成一線。黑棋如下出“禁手“則馬上輸?shù)羝寰帧２贿^(guò)如果“連五”與“禁手”同時(shí)出現(xiàn)這時(shí)“禁手”是無(wú)效的。所以對(duì)于黑棋只有沖四活三（后面會(huì)有解釋）是無(wú)解局面。反觀白棋則多了一種獲勝方式，那就是逼迫黑棋必定要下在禁點(diǎn)。

為了迎合所有玩家，五子棋自然需要做出兩個(gè)版本，或者是可以進(jìn)行禁手上的控制。

?

第二步，實(shí)現(xiàn)游戲界面

這里，我制作了一個(gè)簡(jiǎn)單的界面，但是，對(duì)于人機(jī)對(duì)弈來(lái)說(shuō)，絕對(duì)夠用。和很多網(wǎng)上的精美界面相比，我的界面也許略顯粗糙，但，開發(fā)速度較高，僅用了不到半天時(shí)間。下面我們簡(jiǎn)單看下界面的做法。

界面我采用了WPF，表現(xiàn)層和邏輯層完全分開，前臺(tái)基本可以通過(guò)拖拽完成布局，這里就不做過(guò)多介紹。根據(jù)界面截圖簡(jiǎn)單介紹

1處實(shí)際上市兩個(gè)漸變Label的拼接，2、3是兩個(gè)label，4、5實(shí)際上是兩個(gè)Button，但是沒(méi)有做事件響應(yīng)。通過(guò)按鈕6、7、8、9 的控制，修改label和Button的Content屬性。也許有人會(huì)奇怪，為什么Button會(huì)絲毫看出不出有Button的影子，這里戰(zhàn)友whrxiao寫過(guò)一個(gè)Style如下

<Style x:Key="ButtonStyle1" TargetType="{x:Type Button}">

<Setter Property="Template">

<Setter.Value>

<ControlTemplate TargetType="{x:Type Button}">

<Grid>

<ContentPresenter HorizontalAlignment="{TemplateBinding HorizontalContentAlignment}" VerticalAlignment="{TemplateBinding VerticalContentAlignment}" SnapsToDevicePixels="{TemplateBinding SnapsToDevicePixels}" RecognizesAccessKey="True"/>

</Grid>

</ControlTemplate>

</Setter.Value>

</Setter>

</Style>

這里我們把這個(gè)Style稱為Style1。界面邏輯上，將是否開始、是否禁手和是否電腦先行作為兩個(gè)全局變量的布爾型值，通過(guò)設(shè)置和判斷bool型值進(jìn)行邏輯上的控制。中間的棋盤是個(gè)canvas，一個(gè)15*15的Grid放滿Button并將每個(gè)Button應(yīng)用Style1開始時(shí)候透明度設(shè)為0，也就是根本看不到，在下棋的時(shí)候改變Button的背景和透明度，實(shí)現(xiàn)落子的效果，因?yàn)镚rid的位置關(guān)系，所以可看起來(lái)好像是下在橫豎的交線處。

?

第三步，進(jìn)行輸贏判斷：

因?yàn)橐?guī)則不同，“無(wú)禁手”和“有禁手”的輸贏判斷自然不同。先看無(wú)禁手：這個(gè)比較簡(jiǎn)單，遍歷每個(gè)位置，然后從這個(gè)位置開始，分別判斷它的四個(gè)方向：即橫、豎、左上到右下、左下到右上。每個(gè)方向從中間點(diǎn)開始，往兩邊數(shù)連子數(shù)，然后將兩個(gè)方向的連字?jǐn)?shù)加和再加一（中間的棋子）。如果得到大于等于5，那么就說(shuō)明下子方贏棋。

對(duì)于有禁手的五子棋，輸贏判斷還需要判斷禁手，禁手的判定較為復(fù)雜。將待判斷點(diǎn)放入黑棋子。然后搜索待判斷點(diǎn)周邊棋盤；還原棋盤；利用搜索結(jié)果依次對(duì)各方向進(jìn)行分析，判斷黑棋放入后所產(chǎn)生的棋型是否形成長(zhǎng)連或形成某種四連或三連的的棋型。若形成長(zhǎng)連，判定為禁手，返回長(zhǎng)連禁手標(biāo)識(shí)。若形成某種四連或三連的棋型，該棋型統(tǒng)計(jì)數(shù)加1，再對(duì)下一個(gè)方向進(jìn)行判斷，直到各個(gè)方向分析結(jié)束。若四連棋型或三連棋型的統(tǒng)計(jì)數(shù)大于１，則返回為禁手。其余情況返回非禁手。

?

第四步：構(gòu)造棋型估分

“有禁手”規(guī)則比較復(fù)雜，涉及到比較多下棋方面的技巧，而且對(duì)算法的思路沒(méi)有絲毫影響，所以下面我們主要考慮無(wú)禁手規(guī)則下的AI設(shè)計(jì)。若設(shè)計(jì)好無(wú)禁手AI，只需要讓AI執(zhí)黑時(shí)堅(jiān)決不下到禁手點(diǎn)，就可以很快構(gòu)造有禁手的AI。雖然這種方式?jīng)]有利用有禁手規(guī)則下的技巧，但這些技巧只需要修改下面所講到的估分函數(shù)即可。

我們可以將五子棋的連珠可以分為以下幾種：

成5：即構(gòu)成五子連珠

活4：即構(gòu)成兩邊均不被攔截的四子連珠。

死4：一邊被攔截的四子連珠

活3：兩邊均不被攔截的三字連珠

死3：一邊被攔截的三字連珠

活2：兩邊均不被攔截的二子連珠

死2：一邊被攔截的二子連珠

單子：四周無(wú)相連棋子

根據(jù)五子棋的技巧，可以將五子棋的棋型用連珠進(jìn)行分類，分類過(guò)后我們按照威力給每種棋型打分。因?yàn)槲遄悠逡淮沃宦湟蛔?#xff0c;因此很容易理解，雙活三和三活三的威力是一樣的，類似情況不多做解釋。程序中，我以100分為滿分，對(duì)棋型進(jìn)行了以下打分：

成5, 100分

活4、雙死4、死4活3， 90分

雙活3， 80分

死3活3， 70分

死4， 60分

活3， 50分

雙活2， 40分

死3， 30分

活2， 20分

死2， 10分

單子 0分

有了估分方法，就有了五子棋AI的基礎(chǔ)，接下來(lái)就是一些博弈的方法了。

?

第五步：得到位置估分AI

單純應(yīng)用棋譜以及對(duì)五子棋當(dāng)前局勢(shì)的分析，對(duì)每步進(jìn)行估分，程序中做如下工作：將每個(gè)位置進(jìn)行分析，假設(shè)AI落子在該位置，用以上打分規(guī)則為AI打分,并將得到的分?jǐn)?shù)加一。然后，假設(shè)玩家落子在該點(diǎn)，為玩家打分，然后將所有的分值匯總。取最高分作為這個(gè)位置的估分，接下來(lái)就是取分?jǐn)?shù)最高的位置下棋了。“位置估分”，下棋的時(shí)候，既可以考慮到自己攻擊對(duì)手，又能考慮到對(duì)對(duì)手的防御，可以說(shuō)，很多時(shí)候可以頂上考慮兩步的AI。作實(shí)驗(yàn)，從網(wǎng)上下載了一個(gè)用博弈做的AI，和“位置估分”對(duì)下，結(jié)果是一勝一負(fù)。誰(shuí)先子，誰(shuí)贏得勝利。而且一步估分毫無(wú)疑問(wèn)是最快的，即使遍歷所有位置，也能很快的做出決策。

?

第六步：應(yīng)用博弈樹，提高AI智能

做五子棋的博弈，自然會(huì)用到博弈樹，這里我說(shuō)下自己的思路。在對(duì)弈中,根據(jù)下一步由誰(shuí)來(lái)走,AI對(duì)任何一個(gè)局面根據(jù)前面估分方法給出一個(gè)分?jǐn)?shù),我們把這個(gè)估分方法匯總成一個(gè)評(píng)估函數(shù)，并返回分值。據(jù)此來(lái)選擇下一步的走法。由于人和AI是輪流落子，可以將人的估分也算入，并將前面加負(fù)號(hào)。那么，估值越大表明對(duì)AI越有利，估分越小則表明對(duì)AI越不利。那么每次AI選擇都是從它可能的走法樹的某層節(jié)點(diǎn)，返回評(píng)估值中最大點(diǎn)。而用戶總是從走法樹的某層節(jié)點(diǎn)中選擇最小點(diǎn)，從而形成一棵極大極小搜索樹，然后根據(jù)深度優(yōu)先搜索，可以最后得到固定搜索深度下的一個(gè)最好的走法。我做了下試驗(yàn)，單純應(yīng)用博弈樹，可以在100ms之內(nèi)讓AI考慮完整的兩步，由于組合爆炸，當(dāng)需要考慮三步的時(shí)候，就需要6s左右，4步就需要1分鐘。拿兩步來(lái)和一步估分作比較，雖然比較慢，但是確實(shí)有了一定智能。

?

第七步：考慮層數(shù)，提高AI智能

上面的設(shè)計(jì)對(duì)于返回值是統(tǒng)一處理的,但是，層數(shù)是個(gè)很重要的信息.因?yàn)橄缕鍟r(shí)如果能2步獲勝,不應(yīng)選擇4步獲勝。對(duì)于輸?shù)钠逍蛯訑?shù)就更重要,AI必須盡可能拖延輸?shù)臅r(shí)間，就有更大的可能讓AI化險(xiǎn)為夷。這樣，可以通過(guò)設(shè)置一個(gè)dep值。深度約淺，dep越大，用dep和得到的得分相乘，得到搜索節(jié)點(diǎn)的得分，再進(jìn)行以上算法，進(jìn)一步提高AI的智能。

?

第八步：應(yīng)用α-β剪枝，提高AI速度

在搜索博弈樹的過(guò)程中，實(shí)際上搜索有很多點(diǎn)是多余的，例如下圖

圖中，方形框節(jié)點(diǎn)是該AI走,圓形框節(jié)點(diǎn)是該人走.比如C節(jié)點(diǎn),它需要從E和F當(dāng)中選取最大的值。目前已經(jīng)得出E為2,當(dāng)搜索F節(jié)點(diǎn)時(shí),因?yàn)镕是人走的節(jié)點(diǎn)，那么F需要從K L M中選取最小的，因?yàn)镵已經(jīng)是1，也就是說(shuō)F<=1，那么L，M就不需要搜索，因此就發(fā)生了α剪枝。然后看A節(jié)點(diǎn)，該人走了，需要從C和D中選取最小值，因?yàn)镃節(jié)點(diǎn)是2，而G是7，那么D至少是7。因此，D的其他節(jié)點(diǎn)不必再考慮，就發(fā)生如上圖所示的β剪枝。總結(jié)上面規(guī)律，我們可以得到剪枝方法如下：

當(dāng)前為AI下棋節(jié)點(diǎn)：

α剪枝：如果當(dāng)前節(jié)點(diǎn)的值不比父節(jié)點(diǎn)的前兄弟節(jié)點(diǎn)的大值大,則舍棄此節(jié)點(diǎn)。

β剪枝：如果當(dāng)前節(jié)點(diǎn)子節(jié)點(diǎn)的值不比當(dāng)前節(jié)點(diǎn)的前兄弟節(jié)點(diǎn)中的最小值小,則舍棄該子節(jié)點(diǎn)和該子節(jié)點(diǎn)的所有后兄弟節(jié)點(diǎn)。

當(dāng)前為用戶下棋節(jié)點(diǎn)：

α剪枝：如果當(dāng)前節(jié)點(diǎn)的某子節(jié)點(diǎn)的值不比當(dāng)前節(jié)點(diǎn)的前兄弟節(jié)點(diǎn)中的最大值大,則舍棄該子節(jié)點(diǎn)和該子節(jié)點(diǎn)的所有后兄弟節(jié)點(diǎn)。?
β剪枝：如果當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)的值不比當(dāng)前的父節(jié)點(diǎn)的前兄弟節(jié)點(diǎn)中的最小值小則舍棄此節(jié)點(diǎn)。

經(jīng)過(guò)α-β剪枝，可以極大的減少搜索的數(shù)量，很多時(shí)候，能把幾十億的搜索數(shù)量，縮小到幾億，那么，就可以把搜索深度增1。

?

第九步：應(yīng)用下棋范圍，提高AI速度

當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)的數(shù)量和排列順序?qū)τ谒阉鞯乃俣绕鹬陵P(guān)重要的影響。根據(jù)五子棋的特點(diǎn),可以產(chǎn)生一個(gè)棋面搜索范圍。記錄當(dāng)前棋面所有棋子的最左最右最上最下點(diǎn)構(gòu)成的矩形,我們認(rèn)為下一步棋的位置不會(huì)脫離這個(gè)框3步以上。這樣在棋子較少的時(shí)候，搜索節(jié)點(diǎn)的數(shù)量大大減少。可以將AI的速度提高一倍左右。

?

第十步：利用棋型得分，提高AI速度

因?yàn)槊糠N下法都對(duì)應(yīng)一種得分，所以，可以每次只考慮當(dāng)前得分前十的節(jié)點(diǎn)進(jìn)行下一步搜索，大大減少了搜索范圍，可以進(jìn)一步增加搜索的深度。

第十一步：利用置換表，提高AI速度

?

我們一般用遞歸的方法實(shí)現(xiàn)博弈樹，但是，遞歸的效率是低的，而且很明顯，有很多重復(fù)搜索的節(jié)點(diǎn)，所以，我們可以用一個(gè)表，記錄下所有搜索過(guò)節(jié)點(diǎn)的情況，然后只要遇到搜索到的節(jié)點(diǎn)，就可以直接得到結(jié)果。置于這個(gè)“表”是什么，就是一個(gè)置換表，利用Zobrist算法，進(jìn)行Hash處理，使在表中查找的時(shí)間大大縮短，這樣AI的速度又能提高一個(gè)數(shù)量級(jí)。

?

第十二步：利用多線程，提高AI速度

我們其實(shí)可以利用多核技術(shù)，利用多個(gè)線程，讓算法實(shí)現(xiàn)并行計(jì)算，提高AI的速度。我們?cè)诘谝粚佑靡粋€(gè)線程分配器把第二層的候選節(jié)點(diǎn)分配給多個(gè)線程,每個(gè)線程包含著從第二層一個(gè)候選節(jié)點(diǎn)開始的搜索,然后等所有線程結(jié)束后,將所有線程的結(jié)果進(jìn)行匯總,選出最大值。并行的程序，可以將速度提高一倍左右。

?

第十三步：利用隨機(jī)化算法，讓確定方法不能必勝

由于AI算法的固定性，所以一擔(dān)玩家一次獲勝，按照相同的走法，必然會(huì)再次獲勝。但除了必殺招或者必防招,一個(gè)局面很多時(shí)候沒(méi)有絕對(duì)最好的走法。而是有一些都不錯(cuò)的走法,那么可以把這些評(píng)分差不多走法匯集起來(lái),然后隨機(jī)選擇它們中的一種走法,避免AI的走法的固定.這樣最簡(jiǎn)單的方法避免固定方法AI必輸。

?

第十四步：讓AI自學(xué)習(xí)，不再同一個(gè)地方犯錯(cuò)

上面的算法還沒(méi)有自學(xué)習(xí)的能力,這樣AI在下棋時(shí)還可能會(huì)重蹈覆轍。因此在每盤棋結(jié)束時(shí),如果AI輸，則進(jìn)行大于搜索深度的步數(shù)回退。可以把倒數(shù)為搜索深度數(shù)目的局面定為目標(biāo)局面，從倒數(shù)深度加一步局面進(jìn)行預(yù)測(cè),找到不會(huì)導(dǎo)出必?cái)∧繕?biāo)局面的局面。然后記錄下這個(gè)局面和前面的局面，并據(jù)此修改評(píng)分函數(shù)。這樣AI就不會(huì)犯曾經(jīng)犯過(guò)的錯(cuò)誤，達(dá)到自學(xué)習(xí)的效果。

做到以上十四步，一個(gè)擁有強(qiáng)大AI的五子棋游戲即可誕生！

?

轉(zhuǎn)自：http://www.cnblogs.com/goodness/archive/2010/05/27/1745756.html

總結(jié)

以上是生活随笔為你收集整理的（转载）十四步实现拥有强大AI的五子棋游戏的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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