劉霞 張建剛 邢勝

摘 要：象棋軟件一般可以通過很多方法提高棋力，但最好的方法是優(yōu)化數(shù)據(jù)結(jié)構(gòu)、改進(jìn)搜索方式，這兩種方法都有很高的博弈水平，但機(jī)器學(xué)習(xí)能力都較差。以前應(yīng)用數(shù)據(jù)庫自學(xué)習(xí)的方法都存在很大的缺陷。文章通過將判斷失誤的關(guān)鍵著法和局面值存儲(chǔ)到數(shù)據(jù)庫中，從而使后面的象棋步驟當(dāng)中相同局面時(shí)轉(zhuǎn)變策略，避免相同的失誤步驟，從而實(shí)現(xiàn)自學(xué)習(xí)能力。

關(guān)鍵詞：數(shù)據(jù)庫；博弈樹搜索；關(guān)鍵著法

引言

目前，象棋軟件大多數(shù)存在的問題是不具有自學(xué)習(xí)能力，以前主要應(yīng)用提高數(shù)據(jù)結(jié)構(gòu)和計(jì)算機(jī)運(yùn)行速度的方式來改進(jìn)象棋軟件的水平，而很少應(yīng)用通過數(shù)據(jù)庫記錄計(jì)算機(jī)下棋過程中好的著法和局面值的方法，這種方法可以使計(jì)算機(jī)在以后相同局面時(shí)，轉(zhuǎn)變象棋軟件策略，不重復(fù)失敗的老路，實(shí)現(xiàn)自學(xué)習(xí)能力。

1 棋類游戲典型的自學(xué)習(xí)方法

目前，自學(xué)習(xí)能力的實(shí)現(xiàn)方法有很多種，最主要有兩種：一是應(yīng)用加強(qiáng)的學(xué)習(xí)方法（包括三個(gè)方面：加強(qiáng)學(xué)習(xí)與神經(jīng)網(wǎng)絡(luò)相結(jié)合、同數(shù)據(jù)庫結(jié)合以及瞬時(shí)差分TD算法）；二是自適應(yīng)遺傳算法，其中重點(diǎn)是加強(qiáng)學(xué)習(xí)的TD方法。

1.1 加強(qiáng)學(xué)習(xí)同神經(jīng)網(wǎng)絡(luò)結(jié)合（RBP）

在計(jì)算機(jī)棋類軟件的發(fā)展過程中，機(jī)器自學(xué)習(xí)能力的發(fā)展有著成功的應(yīng)用，比如Gerald Tesauro在1995年推出的西洋雙陸棋TD-Gammon。通過150萬盤比賽，最后取得世界冠軍的水平。國內(nèi)也有這方面的相關(guān)研究，王一非，哈爾濱工程大學(xué)碩士，2007年在其畢業(yè)論文中詳細(xì)的說明并提出了應(yīng)用RBP的缺點(diǎn)：神經(jīng)網(wǎng)絡(luò)運(yùn)算量太大，自學(xué)習(xí)過程時(shí)間長，收斂時(shí)間過慢。

1.2 加強(qiáng)學(xué)習(xí)同數(shù)據(jù)庫結(jié)合

長沙理工大學(xué)碩士付強(qiáng)2006年在其論文《基于激勵(lì)學(xué)習(xí)的中國象棋研究》中已經(jīng)提出了將象棋軟件和數(shù)據(jù)庫結(jié)合的方法，記錄最好著法值，來提高自學(xué)習(xí)能力。經(jīng)過1萬多盤比賽結(jié)果，已經(jīng)下敗了傳統(tǒng)軟件。

1.3 瞬時(shí)差分TD 算法

早在1999年，ChrisSzeto就提出瞬時(shí)差分TD算法來優(yōu)化棋類軟件。經(jīng)過多次游戲?qū)嶒?yàn)，將修正后的棋子子力值保存到數(shù)據(jù)庫中，比之前通過經(jīng)驗(yàn)與試算估計(jì)的方法更容易取得比賽的勝利，說明起到了優(yōu)化作用。

2 基于數(shù)據(jù)庫自學(xué)習(xí)的原理及實(shí)現(xiàn)

我們對過去的方法進(jìn)行改進(jìn)。通過博弈樹搜索，利用數(shù)據(jù)庫記錄計(jì)算機(jī)不同的對手著法，只記錄計(jì)算機(jī)輸棋的情況，將搜索值賦給計(jì)算機(jī)存儲(chǔ)。當(dāng)計(jì)算機(jī)在以后的比賽中遇到此局面時(shí)，做出戰(zhàn)略調(diào)整。從而實(shí)現(xiàn)象棋軟件的自學(xué)習(xí)功能。這種方法尤其在計(jì)算機(jī)輸棋時(shí)，就要向下多搜兩層，所以值會(huì)更精確，值會(huì)更小，因?yàn)椴┺臉涫亲畲笞钚∷阉?，具體解決方案如圖1所示。

對比原方法：此方案中三角代表原來的方法，整個(gè)圖代表應(yīng)用數(shù)據(jù)庫后由原來第五層值變成了現(xiàn)在的第七層值，如此以來就多搜了兩層，所得值更小，更精確。

通過博弈樹的最大最小值搜索，所以當(dāng)深色方框的值更小時(shí)，它必被上層取最小值的圓所選中，而又因?yàn)樗闹敌。诟蠈尤∽畲笾禃r(shí)會(huì)被舍去，所以不會(huì)運(yùn)行最左邊的方案，從而轉(zhuǎn)變策略，實(shí)現(xiàn)了象棋軟件的自學(xué)習(xí)能力。實(shí)驗(yàn)中整盤棋會(huì)有很多種局面，如果按圖1方案，一開始就需要轉(zhuǎn)變策略，但實(shí)際上不必開局轉(zhuǎn)變。所以就需要判斷哪些是失敗的關(guān)鍵著法，需要對記錄著法分析局面值，有所選擇，將影響大的值保留下來，其他影響小的不做記錄，這樣不僅縮小了數(shù)據(jù)庫，而且讓策略的轉(zhuǎn)變發(fā)生在最合適時(shí)。通過實(shí)驗(yàn)得出，分別對正值，負(fù)值，最接近0的值進(jìn)行了實(shí)驗(yàn)，正值是代表勝利，負(fù)值代表輸棋，0值基本代表平局。通過實(shí)驗(yàn)分析，最后選取的關(guān)鍵著法值即為第一次出現(xiàn)劣勢且之后的棋無可挽回的下到輸?shù)闹ā?/p>

3 實(shí)驗(yàn)結(jié)果及分析

黑‘×表示每一局面值，藍(lán)‘○表示不同著法的局面值

此方法證實(shí)了它的自學(xué)習(xí)能力，采用王小春的象棋軟件和應(yīng)用數(shù)據(jù)庫象棋軟件對弈。數(shù)據(jù)庫象棋軟件又分為存儲(chǔ)全部不同著法和存儲(chǔ)關(guān)鍵著法。圖2所示的是數(shù)據(jù)庫軟件先行，同王小春的象棋軟件對弈輸棋的存儲(chǔ)值，黑點(diǎn)表示對弈31盤的評(píng)估值，藍(lán)圈表示存儲(chǔ)全部不同著法中16個(gè)不同值。存儲(chǔ)關(guān)鍵著法中存儲(chǔ)的是第四個(gè)籃圈值即第一次下降且以后沒有更高值的點(diǎn)。

第一局對弈，先行的數(shù)據(jù)庫象棋軟件輸給了王曉春的象棋軟件。數(shù)據(jù)庫象棋軟件將遇到的局面值存儲(chǔ)到數(shù)據(jù)庫中；第二局對弈，存儲(chǔ)關(guān)鍵著法通過記錄的關(guān)鍵著法獲勝，圖3線上的點(diǎn)顯示的是對弈贏棋的局面值；存儲(chǔ)全部不同著法一開始就改變策略，實(shí)施的著法是上一盤的對稱著法，所以又下輸了。第三局對弈，存儲(chǔ)全部不同著法也贏了王曉春的象棋軟件。經(jīng)上述實(shí)驗(yàn)表明在計(jì)算機(jī)輸棋局面下，通過數(shù)據(jù)庫搜索博弈樹，將值賦給此著法。同時(shí)只記錄關(guān)鍵著法，以減小數(shù)據(jù)庫規(guī)模，具有更好的自學(xué)習(xí)能力。

參考文獻(xiàn)

[1]Shi-Jim Yen， Jr-Chang Chen， Tai-Ning Yang， Shun-Chin Hsu， Computer Chinese Chess， ICGA Journal， March 2004.

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

[3]許舜欽.電腦西洋棋和電腦象棋的回顧與前瞻[J].電腦學(xué)刊，1990，2（2）.

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

[5]付強(qiáng)，陳煥文.基于RL算法的自學(xué)習(xí)博弈程序設(shè)計(jì)及實(shí)現(xiàn)[J].長沙理工大學(xué)學(xué)報(bào)，2007.12（4）：73-78.