機器博弈中搜索策略和估值函數的設計

2019-03-04 11:05:01何軒洪迎偉王開譯彭耶萍

電腦知識與技術 2019年34期

何軒洪迎偉王開譯彭耶萍

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

關鍵詞：六子棋;搜索算法;估值函數

中圖分類號：TP391 文獻標識碼：A

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

1 概述

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

2 搜索算法

2.1 博弈樹搜索

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

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

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

2.2 極大極小值搜索

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

2.3 α-β剪枝

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

2.4 MCTS樹搜索

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

1）即使剪枝過后，推導的局面還是太多。

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

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

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

1）選擇

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

2）擴展

給該葉子節點添加一個新的孩子節點。

3）模擬

新的孩子節點進行勝率模擬。

4）回溯

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

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

3 估值函數

3.1 基于“路”和“棋型”結合的估值函數設計

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

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

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

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（路）。如果我們采用“路”來預判棋形狀態值，那么對于六子棋的估值評估函數設計則是一種優化，它不再需要消耗大量的時間對棋形進行匹配。

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

參考文獻：

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

[2]周新林.六子棋博弈系統設計與實現[J].軟件導刊，2015，14（3）：92-94.

[3]閔文杰.六子棋計算機博弈關鍵技術研究[D].重慶：重慶交通大學，2010：88.

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