基于alphabeta算法的智能五子棋

1、基于Alpha-Beta算法的五子棋游戲班級：，學(xué)號：，姓名： 摘要：博弈是人工智能的主要研究領(lǐng)域之一，而五子棋是經(jīng)典的雙agent博弈游戲。本文對針對五子棋游戲的Alpha-Beta搜索算法進(jìn)行研究，設(shè)計(jì)實(shí)際算法，并使用Java完成程序設(shè)計(jì)實(shí)現(xiàn)人機(jī)博弈。為了提高算法效率，在傳統(tǒng)的Alpha-Beta算法的基礎(chǔ)上，根據(jù)五子棋的特點(diǎn)，通過局部搜索、優(yōu)先值啟發(fā)搜索、限制廣度等方法減少搜索的分支數(shù)，極大地提升了算法的效率。關(guān)鍵詞：人工智能；Alpha-Beta搜索；五子棋本組成員：馬猛，馬攀，宋浩宇本人分工：針對五子棋游戲的Alpha-Beta算法的設(shè)計(jì)實(shí)現(xiàn)與優(yōu)化1 引言人工智能是一門綜合性很強(qiáng)的邊

2、緣科學(xué)，它研究如何使計(jì)算機(jī)去做那些過去只能靠人的智力才能完成的工作。而雙agent博弈是人工智能的重要分支，主要研究如何在博弈問題中提高機(jī)器的智能水平。敵對搜索對這一問題的經(jīng)典解決方法，而極大極小算法是敵對搜索中最為基礎(chǔ)的算法，為了提高極大極小搜索的效率，在極大極小搜索算法的基礎(chǔ)上使用Alpha-Beta剪枝所產(chǎn)生的Alpha-Beta搜索算法則是其中最重要的算法之一。本文針對如何實(shí)現(xiàn)人機(jī)博弈中的五子棋游戲，探討了Alpha-Beta搜索算法的設(shè)計(jì)與實(shí)現(xiàn)，并在此基礎(chǔ)上，實(shí)現(xiàn)了改進(jìn)的Alpha-Beta搜索算法，即利用局部搜索、優(yōu)先值啟發(fā)、限制廣度等方法來提高Alpha-Beta搜索算法的效率。

3、2 算法原理與系統(tǒng)設(shè)計(jì)2.1 極大極小算法在人機(jī)博弈問題中，博弈程序的搜索過程即是人類走棋的思考過程。命名兩個博弈者為Max和Min，博弈程序的任務(wù)是為Max尋找最佳的移動位置。因此，深度為偶數(shù)的節(jié)點(diǎn)，對應(yīng)于Max的下一步移動位置，成為Max節(jié)點(diǎn)；深度為奇數(shù)的節(jié)點(diǎn)對應(yīng)于Min的下一步移動的位置，稱為Min節(jié)點(diǎn)。Max作為博弈程序一方，選擇價(jià)值極大的子節(jié)點(diǎn)走棋，而Min方作為對方，為了鉗制Max方，選擇價(jià)值極小的子節(jié)點(diǎn)走棋，這就產(chǎn)生了一個極大極小過程。在決定下一步之前，對這個過程進(jìn)行一定深度的推理，就會形成博弈樹，Max可以通過極大極小搜索在博弈樹中尋找最佳的走法。Shannon在1950年首先

4、提出了極大極小算法1 ，從此奠定了計(jì)算機(jī)博弈的理論基礎(chǔ)。2.2 Alpha-Beta搜索算法在博弈問題中，每一個格局可供選擇的行動方案都有很多，因此會產(chǎn)生十分龐大的博弈樹2。這時如果只進(jìn)行極大極小搜索，博弈樹會存在著一定的數(shù)據(jù)冗余。如圖1所示，節(jié)點(diǎn)下方的數(shù)字代表該節(jié)點(diǎn)的值，方框節(jié)點(diǎn)為極大值，圓形框節(jié)點(diǎn)為極小值。當(dāng)A節(jié)點(diǎn)搜索下一步位置時，它要取B、C中的最小值，而此時已搜索得B節(jié)點(diǎn)值為5，而在搜索C節(jié)點(diǎn)時得知D節(jié)點(diǎn)值為4，此時可剪去E、F節(jié)點(diǎn)，因?yàn)镃節(jié)點(diǎn)的得值必定小于等于4，說明A節(jié)點(diǎn)的值為max(B, C) = 5。這種當(dāng)先輩層的alpha值大于等于后輩beta值而進(jìn)行的剪枝稱為Alpha剪枝

5、。圖1 Alpha剪枝同理，在圖2中，由于在搜索過程中，已知B節(jié)點(diǎn)的值為5，而C的子節(jié)點(diǎn)D的值為6，則max(C)大于等于6，A的值為min(B, C)等于5，則可剪去E、F節(jié)點(diǎn)。這種已知先輩層beta值小于等于后輩層alpha值的剪枝稱為Beta剪枝。 圖2 Beta剪枝將Alpha剪枝與Beta剪枝加入極大極小搜索中，可以極大地提升極大極小搜索效率，稱新的算法為Alpha-Beta搜索算法。該算法和極小化極大算法所得結(jié)論相同，但剪去了不影響最終決定的分枝 3 。下面為本次游戲中采用的Alpha-Beta算法的偽代碼，其中findMin將當(dāng)前棋局視為極小層，并返回當(dāng)前棋局的值；同理，find

6、Max將當(dāng)前棋局視為極大層，并返回當(dāng)前棋局的值；putOne為初始函數(shù)，它得出己方（AI方）的下一步落子位置，并進(jìn)行落子：function findMin(alpha, beta, step) / 尋找當(dāng)前棋局的最小估值if step = 0:return evaluate()min = betafor place in possiblePlaces:chessplace = enemywight = findMax(alpha, min, step-1)chessplace = emptyif wight < min:min = wightif min <= alpha: / a

7、lpha剪枝return minreturn minfunction findMax(alpha, beta, step) / 尋找當(dāng)前棋局的最大估值if step = 0:return evaluate()max = alphafor place in possiblePlaces:chessplace = mywight = findMin(max, beta, step-1)chessplace = emptyif wight > max:max = wightif max >= beta: / beta剪枝return maxreturn maxfunction putOn

8、e():alpha = - Infinitybeta = Infinitymax = -InfinitymaxPlace = nullfor place in possiblePlaces:chessplace = mywight = findMin(alpha, beta, step)chessplace = emptyif max < wight:max = wightmaxPlace = placechessmaxPlace = my在以上偽代碼中，step記錄搜索的深度，alpha為當(dāng)前得到的最大值，beta為當(dāng)前得到的最小值，my表示己方（AI方）棋子，enemy表示敵方棋子，

9、empty表示空。2.3 利用局部搜索對算法進(jìn)行優(yōu)化在五子棋博弈的搜索中，所有空白位置都是合法的位置。對于大小為15x15的棋盤，傳統(tǒng)算法中計(jì)算機(jī)每走一步都要遍歷整個棋盤，這意味著搜索的節(jié)點(diǎn)數(shù)十分龐大。而根據(jù)五子棋的特點(diǎn)，通過仔細(xì)分析可以看出，在某個時刻，棋盤上很多位置都可以不用考慮，而只考慮已有棋子周圍的局部棋盤。提取出局部棋盤后再進(jìn)行搜索，可以大大提高算法的效率。為了確定邊界，設(shè)置變量x_max, x_min, y_max, y_min分別代表邊界的最大最小坐標(biāo)，在第一步落子時，對它們進(jìn)行初始化，假設(shè)棋盤大小為15x15，第一步落子位置為(x, y)，則初始化過程為： if x-1 >

10、;= 0: x_min = x - 1 if x+1 <= 15: x_max = x + 1 if y-1 >= 0: y_min = y - 1 if y+1 <= 15: y_max = y + 1在進(jìn)行每一步落子到(x, y)位置后，需要通過resetMaxMin函數(shù)更新邊界值：function resetMaxMin(x, y):if x-1 >= 0: x_min = min(x_min < x1)if x+1 <= 15: x_max = max(x_max > x+1)if y-1 >= 0: y_min = min(y_min

11、< y-1)if y+1 <= 15: y_max = max(y_max > y+1)在上述偽代碼中，默認(rèn)棋盤大小為15x15，擴(kuò)展邊界大小為1，在實(shí)際應(yīng)用中，可以根據(jù)實(shí)際情況更改擴(kuò)充邊界值。2.4 通過優(yōu)先值啟發(fā)優(yōu)化算法由Alpha-Beta搜索算法原理可知，搜索的廣度決定每一層所擴(kuò)展的節(jié)點(diǎn)數(shù)，而且越早搜索到較優(yōu)者，那么剪枝的效率越高。對此，可以優(yōu)先搜索一層，對這一層的節(jié)點(diǎn)的值進(jìn)行排序，選取對己方最有利的節(jié)點(diǎn)作為最優(yōu)擴(kuò)展節(jié)點(diǎn)。僅對第一層節(jié)點(diǎn)進(jìn)行搜索，雖然可能不是在多層搜索的基礎(chǔ)上的最佳位置，但是它往往是一個較優(yōu)的位置。通過對第一層擴(kuò)展節(jié)點(diǎn)進(jìn)行最優(yōu)值排序，優(yōu)先選擇最優(yōu)節(jié)點(diǎn)進(jìn)

12、行擴(kuò)展，可以使Alpha-Beta剪枝盡早發(fā)生，提高Alpha-Beta剪枝的效率。2.5 限制搜索廣度在進(jìn)行優(yōu)先值啟發(fā)排序后，會發(fā)現(xiàn)大部分優(yōu)先值低的節(jié)點(diǎn)會在之后的Alpha-Beta剪枝中被剪去，而且即使在多層搜索之后，最優(yōu)節(jié)點(diǎn)也往往在頭幾個進(jìn)行一層搜索得到的最優(yōu)節(jié)點(diǎn)中?；谝陨戏治?，在擴(kuò)展節(jié)點(diǎn)時，可以只選擇頭幾個進(jìn)行一層搜索的優(yōu)先值高的節(jié)點(diǎn)，這樣限制了搜索的廣度，提高了剪枝算法的效率。3 實(shí)驗(yàn)或測試結(jié)果通過實(shí)際測試，可以看出算法可以正確運(yùn)行。如圖3所示，當(dāng)人持黑棋先行，算法對白棋的落子位置進(jìn)行搜索，剪枝節(jié)點(diǎn)與預(yù)期吻合，算法最后給出的落子位置符合算法邏輯。 圖3 算法執(zhí)行部分結(jié)果測試4 結(jié)論

13、本文探討了針對五子棋游戲的Alpah-Beta算法，通過Alpha-Beta搜索實(shí)現(xiàn)了人機(jī)博弈的AI部分。為了進(jìn)一步提高效率，根據(jù)五子棋博弈的特性，在傳統(tǒng)算法的基礎(chǔ)上提出了局部搜索、優(yōu)先值啟發(fā)、限制廣度等優(yōu)化措施，提高了Alpha-Beta搜索算法的效率。雖然采用了以上的優(yōu)化措施，但在實(shí)驗(yàn)中，搜索的層數(shù)被最終確定為3層，當(dāng)層數(shù)繼續(xù)增加時，每一步的搜索平均節(jié)點(diǎn)數(shù)將增加，并且可以明顯感覺到延時。因此，在現(xiàn)在的基礎(chǔ)上，如何進(jìn)行進(jìn)一步的優(yōu)化將是今后的主要任務(wù)。參考文獻(xiàn)1 Shannon C E. Programming a Computer for Playing ChessJ.Philosophical Magazine, 1950, 41(314): 256-275.2 王永慶. 人工智