機器博弈主要技術分析

何軒 洪迎偉 王開譯 彭耶萍

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

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

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

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

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

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

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

1.3位棋盤（Bit Boards）

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

2走法生成

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

3博弈樹與搜索算法

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

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

3.1極大極小值算法

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

3.2 Alpha-Beta剪枝

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

3.3 MCTS樹搜索

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

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

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

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

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

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

4結束語

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