基于alphabeta算法的智能五子棋

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

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

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

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

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

6、Max將當前棋局視為極大層，并返回當前棋局的值；putOne為初始函數(shù)，它得出己方（AI方）的下一步落子位置，并進行落子：function findMin(alpha, beta, step) / 尋找當前棋局的最小估值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) / 尋找當前棋局的最大估值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為當前得到的最大值，beta為當前得到的最小值，my表示己方（AI方）棋子，enemy表示敵方棋子，

9、empty表示空。2.3 利用局部搜索對算法進行優(yōu)化在五子棋博弈的搜索中，所有空白位置都是合法的位置。對于大小為15x15的棋盤，傳統(tǒng)算法中計算機每走一步都要遍歷整個棋盤，這意味著搜索的節(jié)點數(shù)十分龐大。而根據(jù)五子棋的特點，通過仔細分析可以看出，在某個時刻，棋盤上很多位置都可以不用考慮，而只考慮已有棋子周圍的局部棋盤。提取出局部棋盤后再進行搜索，可以大大提高算法的效率。為了確定邊界，設置變量x_max, x_min, y_max, y_min分別代表邊界的最大最小坐標，在第一步落子時，對它們進行初始化，假設棋盤大小為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在進行每一步落子到(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)在上述偽代碼中，默認棋盤大小為15x15，擴展邊界大小為1，在實際應用中，可以根據(jù)實際情況更改擴充邊界值。2.4 通過優(yōu)先值啟發(fā)優(yōu)化算法由Alpha-Beta搜索算法原理可知，搜索的廣度決定每一層所擴展的節(jié)點數(shù)，而且越早搜索到較優(yōu)者，那么剪枝的效率越高。對此，可以優(yōu)先搜索一層，對這一層的節(jié)點的值進行排序，選取對己方最有利的節(jié)點作為最優(yōu)擴展節(jié)點。僅對第一層節(jié)點進行搜索，雖然可能不是在多層搜索的基礎上的最佳位置，但是它往往是一個較優(yōu)的位置。通過對第一層擴展節(jié)點進行最優(yōu)值排序，優(yōu)先選擇最優(yōu)節(jié)點進

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

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