- 相關(guān)推薦
面向中國象棋的人機博弈系統(tǒng)研究
１４
湖南農(nóng)業(yè)大學(xué)學(xué)報（社會科學(xué)版?素質(zhì)教育研究）
?ＪｏｕｒｎａｌｏｆＨｕｎａｎＡｇｒｉｃｕｌｔｕｒａｌＵｎｉｖｅｒｓｉｔｙ（ＳｏｃｉａｌＳｃｉｅｎｃｅｓＲｅｓｅａｒｃｈｏｎＱｕａｌｉｔｙＥｄｕｃａｔｉｏｎ）
面向中國象棋的人機博弈系統(tǒng)研究
高建良
（華東理工大學(xué)信息科學(xué)與工程學(xué)院
摘
上海
２００５４０）
要：主要研究了以下搜索算法，負(fù)極大值法，Ａｌｐｈａ－Ｂｅｔａ法，使用歷史啟發(fā)和置換表的Ａｌｐｈａ－Ｂｅｔａ法等。估值是象棋人工智能的重
要組成部分，估值函數(shù)的評估標(biāo)準(zhǔn)要看幾個方面：棋子的基本價值，棋子的靈活性還有棋子的威脅性和攻擊性。
關(guān)鍵詞：中國象棋；搜索算法；Ａｌｐｈａ－Ｂｅｔａ法；估值一、研究背景
深藍(lán)”與當(dāng)時的國際象棋１９９７年，ＩＢＭ公司的超級計算機“
世界冠軍卡斯帕羅夫進(jìn)行了一場大肆渲染的比賽，這次被卡斯帕羅夫稱作“終于來臨的一天”的比賽以卡氏的失敗而告終。ＩＢＭ公司將“深
第一文庫網(wǎng)
藍(lán)”的獲勝稱作是人工智能領(lǐng)域的一個里程碑。人類對機器博弈的研究衍生了大量的研究成果，這些成果不但對人工智能的其它領(lǐng)域產(chǎn)生了重要影響，而且由此衍生而來的多種應(yīng)用，在諸如航空調(diào)度、天氣預(yù)報、資源勘探、軍事博弈，金融／經(jīng)濟調(diào)控等領(lǐng)域，也取得了大量引人矚目的成就。
在我國，中國象棋有著深厚的群眾基礎(chǔ)，能把這項古老的國粹和現(xiàn)代計算機技術(shù)相結(jié)合，編制出超過人類智慧的中國象但由于中棋軟件，是許多研究中國象棋軟件人夢寐以求的目標(biāo)。
國象棋在計算機實現(xiàn)方面比國際象棋更加復(fù)雜，而且中國象棋博弈技術(shù)研究落后于國際象棋，所以中國象棋軟件還遠(yuǎn)未達(dá)到世界冠軍水平。但近年來通過許多中國象棋軟件編程愛好者和多個象棋開發(fā)團(tuán)隊的努力，使中國象棋軟件水平有長足的進(jìn)步，慢棋已達(dá)到業(yè)余大師水平，快棋可以和象棋大師對抗。
件實現(xiàn)更加復(fù)雜。
現(xiàn)有的計算機的運算能力仍然十分有限。不可能３．估值。
一直搜索到分出輸贏的那一步，在有限搜索深度的末端，我們可利用以下幾種靜態(tài)的方法，來估計局面的優(yōu)劣：
（１）棋子的基本價值。棋子的價值評估，簡單的說就是評估
雙方都有哪些棋子在棋盤上。根據(jù)經(jīng)驗，可以讓一個車價值為
１０００，一個馬價值為５００，一個兵價值為１００等等。將的價值為
無限大（通常用一個遠(yuǎn)大于其他棋子的數(shù)）。一方的棋子總值就是棋盤上存活的該方棋子乘以棋子價值的和。
（２）棋子的位置。根據(jù)棋子所處的位置進(jìn)行估值。比如說，
過河兵的價值會遠(yuǎn)遠(yuǎn)大于沒有過河的兵，當(dāng)頭炮一般來說會更有威脅。
（３）棋子的靈活性。棋子的靈活性是指棋子的活動范圍，通
常是越大越好。一匹不能動的馬很難在棋局中發(fā)揮重要作用；同樣，一個蹲在角落里的車也是價值不高的。
（４）棋子的關(guān)系評估。棋子間的關(guān)系也是估值的重要內(nèi)容
之一，我們可以將某個棋子被對方棋子威脅看成是一個不利的因素。
１．棋盤表示。棋盤表示就是使用一種數(shù)據(jù)結(jié)構(gòu)來描述棋
一個典型的中國盤及棋盤上的棋子，通常是使用一個二維數(shù)組。
象棋棋盤是使用９×每一個元素代表棋盤上１０的二維數(shù)組表示。的一個交點。一個沒有棋子的交點所對應(yīng)的元素是０，一個黑帥對應(yīng)的元素是１，黑士則用２表示等等，依此類推，棋盤的數(shù)據(jù)表示直接影響到程序的時間及空間復(fù)雜度。
（５）象棋專業(yè)知識加權(quán)。一個優(yōu)秀的估值還可以對特別的
情形加權(quán)。比如空心炮和三子歸邊等情形可以得到額外的加分。
４．搜索技術(shù)。對于計算機來說，直接通過棋盤信息判別走
法的好壞并不精確。除了輸贏這樣的局面可以可靠地判別外，其他的判斷都只能做到大致估計。判別兩種走法孰優(yōu)孰劣的一個好方法就是察看棋局走下去的結(jié)果。也就是向下搜索若干步，然后比較發(fā)展下去的結(jié)果。為了避免差錯，我們假定對手的思考也和我們一樣，也就是，我們想到的內(nèi)容，對手也想到了。這就是極大極小搜索算法的基本原則，極大極小搜索算法是本書中所有
２．走法產(chǎn)生。博弈的規(guī)則決定了哪些走法是合法的，走法
產(chǎn)生是博弈程序中一個相當(dāng)復(fù)雜而且耗費運算時間的方面。
在中國象棋中，一般情況下每一局面有２０～６０種走法，平均４０種走法，而國際象棋平均只有３５種走法，所以中國象棋軟
參考文獻(xiàn)：
［１］鐘建玲．非英語專業(yè)新生英語自主學(xué)習(xí)現(xiàn)狀分析與思考［Ｊ］．惠州學(xué)院
學(xué)報，２００６，（１）：１１０～１１４．
外語教育出版社，２００４．
大學(xué)英語課堂教學(xué)要求（試行）》［Ｊ］．外語界，２００５，（２）：［５］夏紀(jì)梅．解讀《
１２－１４．
［２］羅立勝．理工科學(xué)生外語學(xué)習(xí)行為模式的探討［Ｊ］．外語與外語教
學(xué)，２００１，（９）：３１～３３．
作者簡介：
鐘建玲（１９７３－），女，廣西昭平人，講師，研究方向：應(yīng)用語言學(xué)，大學(xué)英語教學(xué)。
［３］朱菊芬．非英語專業(yè)新生英語學(xué)習(xí)現(xiàn)狀調(diào)查［Ｊ］．外語界，２００３，（１）：
４０～４７．
［４］教育部高等教育司．大學(xué)英語課程教學(xué)要求（試行）［Ｍ］．上海：上海
２００７年１１月高等教育
湖南農(nóng)業(yè)大學(xué)學(xué)報（社會科學(xué)版?素質(zhì)教育研究）
?ＪｏｕｒｎａｌｏｆＨｕｎａｎＡｇｒｉｃｕｌｔｕｒａｌＵｎｉｖｅｒｓｉｔｙ（ＳｏｃｉａｌＳｃｉｅｎｃｅｓＲｅｓｅａｒｃｈｏｎＱｕａｌｉｔｙＥｄｕｃａｔｉｏｎ）
１５
搜索算法的基礎(chǔ)。在過去的幾十年中，一些相當(dāng)成功的改進(jìn)大大提高了極大極小搜索的效率。Ａｌｐｈａ－Ｂｅｔａ剪枝、置換表、歷史啟發(fā)等手段的綜合應(yīng)用將搜索效率提高了幾個數(shù)量級。
二、主流搜索算法
—極大極小算法。假定我們有一個函１．最基本的算法——
數(shù)可以為每一局面的優(yōu)劣評分。例如甲勝為＋∞；乙勝為－∞；和局為０；其他的情形依據(jù)雙方剩余棋子的數(shù)量及位置評定－∞～＋這樣我們可以建立一棵固定深度的搜索樹，∞之間的具體分?jǐn)?shù)。
其葉子節(jié)點不必是終了狀態(tài)，而只是固定深度的最深一層的節(jié)點，其值由上述函數(shù)評出；對于中間節(jié)點，甲方取子節(jié)點的最大值，乙方取子節(jié)點的最小值。
幾乎所有的人在使用基本的極大極小算法時都選擇了深度優(yōu)先搜索方法。這樣可以在搜索過程中的任何時候僅僅生成整棵樹的一小部分，搜索過的部分被立即刪去。顯然，這個算法對內(nèi)存的要求極低，往往在內(nèi)存只有幾千字節(jié)的機器上也可以實現(xiàn)。并且同其他的選擇相比，速度上也并不遜色。深度優(yōu)先搜索極大極小樹的過程，可以表示為一個遞歸的形式。
差已達(dá)７０倍之多。
置換表的效率隨層次加深而提高，在搜索深度為３層時，
Ａｌｐｈａ－Ｂｅｔａ＋置換表同基本的Ａｌｐｈａ－Ｂｅｔａ搜索中評估的葉節(jié)點
數(shù)目相差約２０％，到６層時此數(shù)目則相差達(dá)３倍。
隨著層數(shù)的加深，置換表的命中率逐漸提高，Ａｌｐｈａ－Ｂｅｔａ＋置換表的速度從第４層開始超過基本的Ａｌｐｈａ－Ｂｅｔａ。而
ＮｅｇａＳｃｏｕｔ＋置換表＋歷史啟發(fā)也從第５層開始超越Ａｌｐｈａ－Ｂｅｔａ＋
歷史啟發(fā)的速度。到第６層時其速度已是Ａｌｐｈａ－Ｂｅｔａ＋歷史啟發(fā)的２．２倍。
歷史啟發(fā)表現(xiàn)出了極高的性能。同置換表相比，歷史啟發(fā)占用的運算時間極少。就單項增強手段看來顯著地優(yōu)于其他方法。
三、估值函數(shù)實現(xiàn)
１．估值基礎(chǔ)
（１）棋子的價值評估。棋子的價值評估，簡單的說就是評估
雙方都有哪些棋子在棋盤上。根據(jù)我們的經(jīng)驗，可以讓一個車價值為５００，一個馬價值為３００，一個兵價值為１００等等。將的價值為無限大（通常用一個遠(yuǎn)大于其他棋子的數(shù)）。一方的棋子總值就是棋盤上存活的該方棋子乘以棋子價值的和。如果紅色的棋子價值總和大于黑色的棋子價值總和，通常這意味著紅方的局勢優(yōu)于黑方。
還可以加入一些其他的明顯規(guī)律，使估值函數(shù)的知識水平提高。例如，兵在棋局中的作用與其過河與否有很大的關(guān)系。一個過河兵的作用比未過河的兵對局勢的影響要大得多。顯然，我們可以把兵的價值根據(jù)其過河與否結(jié)合其他具體位置信息設(shè)計成動態(tài)的。
２．負(fù)極大值算法。負(fù)極大值算法的核心在于：父節(jié)點的值
是各子節(jié)點的值的負(fù)數(shù)的極大值。如要這個算法正確運作，還要注意一點額外的東西。估值函數(shù)必須對誰走棋敏感，也就是說對于一個該紅方走棋的局面返回正的估值的話，則對于一個該黑方走棋的局面返回負(fù)的估值。初看上去，負(fù)極大值算法比極大極在算小值算法稍難理解，但事實上負(fù)極大值算法更容易被使用。法的原理上，這兩種算法完全等效。
３．Ａｌｐｈａ－Ｂｅｔａ搜索算法。將Ａｌｐｈａ剪枝和Ｂｅｔａ剪枝加入ｍｉｎｉｍａｘ搜索，就得到Ａｌｐｈａ－Ｂｅｔａ搜索算法。
Ａｌｐｈａ－Ｂｅｔａ搜索能夠讓我們忽略許多節(jié)點的搜索。對于每
一個被忽略的非葉子節(jié)點來說，這都意味著不僅節(jié)點本身，而且節(jié)點下面的子樹也被忽略掉了。這就導(dǎo)致了Ａｌｐｈａ－Ｂｅｔａ搜索需要遍歷的節(jié)點遠(yuǎn)遠(yuǎn)少于極大極小算法所遍歷的節(jié)點。這也同時意味著對搜索同一棵樹來說，Ａｌｐｈａ－Ｂｅｔａ搜索所花費的時間遠(yuǎn)遠(yuǎn)少于極大極小算法所花費的時間。
同極大極小搜索算法一樣，Ａｌｐｈａ－Ｂｅｔａ搜索算法也有點繁瑣，我們不僅要在奇數(shù)層進(jìn)行ａｌ－ｐｈａ剪枝，而且還要在偶數(shù)層進(jìn)行ｂｅｔａ剪枝。不過只要將負(fù)極大值的形式套用上去，這樣在任何一層都只進(jìn)行ｂｅｔａ剪枝，它就會同負(fù)極大值算法一樣簡潔。
隨著搜索深度的增加，Ａｌｐｈａ－Ｂｅｔａ搜索同負(fù)極大值搜索在時間耗費上和搜索的葉節(jié)點數(shù)目上的差距在迅速增大。即使僅僅在第４層，二者在搜索效率上的差距也超過了２０倍。
（２）棋子的靈活性與棋盤控制。棋子的靈活性是指棋子的
活動范圍，通常是越大越好。一匹不能動的馬很難在棋局中發(fā)揮重要作用；同樣，一個蹲在角落里的車也是價值不高的。
評估棋子的靈活性較為簡單，將一個棋子的所有合法走法羅列出來，乘上該種棋子每一可走步的價值就行了。
與靈活性評估類似，還可以評估博弈雙方對棋盤上位置的控制能力。在象棋中，如果某一位置落在某方棋子的合法走步上，就可以認(rèn)為被該方控制。如果某一位置同時落在雙方的合法走步上，我們可以根據(jù)雙方控制該位置的棋子數(shù)量及棋子價值來決定孰優(yōu)孰劣。能控制更多位置的一方應(yīng)在這項評分上占優(yōu)。
（３）棋子關(guān)系的評估。棋子間的關(guān)系也是估值的重要內(nèi)容
之一，我們可以將某個棋子被對方棋子威脅看成是一個不利的因素。例如紅車的位置在黑馬的合法走步當(dāng)中，此時我們可以把紅車的價值減去一個值（例如２００）來刻畫這種情形。而如果紅馬在黑車的合法走步之中，而紅馬同時也在紅卒的合法走步之中，我們可以認(rèn)為紅馬置于紅卒的保護(hù)之下，沒有受到威脅，價值不變。
棋子關(guān)系的評估應(yīng)考慮到該誰走棋的問題。如果某個紅馬落在黑炮的合法走步之內(nèi)，但此時輪到紅方走棋，應(yīng)認(rèn)為紅馬受
４．使用歷史啟發(fā)和置換表的Ａｌｐｈａ－Ｂｅｔａ的搜索算法。在
各種增強手段當(dāng)中，歷史啟發(fā)對于減少葉子節(jié)點數(shù)目有極大的作用。這也從另一方面證實了Ａｌｐｈａ－Ｂｅｔａ剪枝的效率對節(jié)點順序的極度敏感。當(dāng)置換表和歷史啟發(fā)共同作用時，節(jié)點數(shù)目進(jìn)一步下降了。搜索的最大深度到達(dá)６層的時候，ＮｅｇａＳ－ｃｏｕｔ＋置換表＋歷史啟發(fā)同基本的Ａｌｐｈａ－Ｂｅｔａ搜索中評估的葉節(jié)點數(shù)目相
２００７年１１月高等教育
１６
湖南農(nóng)業(yè)大學(xué)學(xué)報（社會科學(xué)版?素質(zhì)教育研究）
?ＪｏｕｒｎａｌｏｆＨｕｎａｎＡｇｒｉｃｕｌｔｕｒａｌＵｎｉｖｅｒｓｉｔｙ（ＳｏｃｉａｌＳｃｉｅｎｃｅｓＲｅｓｅａｒｃｈｏｎＱｕａｌｉｔｙＥｄｕｃａｔｉｏｎ）
到的威脅較輕。而如果此時輪到黑方走棋，就應(yīng)認(rèn)為紅馬受到的威脅很大，應(yīng)減去一個相對較大的值了。如果將被對方威脅，且輪到對方走棋，此時應(yīng)結(jié)束估值返回失敗的估值（通常是極大或極小值）。棋子間關(guān)系的評估可以在很大程度上提高估值的精度，通常是博弈估值的必備內(nèi)容。
容易戰(zhàn)勝；然而在考慮了棋子靈活性之后，就不會再出現(xiàn)孤炮進(jìn)入敵群子中的冒進(jìn)走法，估值比較完備，人工智能比較好。
２．不同搜索方式與搜索深度結(jié)果分析
Ａｌｐｈａ－Ｂｅｔａ搜索能夠讓我們忽略許多節(jié)點的搜索。對于每
一個被忽略的非葉子節(jié)點來說，這都意味著不僅節(jié)點本身，而且節(jié)點下面的子樹也被忽略掉了。這就導(dǎo)致了Ａｌｐｈａ－Ｂｅｔａ搜索需要遍歷的節(jié)點遠(yuǎn)遠(yuǎn)少于極大極小算法所遍歷的節(jié)點。這也同時意味著對搜索同一棵樹來說，Ａｌｐｈａ－Ｂｅｔａ搜索所花費的時間遠(yuǎn)遠(yuǎn)少于極大極小算法所花費的時間。
選擇ＡｌｐｈａＢｅｔａＳｅａｒｃｈＥｎｇｉｎｅ，分別在１￣５層的深度上運行，與負(fù)極大值的搜索引擎比較，就會發(fā)現(xiàn)，在同樣的深度下，
２．估值核心的優(yōu)化
（１）估值函數(shù)的速度。在博弈樹搜索的過程中，估值核心所
花費的運算時間，對于搜索的速度有著至關(guān)重要的影響。隨著搜索層數(shù)的加深，葉子節(jié)點的數(shù)目迅速上升，估值函數(shù)被數(shù)以百萬次的調(diào)用，花費了大量的運算時間。如何提高估值函數(shù)的速度，也成了博弈性能改進(jìn)的重要話題。
（２）估值函數(shù)與博弈性能。在博弈程序的幾大主要部分
里，估值函數(shù)是與具體的棋類知識緊密結(jié)合的一部分。可以說估值函數(shù)在很大程度上決定了博弈程序的棋力高低。顯然，開發(fā)人員可以向估值函數(shù)加入大量的棋類知識，使之對于局面的評估更為精確，也可以使用簡單的估值函數(shù)，以期能夠使估值的過程簡單而節(jié)省運算時間，期望通過更深層的搜索可以使棋力提高。
一般來說過于簡單的估值函數(shù)和過于復(fù)雜的估值函數(shù)同樣性能不佳。在同等的知識含量下，速度越快，性能越高。在同等速度之下，知識量越大性能越高。在速度和知識量二者的相互作用下，開發(fā)者要尋找的是一種平衡，是能夠使性能最大化的速度和知識量。
四、結(jié)果分析
Ａｌｐｈａ－Ｂｅｔａ搜索引擎的搜索速度快得多。而且，對于同樣的局
面，在同樣的搜索深度下，二者找到的最佳走法完全一樣。
五、結(jié)束語
１．總結(jié)
本文對中國象棋的兩個關(guān)鍵技術(shù)：搜索技術(shù)與估值函數(shù)進(jìn)行了研究，并對不同的搜索技術(shù)與不同估值函數(shù)帶來的不同結(jié)果進(jìn)行了分析，通過分析得出了這些技術(shù)對中國象棋的適合程度。
２．需要繼續(xù)研究及有待解決的問題
（１）估值函數(shù)。在開發(fā)的系統(tǒng)中估值函數(shù)考慮的因素還不
夠全，很多看似細(xì)小的因素在實戰(zhàn)中其實影響很大；估值方法中還沒有引進(jìn)歷史知識，棋譜庫沒有建立，無法跟據(jù)棋譜中已有下法來調(diào)整估值結(jié)果；沒有加入經(jīng)驗值，如空心炮等大家公認(rèn)為有利的局面帶來的附加值等等。
１．不同估值方式結(jié)果分析。如果將靈活性的賦值都?xì)w０，
并且將循環(huán)統(tǒng)計掃描的數(shù)據(jù)（有關(guān)威脅性）去掉，則估值函數(shù)很簡單，下出的棋子很幼稚，現(xiàn)以當(dāng)頭炮走法為例，則電腦走法：紅（人）炮二平五、黑（電腦）車１進(jìn)１、紅炮五進(jìn)四、黑車１平２。
如果將靈活性的賦值都?xì)w０，而將循環(huán)統(tǒng)計掃描的數(shù)據(jù)（有關(guān)威脅性）加上，電腦智能一般，仍以當(dāng)頭炮為例，走法如下：紅（人）炮二平五、黑（電腦）炮２進(jìn)７、紅炮五進(jìn)四、黑馬２進(jìn)３。
如果將靈活性的因素考慮進(jìn)去，并且將循環(huán)統(tǒng)計掃描的數(shù)據(jù)（有關(guān)威脅性）加上，電腦智能不錯，仍以當(dāng)頭炮為例，走法如下：紅（人）炮二平五、黑（電腦）馬２進(jìn)３。
通過上述３次改變的比較，我們可以看出只考慮棋子的基本價值，估值函數(shù)會漏洞很多，導(dǎo)致電腦人工智能很差；考慮了棋子的位置和威脅性，雖然比上一種進(jìn)步許多，但是走招比較激進(jìn)，只考慮了棋子威脅和全局的得分，不靈活，人工智能一般，很
（２）搜索算法。搜索算法在兩個平臺中沒有得到很好的體
現(xiàn)，在系統(tǒng)的研究中因為搜索深度一般不是很大，搜索算法帶來的影響很難通過實驗得出精確結(jié)論；沒有加入殘局庫，無法在某些應(yīng)該有輸贏結(jié)論的局面下得出完全正確的下法。
參考文獻(xiàn)：
［１］王小春．ＰＣ游戲編程（人機博弈）［Ｍ］．重慶：重慶大學(xué)出版社，２００２．［２］陸汝鈐．人工智能［Ｍ］．北京：科學(xué)出版社，１９９５．
［３］王永慶．人工智能原理與方法［Ｍ］．西安：西安交通大學(xué)出版社，１９９８．［４］何華燦．人工智能導(dǎo)論［Ｍ］．西安：西北工業(yè)大學(xué)出版社，１９８８．［５］楊祥金．人工智能［Ｍ］．重慶：科學(xué)技術(shù)文獻(xiàn)出版社重慶分社，１９８８．
作者簡介：
高建良（１９６３－），男，講師，碩士，教研室主任。
２００７年１１月高等教育
【面向中國象棋的人機博弈系統(tǒng)研究】相關(guān)文章：
面向航天制造企業(yè)的制造執(zhí)行系統(tǒng)研究與應(yīng)用05-02
無人機戰(zhàn)術(shù)控制系統(tǒng)研究04-27
無人機安全監(jiān)控與健康管理系統(tǒng)研究04-29
無人機故障預(yù)測與健康管理系統(tǒng)研究05-02
無人機任務(wù)規(guī)劃系統(tǒng)研究及發(fā)展05-02
面向供應(yīng)鏈管理的成本核算模型與系統(tǒng)研究05-03