黑白棋AI設計探究

黃海同

摘要：與博弈有關的算法近年來取得了巨大進步，將這些算法應用于黑白棋AT設計可以帶來顯著的效果。該文所述的探究中，將傳統(tǒng)的AI算法針對黑白棋做一些有效的改進，并使用MCTS搜索、機器學習等方法，很大程度上提高了AT的水平。

關鍵詞：黑白棋；人工智能；算法

中圖分類號：TP18 文獻標識碼：A 文章編號：1009-3044（2016）29-0198-03

1簡介

黑白棋是被稱為“設計理念”僅次于圍棋的棋類游戲。它的棋盤只有8*8大，乍一看貌似簡單，以為只要略微搜索就可以窮盡其中的路數(shù)。然而隨著探究的不斷深入，這個看似簡單的游戲卻不斷涌現(xiàn)出它神秘莫測的一面。

作為一名高中生，經(jīng)過為數(shù)不多課余時間的努力，我所設計的黑白棋程序bwcore實力已經(jīng)達到相當?shù)乃?。?jīng)測試，它在北京大學人工智能對抗平臺botzone.org上戰(zhàn)力排行達到第一。通過與另外一些AI的測試表明，目前的bwcore可以輕易打敗國內(nèi)個人編寫的程序，亦能與專業(yè)公司開發(fā)的黑白棋軟件（zebra，傷心黑白棋等）相抗衡。

本篇著重講述了bwcore是如何更好地運用各類算法，使之融入到黑白棋AI設計中，達到提高AI水平的目的。本文還對AI設計作了一定程度的研究，先是介紹了一些較基礎的算法在黑白棋AI設計中的應用，而后還探討了實現(xiàn)AI的一些更高級的方法，以求有所突破。

2AI設計

2.1Minimax搜索

Minimax搜索的第一要義是雙方都按照對自己最有利的決策，對盤面進行模擬。如果能夠評價某一時刻其中一方的優(yōu)劣程度，則另一方走棋時就會選一種使對方優(yōu)勢盡可能小的走法。如圖所示，按照這種方式模擬出井字棋所有可能的局面，所有局面就構成一棵極大極小博弈樹。

根據(jù)上述做法，不難寫出簡易MiniMax搜索的代碼。當搜索達到指定深度后，進行當前局面的分值估算。val為當前層的分值，當前層的顏色與己方相同時，使之盡可能大。

float Cmp_BW：：MaxMinSearch（Map&fmap，int col，int deep）

{

if deep>target_deep Then

search_cnt++；

return Sence_Evalution

For-Each place_in_board

If place_is_availaleThen

MakeMove

ret=MaxMinSearch（board.color_other，deep+1）；

UnMakeMove

if col==my_color Then

2.2剪枝與改進

Minimax算法提供了一種在博弈樹上尋求最優(yōu)解的方法，但缺點很明顯。算法需要遍歷博弈樹上所有可能的情況，盡管很多時候是根本不可能的（例如一方選擇了一個明顯劣勢的位置）。通過AlphaBeta剪枝可以減少這種情況發(fā)生。如果當前結點獲得的值已經(jīng)小于其父節(jié)點之前得出的值，那么就沒有繼續(xù)搜索的必要，因為按照選擇的邏輯，這個節(jié)點一定會被父節(jié)點排除在外。

經(jīng)測試，搜索的節(jié)點數(shù)明顯減少，約為原來的3/4次方。

測試表明，一般人已經(jīng)難以戰(zhàn)勝4～5層的搜索了。而把搜索深度設定為4層可以在botzone排行榜上達到約40名。

3高級搜索方法

3.1蒙特卡洛搜索

谷歌的圍棋智能AlphaGo就使用了基于蒙特卡洛樹搜索（MCTS）的搜索方式。MCTS在圍棋領域十分成功，在其他方面也有很大的借鑒意義。

蒙特卡洛搜索通過對局面的隨機模擬來獲得對各個節(jié)點搜索的關注程度，可以說在理念上很接近人的思維方式。UCT算法是蒙特卡洛搜索的一種，旨在得分未知的前提下使期望得分最大。UCT算法為每一個節(jié)點計算UCB值，每次擴展時選擇UCB最大的節(jié)點。

其中，X表示以前的收益，N表示總次數(shù)，T表示當前階段的次數(shù)。這個式子的蘊含的內(nèi)容是，如果一個節(jié)點的得分很高，那么就它很值得深入研究，而一些得分較低的節(jié)點有時也會去嘗試，但次數(shù)不會很多。在極端條件下，多個選擇方案中有一個方案的值遠好于其他方案，則UCT算法的收斂速度很快。另一方面，如果所有方案得分相差不大，UCT隨著搜索次數(shù)的增加，所有節(jié)點的得分趨于穩(wěn)定。

結果表明單純的UCT算法效率極高，經(jīng)過很少時間就估算出精確值相近的結果。但因有時隨機選點得出結果差異大，下棋時偶爾會出現(xiàn)失誤。但總體而言，樸素的UCT算法的效果已經(jīng)很優(yōu)秀，測試過程中棋力超過前面基于MiniMax搜索的算法?？梢韵胍姡绻茉赟imulation過程中加以優(yōu)化，還有很大提升空間。

3.2遺傳算法

遺傳算法也是比較好的搜索方式，它通過借鑒生物界的進化規(guī)律來加強搜索。將前面的搜索局面各行列情況視為遺傳算子，搜索過程中經(jīng)過交叉、變異算子，評估新算子的可靠程度，將進化較成功算子反作用于搜索，每次得出更好的搜索方法。具體過程如下：

1）隨機生成n個個體作為迭代的初始群體；

2）計算群體中每個個體的適應程度；

3）進行選擇，把適應度高的個體的基因傳遞給下一代；

4）使新生成個體的基因交叉互換；

5）對基因做一定程度的變異；

6）返回2），除非適應度達到指定水平或已經(jīng)達到最大迭代次數(shù)。

經(jīng)過多次迭代，適應度高（這里即勝率高）的基因將遺傳下來，最終得到高度適應的群體，即我們下一步所期望的走法。

4機器學習與增強學習

前面的幾種搜索方法比原先單純的搜索更具智能性，有更高的效率。目前為止，我們還未對局面的評估做出很好的改進。而估價函數(shù)的選取十分困難，大多依靠編寫者自己的直覺，有時為了讓某個權重來達到合適的值，還要耗費大量時間進行試驗并調節(jié)。所幸，運用機器學習的方法可以使這些問題得到較好的解決。

4.1決策樹與隨機森林

決策樹（Decision Tree）是其中一種比較簡單的做法。決策樹可用于對帶標簽數(shù)據(jù)的分類，并可以在相對短的時間得出效果良好的結果。依照數(shù)據(jù)標注的特點，決策樹的每一個分支對這些樣本進行劃分，最終使樣本按照標簽歸類。預測時，將想要預測的數(shù)據(jù)選擇相應分支找到對應的歸屬即可。

在黑白棋中，如果將黑方獲勝視為樣本中的正類，白方獲勝視為負類，棋盤上黑白棋子的位置作為樣本的標簽，就可以將對局面的評價轉化為分類問題。決策樹通過不停尋找最優(yōu)分裂使數(shù)據(jù)更好地被分離。這里使用C4.5算法，通過信息熵獲得最優(yōu)分裂。由于單純使用棋子的位置作為標簽信息量較大且十分復雜，容易造成一種稱為過擬合的問題。將決策樹上改為隨機森林，可以避免了過擬合，節(jié)約了訓練時間。

4.2神經(jīng)網(wǎng)絡算法

人工神經(jīng)網(wǎng)絡是當下計算機話題最熱門的內(nèi)容之一。神經(jīng)網(wǎng)絡的種類繁多，BP神經(jīng)網(wǎng)絡是神經(jīng)網(wǎng)絡中最簡單的一種模型。

BP神經(jīng)網(wǎng)絡的結構如圖，左邊為輸入層節(jié)點，右邊為輸出層節(jié)點，中間包含一個或多個隱含層。

每個神經(jīng)元從其上一層獲得輸入，將輸入通過自身權值和閾值變換后施以適當激活函數(shù)，傳遞到下一次神經(jīng)元。這樣的過程稱為正向傳遞（Fowed Transfer）過程。根據(jù)正向傳遞得到的網(wǎng)絡輸出與訓練目標比較計算當前網(wǎng)絡的誤差，然后向前調整各個神經(jīng)元權值，就是所謂的反向傳遞（Reverse Transfer）過程。BP網(wǎng)絡不停通過這種方式訓練減小誤差，最終使每個訓練輸入都收斂于目標輸出。

這里使用棋盤上黑白棋子的分布作為輸入層節(jié)點，用01表示，輸出層表示輸贏棋子數(shù)。訓練結果表明，雖然目前的網(wǎng)絡能較好地擬合訓練集中的局面，但對于推廣與訓練集不同的輸入數(shù)據(jù)較為困難，這可能是因為當前所使用網(wǎng)絡的局限性。此外，BP神經(jīng)網(wǎng)絡隱含層的層數(shù)不宜過多，否則收斂十分緩慢。使用深度學習中更高級的神經(jīng)網(wǎng)絡如卷積神經(jīng)網(wǎng)絡（CNN）等應該能夠得到更好的效果，但過程比較復雜，目前個人難以實現(xiàn)。

4.3訓練方式

學習算法需要進行訓練，一種方式是使用接近后期時搜索得出的結果，這種方式獲得樣本的準確度較高。如果按照終局搜索步數(shù)15-20步計，訓練好的AI將可以在近30步時獲取很大優(yōu)勢。

//用后期對局結果作為樣本訓練

void Cmp_BW：：train（int repeat）

For lxain_count

For remain_step>target_step

run_easy（map）//使用簡單方式下棋，節(jié)約時間

score=getScore（map）//獲得比分

deetree.tmin（map，score）；//用樣本訓練

5總結

本次設計AI運行結果已經(jīng)超過了預期的目標，此前沒有想到過可以在排行榜占據(jù)第一的位置。當然，目前算法距離其所能達到的最高水準還有較大差距，因為看起來還有一些明顯的改進方案。不過，作為一個純屬興趣愛好出發(fā)而編寫的程序，能夠取得較好的結果已令人滿意。由于無法在這方面投入太多的時間，所以目前本人對黑白棋AI的研究大致到此，希望將來能夠繼續(xù)深入探究這一方面的問題。