[轉載]十四步實現擁有強大AI的五子棋游戲

又是本人一份人工智能作業……首先道歉，從Word貼到Livewrter，好多格式沒了，也沒做代碼高亮……大家湊活著看……想做個好的人機對弈的五子棋，可以說需要考慮的問題還是很多的，我們將制作擁有強大AI五子棋的過程分為十四步，讓我來步步介紹。

第一步，了解禁手規則

做一個五子棋的程序，自然對五子棋需要有足夠的了解，現在默認大家現在和我研究五子棋之前了解是一樣多的。以這個為基礎，介紹多數人不大熟悉的方面。五子棋的規則實際上有兩種：有禁手和無禁手。由于無禁手的規則比較簡單，因此被更多人所接受。其實，對于專業下五子棋的人來說，有禁手才是規則。所以，這里先對“有禁手”進行一下簡單介紹：

五子棋中“先手必勝”已經得到了論證，類似“花月定式”和“浦月定式”，很多先手必勝下法雖然需要大量的記憶，但高手確能做到必勝。所以五子棋的規則進行了優化，得到了 “有禁手”五子棋。五子棋中，黑棋必然先行。因此“有禁手”五子棋競技中對黑棋有以下“禁手”限制:“三三禁”:黑棋下子位置同時形成兩個以上的三；“四四禁”:黑棋下子位置同時形成兩個以上的四；“長連禁”:六子以上的黑棋連成一線。黑棋如下出“禁手“則馬上輸掉棋局。不過如果“連五”與“禁手”同時出現這時“禁手”是無效的。所以對于黑棋只有沖四活三（后面會有解釋）是無解局面。反觀白棋則多了一種獲勝方式，那就是逼迫黑棋必定要下在禁點。

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

第二步，實現游戲界面

這里，我制作了一個簡單的界面，但是，對于人機對弈來說，絕對夠用。和很多網上的精美界面相比，我的界面也許略顯粗糙，但，開發速度較高，僅用了不到半天時間。下面我們簡單看下界面的做法。

界面我采用了WPF，表現層和邏輯層完全分開，前臺基本可以通過拖拽完成布局，這里就不做過多介紹。根據界面截圖簡單介紹

clip_image002

1處實際上市兩個漸變Label的拼接，2、3是兩個label，4、5實際上是兩個Button，但是沒有做事件響應。通過按鈕6、7、8、9 的控制，修改label和Button的Content屬性。也許有人會奇怪，為什么Button會絲毫看出不出有Button的影子，這里戰友whrxiao寫過一個Style如下

 1 <Style x:Key="ButtonStyle1" TargetType="{x:Type Button}">
 2 <Setter Property="Template">
 3 <Setter.Value>
 4 <ControlTemplate TargetType="{x:Type Button}">
 5 <Grid>
 6 <ContentPresenter HorizontalAlignment="{TemplateBinding HorizontalContentAlignment}" VerticalAlignment="{TemplateBinding VerticalContentAlignment}" SnapsToDevicePixels="{TemplateBinding SnapsToDevicePixels}" RecognizesAccessKey="True"/>
 7 </Grid>
 8 </ControlTemplate>
 9 </Setter.Value>
10 </Setter>
11 </Style>

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

第三步，進行輸贏判斷：

因為規則不同，“無禁手”和“有禁手”的輸贏判斷自然不同。先看無禁手：這個比較簡單，遍歷每個位置，然后從這個位置開始，分別判斷它的四個方向：即橫、豎、左上到右下、左下到右上。每個方向從中間點開始，往兩邊數連子數，然后將兩個方向的連字數加和再加一（中間的棋子）。如果得到大于等于5，那么就說明下子方贏棋。

對于有禁手的五子棋，輸贏判斷還需要判斷禁手，禁手的判定較為復雜。將待判斷點放入黑棋子。然后搜索待判斷點周邊棋盤；還原棋盤；利用搜索結果依次對各方向進行分析，判斷黑棋放入后所產生的棋型是否形成長連或形成某種四連或三連的的棋型。若形成長連，判定為禁手，返回長連禁手標識。若形成某種四連或三連的棋型，該棋型統計數加1，再對下一個方向進行判斷，直到各個方向分析結束。若四連棋型或三連棋型的統計數大于１，則返回為禁手。其余情況返回非禁手。

第四步：構造棋型估分

“有禁手”規則比較復雜，涉及到比較多下棋方面的技巧，而且對算法的思路沒有絲毫影響，所以下面我們主要考慮無禁手規則下的AI設計。若設計好無禁手AI，只需要讓AI執黑時堅決不下到禁手點，就可以很快構造有禁手的AI。雖然這種方式沒有利用有禁手規則下的技巧，但這些技巧只需要修改下面所講到的估分函數即可。

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

成5：即構成五子連珠
活4：即構成兩邊均不被攔截的四子連珠。
死4：一邊被攔截的四子連珠
活3：兩邊均不被攔截的三字連珠
死3：一邊被攔截的三字連珠
活2：兩邊均不被攔截的二子連珠
死2：一邊被攔截的二子連珠
單子：四周無相連棋子

根據五子棋的技巧，可以將五子棋的棋型用連珠進行分類，分類過后我們按照威力給每種棋型打分。因為五子棋一次只落一子，因此很容易理解，雙活三和三活三的威力是一樣的，類似情況不多做解釋。程序中，我以100分為滿分，對棋型進行了以下打分：

成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的基礎，接下來就是一些博弈的方法了。

第五步：得到位置估分AI

單純應用棋譜以及對五子棋當前局勢的分析，對每步進行估分，程序中做如下工作：將每個位置進行分析，假設AI落子在該位置，用以上打分規則為AI打分,并將得到的分數加一。然后，假設玩家落子在該點，為玩家打分，然后將所有的分值匯總。取最高分作為這個位置的估分，接下來就是取分數最高的位置下棋了。“位置估分”，下棋的時候，既可以考慮到自己攻擊對手，又能考慮到對對手的防御，可以說，很多時候可以頂上考慮兩步的AI。作實驗，從網上下載了一個用博弈做的AI，和“位置估分”對下，結果是一勝一負。誰先子，誰贏得勝利。而且一步估分毫無疑問是最快的，即使遍歷所有位置，也能很快的做出決策。

第六步：應用博弈樹，提高AI智能

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

第七步：考慮層數，提高AI智能

上面的設計對于返回值是統一處理的,但是，層數是個很重要的信息.因為下棋時如果能2步獲勝,不應選擇4步獲勝。對于輸的棋型層數就更重要,AI必須盡可能拖延輸的時間，就有更大的可能讓AI化險為夷。這樣，可以通過設置一個dep值。深度約淺，dep越大，用dep和得到的得分相乘，得到搜索節點的得分，再進行以上算法，進一步提高AI的智能。

第八步：應用α-β剪枝，提高AI速度

在搜索博弈樹的過程中，實際上搜索有很多點是多余的，例如下圖

clip_image012

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

當前為AI下棋節點：

α剪枝：如果當前節點的值不比父節點的前兄弟節點的大值大,則舍棄此節點。
β剪枝：如果當前節點子節點的值不比當前節點的前兄弟節點中的最小值小,則舍棄該子節點和該子節點的所有后兄弟節點。

當前為用戶下棋節點：

α剪枝：如果當前節點的某子節點的值不比當前節點的前兄弟節點中的最大值大,則舍棄該子節點和該子節點的所有后兄弟節點。
β剪枝：如果當前節點的子節點的值不比當前的父節點的前兄弟節點中的最小值小則舍棄此節點。

經過α-β剪枝，可以極大的減少搜索的數量，很多時候，能把幾十億的搜索數量，縮小到幾億，那么，就可以把搜索深度增1。

第九步：應用下棋范圍，提高AI速度

當前節點的子節點的數量和排列順序對于搜索的速度起著至關重要的影響。根據五子棋的特點,可以產生一個棋面搜索范圍。記錄當前棋面所有棋子的最左最右最上最下點構成的矩形,我們認為下一步棋的位置不會脫離這個框3步以上。這樣在棋子較少的時候，搜索節點的數量大大減少。可以將AI的速度提高一倍左右。

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

因為每種下法都對應一種得分，所以，可以每次只考慮當前得分前十的節點進行下一步搜索，大大減少了搜索范圍，可以進一步增加搜索的深度。

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

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

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

我們其實可以利用多核技術，利用多個線程，讓算法實現并行計算，提高AI的速度。我們在第一層用一個線程分配器把第二層的候選節點分配給多個線程,每個線程包含著從第二層一個候選節點開始的搜索,然后等所有線程結束后,將所有線程的結果進行匯總,選出最大值。并行的程序，可以將速度提高一倍左右。

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

由于AI算法的固定性，所以一擔玩家一次獲勝，按照相同的走法，必然會再次獲勝。但除了必殺招或者必防招,一個局面很多時候沒有絕對最好的走法。而是有一些都不錯的走法,那么可以把這些評分差不多走法匯集起來,然后隨機選擇它們中的一種走法,避免AI的走法的固定.這樣最簡單的方法避免固定方法AI必輸。

第十四步：讓AI自學習，不再同一個地方犯錯

上面的算法還沒有自學習的能力,這樣AI在下棋時還可能會重蹈覆轍。因此在每盤棋結束時,如果AI輸，則進行大于搜索深度的步數回退。可以把倒數為搜索深度數目的局面定為目標局面，從倒數深度加一步局面進行預測,找到不會導出必敗目標局面的局面。然后記錄下這個局面和前面的局面，并據此修改評分函數。這樣AI就不會犯曾經犯過的錯誤，達到自學習的效果。

做到以上十四步，一個擁有強大AI的五子棋游戲即可誕生！

這篇文章，讓VAllen受益良多，正準備做個高人工智能的五子棋 for Windows 8。

本文轉載自：http://www.cnblogs.com/Blog_SivenZhang/archive/2010/06/13/1757677.html

轉載于:https://www.cnblogs.com/VAllen/articles/WuZiQiStep14Ai.html