機器博弈主要技術(shù)分析

何軒 洪迎偉 王開譯 彭耶萍

摘要：該文針對機器博弈中常見的技術(shù)和各種優(yōu)化方法以六于棋為例進行分析和討論，從棋盤表示、走法生成、博弈樹與搜索算法這三個方面進行展開，從各種技術(shù)的優(yōu)缺點出發(fā)，為機器博弈新思路提供了參考。

關(guān)鍵詞：機器博弈;六子棋;博弈樹;搜索算法;蒙特卡羅樹;剪枝

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

文章編號：1009-3044（2019）33-0172-02

機器博弈是人工智能領(lǐng)域最富挑戰(zhàn)性的項目之一，而六子棋作為一種典型的博弈類競技游戲，相比五子棋黑棋先手必勝的單調(diào)不公平性，其公平性到目前為止還不能被證偽，其狀態(tài)空間大小（約為10¹⁷²）為五子棋（約為10¹⁰⁵）的10⁷²倍，搜索結(jié)點數(shù)大大增加，極具挑戰(zhàn)性。因此，以六子棋作為研究機器博弈的切人點既能促進六子棋的發(fā)展，同時也可推動機器博弈乃至人工智能領(lǐng)域的進步。

六子棋的棋盤大小為19行19列，其規(guī)則為：黑棋先手一子，以后白黑輪流落二子，在縱、橫、斜任意一條直線上先連成六子（或六子以上）者獲勝。如下滿棋盤仍未分出輸贏則判為平局。

占用空間同二維數(shù)組，但如能利用某種方法提取待搜索的特征信息作為模式串，便可借助模式匹配算法，把遞歸搜索轉(zhuǎn)換成線性匹配，提高效率。

1.3位棋盤（Bit Boards）

為提高運算速度、減少存儲空間，常采用位棋盤的方式來表示數(shù)據(jù)，在六子棋中，棋盤上只可能出現(xiàn)：空、黑子、白子這三種情況，使用二進制表示至少需要2位。棋盤上每行共19個點，需要至少38位，考慮使用一個長整型（占8個字節(jié)共64位）則整個棋盤需要19*8B，共152B。利用位進行存儲，可以使用邏輯運算來處理問題，其效率遠高于其他運算。

2走法生成

走法生成即將下一步落子的所有合法位置枚舉出來。枚舉走法的過程往往依賴搜索，因此一個好的走法生成策略是博弈系統(tǒng)效率提升的關(guān)鍵。常見的走法生成策略有：預置表、棋盤掃描、Null-Move啟發(fā)（空著啟發(fā)）以及它們的結(jié)合等。預置表：存儲所有可行的走法，生成走法時直接查表，優(yōu)點即速度快，缺點即局限于規(guī)則較多且走法有限的棋類。棋盤掃描：即按照規(guī)則對棋盤區(qū)域進行遍歷，確定落子位置。Null-Move啟發(fā)（空著啟發(fā)）：假設一方先不動，讓另一方多落子一輪，然后搜索動方獲勝的迫著序列，此時對于不動方來說只需重點防范這個序列，產(chǎn)生的防范區(qū)域稱為R-Zone，不動方便只需在R-Zone中生成走法，大大減少了搜索空間，提高了搜索效率，缺點即工于防范而疏于進攻，難以獲勝乃至防不勝防而落敗，因此空著啟發(fā)常常與其他算法結(jié)合使用。

3博弈樹與搜索算法

博弈樹即對博弈局面及其未來可能性的抽象。就六子棋而言，博弈雙方輪流交替回合，這種情況能夠抽象成一顆與或樹。“與”指我方需要考慮所有的走法，走法之間是與的關(guān)系，或表示對方可能選擇眾多走法中的任意一種。其中交替表現(xiàn)在樹中偶數(shù)層結(jié)點為我方（黑子），奇數(shù)層為對方。

在建立博弈樹的過程中評估函數(shù)需要對每個結(jié)點評估。所謂評分就是給當前棋局打分，對我方越有利分數(shù)越高，反之分數(shù)越低。搜索則是遍歷博弈樹的過程，目前來說，幾乎所有的搜索算法都基于極大極小值思想。

3.1極大極小值算法

在與或博弈樹的基礎上，假設一方為我方，則在搜索的過程中我方回合時總是選擇評分最高的結(jié)點，而輪到對方時，總是選擇評分最低的結(jié)點。

3.2 Alpha-Beta剪枝

極大極小值算法在搜索的過程需要完整遍歷博弈樹的每個結(jié)點，然而有很多結(jié)點不會對局面產(chǎn)生貢獻，如果能夠去掉對這些無用結(jié)點的遍歷，算法的效率就能夠得到極大的提升，這也是一系列改進算法的著手點。對于Mpha-Beta算法來說，它通過改變搜索的上下界來縮小搜索空間，即所謂的剪枝。

3.3 MCTS樹搜索

大名鼎鼎的MphaGoZero也是基于該算法，MCTS即蒙特卡羅樹搜索。雖然同樣通過剪枝來縮小搜索空間，與Mpha-Beta不同的是，它對結(jié)點的評判依據(jù)不是人為構(gòu)造的評估函數(shù)，而是蒙特卡羅模擬，所以隨著搜索深度增加，越接近最優(yōu)解，收斂較快。尤其適合應用于分支較多的搜索問題。該搜索算法主要有四個部分：選擇、擴展、模擬以及回溯更新。

選擇階段，從起點開始遞歸地對評價最高的結(jié)點進行搜索，評價一般采用UCT策略，該策略在搜索時采用UCB算法（Upper Confidence Bounds置信區(qū)間上界）其思想是：先對起點所有的子結(jié)點都搜索一遍，按照公式③計算每個結(jié)點的分數(shù)，然后選擇分數(shù)高的繼續(xù)搜索。

s指當前結(jié)點，p表示父結(jié)點Score，表示當前結(jié)點的分數(shù)，p（s）表示當前結(jié)點的累計分數(shù)，N表示結(jié)點的訪問次數(shù)，c是一個自定常數(shù)。

擴展階段，選中一個結(jié)點對其進行擴展子節(jié)點。

模擬階段，根據(jù)蒙特卡羅模擬方法對拓展出的子節(jié)點進行模擬，即隨機選擇一個可落子位置作為其子節(jié)點，然后子節(jié)點繼續(xù)模擬，直到博弈結(jié)束。

更新階段，將子結(jié)點的得分累加到其父節(jié)點，不斷從下向上累加更新。

4結(jié)束語

限于版面以及評估函數(shù)的差異性，本文沒有詳細討論評估函數(shù)部分。機器博弈所涉及的領(lǐng)域較多，作者僅以所了解進行討論，希望能給讀者一點收獲。