五子棋人工智能研究與實踐

牛愷澤，鄧 鑫

（1.北京交通大學附屬中學分校，北京 100088；2.國家氣象信息中心，北京 100081）

1 引言

人工智能是一門研究如何利用計算機來模擬人類智能的學科，被認為是21世紀三大尖端技術之一。近年來，人工智能技術得到了迅猛發展，在很多領域都開展了深入研究，例如：自然語言處理、生物模式識別等。在很多行業，人工智能已經能夠替代人類完成工作，例如：客服聊天機器人、交易員等[1]。博弈問題是人工智能的其中一個重要分支，是個零和問題，即決策如果對一方是有利的，對另一方肯定是不利的。博弈問題涉及人工智能中的推理技術、搜索方法和決策規劃。1997年，IBM公司研發的“深藍”國際象棋程序，戰勝了著名國際象棋棋手卡斯帕羅夫；2016年，谷歌旗下的子公司DeepMind研發的AlphaGo擊敗了韓國圍棋世界冠軍李世石；2017年，同樣是AlphaGo，擊敗了中國的世界冠軍柯潔。這些都是人工智能技術應用于人機博弈問題的重要事跡。

2 問題描述

五子棋問題是典型的博弈問題，其基本規則為：下棋的雙方分別執黑白兩色棋子，通過輪流放下本方棋子于棋盤中來最后決出勝負，決出勝負的標準是率先有五個本方棋子連成一條線的一方勝出（橫著，豎著或者斜著五個同色的棋子都可以）[2]。五子棋問題的基本模型描述為：在五子棋人機博弈系統中，構建落子算法，使得計算機具有人的智能，能夠對當前局面進行判斷，并且做出落子判斷，直至勝出。

五子棋問題中的基本棋型定義如下：

（1）五子連珠：至少五個同色棋子連在一起。

（2）活四：有兩個點可以落子形成連五點。

（3）固四：有一個點可以落子形成連五點。

（4）雙固四：落子之后可以形成兩個固四。

（5）活三：落子后能形成活四。

（6）雙活三：落子后能形成2個活三。

在五子棋博弈問題中，下棋方不僅要考慮落子對當前棋局的影響，而且還有考慮落子對將來棋局的影響，也就是說，不能只考慮局部最優，而要盡可能地考慮全局最優。因此，經過分析，五子棋博弈問題主要涉及到兩個關鍵問題，分別是：下一步最佳落子位置搜索和估值函數的設計。

（1）下一步最佳落子位置搜索。對于15×15的棋局，棋盤縱橫各有15條線，總共構成225個可落子的點。對每一個棋局，需要搜索可落子位置，并做出評估以確定下一步最佳落子位置。

（2）估值函數設計。估值函數F（n）是對棋局的一個量化評價，針對某一棋局，分析搜索范圍內各可落子點的落子估值，根據該值來進行落子判斷。估值越大代表對己方越有利，估值越小代表隊己方越不利。

3 算法研究

3.1 下一步最佳落子位置

3.1.1 傳統搜索算法

（1）博弈樹。遍歷所有走法，構成一顆搜索數，即博弈樹。根節點為先手第一步走法，下面走法構成樹的子節點，直至棋局結束。在博弈樹的構建過程中，執棋雙方輪流擴展節點，所有能使己方獲勝的節點都是可解節點，所有使對方獲勝的節點為不可解節點。完整的博弈樹需要窮舉所有棋局，復雜度非常高，因此通常做法是只生成一定深度的博弈樹。（2）極大極小算法。該算法是在博弈樹上尋找最優解的一個過程，即對各個子節點進行取舍的過程，本質上是博弈樹算法的優化算法，復雜度優于博弈樹算法，也稱為不完全搜索樹。算法中定義一個估值函數，利用估值函數得到當前端節點得分，并倒推其父節點的得分，對于己方節點，選擇子節點中的最大得分作為父節點得分；而對于對方節點，選擇子節點中的最小得分作為父節點得分。該算法需要先生成不完全博弈樹，并計算所有節點的得分，當搜索深度較低時將影響決策的準確性，當搜索深度較高時復雜度仍然會很高。（3）α-β剪枝。該算法是對極大極小算法的優化，在博弈樹生成的過程中，通過計算與比較節點得分的上下界快速裁剪不必要的搜索分支，從而提高搜索效率。

3.1.2 改進搜索算法

傳統搜索算法的缺陷在于計算復雜度問題，無法解決搜索深度增加帶來的呈幾何級數增加的計算量問題。因此，根據五子棋的規律和特點，對傳統搜索算法進行改進，以進一步提高算法的執行效率和對弈能力。

（1）矩形域搜索。構建棋盤上已有棋子的點的最大矩形區域，在矩形區域內部和外圍的鄰域范圍內進行搜索，如圖1所示。一開始由于棋盤上棋子數較少，并且相對比較集中，那么矩形區域及其鄰域都很小，搜索點數相對較少。隨著局勢的進行，棋盤上的棋子數目不斷增加，矩形區域的范圍也會變大，搜索的點數也會相應的增加。不過與搜索棋盤上所有的點相比，該算法確實減少了不少的搜索工作量，在一定程度上能夠提高搜索效率。

圖1 矩形域搜索

（2）八連通域搜索。構建棋盤上已有棋子的點的八連通區域，八連通區域范圍內進行搜索，包括棋子圍出的內部空白區域在內，如圖2所示。該算法思路與矩形域搜索算法一致，并且能夠進一步提高搜索效率。

圖2 八連通域搜索

（3）路徑搜索。搜索路徑如圖3所示，從棋盤中心出發，沿著圖中箭頭方向進行搜索。通過一定的判定規則，確定停止搜索的條件，在適當的時候停止對棋盤的搜索，同時標記出搜索過程中所經過的已有棋子的點的鄰域，作為考慮落子的位置。該算法設計的依據為：根據五子棋的特點，棋盤中間部分相比較于棋盤的四周更適合落子，所以應當優先考慮。一般下棋都是從棋盤中心開始下，這樣棋子大部分都會集中在棋盤的中心區域。這樣從中心向外進行有規律的擴展，搜索效率會有顯著提高。

圖3 路徑搜索

3.2 估值函數設計

在估值函數中，需要對整個棋盤形勢進行分析，既要考慮此時自己的收益值，也要考慮對手的收益值，兩者加權，從而得到一個相對合理的評價值。估值函數的設計涉及到對如下棋局進行參數調優，分別是：五子連珠、活四、雙活三、活三+固四、雙固四、沖四、活N和固N。

（1）訓練集設計。設定1000組的權值，每一組權值人機對弈50次，計算勝率，則訓練集中有1000個樣本。

（2）參數調優。利用人工神經網絡[3]進行求解，得到最優的一組參數，如表1所示。

4 實現

在Windows 7下開發，對上述算法進行實踐，完成五子棋人工對弈程序。通過實際對弈，該程序在計算機先手、人先手下的情況均能得到不錯的勝率，如圖4、圖5所示。

表1 最優的一組參數

圖4 計算機先手

圖5 人先手

5 結束語

五子棋人工智能是人工智能中博弈問題的經典問題。本文設計了一個五子棋人工對弈程序，在該程序中，對下一步最佳落子位置的搜索算法進行了改進，并研究了各棋局的參數調優方法。通過實際對弈表明，該算法具有較好的博弈性；同時，該算法存在的問題為：人先手情況下初始落子的智能性較差，需要進一步的優化改善。