何軒 洪迎偉 王開譯 彭耶萍

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

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

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2019）34-0053-02

1 概述

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

2 搜索算法

2.1 博弈樹搜索

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

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

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

2.2 極大極小值搜索

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

2.3 α-β剪枝

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

2.4 MCTS樹搜索

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

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

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

舍棄絕對(duì)不合理的局面后，人類棋手一般會(huì)選擇一個(gè)看起來特別有價(jià)值的局面做深入推演，而并不是同時(shí)推演幾個(gè)待選局面。

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

1）選擇

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

2）擴(kuò)展

給該葉子節(jié)點(diǎn)添加一個(gè)新的孩子節(jié)點(diǎn)。

3）模擬

新的孩子節(jié)點(diǎn)進(jìn)行勝率模擬。

4）回溯

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

蒙特卡羅樹能夠快速深入推演比較有價(jià)值的局面，舍棄獲勝概率比較小的節(jié)點(diǎn)，不推演其子節(jié)點(diǎn)，使得搜索深度大大增加，但是也有可能一開始就誤人歧途，因?yàn)榭赡芡蒲莸阶詈蟀l(fā)現(xiàn)推演的這個(gè)分支的勝率沒有其他分支的高。

3 估值函數(shù)

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

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

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

“路”的總數(shù)較少?，F(xiàn)在我們以六子棋為例，按照橫向、縱向、左斜、右斜4個(gè)方向的特點(diǎn)，可以分別計(jì)算出六子棋在各個(gè)方向的“路”的數(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)值，那么對(duì)于六子棋的估值評(píng)估函數(shù)設(shè)計(jì)則是一種優(yōu)化，它不再需要消耗大量的時(shí)間對(duì)棋形進(jìn)行匹配。

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

收稿日期：2019-10-15

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