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

牛愷澤，鄧 鑫

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

1 引言

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

2 問題描述

五子棋問題是典型的博弈問題，其基本規(guī)則為：下棋的雙方分別執(zhí)黑白兩色棋子，通過輪流放下本方棋子于棋盤中來最后決出勝負(fù)，決出勝負(fù)的標(biāo)準(zhǔn)是率先有五個本方棋子連成一條線的一方勝出（橫著，豎著或者斜著五個同色的棋子都可以）[2]。五子棋問題的基本模型描述為：在五子棋人機(jī)博弈系統(tǒng)中，構(gòu)建落子算法，使得計算機(jī)具有人的智能，能夠?qū)Ξ?dāng)前局面進(jìn)行判斷，并且做出落子判斷，直至勝出。

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

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

（2）活四：有兩個點(diǎn)可以落子形成連五點(diǎn)。

（3）固四：有一個點(diǎn)可以落子形成連五點(diǎn)。

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

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

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

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

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

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

3 算法研究

3.1 下一步最佳落子位置

3.1.1 傳統(tǒng)搜索算法

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

3.1.2 改進(jìn)搜索算法

傳統(tǒng)搜索算法的缺陷在于計算復(fù)雜度問題，無法解決搜索深度增加帶來的呈幾何級數(shù)增加的計算量問題。因此，根據(jù)五子棋的規(guī)律和特點(diǎn)，對傳統(tǒng)搜索算法進(jìn)行改進(jìn)，以進(jìn)一步提高算法的執(zhí)行效率和對弈能力。

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

圖1 矩形域搜索

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

圖2 八連通域搜索

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

圖3 路徑搜索

3.2 估值函數(shù)設(shè)計

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

（1）訓(xùn)練集設(shè)計。設(shè)定1000組的權(quán)值，每一組權(quán)值人機(jī)對弈50次，計算勝率，則訓(xùn)練集中有1000個樣本。

（2）參數(shù)調(diào)優(yōu)。利用人工神經(jīng)網(wǎng)絡(luò)[3]進(jìn)行求解，得到最優(yōu)的一組參數(shù)，如表1所示。

4 實現(xiàn)

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

表1 最優(yōu)的一組參數(shù)

圖4 計算機(jī)先手

圖5 人先手

5 結(jié)束語

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