基于數據庫自學習的中國象棋研究

劉霞 張建剛 邢勝

摘 要：象棋軟件一般可以通過很多方法提高棋力，但最好的方法是優化數據結構、改進搜索方式，這兩種方法都有很高的博弈水平，但機器學習能力都較差。以前應用數據庫自學習的方法都存在很大的缺陷。文章通過將判斷失誤的關鍵著法和局面值存儲到數據庫中，從而使后面的象棋步驟當中相同局面時轉變策略，避免相同的失誤步驟，從而實現自學習能力。

關鍵詞：數據庫；博弈樹搜索；關鍵著法

引言

目前，象棋軟件大多數存在的問題是不具有自學習能力，以前主要應用提高數據結構和計算機運行速度的方式來改進象棋軟件的水平，而很少應用通過數據庫記錄計算機下棋過程中好的著法和局面值的方法，這種方法可以使計算機在以后相同局面時，轉變象棋軟件策略，不重復失敗的老路，實現自學習能力。

1 棋類游戲典型的自學習方法

目前，自學習能力的實現方法有很多種，最主要有兩種：一是應用加強的學習方法（包括三個方面：加強學習與神經網絡相結合、同數據庫結合以及瞬時差分TD算法）；二是自適應遺傳算法，其中重點是加強學習的TD方法。

1.1 加強學習同神經網絡結合（RBP）

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

1.2 加強學習同數據庫結合

長沙理工大學碩士付強2006年在其論文《基于激勵學習的中國象棋研究》中已經提出了將象棋軟件和數據庫結合的方法，記錄最好著法值，來提高自學習能力。經過1萬多盤比賽結果，已經下敗了傳統軟件。

1.3 瞬時差分TD 算法

早在1999年，ChrisSzeto就提出瞬時差分TD算法來優化棋類軟件。經過多次游戲實驗，將修正后的棋子子力值保存到數據庫中，比之前通過經驗與試算估計的方法更容易取得比賽的勝利，說明起到了優化作用。

2 基于數據庫自學習的原理及實現

我們對過去的方法進行改進。通過博弈樹搜索，利用數據庫記錄計算機不同的對手著法，只記錄計算機輸棋的情況，將搜索值賦給計算機存儲。當計算機在以后的比賽中遇到此局面時，做出戰略調整。從而實現象棋軟件的自學習功能。這種方法尤其在計算機輸棋時，就要向下多搜兩層，所以值會更精確，值會更小，因為博弈樹是最大最小搜索，具體解決方案如圖1所示。

對比原方法：此方案中三角代表原來的方法，整個圖代表應用數據庫后由原來第五層值變成了現在的第七層值，如此以來就多搜了兩層，所得值更小，更精確。

通過博弈樹的最大最小值搜索，所以當深色方框的值更小時，它必被上層取最小值的圓所選中，而又因為它的值小，在更上層取最大值時會被舍去，所以不會運行最左邊的方案，從而轉變策略，實現了象棋軟件的自學習能力。實驗中整盤棋會有很多種局面，如果按圖1方案，一開始就需要轉變策略，但實際上不必開局轉變。所以就需要判斷哪些是失敗的關鍵著法，需要對記錄著法分析局面值，有所選擇，將影響大的值保留下來，其他影響小的不做記錄，這樣不僅縮小了數據庫，而且讓策略的轉變發生在最合適時。通過實驗得出，分別對正值，負值，最接近0的值進行了實驗，正值是代表勝利，負值代表輸棋，0值基本代表平局。通過實驗分析，最后選取的關鍵著法值即為第一次出現劣勢且之后的棋無可挽回的下到輸的著法。

3 實驗結果及分析

黑‘×表示每一局面值，藍‘○表示不同著法的局面值

此方法證實了它的自學習能力，采用王小春的象棋軟件和應用數據庫象棋軟件對弈。數據庫象棋軟件又分為存儲全部不同著法和存儲關鍵著法。圖2所示的是數據庫軟件先行，同王小春的象棋軟件對弈輸棋的存儲值，黑點表示對弈31盤的評估值，藍圈表示存儲全部不同著法中16個不同值。存儲關鍵著法中存儲的是第四個籃圈值即第一次下降且以后沒有更高值的點。

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

參考文獻

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

[2]徐心和，王驕.中國象棋計算機博弈關鍵技術分析[J].小型微型計算機系統，2006，27（6）：961-965.

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

[4]付強，陳煥文.中國象棋人機對弈的自學習方法研究[J].計算機技術與發展，2007，17（12）.

[5]付強，陳煥文.基于RL算法的自學習博弈程序設計及實現[J].長沙理工大學學報，2007.12（4）：73-78.