alphabeta剪枝算法在黑白棋應(yīng)用中的優(yōu)化

1、alpha-beta剪枝算法在黑白棋應(yīng)用中的優(yōu)化摘要:alpha-beta剪枝算法是一種傳統(tǒng)的搜索算法, 它在博弈算法中有著非常廣泛的運(yùn)用,它大大減少了相同搜索深度下的計(jì)算量,但其仍然不能滿足有限時(shí)間內(nèi)進(jìn)行搜索的需求。為此,有很多針對(duì)該算法的優(yōu)化方法,但這些優(yōu)化方法大都是以消耗更多空間為代價(jià)的。本文以黑白棋為例,從全局考慮,提出幾種優(yōu)化策略,以較少的計(jì)算量,獲得較高智能性。經(jīng)過實(shí)驗(yàn)測試,在PC機(jī)中對(duì)相同的搜索層次,發(fā)現(xiàn)優(yōu)化方法的算法可以較大幅度地提高效率. 關(guān)鍵詞: alpha-beta剪枝算法,人工智能,黑白棋,算法優(yōu)化Abstract: alpha-beta algorithm is a

2、kind of typical method for optimizing adversarial search, which is used widely in game playing algorithm for it reduces the computation amount obviously in the same search depth, but it still does not meet the requirement of searching in a limited time. So, there are many enhancements on its optimiz

3、ation, but most of those enhancements consume more space. This paper takes black and white chess for example, presents some strategies of enhancement from a global angle, and those methods could use less computation amount and get more intelligence at the same time. The experiment in PC shows that t

4、he optimized algorithm could improve efficiency at a high extent compared to the non-optimized algorithm at the same condition.Keywords: alpha-beta pruning algorithm; artificial intelligence; searching technique; algorithm optimize引言目前,已經(jīng)有很多對(duì)alpha-beta算法的優(yōu)化,提高了搜索的性能,其中有一些已經(jīng)被廣泛證實(shí)是有效的算法,它們主要包括以下幾種:置換表

5、(transposition tables)、駁斥表(refutation tables)、窄窗搜索(aspiration search)和最小窗口搜索(minimal window)、啟發(fā)式搜索(heuristic),它們的主要思想在這里就不再贅述。本文提出了新的優(yōu)化算法.1 博弈程序各部分性能分析本文討論的博弈程序主要是指確定的、二人、零和、完備信息的博弈搜索。也就是說,沒有隨機(jī)因素的博弈在兩個(gè)人之間進(jìn)行,在任何一個(gè)時(shí)刻,一方失去的利益即為另一方得到的利益,不會(huì)出現(xiàn)“雙贏”的局面,而且在任何時(shí)刻,博弈的雙方都明確的知道每一個(gè)棋子是否存在和存在于哪里。博弈程序就是產(chǎn)生一個(gè)對(duì)自己最有利的走步,

6、主要產(chǎn)生過程就是,博弈程序根據(jù)當(dāng)前棋盤上的局面,獲得所有自己能夠行進(jìn)的所有走步,然后對(duì)每一種走步進(jìn)行試探。所謂試探就是如果博弈程序采用該走步,那么對(duì)手有可能會(huì)產(chǎn)生哪個(gè)走步,此時(shí)博弈程序會(huì)獲得對(duì)方所有可能會(huì)出現(xiàn)的走步,再對(duì)對(duì)方的每一種可能的走步進(jìn)行試探,如此反復(fù),當(dāng)達(dá)到指定的層次時(shí),停止試探,并對(duì)局面進(jìn)行評(píng)估,博弈程序選擇對(duì)自己最有利或者選擇對(duì)自己損害最小的那個(gè)走步,于是產(chǎn)生一個(gè)試探的路徑,這個(gè)路徑的第一步就是當(dāng)前局面下最有利的一步。從前面的博弈程序搜索過程可以看出,程序可以分成4個(gè)模塊:(1)當(dāng)前局面下,所有可走步的產(chǎn)生(Generate);(2)對(duì)當(dāng)前局面進(jìn)行評(píng)估(Evaluate);(3)

7、產(chǎn)生新的局面(Forward);(4)恢復(fù)前一個(gè)局面(Backward);博弈程序消耗的時(shí)間與搜索的層數(shù)緊密相關(guān),更準(zhǔn)確地說,時(shí)間是與搜索的節(jié)點(diǎn)(局面)數(shù)緊密相關(guān)。對(duì)于一般的最大最小搜索，即使每一步只有很少的走法，搜索位置的數(shù)目也會(huì)隨著搜索深度的增加呈指數(shù)級(jí)增長。如下圖所示,一種簡單的游戲樹,每層更多的節(jié)點(diǎn)(局面)意味著將要在更多的局面下調(diào)用可走步產(chǎn)生模塊;將要對(duì)更多的局面進(jìn)行局面評(píng)估;將要調(diào)用更多的局面產(chǎn)生模塊和恢復(fù)局面模塊。在大多數(shù)的棋形中，每步平均有十種下法，假設(shè)電腦搜索九步(程序術(shù)語稱為搜索深度為九)，就要搜索十億個(gè)位置(十的九次方)，這樣極大地限制了電腦的棋力,我們總不能忍受電腦棋手

8、一年才下一步棋。因此降低博弈程序的時(shí)間就是盡可能地縮減搜索的節(jié)點(diǎn)數(shù),而不能單一地減少某個(gè)模塊消耗的時(shí)間,各模塊的時(shí)間消耗都是依賴節(jié)點(diǎn)數(shù)的,即單一模塊的性能提高與節(jié)點(diǎn)數(shù)的減少相比是微不足道的。那么提高博弈程序性能的關(guān)鍵就是減少搜索的節(jié)點(diǎn)數(shù)。減少搜索結(jié)點(diǎn)的最簡單的方法是減小搜索深度，但這大大影響了電腦棋手的棋力.alpha-beta剪枝大大減少了檢測的數(shù)目，提高電腦搜索的速度.很多棋類程序都采用了這種算法。2.新的優(yōu)化算法alpha-beta剪枝大大減少了相同搜索深度下的計(jì)算量,但其仍然不能滿足有限時(shí)間內(nèi)進(jìn)行搜索的需求。因此就有必要對(duì)其再進(jìn)行優(yōu)化.我提出三種可能的優(yōu)化方案.一.對(duì)當(dāng)前層的所有局面進(jìn)

9、行評(píng)估,而不是等到遞歸到最深層時(shí)才進(jìn)行局面評(píng)估,然后刪去對(duì)自己最不利的N個(gè)走步。這就要求對(duì)可能的走步進(jìn)行排序,這種思路基于如下的經(jīng)驗(yàn)判斷:智者不會(huì)選擇當(dāng)前局面較差的走步,因?yàn)槿绻?dāng)前局面選擇較差的走步,那么在更深一層能夠進(jìn)行彌補(bǔ)的概率幾乎為零。如果N取1,那么可以想象沒有哪個(gè)智者會(huì)選擇當(dāng)前局面下最差的一步,這是合理的,也由此可以適當(dāng)擴(kuò)大N的取值,減少搜索的節(jié)點(diǎn)數(shù)。搜索層數(shù)與搜索節(jié)點(diǎn)數(shù)上面的方法基于經(jīng)驗(yàn)的成分大一些,理論性不十分可靠.二.依靠估值函數(shù)對(duì)局面進(jìn)行評(píng)估,確實(shí)存在不精確的問題,而且博弈游戲的規(guī)則千差萬別很難找到一種很通用的估值方法,另外對(duì)局面的評(píng)估在一定程度上受博弈程序設(shè)計(jì)者主觀的影響

10、。盡管如此,還是可以在局面評(píng)估之前,也就是在產(chǎn)生當(dāng)前局面所有可走步的時(shí)候,理性選擇或分好的走步和差的走步,這與上一種方法的估值不同,它是在可走步產(chǎn)生模塊加入一些智能的分析,從而獲得較少的節(jié)點(diǎn),達(dá)到較少搜索節(jié)點(diǎn)的目的。三.采用知識(shí)數(shù)據(jù)庫減少搜索節(jié)點(diǎn)數(shù),這要求設(shè)計(jì)的程序具有存儲(chǔ)棋局信息和學(xué)習(xí)的能力.計(jì)算機(jī)在與人對(duì)弈時(shí)將有用的棋局信息進(jìn)行存儲(chǔ),并挖掘出好的對(duì)弈策略,并在以后的對(duì)弈過程中運(yùn)用這些策略,這能有效地減少搜索節(jié)點(diǎn)數(shù),隨著知識(shí)數(shù)據(jù)庫的豐富計(jì)算機(jī)的棋力會(huì)得到提高.以上三種方案不是孤立的,對(duì)于方案三能夠很好地為方案一,二提供服務(wù),如面對(duì)一種棋局時(shí),計(jì)算機(jī)運(yùn)用已有知識(shí)數(shù)據(jù)庫能夠?qū)Ξ?dāng)前的局面進(jìn)行較為智

11、能的評(píng)估,而不是機(jī)械地采用固定的評(píng)估方式,快速刪除對(duì)自己不利的走步從而達(dá)到減少搜索節(jié)點(diǎn)數(shù)的目的.3 實(shí)驗(yàn)設(shè)計(jì)以黑白棋為博弈程序的實(shí)例,測試和比較兩種優(yōu)化方法。選擇黑白棋作為實(shí)例,主要基于以下幾個(gè)原因:(1)中國黑白棋的規(guī)則簡單,使得估值函數(shù)受主觀的影響較小,便于更客觀地比較各種優(yōu)化算法的性能,排除了一些主觀因素。(2黑白棋的棋子走法簡單,便于測試和比較對(duì)可走步產(chǎn)生模塊的優(yōu)化方法。(3)黑白棋的獲勝規(guī)則簡單,便于比較在保持相同智能性前提下,各種優(yōu)化算法的性能 本實(shí)驗(yàn)所運(yùn)行的環(huán)境:硬件環(huán)境: CPU Intel Core2 Duo T7500 2.2G, RAM 2G。軟件環(huán)境: Windows

12、XP SP2,Visual Studio 2008。兩種優(yōu)化算法中的第一種算法直接刪除最差的N個(gè)走步,需要對(duì)當(dāng)前局面進(jìn)行排序;第二種算法采用了與第一種算法不同的可走步生成函數(shù),主要不同點(diǎn)是前者優(yōu)化了可走步產(chǎn)生模塊.把第一種算法命名為排序化算法,把第二種算法命名為智能產(chǎn)生算法,智能條件為:邊角判斷,線判斷,在實(shí)驗(yàn)中將兩種優(yōu)化算法都應(yīng)用于優(yōu)化程序中,為了保證測試有更好地對(duì)比性,在實(shí)驗(yàn)過程中盡可能以相同的方式同計(jì)算機(jī)進(jìn)行對(duì)弈.4實(shí)驗(yàn)結(jié)果 未優(yōu)化程序和優(yōu)化程序都將執(zhí)行的結(jié)果信息寫進(jìn)文本文中,數(shù)據(jù)如下分析上述數(shù)據(jù)可以得出:對(duì)于優(yōu)化過的程序,每步棋的搜索次數(shù)有4%-7%的減少,搜索時(shí)間也有4%-8%的減少

13、,但對(duì)于序號(hào)為2的那條數(shù)據(jù)有點(diǎn)特殊(優(yōu)化程序的搜索時(shí)間反而更長),這是由于現(xiàn)在的操作系統(tǒng)為多任務(wù)式的,程序執(zhí)行是由操作系統(tǒng)調(diào)度的,有可能在優(yōu)化程序執(zhí)行時(shí)系統(tǒng)處于繁忙時(shí)刻,導(dǎo)致搜索時(shí)間更長,但搜索次數(shù)還是更少,這符合事實(shí).5總結(jié)兩種新的博弈程序算法是對(duì)標(biāo)準(zhǔn)alpha-beta算法的優(yōu)化,從實(shí)驗(yàn)數(shù)據(jù)看優(yōu)化算法獲得良好的效果,這主要是由于在每層都減少了搜索的節(jié)點(diǎn)數(shù),程序?qū)崿F(xiàn)了兩種解決方案,對(duì)于第三種還在研究中,這個(gè)具有一定的難度,但相信方案三如果能夠?qū)崿F(xiàn)將會(huì)更大程度地提高程序的性能和智能度. 參考文獻(xiàn)1SCHAEFFER J. The History Heuristic and Alpha-Beta Search Enhancements in Practice J . IEEE Transactions on pattern analysis and machine intelligence,11(11).2GILLOGLY J.Performance analysis of the technology chess program D . Pittsburgh: Carnegie-Mellon Univ.,1978.3PLAAT