朱伊波 梁楠楠

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

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

一、引言

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

二、基于Alpha-Beta搜索算法的變長(zhǎng)搜索算法的操作原理

以點(diǎn)格棋博弈樹(shù)為例，如圖所示

變長(zhǎng)搜索方案示例圖

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

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

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

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

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

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

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

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

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

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

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

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

四、棋局離散度的獲取

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

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

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

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

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

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

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

GAMFal算法流程圖

七、實(shí)驗(yàn)方案

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

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

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

AG過(guò)程流程圖

八、結(jié)語(yǔ)

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

【參考文獻(xiàn)】

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

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

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

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

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