杜向然

中國(guó)象棋評(píng)估函數(shù)的分析

杜向然

（天津海運(yùn)職業(yè)學(xué)院，天津市 300350）

中國(guó)象棋計(jì)算機(jī)博弈是人工智能的一個(gè)重要研究領(lǐng)域，它研究的核心是如何使搜索算法與評(píng)估函數(shù)更有效的結(jié)合。文章介紹了中國(guó)象棋博弈系統(tǒng)中評(píng)估函數(shù)的常用構(gòu)造方法，并對(duì)這些方法進(jìn)行分析。

中國(guó)象棋；評(píng)估函數(shù)；增強(qiáng)學(xué)習(xí)；神經(jīng)網(wǎng)絡(luò)

一、引言

中國(guó)象棋計(jì)算機(jī)博弈的研究已經(jīng)開(kāi)展了很多年，它的研究成果已經(jīng)被應(yīng)用到很多實(shí)際的領(lǐng)域當(dāng)中。在中國(guó)象棋博弈系統(tǒng)的組成部分中，評(píng)估函數(shù)是最重要的部分之一，好的評(píng)估函數(shù)可以準(zhǔn)確地判斷當(dāng)前棋局的形勢(shì)，從而保證搜索引擎的搜索方向正確。

二、評(píng)估函數(shù)

象棋博弈者在走棋時(shí)，他需要考慮全部有價(jià)值的走法，并且通過(guò)前瞻若干步，才能形成博弈者的當(dāng)前決策。在這個(gè)過(guò)程中，如何對(duì)棋局進(jìn)行評(píng)估，以及如何讓棋局朝著有利的方向進(jìn)行呢？為了解決這個(gè)問(wèn)題人們提出了評(píng)估函數(shù)。下面將介紹幾種常用的構(gòu)造評(píng)估函數(shù)的方法。

（一）傳統(tǒng)評(píng)估函數(shù)

傳統(tǒng)評(píng)估函數(shù)也叫靜態(tài)評(píng)估函數(shù)，它是通過(guò)計(jì)算博弈雙方評(píng)估值的差值得到的。我們假設(shè)現(xiàn)在是紅方走棋，那么此時(shí)的評(píng)估函數(shù)就可以表示下式

Evaluation（Current Board）＝Evaluation（Red）－Evaluation（Black）

其中Evaluation（x）表示的是評(píng)估函數(shù)，Evaluation（Red）表示紅方狀態(tài)的評(píng)估值；Evaluation（Black）表示黑方狀態(tài)的評(píng)估值。

1．評(píng)估函數(shù)的組成

評(píng)估函數(shù)通常從六個(gè)方面評(píng)價(jià)博弈雙方的局勢(shì)：棋子的價(jià)值、棋子位置的價(jià)值、棋子對(duì)棋盤(pán)的控制、棋子的靈活性、棋子之間的威脅和保護(hù)以及一些對(duì)棋局影響較大的特征。

棋子的價(jià)值代表的棋子的重要程度。根據(jù)中國(guó)象棋規(guī)則，每個(gè)棋子都有自己獨(dú)特的走法，這樣導(dǎo)致了每種類型棋子的作用和重要程度都不相同。

棋子位置的價(jià)值表示的是不同棋子在棋盤(pán)不同位置上會(huì)有不同的價(jià)值，這里的價(jià)值主要是指對(duì)博弈對(duì)手的威脅程度。

棋子的靈活性是指每個(gè)棋子可以“走動(dòng)”的范圍。一般來(lái)說(shuō)，我們認(rèn)為棋子能“走動(dòng)”的范圍越多，它對(duì)防守或進(jìn)攻的貢獻(xiàn)越大。

中國(guó)象棋講究的是棋子之間的配合，需要讓棋子之間構(gòu)成一個(gè)相互聯(lián)系的整體，棋子之間的威脅與保護(hù)正是這方面的體現(xiàn)。棋子的安全程度取決于它的保護(hù)者和威脅者的個(gè)數(shù)、類型和當(dāng)前輪到哪方走等多種因素。

棋子對(duì)棋盤(pán)的控制與棋子之間的威脅和保護(hù)在處理方法上有很多相似之處，它們之間的區(qū)別是前者是對(duì)棋盤(pán)中某些位置的控制，而后者是對(duì)棋子的控制。棋子對(duì)棋盤(pán)的控制這個(gè)特征在棋局開(kāi)始和中盤(pán)的時(shí)候都是很有價(jià)值的，但是當(dāng)棋局進(jìn)入到殘局階段，棋盤(pán)上的棋子比較少，每個(gè)棋子控制的范圍自然增多，這時(shí)棋子對(duì)棋盤(pán)的控制這個(gè)特征在評(píng)估函數(shù)中的作用就下降了。

下棋時(shí)的一些戰(zhàn)術(shù)和棋子之間配合的價(jià)值也需要在評(píng)估函數(shù)中體現(xiàn)。下棋時(shí)的戰(zhàn)術(shù)主要包括：捉雙、牽制和抽子等。棋子間的配合主要是指兵、車、馬和炮之間的配合，比如：過(guò)河兵牽手、連環(huán)馬和霸王車等。這些棋子間配合的價(jià)值往往大于配合棋子的價(jià)值之和。

2．傳統(tǒng)評(píng)估函數(shù)的優(yōu)缺點(diǎn)

傳統(tǒng)評(píng)估函數(shù)的優(yōu)點(diǎn)是充分考慮中國(guó)象棋的知識(shí)和象棋專家的經(jīng)驗(yàn)，但同時(shí)也正是由于這些優(yōu)點(diǎn)導(dǎo)致它會(huì)有如下的缺點(diǎn)：首先、評(píng)估函數(shù)需要花費(fèi)過(guò)多的時(shí)間，從而減少了搜索算法的搜索深度。其次、過(guò)分依賴象棋專家的經(jīng)驗(yàn)，這樣構(gòu)造的評(píng)估函數(shù)容易受到象棋專家水平和經(jīng)驗(yàn)的限制。最后、評(píng)估函數(shù)是固定不變的。中國(guó)象棋中的局勢(shì)千變?nèi)f化，如果一直都用一成不變的評(píng)估函數(shù)對(duì)所有的棋局進(jìn)行評(píng)價(jià)，這顯然是不可靠的。

（二）自學(xué)習(xí)方法得到的評(píng)估函數(shù)

通過(guò)自學(xué)習(xí)方法得到評(píng)估函數(shù)主要包括增強(qiáng)學(xué)習(xí)與神經(jīng)網(wǎng)絡(luò)相結(jié)合構(gòu)造評(píng)估函數(shù)，增強(qiáng)學(xué)習(xí)與數(shù)據(jù)庫(kù)相結(jié)合構(gòu)造評(píng)估函數(shù)以及遺傳算法優(yōu)化評(píng)估函數(shù)。

1．增強(qiáng)學(xué)習(xí)與神經(jīng)網(wǎng)絡(luò)結(jié)合構(gòu)造評(píng)估函數(shù)

增強(qiáng)學(xué)習(xí)與神經(jīng)網(wǎng)絡(luò)結(jié)合構(gòu)造評(píng)估函數(shù)是通過(guò)瞬時(shí)差分（TD）算法訓(xùn)練以神經(jīng)網(wǎng)絡(luò)表示的評(píng)估函數(shù)，其中TD算法是增強(qiáng)學(xué)習(xí)方法中的一種，這種算法的思想是通過(guò)相鄰狀態(tài)之間的差值引導(dǎo)智能體完成對(duì)未知狀態(tài)的預(yù)測(cè)。神經(jīng)網(wǎng)絡(luò)（圖1）是由許多神經(jīng)元互連在一起所組成的復(fù)雜網(wǎng)絡(luò)，通過(guò)不斷調(diào)整網(wǎng)絡(luò)權(quán)值達(dá)到學(xué)習(xí)的目的。

圖1 神經(jīng)網(wǎng)絡(luò)

TD與神經(jīng)網(wǎng)絡(luò)結(jié)合學(xué)習(xí)評(píng)估函數(shù)的具體過(guò)程是：首先，通過(guò)神經(jīng)網(wǎng)絡(luò)形成評(píng)估函數(shù)。神經(jīng)網(wǎng)絡(luò)的輸入層表示的是象棋的當(dāng)前局面，輸出層表示的是對(duì)當(dāng)前棋局的評(píng)估值。如圖1，輸入層中A1，A2…A90表示的是當(dāng)前棋盤(pán)中每個(gè)點(diǎn)的狀態(tài)。輸出層中C表示的是對(duì)當(dāng)前棋局的評(píng)估值，C的取值范圍是0到1之間，當(dāng)C＝1表示取勝，C＝0表示失敗。其次，根據(jù)棋局的最終結(jié)果，使用TD預(yù)測(cè)網(wǎng)絡(luò)誤差。最后，使用誤差反傳的方法不斷修改節(jié)點(diǎn)的權(quán)值來(lái)逼近精確評(píng)估值。

2．增強(qiáng)學(xué)習(xí)與數(shù)據(jù)庫(kù)結(jié)合構(gòu)造評(píng)估函數(shù)

象棋比賽時(shí)，輸棋一方常常是因?yàn)橄缕暹^(guò)程中的某一步或某幾步出現(xiàn)失誤，最終導(dǎo)致失敗。如果能把判斷失誤的局面記下來(lái)，下次再遇到同樣的局面時(shí)就不會(huì)犯同樣的錯(cuò)誤了?；谶@樣的思想，增強(qiáng)學(xué)習(xí)與數(shù)據(jù)庫(kù)結(jié)合構(gòu)造評(píng)估函數(shù)的算法應(yīng)運(yùn)而生。該算法的具體過(guò)程是：首先，博弈系統(tǒng)進(jìn)行比賽，同時(shí)記錄與系統(tǒng)預(yù)測(cè)不同的對(duì)手招法。其次，如果這些招法導(dǎo)致了對(duì)手的獲勝，那么就通過(guò)增強(qiáng)學(xué)習(xí)的方法修改這些局面的評(píng)估值。最后，將這些局面和相應(yīng)的評(píng)估值放入到數(shù)據(jù)庫(kù)中。這樣下次再遇到同樣的局面時(shí)就可以直接從數(shù)據(jù)庫(kù)中取出相應(yīng)的評(píng)估值，從而達(dá)到自學(xué)習(xí)的效果。

3．遺傳算法優(yōu)化評(píng)估函數(shù)

遺傳算法是一種全局優(yōu)化算法，它借用了生物遺傳學(xué)的方法，通過(guò)選擇，交叉、變異等機(jī)制實(shí)現(xiàn)了個(gè)體適應(yīng)性的提高，遺傳算法優(yōu)化評(píng)估函數(shù)時(shí)，每組染色體串代表的是一組評(píng)估函數(shù)的參數(shù)，至于染色體串的編碼方式通常采用的是二進(jìn)制編碼的方式，適應(yīng)度函數(shù)采用的是錦標(biāo)賽算法。遺傳算法在進(jìn)行優(yōu)化時(shí)，每次讓兩個(gè)個(gè)體之間進(jìn)行互換先后手的兩場(chǎng)比賽，如果一方獲勝，那么對(duì)該方的適應(yīng)度進(jìn)行獎(jiǎng)勵(lì)，輸了對(duì)適應(yīng)度進(jìn)行懲罰，和了則不操作。當(dāng)每?jī)蓚€(gè)個(gè)體之間都進(jìn)行先后手互換的兩場(chǎng)比賽之后，找出適應(yīng)度最高的一些染色體作為下一代的父?jìng)€(gè)體，通過(guò)對(duì)這些父?jìng)€(gè)體進(jìn)行交叉和變異的操作形成新的種群。

自學(xué)習(xí)方法構(gòu)造評(píng)估函數(shù)的優(yōu)點(diǎn)是：一方面使搜索引擎和評(píng)估函數(shù)達(dá)到一種平衡，這樣既可以保證評(píng)估函數(shù)的準(zhǔn)確性在可接受的范圍內(nèi)，又保證了搜索引擎達(dá)到一個(gè)理想的搜索深度。同時(shí)，評(píng)估函數(shù)也可以與博弈系統(tǒng)中的其他部分進(jìn)行有效的合作。另一方面使博弈系統(tǒng)具有自學(xué)習(xí)的能力，也就是使它具有了“智能”。這樣可以使博弈系統(tǒng)通過(guò)“自身”的經(jīng)驗(yàn)提高棋力，從而實(shí)現(xiàn)在沒(méi)有人（或外力）的干預(yù)下達(dá)到提高棋力的目的。這種方法的缺點(diǎn)是：算法的訓(xùn)練時(shí)間過(guò)長(zhǎng)。評(píng)估函數(shù)進(jìn)行優(yōu)化時(shí)，需要博弈系統(tǒng)進(jìn)行大量的實(shí)驗(yàn)，反復(fù)調(diào)試才能確定一個(gè)合適的函數(shù)，而且算法容易陷入到局部極值中。

三、總結(jié)

本文詳細(xì)講述了中國(guó)象棋博弈系統(tǒng)中常用的構(gòu)造評(píng)估函數(shù)的方法：傳統(tǒng)的評(píng)估函數(shù)和自學(xué)習(xí)方法構(gòu)造的評(píng)估函數(shù)，并著重介紹了這兩類方法的實(shí)現(xiàn)原理以及各自的優(yōu)缺點(diǎn)?？傮w來(lái)說(shuō)，雖然這些技術(shù)已經(jīng)在很多棋類系統(tǒng)中獲得了成功，但要想在中國(guó)象棋計(jì)算機(jī)博弈中取得同樣的效果，還需要與中國(guó)象棋的特點(diǎn)加以結(jié)合，并不斷完善。不過(guò)，隨著中國(guó)象棋博弈研究的深入和越來(lái)越多的學(xué)者投身到這項(xiàng)研究中，中國(guó)象棋博弈系統(tǒng)成功的日子已經(jīng)不遠(yuǎn)了。

［1］Sheng Xing，Bo－Jun Xie，Chun－Ru Dong，Yu－lin He．Neural Net wor k Co mbined with TD Lear ning in Chinese Chess Procedure．International Conference on Machine Learning and Cybernetics．2008．

［2］Shi－Ji m Yen，Jr－Chang Chen，Tai－Ning Yang，Shun－Chin Hsu．Computer Chinese Chess．ICGA．2004，（03）．

［3］付強(qiáng)，陳煥文．中國(guó)象棋人機(jī)對(duì)弈的自學(xué)習(xí)方法研究［J］．計(jì)算機(jī)技術(shù)與發(fā)展．2007，（12）．

［4］王驕，王濤，羅艷紅等．中國(guó)象棋計(jì)算機(jī)博弈系統(tǒng)評(píng)估函數(shù)的自適應(yīng)遺傳算法實(shí)現(xiàn)［J］．東北大學(xué)學(xué)報(bào)．2005，（10）．

Analysis of Chinese Chess Evaluation Function

DU Xiang－ran

（Tianjin Mariti me Vocational College，Tianjin 300350 China）

Computer－game of Chinese chess is an i mportant research field of artificial intelligence，whose core is to effectively combine the search algorith m and the evaluation f unction．This paper introduces and analyzes the common constructor for evaluation f unction in computer－game of Chinese chess

Chinese chess；evaluation f unction；lear ning reinforcement；neural net work

O39

A

1673－582X（2012）02－0087－03

2011－09－02

杜向然（1982－），男，天津人，天津海運(yùn)職業(yè)學(xué)院信息工程系助教，碩士研究生，主要研究方向是人工智能與機(jī)器博弈。