王允臣，畢方明

中國礦業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 徐州 221116

1 引言

機(jī)器博弈是人工智能研究的重要分支，被喻為人工智能領(lǐng)域的果蠅。計(jì)算機(jī)博弈系統(tǒng)可分為四部分：局面表示、行動集合、評估函數(shù)和博弈樹搜索。搜索算法是人工智能中問題求解的基本方法。Von Nenumann和Boerl在20世紀(jì)20年代提出的極小極大定理是搜索算法的數(shù)學(xué)基礎(chǔ)；始于20世紀(jì)50年代的alpha-beta剪枝算法在搜索效率上前進(jìn)了一大步。1980年的PVS（Principal Variation Search，亦稱NegaScout）搜素算法，內(nèi)部節(jié)點(diǎn)強(qiáng)有序時效率優(yōu)于alpha-beta搜索；1994年出現(xiàn)的MTD（f）算法，始終用空窗探測逼近真值，借助“置換表”增速完成搜索，略優(yōu)于PVS搜索[1]，兩者為目前的主流方法。多數(shù)游戲的博弈樹非常龐大，無法完備搜索，常規(guī)做法是搜索一定的深度，此時的葉節(jié)點(diǎn)由評估函數(shù)近似估值。評估函數(shù)的好壞直接影響到之后局勢的發(fā)展[2]，如果說搜索引擎是博弈系統(tǒng)的眼睛，評估函數(shù)則是博弈系統(tǒng)的大腦。評估函數(shù)一般必須包含5個方面的要素，分別是固定子力值、棋子位置值、棋子靈活度值、威脅與保護(hù)值、動態(tài)調(diào)整值。每一方面的值又是由許多參數(shù)構(gòu)成的。評估函數(shù)中上述參數(shù)的組合往往依賴于編程人員自身的知識和經(jīng)驗(yàn)，這就導(dǎo)致很難達(dá)到最優(yōu)。有學(xué)者已經(jīng)把遺傳算法引入評估函數(shù)，試圖學(xué)習(xí)棋子之間的動態(tài)聯(lián)系，但是效果不是很理想。本文以點(diǎn)點(diǎn)連格棋為例，設(shè)計(jì)了一種評估函數(shù)，使用遺傳算法[3]對評估函數(shù)中的參數(shù)進(jìn)行優(yōu)化，為了加快遺傳算法的收斂速度，在適應(yīng)度函數(shù)中加入了問題領(lǐng)域知識[4]。

2 遺傳算法應(yīng)用于評估函數(shù)參數(shù)優(yōu)化的解決方案

遺傳算法是由美國Michigan大學(xué)的Holland教授于1969年提出，后經(jīng)Dejong、Goldberg等人歸納總結(jié)所形成的一類模擬進(jìn)化算法。近年來，遺傳算法作為智能計(jì)算（神經(jīng)網(wǎng)絡(luò)、模糊處理和進(jìn)化計(jì)算）的重要組成部分，一直是研究的一個熱點(diǎn)，在應(yīng)用領(lǐng)域也取得了相當(dāng)好的結(jié)果，如多極值函數(shù)的優(yōu)化問題、組合優(yōu)化問題、調(diào)度問題等。

遺傳算法并行度高，對初值的依賴性小，具有快速全局搜索能力，而且魯棒性也明顯優(yōu)于傳統(tǒng)爬山法[5]、模擬退火算法[6]和蟻群算法，但是具有早熟和收斂速度慢的特點(diǎn)，針對其缺點(diǎn)本文將目標(biāo)函數(shù)相鄰兩代的一階差分信息加入適應(yīng)度函數(shù)加強(qiáng)搜索能力，防止早熟，并采用改進(jìn)遺傳算法使得收斂速度得到提高，使其最有可能在點(diǎn)點(diǎn)連格棋中取得成功。

2.1 點(diǎn)點(diǎn)連格棋基本概念

自由度：格子中未被占領(lǐng)的邊的條數(shù)。

相鄰：坐標(biāo)分別為(i,j)和(k,l)的兩個格子成為相鄰的條件為：當(dāng)且僅當(dāng)|i-k|+|j-l|=1，并且兩個公共邊未被占領(lǐng)。

鏈：存在一組格子BS={b0,b1,…,bi,…,bn}，有bi的自由度為2，且b0、bn之間最多只有一個相鄰屬于BS，其余所有格子均有兩個相鄰，并有這兩個格子均為BS中的格子，那么BS稱為鏈，b0與bn稱為該鏈的端點(diǎn)，b0與bn可以為同一個格子。

短鏈：由1個或2個格子組成的鏈。

長鏈：由3個或3個以上的格子組成的鏈。

雙交：下棋方一步就可以占領(lǐng)兩個格子的情形。

2.2 評估函數(shù)的參數(shù)選取

點(diǎn)點(diǎn)連格棋以一個空的棋盤開始，對弈雙方輪流在相鄰的兩點(diǎn)之間放置一橫線或豎線。當(dāng)一方占領(lǐng)一個格子之后得到一分，并繼續(xù)下一步。當(dāng)所有的線被占領(lǐng)之后，游戲結(jié)束。得分較高者得勝。點(diǎn)點(diǎn)連格棋評估函數(shù)的設(shè)計(jì)通常依賴于幾個定理[7]，下面加以介紹。

定理1無論初始棋盤的尺寸如何，總有以下式子成立：

其中，Dots指的是初始棋盤點(diǎn)的個數(shù)，Doublecrosses指的是棋局結(jié)束時，共形成的雙交的個數(shù)，Turns指的是棋局結(jié)束時，共經(jīng)歷了多少輪的走棋。

定理2如果棋盤共有奇數(shù)個點(diǎn)，則先手方應(yīng)當(dāng)形成奇數(shù)條長鏈以取勝，后手方應(yīng)形成偶數(shù)條長鏈以取勝；若棋盤共有偶數(shù)個點(diǎn)，則先手方應(yīng)當(dāng)形成偶數(shù)條長鏈，后手方應(yīng)形成奇數(shù)條長鏈以取勝。

定理2被稱為長鏈定理，它是Berlekamp對定理1的一個推論。

長鏈定理是評估函數(shù)設(shè)計(jì)的重要依據(jù)。以4×4棋盤為例，根據(jù)長鏈定理，我方應(yīng)該致力于形成偶數(shù)條長鏈，假設(shè)我方行棋之后形成如圖1（a）所示的棋局（這里有a，b兩條長鏈），那么無論對方采取何種策略，最終一條鏈一定可以由我方捕獲，我方處于優(yōu)勢地位。然而僅僅依賴長鏈定理無法保證評估函數(shù)準(zhǔn)確性。比如我方行棋之后形成如圖1（b）所示的棋局，這里同樣有a，b兩條長鏈，但是對手只需選擇圖中1處的邊，就可以扭轉(zhuǎn)局勢，使我方處于絕對的劣勢。以上分析表明，棋局的估值取決于多種棋型的配合[8]同時對棋型數(shù)目的奇偶性敏感。為此，本文設(shè)計(jì)了如下評估函數(shù)：

其中ri=nimod2,ni表示第i種棋型在當(dāng)前棋局中的數(shù)目；Ai1,Ai2是第i種棋型的參數(shù)；N代表棋局中不同棋型的種類數(shù)，本文中選取的棋型為長鏈、短鏈、雙交、自由度為3、自由度為4的格子，因此N=5。

圖1 偶數(shù)條長鏈情形

2.3 適應(yīng)度函數(shù)的計(jì)算

適應(yīng)度是描述個體性能的主要指標(biāo)，遺傳算法根據(jù)適應(yīng)度的大小對個體進(jìn)行優(yōu)勝劣汰。適應(yīng)度函數(shù)的選擇決定了算法優(yōu)化的導(dǎo)向，對算法的收斂性以及收斂速度的影響較大。

遺傳算法可采用的選擇方法很多，有輪盤選擇法、局部選擇法、截?cái)噙x擇法和錦標(biāo)賽選擇法等。首先采用如下方法設(shè)計(jì)目標(biāo)函數(shù)，讓每個個體與現(xiàn)有的博弈算法（陪練算法）進(jìn)行先后手的比賽，根據(jù)每場比賽所花費(fèi)的回合數(shù)來確定目標(biāo)函數(shù)的取值。如果己方獲勝，則回合數(shù)越少函數(shù)值應(yīng)該越大；如果對方獲勝，則回合數(shù)越多目標(biāo)函數(shù)值應(yīng)該越大。因此目標(biāo)函數(shù)的設(shè)計(jì)如下：

其中x為一場比賽的回合數(shù)，k為可調(diào)系數(shù)，它表示己方獲勝時回合數(shù)對適應(yīng)度的重要程度。這里取k=6。適應(yīng)度函數(shù)直接由目標(biāo)函數(shù)映射而成，即：

為充分考慮目標(biāo)函數(shù)的變化趨勢，防止遺傳過程中優(yōu)選的染色體只在一個較平坦的區(qū)域徘徊，導(dǎo)致“早熟”的情況，本文借鑒何新貴、梁久禎提出的方法[4]，把目標(biāo)函數(shù)的相鄰兩代的一階差分加入進(jìn)來，采用如下新的適應(yīng)度函數(shù)：

其中，權(quán)值ε∈[ ]0,1，稱為控制因子，用以體現(xiàn)適應(yīng)度函數(shù)值和函數(shù)值變化率對求解問題的重要程度；fit()x為原始適應(yīng)度函數(shù)，fitmin和fitmax分別表示當(dāng)前代群體中個體適應(yīng)度的最小值和最大值；?f()x ，?fmin和?fmax分別定義為：

其中xp，xc分別表示父代和子代染色體，n表示種群規(guī)模。

為了提高效率，本文對染色體中的每個參數(shù)進(jìn)行分別考慮，本文中一個染色體對應(yīng)10個參數(shù)，一個參數(shù)對應(yīng)一種棋型的權(quán)重，因此一個染色體對應(yīng)一個適應(yīng)度矩陣[fit(x)′1，fit(x)2，…，fit(x)′i…，fit(x)′n]，這里 n=10。

2.4 交叉和變異操作

交叉方法很多，有單點(diǎn)交叉、多點(diǎn)交叉、順序交叉、循環(huán)交叉等等。為了方便起見，本文采用單點(diǎn)交叉，隨機(jī)地選擇染色體中的一個二進(jìn)制位作為交叉點(diǎn)將父個體的兩個參數(shù)交叉形成子個體的兩個參數(shù)。

對每個參數(shù)以一定的變異率進(jìn)行突變[9]，因?yàn)椴捎玫氖嵌M(jìn)制串表示，這里只需根據(jù)變異率對基因進(jìn)行0-1翻轉(zhuǎn)即可。變異是一種局部隨機(jī)搜索，與選擇/交叉算子結(jié)合在一起，保證了遺傳算法的有效性。同時保持了種群的多樣性，防止出現(xiàn)非成熟收斂。

這里選擇對染色體中每一個參數(shù)進(jìn)行操作是由于一條染色體對應(yīng)的參數(shù)比較多，如果直接對整條染色體進(jìn)行操作，那么有的參數(shù)可能得不到更多的交叉和變異操作，使得收斂時間變長，效果不理想。

2.5 改進(jìn)遺傳算法

文獻(xiàn)[10]指出遺傳算法具有收斂速度慢的缺點(diǎn)。這對于該文研究的問題來說是一個極大的挑戰(zhàn)。因?yàn)檫m應(yīng)度函數(shù)是基于博弈結(jié)果設(shè)計(jì)的，每個個體都需要與陪練算法進(jìn)行博弈并決出勝負(fù)方可計(jì)算其適應(yīng)度值。隨著進(jìn)化程度的提高，博弈所需要的時間也會極大地增加，其中的時間代價無疑是一個極大的挑戰(zhàn)。本文從以下兩方面對遺傳算法進(jìn)行改進(jìn)：引入自適應(yīng)遺傳算法，使交叉率和變異率隨著個體適應(yīng)度自動調(diào)整；加入啟發(fā)式信息指導(dǎo)下一代的生成。

遺傳算法的收斂性受交叉率pc和變異率pm的影響[11-12]。交叉率越大新個體產(chǎn)生的速度越快，但是交叉率過大又不利于保護(hù)目前適應(yīng)度高的個體的染色體結(jié)構(gòu)，而交叉率過低，又使得個體進(jìn)化過于緩慢，搜索過程停滯不前。對于變異率，如果變異率過低不利于產(chǎn)生新個體，而且搜索容易陷入局部最優(yōu)，變異率過高，遺傳算法很容易退化為隨機(jī)搜索算法。由于目前還沒有固定的方式來確定pc和pm，只能通過實(shí)驗(yàn)的方法不斷優(yōu)化，這個過程比較繁瑣。為此，本文引入自適應(yīng)遺傳算法[9，13]，對每個染色體設(shè)計(jì)如下的交叉率和變異率矩陣[pc1,pc2,…,pci,…,pcn]和 [pm1,pm2,…,pmi,…,pmn]，其中n=10，對應(yīng)一個染色體中的參數(shù)總數(shù)。pci和pmi隨著個體適應(yīng)度自動調(diào)整。下面給出pci和pmi的計(jì)算公式如下：

其中，pca=0.9，pcb=0.6，pma=0.1，pmb=0.001。fmax是群體中最大適應(yīng)度值；favg是每代群體的平均適應(yīng)值；f′是要交叉的兩個個體中較大的適應(yīng)值；f是要突變個體的適應(yīng)度值。分析式子可知當(dāng)適應(yīng)度值越接近最大適應(yīng)度值，pci和pmi的值就越小，這就降低了優(yōu)良基因被破壞的可能，保證了算法的收斂性。

文獻(xiàn)[5]指出爬山法具有收斂速度快的優(yōu)點(diǎn)。本文受爬山法啟發(fā)，在遺傳算法中加入啟發(fā)式信息指導(dǎo)下一代的生成，以求加快算法的收斂速度。

2.2節(jié)設(shè)計(jì)的評估函數(shù)共有10個參數(shù)，為了提高啟發(fā)式信息的準(zhǔn)確度，本文對每個參數(shù)進(jìn)行分別考慮。具體操作如下：根據(jù)當(dāng)前代個體適應(yīng)度值采用輪盤賭方法選出雙親并按照2.4節(jié)介紹的交叉變異操作產(chǎn)生新個體，重復(fù)這個過程直到生成代替上一代種群的新一代種群。在選出下一代群體之后對所有個體按照適應(yīng)度值從小到大排序。按照順序遍歷每一個參數(shù)j，把編碼該參數(shù)的bit位轉(zhuǎn)換為整數(shù)值，如果所有值都是遞增的，那么就把pnj更新為pnj+Δj并更新到該染色體編碼中，否則就取所有值的平均值δj并取與其相差絕對值最大的一個染色體，將其參數(shù)pij更新為δj并更新到該染色體編碼中。

其中pij代表當(dāng)前代中第i個個體（染色體）的第j個參數(shù)轉(zhuǎn)換成整數(shù)后對應(yīng)的值，n代表當(dāng)前代中個體的總數(shù)。

3 實(shí)驗(yàn)測試與結(jié)果

3.1 實(shí)驗(yàn)策略

改進(jìn)遺傳算法需要大量的博弈訓(xùn)練才能得到較好的結(jié)果，時間問題是必須要考慮的關(guān)鍵因素。本文采用梯度訓(xùn)練的方法來達(dá)到花費(fèi)較少時間取得更好效果的目的。具體包括三個方面，選擇一種高效的博弈樹搜索算法；逐步提高博弈算法搜索的深度；逐步增強(qiáng)陪練算法的強(qiáng)度。

1978年，Stockman提出了SSS*算法[14]并且證明它是一個正確的極小極大算法而且它永遠(yuǎn)不會搜索alpha-beta剪枝的節(jié)點(diǎn)。然而SSS*算法最大的缺點(diǎn)就是較大的存儲需求，并且需要維護(hù)OPEN表。文獻(xiàn)[15]針對SSS*算法[14]的存儲需求大，需要維護(hù)OPEN表順序等缺點(diǎn)提出了AB-SSS*算法。AB-SSS*算法通過反復(fù)的以空窗調(diào)用alpha-beta過程實(shí)現(xiàn)了與SSS*算法完全相同的搜索過程，解決了SSS*算法存在的缺點(diǎn)。而且由文獻(xiàn)[14]知道，SSS*算法搜索的節(jié)點(diǎn)數(shù)比alpha-beta少，效率高。因此本文采用AB-SSS*算法作為二者的搜索算法。

搜索深度對時間的影響是巨大的，開始階段由于評估函數(shù)參數(shù)未得到有效優(yōu)化，即使搜索很大的深度最終得到的估值仍然是不準(zhǔn)確的，因此時間代價過高。然而當(dāng)評估函數(shù)參數(shù)得到有效優(yōu)化后，如果搜索深度仍得不到相應(yīng)提高，棋力就無法更好的提升，遺傳算法會認(rèn)為這是由于當(dāng)前個體的基因不夠優(yōu)良從而繼續(xù)對其進(jìn)行進(jìn)化，這樣算法收斂的時間就會增加。

陪練算法的強(qiáng)弱同樣會影響訓(xùn)練時間和結(jié)果的準(zhǔn)確性。開始階段陪練算法過強(qiáng)，遺傳算法的選擇趨于單一化；陪練算法一直很弱，則不利于選擇出優(yōu)良個體。本文對訓(xùn)練的不同階段采用不同強(qiáng)度的陪練算法。

陪練算法的強(qiáng)弱體現(xiàn)在兩個方面：評估函數(shù)的準(zhǔn)確度和搜索的深度。在訓(xùn)練的開始階段（前100代），使用根據(jù)自己的經(jīng)驗(yàn)設(shè)計(jì)的評估函數(shù)，評估函數(shù)估值計(jì)算的偽代碼如下所示：

在訓(xùn)練到達(dá)一定階段后，再采用與遺傳算法得出的相同參數(shù)的評估函數(shù)，這時通過搜索深度來區(qū)分二者的棋力。在訓(xùn)練的前期（前100代）中期（100代到200代）后期（200代到300代），遺傳算法的AB-SSS*算法的搜索深度分別取2、5、7；陪練算法的AB-SSS*算法的搜索深度分別取2、8、10。AB-SSS*算法的偽代碼參考文獻(xiàn)[14]。

3.2 實(shí)驗(yàn)結(jié)果

對改進(jìn)適應(yīng)度函數(shù)和自適應(yīng)遺傳算法的評估函數(shù)進(jìn)行梯度訓(xùn)練實(shí)驗(yàn)，實(shí)驗(yàn)由50代、100代、150代、200代、250代、300代的冠軍組成一個小組進(jìn)行組內(nèi)先后手的循環(huán)賽，勝者加3分，和棋加1分，負(fù)者加0分。最后的積分情況如圖2所示。

圖2 訓(xùn)練積分表

通過圖2可以發(fā)現(xiàn)，采用改進(jìn)遺傳算法梯度訓(xùn)練的評估函數(shù)，訓(xùn)練代數(shù)越多，棋力越強(qiáng)，效果明顯，而采用改進(jìn)遺傳算法非梯度訓(xùn)練的評估函數(shù)，棋力差別相對較小，且會有不穩(wěn)定的情況。這說明改進(jìn)遺傳算法具有更快的收斂速度。為了進(jìn)一步驗(yàn)證本文提出的梯度訓(xùn)練方案的有效性，取改進(jìn)遺傳算法梯度訓(xùn)練、改進(jìn)遺傳算法非梯度訓(xùn)練以及改進(jìn)蟻群算法[16]非梯度訓(xùn)練300代的冠軍組成一個小組進(jìn)行組內(nèi)先后手的循環(huán)賽，重復(fù)進(jìn)行10次，統(tǒng)計(jì)獲勝情況如圖3所示。

圖3 獲勝情況

通過圖3可以發(fā)現(xiàn)，對于遺傳算法和蟻群算法，梯度訓(xùn)練的勝率均高于非梯度訓(xùn)練，同時改進(jìn)遺傳算法的獲勝率高于改進(jìn)蟻群算法。這也驗(yàn)證了本文提出的梯度訓(xùn)練方案的有效性。

實(shí)驗(yàn)發(fā)現(xiàn)程序迭代到300代以后，被優(yōu)化的各個參數(shù)基本已不再變化此時的參數(shù)值如表1所示。

表1 訓(xùn)練結(jié)果

用進(jìn)化到300代的參數(shù)組和完全根據(jù)經(jīng)驗(yàn)設(shè)定的參數(shù)組的程序進(jìn)行了比賽，結(jié)果進(jìn)化到300代的參數(shù)組的勝率明顯占優(yōu)。

為了驗(yàn)證提出的梯度訓(xùn)練方法可以在保證準(zhǔn)確度的情況下減少訓(xùn)練的時間，對遺傳算法和陪練算法在不同的訓(xùn)練階段采用相同的深度8，并且均采用相同的評估函數(shù)，進(jìn)行實(shí)驗(yàn)（由于耗時嚴(yán)重，只訓(xùn)練50代）。結(jié)果如表2所示。

表2 訓(xùn)練時間

通過表2發(fā)現(xiàn)，二者耗時差距明顯，用梯度訓(xùn)練與非梯度訓(xùn)練相同代數(shù)的評估函數(shù)在相同的環(huán)境（搜索算法一致，搜索深度相同）下進(jìn)行50場對抗，統(tǒng)計(jì)輸贏情況如表3所示。

表3 博弈數(shù)據(jù)

通過表3，看到搜索深度的增加并沒有帶來明顯的優(yōu)勢，這也在一定程度上驗(yàn)證了本文的策略。

4 結(jié)論

經(jīng)典遺傳算法本身存在著收斂速度慢等缺陷，本文采用了一種新的適應(yīng)度函數(shù)的計(jì)算方法，考慮了目標(biāo)函數(shù)在搜索點(diǎn)的變化趨勢，并將該信息加入適應(yīng)度函數(shù)指導(dǎo)搜索的進(jìn)行，使得搜索朝著具有較大函數(shù)值變化率的方向進(jìn)行。采用改進(jìn)遺傳算法使用啟發(fā)式信息指導(dǎo)下一代個體的生成，這些措施使算法的收斂度得到了提高。本文提出的梯度訓(xùn)練方案，有效地節(jié)省了訓(xùn)練時間。把遺傳算法引入到評估函數(shù)參數(shù)優(yōu)化中，避免了傳統(tǒng)的手工調(diào)整參數(shù)，保證了參數(shù)的準(zhǔn)確性和客觀性，實(shí)驗(yàn)表明評估函數(shù)參數(shù)優(yōu)化后的點(diǎn)點(diǎn)連格棋的棋力得到了提高，這也為開發(fā)高水平博弈算法提供了一種新的思路。

[1]Qiu Hongkun，Zhang Peng，Wang Yajie，et al.Analysis of search algorithm in computer game of Amazons[C]//The26thChineseControlandDecisionConference（2014 CCDC），2014：3947-3950.

[2]Runarsson T P，Lucas S M.Preference learning for move prediction and evaluation function approximation in othello[J].IEEE Transactions on Computational Intelligence&Ai in Games，2014，6（3）：300-313.

[3]Wei Xiaokun，Shao Wei，Zhang Cheng，et al.Improved self-adaptive genetic algorithm with quantum scheme for electromagnetic optimization[J].Microwaves，Antennas&Propagation IET，2014，8（12）：965-972.

[4]權(quán)芳芳，許峰.基于梯度的自適應(yīng)量子遺傳算法[J].軟件導(dǎo)刊，2012，11（8）：31-33.

[5]羅彪，鄭金華，楊平.基于定向爬山的遺傳算法[J]計(jì)算機(jī)工程與應(yīng)用，2008，44（6）：92-95.

[6]Gao C，Gao Y，Lv S.Improved simulated annealing algorithm for flexible job shop scheduling problems[C]//Chinese Control and Decision Conference，2016.

[7]Li Shuqin，Li Dongming，Yuan Xiaohua.Research and implementation of Dots-and-Boxes[J].Journal of Software，2012：256-262.

[8]谷蓉.計(jì)算機(jī)圍棋博弈系統(tǒng)的若干問題研究[D].北京：清華大學(xué)，2003.

[9]Tao X，Wang S，Huangfu Y，et al.Geometry and power optimization of coilgun based on adaptive genetic algorithms[J].IEEE Transactions on Plasma Science，2015，43（5）：1208-1214.

[10]Leuven J，Reehuis E，Emmerich M，et al.User-derived mutation in highly constrained truck loading optimization[C]//IEEE Congress on Evolutionary Computation，CEC 2015，Sendai，Japan，May 2015.

[11]黃春.改進(jìn)遺傳算法的函數(shù)優(yōu)化及應(yīng)用[D].南寧：廣西大學(xué)，2015.

[12]劉明，王瑞.基于自適應(yīng)遺傳算法的改進(jìn)PID參數(shù)優(yōu)化[J].計(jì)算機(jī)測量與控制，2015，23（3）：791-793.

[13]王驕，王濤，羅艷紅，等.中國象棋計(jì)算機(jī)博弈系統(tǒng)評估函數(shù)的自適應(yīng)遺傳算法實(shí)現(xiàn)[J].東北大學(xué)學(xué)報(bào)：自然科學(xué)版，2005，26（10）：949-952.

[14]Stockman G C.A minimax algorithm better than alphabeta?[J].Artificial Intelligence，1978，12（2）：179-196.

[15]Plaat A，Schaeffer J，Pijls W，et al.SSS*=alpha-bet+TT，TR-CS_94-17[R].Edmonton，AB，Canada：Universityof Alberta，1994-12.

[16]高雷阜，張秀麗，王飛.改進(jìn)蟻群算法在SVM參數(shù)優(yōu)化研究中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2015，51（13）：139-144.