張恩海,李彥平,朱俊威

(沈陽(yáng)大學(xué) 遼寧省裝備制造綜合自動(dòng)化重點(diǎn)實(shí)驗(yàn)室,遼寧 沈陽(yáng) 110044)

中國(guó)象棋多自動(dòng)機(jī)復(fù)合模型及其估值方法研究

張恩海,李彥平,朱俊威

(沈陽(yáng)大學(xué) 遼寧省裝備制造綜合自動(dòng)化重點(diǎn)實(shí)驗(yàn)室,遼寧 沈陽(yáng) 110044)

應(yīng)用離散事件動(dòng)態(tài)系統(tǒng)有限自動(dòng)機(jī)理論,建立了中國(guó)象棋多自動(dòng)機(jī)復(fù)合模型·針對(duì)中國(guó)象棋機(jī)器博弈中傳統(tǒng)靜態(tài)估值方法對(duì)局面估值的不準(zhǔn)確性,提出了動(dòng)態(tài)估值方法·通過(guò)對(duì)原有的靜態(tài)估值方法引入變量參數(shù),提高了估值的準(zhǔn)確性·

機(jī)器博弈;多自動(dòng)機(jī);靜態(tài)估值;動(dòng)態(tài)估值

機(jī)器博弈,又稱計(jì)算機(jī)博弈,就是讓計(jì)算機(jī)像人一樣思維,進(jìn)行棋類的博弈·1997年5月,計(jì)算機(jī)“深藍(lán)”戰(zhàn)勝了國(guó)際象棋大師卡斯帕羅夫,標(biāo)志計(jì)算機(jī)在棋類博弈上已經(jīng)超越了人類·事實(shí)上,“深藍(lán)”的這種思維并不同于人類的智慧,雖然它戰(zhàn)勝了國(guó)際象棋大師,但并不意味著計(jì)算機(jī)就比人腦聰明·

計(jì)算機(jī)缺乏的是人類的意識(shí),在人機(jī)博弈中計(jì)算機(jī)獲勝的原因在于其強(qiáng)大的計(jì)算能力·稱其為“智能”還為時(shí)過(guò)早,只不過(guò)是從窮舉出數(shù)萬(wàn)億的可能情況中選擇最好的棋步而已·然而,用人工智能來(lái)代替人腦或者協(xié)助人腦工作是我們不懈的追求·

近年來(lái),作為人工智能學(xué)科的“果蠅”,計(jì)算機(jī)博弈日益成為人工智能工作者的主要研究對(duì)象之一[1]·

1 多自動(dòng)機(jī)復(fù)合模型

在傳統(tǒng)的系統(tǒng)與控制理論領(lǐng)域中,主要研究對(duì)象限于一類本質(zhì)上屬于物理世界范疇的連續(xù)變量動(dòng)態(tài)系統(tǒng),簡(jiǎn)稱為CVDS·而離散事件動(dòng)態(tài)系統(tǒng)是區(qū)別于 CVDS的另一類系統(tǒng),簡(jiǎn)稱DEDS[2]·DEDS由離散事件驅(qū)動(dòng),是本質(zhì)離散的狀態(tài)與事件按照一定的運(yùn)行規(guī)則相互作用,進(jìn)而導(dǎo)致系統(tǒng)狀態(tài)不斷演化的一類動(dòng)態(tài)系統(tǒng)[3]·

中國(guó)象棋是廣受歡迎的棋類游戲·通過(guò)對(duì)中國(guó)象棋的屬性分析,不難發(fā)現(xiàn),中國(guó)象棋博弈系統(tǒng)主要由兩部分構(gòu)成,即局面和招法·招法是驅(qū)動(dòng)中國(guó)象棋博弈系統(tǒng)局面狀態(tài)演變的基本因素·局面的狀態(tài)都發(fā)生在離散時(shí)間點(diǎn),即在招法給出時(shí)局面才能發(fā)生躍變,其他時(shí)刻保持不變,并且在空間中具有一種不連續(xù)的固有屬性·招法的變化域和局面的狀態(tài)空間也都具有離散性·基于以上因素,有理由認(rèn)為中國(guó)象棋博弈系統(tǒng)屬于離散事件動(dòng)態(tài)系統(tǒng),招法即是觸發(fā)DEDS狀態(tài)變化的事件[4]·

中國(guó)象棋博弈過(guò)程中,局面間的轉(zhuǎn)換是由棋子的移動(dòng)引起的,所以對(duì)其每個(gè)棋子建立模型是非常必要的·

在棋子a行走時(shí),行棋規(guī)則和其他棋子會(huì)對(duì)棋子a的招法選擇產(chǎn)生一些制約·表1為復(fù)合制約表,32個(gè)棋子組成一個(gè)二維表,該表能夠清晰表現(xiàn)出每個(gè)棋子的可能招法,這樣,32個(gè)有限自動(dòng)機(jī)各自的行動(dòng)和相互的制約都可以十分清楚地表達(dá)了出來(lái)·按照復(fù)合制約表和復(fù)合模型,32個(gè)棋子就可以自由行動(dòng)起來(lái)·

在復(fù)合制約表中,KMM為棋子馬/馬的行棋規(guī)則,當(dāng)KMM為真時(shí),棋子馬/馬可行棋到目標(biāo)位置 qij,即

表1 復(fù)合制約表

2 動(dòng)態(tài)估值方法

估值方法和搜索算法,是中國(guó)象棋計(jì)算機(jī)博弈中的兩大核心問(wèn)題·估值方法的好壞直接影響棋力的高低·估值通常與博弈樹搜索結(jié)合使用·由于在較少的步數(shù)內(nèi),一般難以將死對(duì)方·在難以判斷輸贏的情況下判斷某一局面的好壞,可行的辦法就是對(duì)局面進(jìn)行量化,通過(guò)數(shù)值來(lái)衡量局面的優(yōu)劣·估值需要考慮不同類型的象棋知識(shí)[5]·

在對(duì)局面估值時(shí),預(yù)先設(shè)定好棋子的子力、位置、攻擊、靈活度等類型知識(shí)的分值·當(dāng)局面確定后,根據(jù)局面的信息直接調(diào)取對(duì)應(yīng)類型的知識(shí)的分值進(jìn)行加減運(yùn)算,計(jì)算過(guò)程中不存在變量,這種估值方法稱做靜態(tài)估值方法·在中國(guó)象棋計(jì)算機(jī)博弈中,靜態(tài)估值方法是普遍使用的估值方法·但該方法中預(yù)先設(shè)定好象棋類型知識(shí)的分值,是根據(jù)專家經(jīng)驗(yàn)得出的,由于專業(yè)棋手的經(jīng)驗(yàn)是隨著對(duì)局的增加而增加的,因此提出動(dòng)態(tài)估值方法,該方法在計(jì)算過(guò)程中,對(duì)靜態(tài)估值方法中部分類型知識(shí)引入權(quán)值變量,權(quán)值變量隨對(duì)局的增加而變化,能更有效地提高估值的準(zhǔn)確性·動(dòng)態(tài)估值方法下類型知識(shí)如下·

(1)子力·是棋子在某一局面下的價(jià)值·棋盤上的棋子的子力由棋子本身的價(jià)值、在棋盤上的位置和靈活度三部分組成·所以,某一局面的子力值為棋盤上所有己方棋子的子力之和,表達(dá)式為

式中,BV(a)為棋子a的本身價(jià)值;W Z(q(a))為棋子a所在位置的分值;L H(a,q(a))為棋子a靈活度的分值·

(2)攻擊·對(duì)弈的某一局面,從吃對(duì)方棋子的角度來(lái)表示對(duì)對(duì)方的威脅·如果己方棋子可以吃對(duì)方的某個(gè)棋子,就把對(duì)方棋子的子力據(jù)為己有·當(dāng)己方棋子可以同時(shí)吃對(duì)方多個(gè)棋子時(shí),因?yàn)橐徊街荒艹砸粋€(gè)棋子,所以將子力最大的對(duì)方棋子據(jù)為己有,其他的按一定比例占據(jù)·此比例系數(shù)可根據(jù)局面情況而定·最后把己方所有棋子的攻擊分值求和,表達(dá)式為

(3)被攻擊·同攻擊值的定義相反,在某一局面下,己方棋子受到對(duì)方棋子的威脅,分值設(shè)定與攻擊相似,但值為負(fù)數(shù)·顯然,己方的攻擊值等于對(duì)方的被攻擊值的相反數(shù),對(duì)方的攻擊值等于己方的被攻擊值的相反數(shù)·對(duì)方攻擊值表達(dá)式為

(4)將帥安全·計(jì)算將帥是否受到威脅·設(shè)定一個(gè)安全區(qū)域,從己方將帥所在行算起,五行內(nèi)如果有對(duì)方棋子,則說(shuō)明己方將帥已經(jīng)受到威脅,將帥安全的值也為負(fù),其表達(dá)式為

式中,ZL(d)為棋子d的子力;βd為比例系數(shù),0＜βd,表示對(duì)方棋子對(duì)己方將帥的威脅程度;D是己方安全區(qū)域內(nèi)的對(duì)方棋子的集合,d∈D·

(5)棋子配合·棋子配合是指棋子與棋子間的保護(hù)關(guān)系·重點(diǎn)是車/車、馬/馬、炮/的配合·當(dāng)一個(gè)棋子被保護(hù)時(shí),在棋子子力的基礎(chǔ)上加上其他棋子的子力·因?yàn)樵摲种抵饕瑢?duì)局面起作用的配合,如將帥旁邊的仕等,對(duì)局面的作用不是很大,所以要在子力前加一個(gè)比例系數(shù),表達(dá)式為

己方對(duì)局面的估值是求取各項(xiàng)分值之和,不僅要計(jì)算本方的,還要計(jì)算對(duì)方的.本方為正值,對(duì)方為負(fù)值,其代數(shù)和即為當(dāng)前局面的估值·己方局面評(píng)估值表達(dá)式為

顯然,與靜態(tài)估值相比,動(dòng)態(tài)估值在原估值方法的基礎(chǔ)上增加了參數(shù)αc,ηe,βd,γp,θj,ωk·參數(shù)確定方法如下(以紅方為例):

第一步,取一象棋名局實(shí)例,要求該實(shí)例中帶有紅方轉(zhuǎn)折性招法;

第二步,對(duì)該轉(zhuǎn)折性走法后的局面進(jìn)行估值,設(shè)值為

第三步,在博弈樹下,與該局面同為一層的其他局面中取估值最大的局面,設(shè)其值為

第六步,求解n元一次不等式組,求解參數(shù)的范圍·

每測(cè)試一局,都會(huì)對(duì)參數(shù)的相互關(guān)系進(jìn)行一次調(diào)整,隨著測(cè)試局?jǐn)?shù)的增加,參數(shù)的相互關(guān)系趨于穩(wěn)定·通過(guò)對(duì)實(shí)戰(zhàn)棋局的模擬,在參數(shù)相互關(guān)系下,手動(dòng)調(diào)整如表2所示·

表2 手動(dòng)調(diào)整表

驗(yàn)證此估值方法的優(yōu)越性,采用中國(guó)象棋名局進(jìn)行測(cè)試·如局面1至局面4所示,其為柳大華實(shí)戰(zhàn)百局144局(湖北柳大華先勝杭州陳孝)中的四個(gè)局面,局面1、3是對(duì)方走棋結(jié)束,局面2、4是我方走棋結(jié)束(應(yīng)手)·局面1到局面2是本局的轉(zhuǎn)折,如圖1形勢(shì),紅方退車邀兌黑車,一擊中的,使黑方陣勢(shì)立即崩潰·從局面1到局面2有35種走法,對(duì)可能出現(xiàn)的35個(gè)局面分別估值,結(jié)果局面2分值最高,故我方選擇局面2對(duì)應(yīng)的走法·

圖1 局面1至局面2

圖2 局面3至局面4

局面3到局面4是紅方穩(wěn)定勝局的走法,如圖2形勢(shì),紅方退相調(diào)整陣勢(shì),紅無(wú)后顧之憂·從局面3到局面4有46種走法,對(duì)可能出現(xiàn)的46個(gè)局面分別估值,結(jié)果局面4分值最高,故我方選擇局面4對(duì)應(yīng)的走法·

隨著模擬棋局的增加,參數(shù)的值也趨于穩(wěn)定·由象棋名局測(cè)試,可見該估值方法已接近象棋大師水平·

3 結(jié) 語(yǔ)

本文簡(jiǎn)單介紹了機(jī)器博弈·應(yīng)用有限自動(dòng)機(jī)理論對(duì)中國(guó)象棋建模·在傳統(tǒng)靜態(tài)估值基礎(chǔ)上提出了引入權(quán)值的動(dòng)態(tài)估值方法,并對(duì)估值的類型知識(shí)進(jìn)行了重新設(shè)定,使局面的判定信息更加準(zhǔn)確·通過(guò)對(duì)經(jīng)典棋局的檢驗(yàn),該估值方法對(duì)局面的判定已接近象棋大師水平·

[1] 徐心和,鄧志立,王驕.機(jī)器博弈研究面臨的各種挑戰(zhàn)[J].智能系統(tǒng)學(xué)報(bào),2008,3(4):288-293.

[2] 鄭大鐘,趙千川.離散事件動(dòng)態(tài)系統(tǒng)[M]·北京:清華大學(xué)出版社,2001.

[3] 徐心和,鄭新穎.棋牌游戲與事件對(duì)策[J].控制與決策,2007,22(7):787-790.

[4] 徐心和,王驕.中國(guó)象棋計(jì)算機(jī)博弈關(guān)鍵技術(shù)分析[J].小型微型計(jì)算機(jī)系統(tǒng),2006,27(6):961-969.

[5] 徐心和,王浩.孔凡禹事件對(duì)策理論及在棋類游戲中的應(yīng)用[J].中南大學(xué)學(xué)報(bào):自然科學(xué)版,2007,38(Sup1):718-721.

Multi-Automata Compound Model of Chinese Chess and Evaluation Methods

ZHAN G Enhai,L I Yanping,ZHU Junwei
(Key Laboratory of Manufacturing Industrial Integrated Automation,Shenyang University,Shenyang 110044,China)

According to the theory of discrete event dynamical systems(DEDS),a multi-automata compound model of Chinese Chess is established.The traditional static evaluation used in Chinese Chess game on computer currently could not reflect the information of situation accurately,so a method of dynamic evaluation is proposed.Moreover,by introducing parameter in the traditional method of static evaluation,the accuracy of evaluation is improved.

computer game;multi-automata;static evaluation;dynamic evaluation

TP 301.1

A

1008-9225(2011)02-0007-05

2010-11-10

張恩海(1983-),男,遼寧沈陽(yáng)人,沈陽(yáng)大學(xué)碩士研究生;李彥平(1957-),男,遼寧錦州人,沈陽(yáng)大學(xué)教授,博士·

【責(zé)任編輯:劉乃義】