基于alpha-beat算法的棋局研究

朱伊波 梁楠楠

【摘 要】針對點格棋博弈系統(tǒng)，傳統(tǒng)搜索算法由于采用了等深度搜索，存在時間資源分配不合理，且評估函數(shù)只能依靠人工調(diào)參的問題，嚴(yán)重影響了算法執(zhí)行效率。本課題擬采用基于α-β搜索算法的變長搜索方案，盡可能地減少在節(jié)點較多時的搜索時間，以提升搜索算法的效率;同時引入遺傳算法、神經(jīng)網(wǎng)絡(luò)等算法，根據(jù)棋局狀態(tài)動態(tài)調(diào)整評估函數(shù)參數(shù)，以達(dá)到提升棋力的目的。

【關(guān)鍵詞】點格棋;α-β搜索算法;神經(jīng)網(wǎng)絡(luò)

一、引言

點格棋由于其棋型種類繁雜多變，沒有定式，以及在安全邊存在的情況下，估值會由于其安全邊占有順序的不同而有誤差，目前，點格棋博弈系統(tǒng)所采用的招法確定優(yōu)化方法大多都是阿爾法-貝塔（Alpha-Beta）算法，Alpha-Beta算法是對極大極小算法的優(yōu)化，同時，也是一種對博弈樹的剪枝策略。本項目便是針對Alpha-Beta算法進(jìn)行研究。

二、基于Alpha-Beta搜索算法的變長搜索算法的操作原理

以點格棋博弈樹為例，如圖所示

變長搜索方案示例圖

其中□代表己方拓展的節(jié)點，○代表對方拓展的節(jié)點，點格棋博弈樹就是通過博弈雙方輪流拓展節(jié)點來構(gòu)建的。在d=4的一層節(jié)點被分成了4組，以第一組為例，節(jié)點n1的離散度為0.3小于n2，同樣n3的離散度也小于n2，則只需要對n2進(jìn)一步搜索。

三、變長搜索方案實現(xiàn)的框架構(gòu)建

選取UCT搜索算法作為框架來實現(xiàn)該改進(jìn)方案。UCT算法（上限置信區(qū)間算法）是蒙特卡洛算法的一種延伸算法，同時又將UCB算法應(yīng)用到博弈樹搜索上，通過UCB值的大小來選擇進(jìn)行評估的節(jié)點而不再是隨機(jī)選擇，通過UCB算法引導(dǎo)博弈樹向更好的方向生長，有利于更快的獲得最優(yōu)解。UCT算法是蒙特卡洛算法當(dāng)完成大量隨機(jī)模擬后，不再根據(jù)模擬結(jié)果產(chǎn)生的勝率選擇節(jié)點，因為根據(jù)UCB值更好的節(jié)點會被進(jìn)行更多次的訪問，所選擇的節(jié)點是訪問次數(shù)最多的節(jié)點。UCT算法根據(jù)模擬棋局的結(jié)果，以概率大小判斷棋局盤面對己方的優(yōu)劣，預(yù)估節(jié)點的好壞，優(yōu)先選擇表現(xiàn)好的節(jié)點。

UCT算法的具體流程如下：在每次選擇最佳著法開始時，會建立一棵搜索樹，然后依次進(jìn)行如下操作：

①以當(dāng)前節(jié)點為根節(jié)點開始進(jìn)行搜索;

②利用UCB公式計算節(jié)點的UCB值，巧始時對節(jié)點隨機(jī)賦UCB值，選擇UCB值高的子節(jié)點進(jìn)行搜索;

③若此子節(jié)點不是葉節(jié)點，則重復(fù)②直至搜索到葉子節(jié)點;

④檢查該葉子節(jié)點是否達(dá)到規(guī)定的訪問次數(shù)，如果達(dá)到規(guī)定的訪問次數(shù)，則拓展該結(jié)點，該結(jié)點訪問次數(shù)加1，跳到①，如果沒有達(dá)到規(guī)定的訪問次數(shù)跳到⑤;

⑤對弈雙方均按照隨機(jī)策略，輪流著子，直至棋局結(jié)束，獲得模擬結(jié)果。

⑥根據(jù)模擬結(jié)果，更新博弈樹結(jié)點收益值：勝利收益1，負(fù)收益0;

⑦由①開始重復(fù)，直到時間結(jié)束，或達(dá)到預(yù)設(shè)次數(shù);

⑧由根節(jié)點的所有子節(jié)點中，選擇平均收益值最高者，作為最佳節(jié)點，此節(jié)點就是UCT算法搜索的結(jié)果。

四、棋局離散度的獲取

本項目采用并查集來將棋局劃分為不同鄰接區(qū)域，首先將棋局轉(zhuǎn)換為一個只含0或1的矩陣，如果一個格子的自由度為4，就將對應(yīng)的位置置0否則置1。這樣就將劃分鄰接區(qū)域問題轉(zhuǎn)化為找出該矩陣中所有相鄰的1連成的區(qū)域，之后計算離散度就簡單了。

五、遺傳算法優(yōu)化的評估函數(shù)的設(shè)計

適應(yīng)度函數(shù)設(shè)計。由于經(jīng)典遺傳算法本身收斂速度慢，所以本項目采用適應(yīng)度函數(shù)的計算方法，考慮目標(biāo)函數(shù)在搜索點的變化趨勢，并將目標(biāo)函數(shù)的變化信息加入適應(yīng)度函數(shù)指導(dǎo)搜索的進(jìn)行，使得搜索朝著具有較大函數(shù)值變化率的方向進(jìn)行;

遺傳算法梯度訓(xùn)練。通過選擇一種高效的博弈樹搜索算法逐步提高博弈算法搜索的深度，逐步增強(qiáng)陪練算法的強(qiáng)度，有效的節(jié)省了訓(xùn)練時間;

變異和交叉操作。采用單點交叉，隨機(jī)地選擇染色體中的一個二進(jìn)制位作為交叉點將父個體的兩個參數(shù)交叉形成子個體的兩個參數(shù)。

六、數(shù)據(jù)處理

設(shè)計離散度函數(shù)、棋局評估函數(shù)、目標(biāo)函數(shù)、適應(yīng)度函數(shù)。同時利用GAMFal 算法。GAMFal 算法的核心是 Multi-Ochiai 可疑度系數(shù)計算公式和遺傳操作算子的選擇，圖 2 給出了整個算法的流程圖，算法共分為兩個階段，第 1 階段首先使用貪心算法對多缺陷分布的種群進(jìn)行初始化;然后執(zhí)行選擇、交叉和變異算子，生成新的個體并添加到種群中，同時以 Multi-Ochiai 可疑度系數(shù)作為適應(yīng)度值對個體進(jìn)行評價并進(jìn)化得到新種群;如果終止條件被滿足，則將得到最終的最優(yōu)多缺陷分布種群.然后進(jìn)入第 2 階段，依據(jù)最優(yōu)種群中的多缺陷分布得到對應(yīng)的程序?qū)嶓w的可疑度排序，算法結(jié)束。

GAMFal算法流程圖

七、實驗方案

首先，對改進(jìn)的搜索算法進(jìn)行驗證，實驗由兩程序A和B在Microsoft Visual studio 2012開發(fā)的平臺下進(jìn)行對弈，其中A為傳統(tǒng)的UCT算法，B為作變長搜索改進(jìn)后的UCT算法，記錄兩種算法在不同搜索深度下搜索到的節(jié)點數(shù)、所耗時間和勝負(fù)情況;

同樣使用A、B兩程序進(jìn)行對弈，其中A使用的是按照自己經(jīng)驗設(shè)置參數(shù)的評估函數(shù)，B采用經(jīng)過訓(xùn)練的遺傳算法優(yōu)化后的評估函數(shù)，雙方搜索算法均采用傳統(tǒng)的UCT算法，統(tǒng)計兩個程序在不同搜索深度下搜到的節(jié)點數(shù)和對局的勝負(fù)情況。

使用一個貪心算法過程 Additional-Greedy（AG）來生成初始候選解種群，該算法能在滿足所有個體符合條件的情況下，盡可能地保證初始種群的多樣性，算法的流程圖如圖所示.AG 過程的輸入包括覆蓋矩陣 M、測試用例結(jié)果向量 R 以及遺傳算法種群中包含的個體數(shù)量 Np.AG 過程首先生成 n 個個體，每一個個體（即候選缺陷分布）均只有一條語句被認(rèn)為有錯，即長度為 n 的二進(jìn)制串中只有一個位置為1，其他為 0，且個體之間 1 的位置互異，如圖所示.計算每一個個體的（C）值，如果（C）=|TF|，則該候選缺陷分布C能夠解釋所有的失敗測試用例，是本問題的一個可行解.如果（C）>|TF|，則需要對該個體進(jìn)行修正，即在該候選缺陷分布中加入語句 ex（即把缺陷分布組合中 ex 對應(yīng)的位置置 1），使得該候選缺陷分布能夠解釋所有的失敗的測試用例.ex 需要能夠解釋最多的原候選缺陷分布不能解釋的失敗測試用例;也就是說，在 ex 被加入到候選缺陷分布 C 后，（C）增加的幅度最大;ex 加入后，C 如果能夠解釋所有的失敗測試用例，則該過程結(jié)束，若不能，則繼續(xù)加入語句，直到該個體能夠解釋所有失敗測試用例為止.至此，AG 過程獲得了一個有 n 個可行個體的種群.如果 n Np，則復(fù)制數(shù)個可行個體直至將初始種群中個體數(shù)量補(bǔ)充至 Np;如果 n Np，則選擇其中 Multi-Ochiai 可疑度值最大，即適應(yīng)度值最高的 Np 個個體作為初始種群.AG 過程生成的 Np 個個體的初始種群具有相對較高的適應(yīng)度值，且具有較好的多樣性，因為每個個體都是由具有不同缺陷位置的候選缺陷分布擴(kuò)展而來.高質(zhì)量的初始種群有利于遺傳算法最終得到較好的結(jié)果. 初始化得到的種群將依次使用選擇、交叉和變異算子來產(chǎn)生新的個體.新個體再重插入到種群中，開始新一輪的選擇、交叉和變異。

AG過程流程圖

八、結(jié)語

點格棋未來將會優(yōu)化出更加先進(jìn)的計算方式，但當(dāng)下α-β算法仍是主流方式。本文對α-β算法提出一種優(yōu)化，希望為來點格棋算法會更加先進(jìn)。

【參考文獻(xiàn)】

[1]劉洋，點格棋博弈中UCT算法的研究與實現(xiàn)[D]，合肥，安徽大學(xué)，2018.

[2]李學(xué)俊，王小龍，吳蕾，等.六子棋中基于局部“路"掃描方式的博弈樹生成算法[J].智能系統(tǒng)學(xué)報，2015（2）：267一272.

[3]唐霜霜，點格棋機(jī)器博弈系統(tǒng)的研宄與實現(xiàn)[ D]，合肥：安徽大學(xué)，2015，

[4]劉淑英，穆遠(yuǎn)彪，李紅·基于alpha-beta剪枝搜索算法的中國象棋游戲設(shè)計[J].信息通信，2015（8）：47一48.

[5]陳業(yè)鵬·基于Alpha-Beta搜索算法的中國象棋人機(jī)對戰(zhàn)的設(shè)計與實現(xiàn)[J ]、計算機(jī)光盤軟件與應(yīng)用，2012（4）197一199.