何軒 洪迎偉 王開譯 彭耶萍

摘要：機器博弈是人工智能的頭部領(lǐng)域。該文以六子棋為例，重點介紹了搜索策略和估值函數(shù)的設(shè)計，主要介紹了博弈樹，極大極小值算法，α-β剪枝，MCTS以及基于“路”和“棋型”結(jié)合的估值函數(shù)。

關(guān)鍵詞：六子棋;搜索算法;估值函數(shù)

中圖分類號：TP391 文獻標(biāo)識碼：A

文章編號：1009-3044（2019）34-0053-02

1 概述

作為二十一世紀(jì)三大尖端技術(shù)之一的人工智能，其頭部研究領(lǐng)域的機器博弈被認(rèn)為是最富有挑戰(zhàn)性的項目之一。而由吳毅成教授所提出的六子棋，以其玩法簡單，情況多變，豐富的樂趣性吸引了大量玩家，并且成為機器博弈的競賽項目之一。

2 搜索算法

2.1 博弈樹搜索

搜索的目的不僅是找出當(dāng)前所有可以落子的地方，還要考慮到之后更多步數(shù)所產(chǎn)生的情況。博弈樹指的是以樹的形式把對手和計算機所有落子的情況表示出來。

該博弈樹以當(dāng)前局面為根節(jié)點，每一個節(jié)點表示一個推導(dǎo)的局面，每一層表示一方所有可能的落子情況，樹的層數(shù)表示搜索深度。該樹描述的是以當(dāng)前局面為起始，走n步以后的所有情況。

單純的博弈樹效率很低，所以真正的棋手那樣，過濾掉許多不需要考慮的情況，降低搜索的深度，通過改進算法實現(xiàn)在規(guī)定時間求出最佳路徑。

2.2 極大極小值搜索

假設(shè)雙方都采用最佳的策略，每一種局面都通過估值函數(shù)來確定局面的好壞，那么對于己方來說每次都要選擇最好的，每次都認(rèn)為對方選擇的是最佳策略，選擇估值最低的局面展開博弈樹。

2.3 α-β剪枝

α—β剪枝是在極大極小值搜索的基礎(chǔ)上，舍棄每一次局面沒有必要繼續(xù)搜索下去的情況。對于MAX的情況來說，只保留最大的分支，對于MIN的情況，只保留最小的分支。

2.4 MCTS樹搜索

如果直接把α-β剪枝算法直接應(yīng)用于實際的機器博弈，會有幾個問題。

1）即使剪枝過后，推導(dǎo)的局面還是太多。

2）對于每一個局面，如果為了得出每一層準(zhǔn)確的估值，而進行相同時間的搜索，會導(dǎo)致搜索的深度不夠，無法建立更加深層次的博弈樹。

舍棄絕對不合理的局面后，人類棋手一般會選擇一個看起來特別有價值的局面做深入推演，而并不是同時推演幾個待選局面。

蒙特卡羅樹分為四個部分，圖中每一個結(jié)點代表一種推導(dǎo)出來的局面，左邊是總勝利次數(shù)，右邊是總模擬次數(shù)。

1）選擇

從根節(jié)點開始依次遍歷孩子節(jié)點中勝率最高的，直到葉子節(jié)點。

2）擴展

給該葉子節(jié)點添加一個新的孩子節(jié)點。

3）模擬

新的孩子節(jié)點進行勝率模擬。

4）回溯

把模擬結(jié)果從孩子節(jié)點開始一直回溯到根節(jié)點本身。

蒙特卡羅樹能夠快速深入推演比較有價值的局面，舍棄獲勝概率比較小的節(jié)點，不推演其子節(jié)點，使得搜索深度大大增加，但是也有可能一開始就誤人歧途，因為可能推演到最后發(fā)現(xiàn)推演的這個分支的勝率沒有其他分支的高。

3 估值函數(shù)

3.1 基于“路”和“棋型”結(jié)合的估值函數(shù)設(shè)計

現(xiàn)在大部分的棋博弈中，都是基于棋形結(jié)構(gòu)的分析，這種結(jié)構(gòu)有一種高度模型匹配的算法在里面，所以這就對于準(zhǔn)確定位棋形的模型的要求很高。不僅模型構(gòu)建對空間的占用率大，而且后期計算機對棋形的匹配費時較大，這樣使得算法的時間和空間復(fù)雜度都很高。因此對棋形的預(yù)判效率是衡量“棋型”估值函數(shù)算法好壞的關(guān)鍵。六子棋常見棋形有19種，常用的位置信息有眠五、眠四、活五、活四，每一種棋形又存在多種交叉情況如圖1、圖2，這就更加使得對棋形的預(yù)判難度加大，所以如何有效和精準(zhǔn)地預(yù)判，搜索棋形，已經(jīng)成為六子棋機器博弈的難題。

下面，我們分析一下“路”這種思想是如何在棋盤中進行模擬的？我們現(xiàn)實當(dāng)中的路，有彎曲的、有筆直的，但是在棋盤當(dāng)中，“路”的思想，其實就是數(shù)學(xué)理論中的一個結(jié)論，即若知道兩個點，那么在兩點之間必定可以確定一條直線。所以在棋盤中的“路”，就是指在棋盤上存在兩顆棋子，在這兩顆棋子之間，還經(jīng)過了4枚同色的棋子。由于每條“路”都是連續(xù)的6個點位，如果把每一個位點換成0和1的二進制碼，白棋是10，黑棋是01，空格是00，然后用計算機的空間數(shù)組存儲每一條路的串碼，那么對于計算機的預(yù)判和運算是不是得到了很大的優(yōu)化。例如，某“路”中已經(jīng)存在4顆子，就不用再去判斷它到底是活四、眠四、跳四等棋形。同時，如果把“路”定義為一種類，“路”的一些特點是類的屬性，那么我們就可以利用面向?qū)ο蟮乃枷?，對“路”的估值函?shù)進行優(yōu)化。這樣能方便地予以實現(xiàn)“路”的特點，以便于預(yù)判。

“路”的總數(shù)較少?，F(xiàn)在我們以六子棋為例，按照橫向、縱向、左斜、右斜4個方向的特點，可以分別計算出六子棋在各個方向的“路”的數(shù)目和情況：

1）橫向，19行x （19 - 6+1）路/行=266路，如圖3的三種情況;

2）縱向，19列x（19- 6+1）路/列=266路;如圖4的四種情況;

3）左斜，14行x （19 - 6+1）路/行=196路;如圖5的四種情況;

4）右斜，14列x （19- 6+1）路/列=196路;如圖6的四種情況。

因此，在19x19圍棋盤上，總共有266x2+ 196x2= 924（路）。如果我們采用“路”來預(yù)判棋形狀態(tài)值，那么對于六子棋的估值評估函數(shù)設(shè)計則是一種優(yōu)化，它不再需要消耗大量的時間對棋形進行匹配。

到了這里，我們又要回到之前對“棋形”模型匹配的估值函數(shù)算法的問題和不足，前面講的“路”值估值方法，可以說是對棋局評估函數(shù)的一種建立和優(yōu)化。

參考文獻：

[1]李學(xué)俊.六子棋中基于局部“路”掃描方式的博弈樹生成算法[J].智能系統(tǒng)學(xué)報，2015，10（2）：267-272.

[2]周新林.六子棋博弈系統(tǒng)設(shè)計與實現(xiàn)[J].軟件導(dǎo)刊，2015，14（3）：92-94.

[3]閔文杰.六子棋計算機博弈關(guān)鍵技術(shù)研究[D].重慶：重慶交通大學(xué)，2010：88.

[4]陳光年.基于智能算法的六子棋博弈行為選擇的應(yīng)用研究[D].重慶：重慶理工大學(xué)2010：76.

[5]王小龍.連珠模式棋類博弈的搜索優(yōu)化[D].合肥：安徽大學(xué)，2014：74.

[6]張小川.六子棋博弈的評估函數(shù)[J].重慶：重慶理工大學(xué)學(xué)報：自然科學(xué)版，2010，24（2）：64-68.

【通聯(lián)編輯：朱寶貴】

收稿日期：2019-10-15

作者簡介：何軒（1999-），男，吉首大學(xué)軟件工程專業(yè)本科在讀;洪迎偉（2001-），男，吉首大學(xué)軟件工程專業(yè)本科在讀;王開譯（1999—），男，吉首大學(xué)軟件工程專業(yè)本科在讀;彭耶萍（1981-），女，主要研究方向為數(shù)據(jù)挖掘及算法。