【摘要】 論述了哈希技術(shù)在中國象棋人機博弈系統(tǒng)的搜索引擎和開局庫中的應(yīng)用以及實現(xiàn)原理,論證了基于哈希技術(shù)的編碼方式的開局庫的優(yōu)越性,對基于哈希技術(shù)的置換表算法分析了使用單一的置換表所存在的缺陷,并通過數(shù)據(jù)證明了一種雙置換表的優(yōu)越性,使置換表這一啟發(fā)式搜索算法在搜索引擎中的作用更加合理。
 
【關(guān)鍵詞】 博弈樹； 置換表； 搜索引擎； 開局庫；

    引言
　　在中國象棋的人機博弈的研究中，局面搜索算法是核心，中國象棋的博弈過程中，針對某一局面，平均著法達到60步，故減少搜索的節(jié)點，提高搜索的速度和節(jié)省搜索過程中內(nèi)存開銷，就成了中國象棋搜索研究一個終極目標。Alpha-Beta搜索算法是人機博弈的一個基本算法，但是該算法在搜索過程中，存在大量的冗余[1]。本文即在這一基本算法的基礎(chǔ)上，加入置換表技術(shù)和Hash table技術(shù)，以提高搜索速度。
　　1 Alpha-Beta搜索算法
　　如圖1所示，結(jié)點下面的數(shù)字為該節(jié)點所代表的局面評估值。在左圖中，節(jié)點B的值為18，節(jié)點D的值為16，因為C節(jié)點要取其子節(jié)點的最小值，故可以判定節(jié)點C的值將小于或者等16，而A節(jié)點的值為B節(jié)點和C節(jié)點的最大值，這樣無論E節(jié)點和F節(jié)點的值為多少，都不影響A節(jié)點的取值，因為A節(jié)點此時肯定會取B節(jié)點的值18本文由筆耕文化傳播http://www.bigengculture.com/收集整理，這樣將節(jié)點D的后繼節(jié)點減去稱Alpha剪枝。觀察圖1的右半部的極大極小樹，A節(jié)點要取B節(jié)點和C節(jié)點的最小值，C節(jié)點要取其子結(jié)點的最大值，而D節(jié)點的值為18，故C節(jié)點的值最小為18，這個值已經(jīng)大于B節(jié)點的值了，所以無論E節(jié)點和F節(jié)點的值為多少，都不影響A了點的取值，所以將節(jié)點D的后繼節(jié)點減去稱Beta剪枝。
　　原始的Alpha-Beta搜索算法略顯繁瑣，需要在奇數(shù)層進行Alpha剪枝，在偶數(shù)層進行Beta剪枝，利用負極大值搜索的思想，可以統(tǒng)一在任何一層進行Beta剪枝。
　　2 置換表的思想
　　Alpha-Beta 搜索算法的剪枝過程對搜索節(jié)點的排序順序依賴很大，當搜索順序的排列為最差情況時，其搜索效果與極大極小值相同[2]。其實在搜索的過程中，隨著搜索層次的加深，會出現(xiàn)一些節(jié)點是原來搜索過的，如果能直接利用已經(jīng)搜索過的節(jié)點局面評估值，而不重新搜索一次，這樣相同于進行了很大程度的剪枝[3]。我們可以利用一個數(shù)組將已經(jīng)搜索過和節(jié)點保存起來，在搜索新的節(jié)點時，先到數(shù)組中檢查以前是否已經(jīng)搜索過本節(jié)點，如果是，則直接用數(shù)組里保存的局面評估值，如果沒有，則繼續(xù)正常搜索，這就是置換表（Transposition Table）的思想。
　　3 哈希表來實現(xiàn)置換表搜索
　　因為在搜索的過程中，節(jié)點數(shù)量非常大，如果將每一個節(jié)點都與數(shù)組中的元素一一對應(yīng)，內(nèi)存開銷太大，不可能實現(xiàn)。為了解決這一問題，可以利用哈希表技術(shù)。每一個搜索節(jié)點對應(yīng)哈希表中一個節(jié)點，但是反過來，哈希表中的一個節(jié)點并不一定只對應(yīng)一個搜索節(jié)點，這就是哈希沖突，在同一次搜索過程中，哈希沖空的可能性并不高，在實際的應(yīng)用中這是一個可靠的辦法。根據(jù)中國象棋搜索的特點，定義如下哈希數(shù)組。
　　對要搜索的每一節(jié)點，計算出它的一個哈希值（hashIndex，通常是一個32位數(shù)對哈希表大小取模）以確定此局面在哈希表中的位置。計算另一個哈希值checksum，來檢驗表中的數(shù)據(jù)項是否是所要的那一項。64位的哈希值checksum發(fā)生沖突的幾率很小，幾乎可以將其沖突忽略。即使因為哈希沖突導(dǎo)致沒有獲得原來搜索過的節(jié)點，也不會影響博弈系統(tǒng)的運行，因為還可以采用基礎(chǔ)的alpha-beta算法進行搜索。
　　在對某一局面搜索之前，先查看哈希表項hashTable[hashIndex]， 如果hashTable[hashIndex].checksum == Checksum，并且hashTable[hashIndex].depth大于或者等于最大搜索深度減去當前層數(shù)，就返回hashTable[hashIndex].eval作為當前局面的估值。當對一個局面搜索完成后，將Checksum、當前層數(shù)和估值結(jié)果保存到hashTable[hashIndex]當中，以備后面的搜索使用。置換表與alpha-beta搜索協(xié)同工作的實現(xiàn)機制如下面的類C語言偽代碼所示。
　　4 實驗
　　基于以上核心算法，利用JAVA語言設(shè)計了一個實用系統(tǒng)。中國象棋的棋盤用一個10行9列的二維數(shù)組與之對應(yīng)，而各棋子用對應(yīng)的數(shù)字表示。棋局評估主要從剩余棋子基本值、棋子靈活性、棋子受攻擊度、棋子受保護度，棋子位置附加值這幾個方面來衡量。分別計算這幾種類型的值，然后將它們的和作為棋局的優(yōu)劣值，供搜索引擎使用。實驗主要是比較alpha-beta+置換表算法與基本的alpha-beta算法在不同的搜索層次上搜索結(jié)點的個數(shù)，通過實驗可知從第3層開始，alpha-beta+置換表評估的節(jié)點數(shù)目要少于alpha-beta搜索在同樣深度搜索中評估的節(jié)點數(shù)。而且隨著搜索的最大深度的增加，置換表的命中率也不斷提高，表明重復(fù)的節(jié)點所點的比例隨深度增加而增加。這表明alpha-beta+置換表評估的節(jié)點數(shù)同alpha-beta搜索評估的節(jié)點數(shù)相比的比例越來越低。由于置換表的操作對每一節(jié)點都要花費一定的時間，所以在較淺的搜索當中（例如3層），由于命中率較低，雖然alpha-beta+置換表評估的節(jié)點數(shù)比alpha-beta搜索少，但花費的時間仍多于alpha-beta搜索。但隨著搜索深度的增加，alpha-beta+置換表開始顯露出時間上的優(yōu)勢。當搜索的最大深度為5時，alpha-beta+置換表的搜索速度達到alpha-beta的2倍以上。

    參考資料：

• [1] 岳金朋,馮速.  博弈樹搜索算法在中國象棋中的應(yīng)用[J]. 計算機系統(tǒng)應(yīng)用. 2009(09)
• [2] 舒康元,胡福喬.  中國象棋計算機博弈引擎改進[J]. 微計算機信息. 2009(29)
• [3] 鮑鵬,高珩,王偉.  中國象棋的編程設(shè)計[J]. 電腦學(xué)習(xí). 2009(05)
• [4] 鄒競.  基于MTD(f)的中國象棋人機博弈算法的設(shè)計與優(yōu)化[J]. 計算機與數(shù)字工程. 2008(09)
• [5] 魏欽剛,王驕,徐心和,南曉斐.  中國象棋計算機博弈開局庫研究與設(shè)計[J]. 智能系統(tǒng)學(xué)報. 2007(01)

本文編號：9009