愛恩斯坦棋計算機博弈算法研究與改進

楊昌杰 陳柯成 劉躍元 王京

摘要：人工智能技術高速發展，作為人工智能領域的重要方向——計算機博弈蓬勃開展，愛恩斯坦棋作為計算機博弈的一類棋種，是中國大學生計算機博弈大賽的比賽項目，具有信息不完全、走棋受概率影響等特點。文章通過對愛恩斯坦棋的搜索算法進行系統研究，提出基于定式處理的改進型Alpha-Beta剪枝算法，經驗證該算法可以提高在博弈比賽中的勝率。

關鍵詞：人工智能；愛恩斯坦棋；Alpha-Beta剪枝；定式處理

計算機博弈[1]是人工智能的重要組成部分，計算機博弈的杰出代表Alpha-Go[2]所應用的圍棋是一種完全信息的博弈棋種。然而，愛恩斯坦棋是一種不完全信息博弈棋種，同時，愛恩斯坦棋的走棋棋子是通過擲骰子決定的，所以具有隨機性。同時雙方都不能提前判斷對手的下一步走棋棋子，導致信息的不完全性。對比圍棋中使用蒙特卡洛樹搜索（Monte Cairo Tree Search，MCTS）算法，愛恩斯坦棋棋盤較小、棋子數較少，使用Alpha-Beta剪枝算法具有數據處理相對較少、輕便容易等優勢，非常適合愛恩斯坦棋的搜索處理。但是在博弈游戲中由于受到行棋走時間的限制，如若不對搜索算法加以處理，在較高層次的搜索情況下，仍會存在搜索時效相對較慢、總時間超時等問題。

基于以上問題可以看出，評價函數的好壞對走棋是否合理至關重要，搜索算法對行棋也有顯著影響，所以本文從評價函數和搜索算法兩方面展開研究，旨在減小愛恩斯坦棋行棋過程中隨機性對行棋的影響，并結合適當的搜索算法，縮短搜索時間，進一步提高在對弈中的勝率。本文將藍棋作為本方，紅棋作為敵方。

1 定式處理改進Alpha-Beta剪枝算法

極大極小搜索算法是計算機博弈游戲設計中最常見的搜索算法，它的核心思想是博弈雙方從自身角度出發，總是做最優選擇。基本思路是：對弈雙方分別為A和B，當輪到A方走步時，B方應考慮最壞情況；當輪到B方走步時，A方應考慮最壞情況，評價往回倒推時，相應于兩位棋手的對抗策略，交替使用取值方法來傳遞倒推值。一般地，極大極小算法采用回溯的方式遞歸調用完成，顯然其在搜索深度上受到了極大的限制，很難進行深層次的評估，而有很多節點再進行深層次的搜索是沒有太大意義。Alpha-Beta剪枝算法[3]是基于極大極小搜索算法的無損剪枝算法，是最基本也最有效的剪枝方法，雖然它沒有辦法消除極大極小算法搜索過程中節點的指數級增長，但可以將其減半。

常用的Alpha-Beta剪枝算法的改進策略有殺手啟發、歷史啟發、MTD（f）算法[4]等。實驗表明，愛恩斯坦棋項目中先后手對估值的影響影響略大，且博弈過程中經常出現分支或前后兩步之間估值差距過大的情況，因此使用渴望搜索不太適合，對效率的提升不夠明顯。轉移表通過記錄已經搜索過的節點（或子樹）的搜索結果，包括子樹的博弈值、最佳移動和位置，給予當前搜索和走棋以提示。轉移表會占用大量內存，雖然可以采用散列的方式管理存取，但是對于愛恩斯坦棋來說，每一枚棋子最多有3種走向可以選擇。

通過大量實驗表明，一般來說，棋子走對角線是最優的，且由于博弈樹搜索性能的瓶頸，每次搜索很難達到之后走棋再搜索所能達到的搜索深度，這意味著，每次走棋幾乎都“否定”了之前的搜索結果，所以轉移表對最優走法的提示功能有限。通過大量實驗對局發現，在開局階段內層棋子吃掉外層棋子換取走棋靈活性對于愛恩斯坦棋后期走棋更為有利，且開局階段棋型相對固定，這樣就可以采取在Alpha-Beta剪枝算法層前加入定式處理層，只要棋型滿足某種條件就走固定的走法，這種思路可以避免開局階段棋子數多、在多層搜索時出現的計算體量大、耗時長、很多節點進行深層次的搜索是沒有太大意義的情況，形成了基于定式處理的改進型Alpha-Beta剪枝算法。

基于定式處理的改進型Alpha-Beta剪枝算法流程如圖1所示。

下面以一個定式處理為例，該定式一般應用于開局，如圖2所示，檢索藍棋所在的副對角線右方區域，如果滿足副對角線右方區域只存在一個紅棋，則只要行棋藍棋可行棋3個方向能吃掉紅棋則一定吃掉，若如可走藍4，直接定式處理吃掉紅5，而不是斜走。

如果滿足副對角線右方區域不存在一個紅棋，則藍棋棋子最外層和最內層棋子斜走，同時根據開局階段吃掉外層棋子換取靈活性思路，次層棋子吃掉最外層兩翼的棋子（見圖3）。同時還可以加入根據場上棋子數調整Alpha-Beta剪枝算法的搜索層數等定式。

定式處理層的加入是基于愛恩斯坦棋棋局小、能吃本方棋子、走法相對單一的特點，對于能夠進行定式處理的局面，不需要進入Alpha-Beta剪枝搜索層，直接處理完畢后跳至走棋層，這樣既能夠克服由于Alpha-Beta剪枝在高層次搜索時計算量成幾何層次增長、耗時長的缺點，同時也利于后期參數調整、試驗矯正階段可以通過定式處理，彌補由于Alpha-Beta剪枝算法系統誤差導致的剪枝掉最優行棋的情況，到達找到最優走法、提高比賽勝率的目的。

2 實驗結果

本文的基于定式處理改進Alpha-Beta剪枝的策略與使用傳統期望距離的Alpha-Beta剪枝進行博弈結果如表1所示。

該策略驗證在勝率方面對戰一般距離期望的Alpha-Beta 剪枝算法程序有較大優勢，同時耗時也僅為一般策略的72.6%，同時，該策略應用的程序“WjCkGo”，在2017年全國大學生計算機博弈大賽愛恩斯坦棋項目獲得一等獎（季軍），證明該策略明顯增加了勝率。

3 結語

本文通過運用一些靈活且實用的定式處理算法，判斷當前局面是否可以進入定式處理層而直接輸出走棋。這種在適宜局面不需要進入Alpha-Beta剪枝層的改進型Alpha-Beta 剪枝層算法，減少了決策時間，而且還可以通過后期不斷測試，完善定式處理層，達到較好的走棋水平，同時也應該意識到，要進一步加強對殘局的處理，完善特定棋型時剪枝算法出現的系統漏洞。

[參考文獻]

[1]王驕，徐心和.計算機博弈：人工智能的前沿領域——全國大學生計算機博弈大賽[J].計算機教育，2012（7）：14-18.

[2]劉知青，吳修竹.解讀AlphaGo背后的人工智能技術[J].控制理論與應用，2016（12）：1685-1687.

[3]曹森.對α-β剪枝算法的性能改進研究[D].呼和浩特：內蒙古師范大學，2012.

[4]LORENTZ R J.An MCTS program to play EinStein Wtirfelt Nicht[M].Berlin：Advances in Computer Games， 2011.