黃海同

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

關(guān)鍵詞：黑白棋；人工智能；算法

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）29-0198-03

1簡(jiǎn)介

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

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

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

2AI設(shè)計(jì)

2.1Minimax搜索

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

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

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剪枝與改進(jìn)

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

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

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

3高級(jí)搜索方法

3.1蒙特卡洛搜索

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

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

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

結(jié)果表明單純的UCT算法效率極高，經(jīng)過很少時(shí)間就估算出精確值相近的結(jié)果。但因有時(shí)隨機(jī)選點(diǎn)得出結(jié)果差異大，下棋時(shí)偶爾會(huì)出現(xiàn)失誤。但總體而言，樸素的UCT算法的效果已經(jīng)很優(yōu)秀，測(cè)試過程中棋力超過前面基于MiniMax搜索的算法。可以想見，如果能在Simulation過程中加以優(yōu)化，還有很大提升空間。

3.2遺傳算法

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

1）隨機(jī)生成n個(gè)個(gè)體作為迭代的初始群體；

2）計(jì)算群體中每個(gè)個(gè)體的適應(yīng)程度；

3）進(jìn)行選擇，把適應(yīng)度高的個(gè)體的基因傳遞給下一代；

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

5）對(duì)基因做一定程度的變異；

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

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

4機(jī)器學(xué)習(xí)與增強(qiáng)學(xué)習(xí)

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

4.1決策樹與隨機(jī)森林

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

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

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

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

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

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

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

4.3訓(xùn)練方式

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

//用后期對(duì)局結(jié)果作為樣本訓(xùn)練

void Cmp_BW：：train（int repeat）

For lxain_count

For remain_step>target_step

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

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

deetree.tmin（map，score）；//用樣本訓(xùn)練

5總結(jié)

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