基于置換表技術的中國象棋搜索算法研究

黎利輝

【摘 要】中國象棋的基礎搜索——Alpha-Beta 算法的剪枝過程對搜索節(jié)點的排序順序依賴很大，當搜索順序的排列為最差情況時，該算法基本上不能實現(xiàn)剪枝。搜索過程其實會出現(xiàn)很多重復的節(jié)點，利用哈希表的思想，把以前搜索過的節(jié)點保存起來，這樣在搜索某一節(jié)點之前，先到哈希表里去查找以前是否搜索過，如果以前搜索過，則直接返回哈希表里保存的局面評估值；如果沒有，則采用正常的Alpha-Beta算法進行搜索。通過實現(xiàn)可知當搜索層次大于5層時，改進后的算法比Alpha-Beta算法在搜索節(jié)點數(shù)量和時間有都有很大的優(yōu)化。

【關鍵詞】中國象棋；置換表；哈希表；博弈樹搜索

0 引言

在中國象棋的人機博弈的研究中，局面搜索算法是核心，中國象棋的博弈過程中，針對某一局面，平均著法達到60步，故減少搜索的節(jié)點，提高搜索的速度和節(jié)省搜索過程中內(nèi)存開銷，就成了中國象棋搜索研究一個終極目標。Alpha-Beta搜索算法是人機博弈的一個基本算法，但是該算法在搜索過程中，存在大量的冗余[1]。本文即在這一基本算法的基礎上，加入置換表技術和Hash table技術，以提高搜索速度。

1 Alpha-Beta搜索算法

如圖1所示，結點下面的數(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，這樣將節(jié)點D的后繼節(jié)點減去稱Alpha剪枝。觀察圖1的右半部的極大極小樹，A節(jié)點要取B節(jié)點和C節(jié)點的最小值，C節(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ù)組中的元素一一對應，內(nèi)存開銷太大，不可能實現(xiàn)。為了解決這一問題，可以利用哈希表技術。每一個搜索節(jié)點對應哈希表中一個節(jié)點，但是反過來，哈希表中的一個節(jié)點并不一定只對應一個搜索節(jié)點，這就是哈希沖突，在同一次搜索過程中，哈希沖空的可能性并不高，在實際的應用中這是一個可靠的辦法。根據(jù)中國象棋搜索的特點，定義如下哈希數(shù)組。

對要搜索的每一節(jié)點，計算出它的一個哈希值（hashIndex，通常是一個32位數(shù)對哈希表大小取模）以確定此局面在哈希表中的位置。計算另一個哈希值checksum，來檢驗表中的數(shù)據(jù)項是否是所要的那一項。64位的哈希值checksum發(fā)生沖突的幾率很小，幾乎可以將其沖突忽略。即使因為哈希沖突導致沒有獲得原來搜索過的節(jié)點，也不會影響博弈系統(tǒng)的運行，因為還可以采用基礎的alpha-beta算法進行搜索。

在對某一局面搜索之前，先查看哈希表項hashTable[hashIndex]， 如果hashTable[hashIndex].checksum == Checksum，并且hashTable[hashIndex].depth大于或者等于最大搜索深度減去當前層數(shù)，就返回hashTable[hashIndex].eval作為當前局面的估值。當對一個局面搜索完成后，將Checksum、當前層數(shù)和估值結果保存到hashTable[hashIndex]當中，以備后面的搜索使用。置換表與alpha-beta搜索協(xié)同工作的實現(xiàn)機制如下面的類C語言偽代碼所示。

4 實驗

基于以上核心算法，利用JAVA語言設計了一個實用系統(tǒng)。中國象棋的棋盤用一個10行9列的二維數(shù)組與之對應，而各棋子用對應的數(shù)字表示。棋局評估主要從剩余棋子基本值、棋子靈活性、棋子受攻擊度、棋子受保護度，棋子位置附加值這幾個方面來衡量。分別計算這幾種類型的值，然后將它們的和作為棋局的優(yōu)劣值，供搜索引擎使用。實驗主要是比較alpha-beta+置換表算法與基本的alpha-beta算法在不同的搜索層次上搜索結點的個數(shù)，通過實驗可知從第3層開始，alpha-beta+置換表評估的節(jié)點數(shù)目要少于alpha-beta搜索在同樣深度搜索中評估的節(jié)點數(shù)。而且隨著搜索的最大深度的增加，置換表的命中率也不斷提高，表明重復的節(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]王小春.PC游戲編程[M].重慶：重慶大學出版社，2002.

[2]Knuth D E， Moore R W. An analysis of Alpha-Betapruning[J].Artificial Intelligence， 1975，6：293.

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

[責任編輯：周天鳳]

【摘 要】中國象棋的基礎搜索——Alpha-Beta 算法的剪枝過程對搜索節(jié)點的排序順序依賴很大，當搜索順序的排列為最差情況時，該算法基本上不能實現(xiàn)剪枝。搜索過程其實會出現(xiàn)很多重復的節(jié)點，利用哈希表的思想，把以前搜索過的節(jié)點保存起來，這樣在搜索某一節(jié)點之前，先到哈希表里去查找以前是否搜索過，如果以前搜索過，則直接返回哈希表里保存的局面評估值；如果沒有，則采用正常的Alpha-Beta算法進行搜索。通過實現(xiàn)可知當搜索層次大于5層時，改進后的算法比Alpha-Beta算法在搜索節(jié)點數(shù)量和時間有都有很大的優(yōu)化。

【關鍵詞】中國象棋；置換表；哈希表；博弈樹搜索

0 引言

在中國象棋的人機博弈的研究中，局面搜索算法是核心，中國象棋的博弈過程中，針對某一局面，平均著法達到60步，故減少搜索的節(jié)點，提高搜索的速度和節(jié)省搜索過程中內(nèi)存開銷，就成了中國象棋搜索研究一個終極目標。Alpha-Beta搜索算法是人機博弈的一個基本算法，但是該算法在搜索過程中，存在大量的冗余[1]。本文即在這一基本算法的基礎上，加入置換表技術和Hash table技術，以提高搜索速度。

1 Alpha-Beta搜索算法

如圖1所示，結點下面的數(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，這樣將節(jié)點D的后繼節(jié)點減去稱Alpha剪枝。觀察圖1的右半部的極大極小樹，A節(jié)點要取B節(jié)點和C節(jié)點的最小值，C節(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ù)組中的元素一一對應，內(nèi)存開銷太大，不可能實現(xiàn)。為了解決這一問題，可以利用哈希表技術。每一個搜索節(jié)點對應哈希表中一個節(jié)點，但是反過來，哈希表中的一個節(jié)點并不一定只對應一個搜索節(jié)點，這就是哈希沖突，在同一次搜索過程中，哈希沖空的可能性并不高，在實際的應用中這是一個可靠的辦法。根據(jù)中國象棋搜索的特點，定義如下哈希數(shù)組。

對要搜索的每一節(jié)點，計算出它的一個哈希值（hashIndex，通常是一個32位數(shù)對哈希表大小取模）以確定此局面在哈希表中的位置。計算另一個哈希值checksum，來檢驗表中的數(shù)據(jù)項是否是所要的那一項。64位的哈希值checksum發(fā)生沖突的幾率很小，幾乎可以將其沖突忽略。即使因為哈希沖突導致沒有獲得原來搜索過的節(jié)點，也不會影響博弈系統(tǒng)的運行，因為還可以采用基礎的alpha-beta算法進行搜索。

在對某一局面搜索之前，先查看哈希表項hashTable[hashIndex]， 如果hashTable[hashIndex].checksum == Checksum，并且hashTable[hashIndex].depth大于或者等于最大搜索深度減去當前層數(shù)，就返回hashTable[hashIndex].eval作為當前局面的估值。當對一個局面搜索完成后，將Checksum、當前層數(shù)和估值結果保存到hashTable[hashIndex]當中，以備后面的搜索使用。置換表與alpha-beta搜索協(xié)同工作的實現(xiàn)機制如下面的類C語言偽代碼所示。

4 實驗

基于以上核心算法，利用JAVA語言設計了一個實用系統(tǒng)。中國象棋的棋盤用一個10行9列的二維數(shù)組與之對應，而各棋子用對應的數(shù)字表示。棋局評估主要從剩余棋子基本值、棋子靈活性、棋子受攻擊度、棋子受保護度，棋子位置附加值這幾個方面來衡量。分別計算這幾種類型的值，然后將它們的和作為棋局的優(yōu)劣值，供搜索引擎使用。實驗主要是比較alpha-beta+置換表算法與基本的alpha-beta算法在不同的搜索層次上搜索結點的個數(shù)，通過實驗可知從第3層開始，alpha-beta+置換表評估的節(jié)點數(shù)目要少于alpha-beta搜索在同樣深度搜索中評估的節(jié)點數(shù)。而且隨著搜索的最大深度的增加，置換表的命中率也不斷提高，表明重復的節(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]王小春.PC游戲編程[M].重慶：重慶大學出版社，2002.

[2]Knuth D E， Moore R W. An analysis of Alpha-Betapruning[J].Artificial Intelligence， 1975，6：293.

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

[責任編輯：周天鳳]

【摘 要】中國象棋的基礎搜索——Alpha-Beta 算法的剪枝過程對搜索節(jié)點的排序順序依賴很大，當搜索順序的排列為最差情況時，該算法基本上不能實現(xiàn)剪枝。搜索過程其實會出現(xiàn)很多重復的節(jié)點，利用哈希表的思想，把以前搜索過的節(jié)點保存起來，這樣在搜索某一節(jié)點之前，先到哈希表里去查找以前是否搜索過，如果以前搜索過，則直接返回哈希表里保存的局面評估值；如果沒有，則采用正常的Alpha-Beta算法進行搜索。通過實現(xiàn)可知當搜索層次大于5層時，改進后的算法比Alpha-Beta算法在搜索節(jié)點數(shù)量和時間有都有很大的優(yōu)化。

【關鍵詞】中國象棋；置換表；哈希表；博弈樹搜索

0 引言

在中國象棋的人機博弈的研究中，局面搜索算法是核心，中國象棋的博弈過程中，針對某一局面，平均著法達到60步，故減少搜索的節(jié)點，提高搜索的速度和節(jié)省搜索過程中內(nèi)存開銷，就成了中國象棋搜索研究一個終極目標。Alpha-Beta搜索算法是人機博弈的一個基本算法，但是該算法在搜索過程中，存在大量的冗余[1]。本文即在這一基本算法的基礎上，加入置換表技術和Hash table技術，以提高搜索速度。

1 Alpha-Beta搜索算法

如圖1所示，結點下面的數(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，這樣將節(jié)點D的后繼節(jié)點減去稱Alpha剪枝。觀察圖1的右半部的極大極小樹，A節(jié)點要取B節(jié)點和C節(jié)點的最小值，C節(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ù)組中的元素一一對應，內(nèi)存開銷太大，不可能實現(xiàn)。為了解決這一問題，可以利用哈希表技術。每一個搜索節(jié)點對應哈希表中一個節(jié)點，但是反過來，哈希表中的一個節(jié)點并不一定只對應一個搜索節(jié)點，這就是哈希沖突，在同一次搜索過程中，哈希沖空的可能性并不高，在實際的應用中這是一個可靠的辦法。根據(jù)中國象棋搜索的特點，定義如下哈希數(shù)組。

對要搜索的每一節(jié)點，計算出它的一個哈希值（hashIndex，通常是一個32位數(shù)對哈希表大小取模）以確定此局面在哈希表中的位置。計算另一個哈希值checksum，來檢驗表中的數(shù)據(jù)項是否是所要的那一項。64位的哈希值checksum發(fā)生沖突的幾率很小，幾乎可以將其沖突忽略。即使因為哈希沖突導致沒有獲得原來搜索過的節(jié)點，也不會影響博弈系統(tǒng)的運行，因為還可以采用基礎的alpha-beta算法進行搜索。

在對某一局面搜索之前，先查看哈希表項hashTable[hashIndex]， 如果hashTable[hashIndex].checksum == Checksum，并且hashTable[hashIndex].depth大于或者等于最大搜索深度減去當前層數(shù)，就返回hashTable[hashIndex].eval作為當前局面的估值。當對一個局面搜索完成后，將Checksum、當前層數(shù)和估值結果保存到hashTable[hashIndex]當中，以備后面的搜索使用。置換表與alpha-beta搜索協(xié)同工作的實現(xiàn)機制如下面的類C語言偽代碼所示。

4 實驗

基于以上核心算法，利用JAVA語言設計了一個實用系統(tǒng)。中國象棋的棋盤用一個10行9列的二維數(shù)組與之對應，而各棋子用對應的數(shù)字表示。棋局評估主要從剩余棋子基本值、棋子靈活性、棋子受攻擊度、棋子受保護度，棋子位置附加值這幾個方面來衡量。分別計算這幾種類型的值，然后將它們的和作為棋局的優(yōu)劣值，供搜索引擎使用。實驗主要是比較alpha-beta+置換表算法與基本的alpha-beta算法在不同的搜索層次上搜索結點的個數(shù)，通過實驗可知從第3層開始，alpha-beta+置換表評估的節(jié)點數(shù)目要少于alpha-beta搜索在同樣深度搜索中評估的節(jié)點數(shù)。而且隨著搜索的最大深度的增加，置換表的命中率也不斷提高，表明重復的節(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]王小春.PC游戲編程[M].重慶：重慶大學出版社，2002.

[2]Knuth D E， Moore R W. An analysis of Alpha-Betapruning[J].Artificial Intelligence， 1975，6：293.

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

[責任編輯：周天鳳]