五子棋中Alpha-Beta搜索算法的研究與改進

1、五子棋中 Alpha-Beta 搜索 搜索算法的研究與改進 算法的研究與改進程 宇 , 雷小鋒(中國礦業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院,江蘇 徐州 221008摘 要 :對五子棋中 Alpha-Beta 搜索算法進行研究。依據(jù)五子棋的特點,提出一種局部搜索的算法,該算法可直接減少搜索的平均分枝因 子。結(jié)合 Alpha-Beta 搜索算法效率與子節(jié)點著法順序高度相關(guān)的特點,給出靜態(tài)評價啟發(fā)以及迭代深化的方法優(yōu)化著法順序。實驗結(jié)果表 明,該方法能提升 Alpha-Beta 搜索算法的效率。關(guān)鍵 關(guān)鍵詞 詞 :五子棋; Alpha-Beta 搜索算法;局部搜索;靜態(tài)評價啟發(fā);迭代深化;著法順序Resear

2、ch and Improvement on Alpha-BetaSearch Algorithm in GobangCHENG Yu, LEI Xiao-feng(School of Computer Science and Technology, China University of Mining and Technology, Xuzhou 221008, China【 Abstract 】 This paper researches Alpha-Beta search algorithm. According to the characteristics of Gobang, it p

3、roposes a local search method, thereby directly reducing the search node branch number; combined with the fact that Alpha-Beta algorithm efficiency is highly relevant to the child node order, this paper proposes the static evaluation heuristic and iterative deepening methods for optimization of move

4、 ordering. Experimental results show that this method enhances the efficiency of Alpha-Beta search algorithm.計 算 機 工 程 Computer Engineering 第 38卷 第 17期V ol.38 No.17 2012年 9月September 2012·人工智能及識別技術(shù) 人工智能及識別技術(shù)·· 文章編 文章編號 號 :1000 3428(201217 0186 03 文獻標(biāo)識碼 文獻標(biāo)識碼:A中圖分類號 中圖分類號:TP3111 概述人機博弈

5、是人工智能的重要分支, 主要研究如何提高 機器的智能水平的問題。 提高機器的搜索能力將大大提高 機器的智能, 人們在對人機博弈搜索算法研究中產(chǎn)生了大 量的研究成果,其中,極大極小算法是其中最為基礎(chǔ)的算 法, 而改進極大極小算法所產(chǎn)生的 Alpha-Beta 搜索算法則 是其中最重要的算法之一。 Alpha-Beta 搜索算法的效率與 平均分枝因子以及著法排列順序息息相關(guān) 1,因此,根據(jù) 五子棋的特點對算法搜索的平均分枝因子和著法排列順 序進行改進成為提高 Alpha-Beta 搜索算法的效率的關(guān)鍵。 為完善 Alpha-Beta 搜索算法, 本文對該算法進行研究, 提 出改進的 Alpha-B

6、eta 搜索算法, 即局部搜索、 靜態(tài)評價啟 發(fā)、迭代深化來提高 Alpha-Beta 搜索算法的效率。2 極大極小算法在人機博弈中, 搜索的過程是博弈程序就當(dāng)前棋局對 未來棋局的思考過程。 這一思考過程和人類走棋的思考過 程是一樣的,即當(dāng)己方在所有著法中選擇走一步后,思考 對方能有什么著法,如此反復(fù)下去,這一過程就產(chǎn)生 了一顆博弈樹。在這一過程中,博弈程序必須假定對方和 己方一樣的“聰明” ,也就是說己方在選擇走最有利于自己的著法的過程中,對方也會選擇最有利于它自己的著 法,這就是極大極小算法的過程,顧名思義,指在搜索的 過程中存在取極大值一方和取極小值的另一方。 為表述方 便,將取極大值的

7、一方設(shè)為 max ,另一方設(shè)為 min 。 max 作為博弈程序一方,選擇價值極大的子節(jié)點走棋, min 方 作為對方,為了鉗制 max 方,選擇價值極小的子節(jié)點走 棋, 這就產(chǎn)生了一個極大極小過程。 Shannon 在 1950年首 先提出了極大極小算法 2,從此奠定了計算機博弈的理論 基礎(chǔ) 3-7。3 Alpha-Beta 搜索算法3.1 Alpha-Beta 搜索算法原理在極大極小算法的搜索過程中, 存在一定程度的數(shù)據(jù) 冗余 8。一種稱為極大值冗余,如圖 1所示,這是一棵極 大極小樹的某一部分,節(jié)點下數(shù)字為該節(jié)點的值,節(jié)點 B 的值為 20, 節(jié)點 D 的值為 15, 這里, C 為取極

8、小值的 min 節(jié)點,因此節(jié)點 C 的值將小于等于 15;而節(jié)點 A 為取最 大值 max 的節(jié)點,因此 A 只可能取到 B 的值,也就是說 不再需要搜索 C 的其他子節(jié)點 E 和 F 的值就可以得出節(jié) 點 A 的值。 這樣將節(jié)點 D 的后繼兄弟節(jié)點減去稱為 Alpha 剪枝。另一種稱為極小值冗余,如圖 2所示,這也是一棵第 38卷 第 17期 187 程 宇,雷小鋒:五子棋中 Alpha-beta 搜索算法的研究與改進 極大極小樹的某部分,節(jié)點 B 的值為 10,節(jié)點 D 的估值 為 19,這里, C 節(jié)點為取最大值 max 節(jié)點。因此, C 的 值將大于等于 19;節(jié)點 A 為取小值的 m

9、in 節(jié)點,因此 A 的值只能取 B 的值 10,也就是說不再需要求節(jié)點 C 的子 節(jié) E 和 F 的值就可以得出節(jié)點 A 的值。這樣將節(jié)點 D 的 后繼兄弟節(jié)點減去稱為 Beta 剪枝。圖 1 極大值冗余的 Alpha 剪枝圖 2 極小值冗余的 Beta 剪枝通過把 Alpha-Beta 剪枝的原理應(yīng)用于極大極小算法 中就形成了 Alpha-Beta 搜索算法。在搜索過程中 max 節(jié)點的當(dāng)前最大值稱為 值, min 節(jié)點當(dāng)前最小值被稱為 值。算法剛開始時取 值為 ,取 為 + ,在搜索過程中 max 節(jié)點將搜索更大的值賦給 值, min 節(jié)點將搜索 更小的值賦給 值。 對于 max 節(jié)點,

10、 當(dāng)在搜索過程中出現(xiàn) 了 值大于 值時,就進行 Alpha 剪枝并返回 值,如果 沒有 Alpha 剪枝出現(xiàn),則返回 值;對于 min 節(jié)點,當(dāng)在 搜索過程中出現(xiàn)了 值大于 值時,就進行 Beta 剪枝并 返回 值,如果沒有出現(xiàn) Beta 剪枝,則返回 值。 3.2 Alpha-Beta 搜索算法效率由極大極小算法的原理可知, 如果將博弈搜索樹平均 分枝因子記為 b ,搜索深度記為 d ,那么極大極小算法搜 索的總節(jié)點數(shù)為:23111dddd b b b b b b b += (1如果使用 Alpha-Beta 搜索算法, 1975年, Knuth 等證 明在節(jié)點排列最為理想的情況下, 搜索的

11、總節(jié)點數(shù) n 為 1:221d n b = (2其中, d 為偶數(shù)。(1 2(1 21d d n b b +=+ (3其中, d 為偶數(shù)。這個數(shù)字大約是極大極小算法搜索節(jié)點數(shù)的平方根 的 2倍。由此可以看出,減少平均分枝因子以及優(yōu)化著法 排列順序?qū)?Alpha-Beta 搜索算法效率的提高起到非常 大的作用。4 改進的 Alpha-Beta 搜索算法本節(jié)依據(jù)五子棋的特點,分別提出了 3種改進方法。 局部搜索,對棋盤進行局部化搜索,減少平均分枝因子; 靜態(tài)評價啟發(fā)和迭代深化方法,優(yōu)化著法排列順序。下文 將詳細闡述。4.1 局部搜索在五子棋博弈的搜索中, 所有空白位置都是合法的著 法。對于 10

12、×10的棋盤,這意味著棋局剛開始時,博弈搜 索的第 1層的分枝因子為 10×101=99,第 2層為 98,如 果用 d 表示搜索深度,那么 d 層的分枝因子為 100 d 。如 果不考慮減枝的情況, 那么搜索的總節(jié)點數(shù), 由式 (1可以 看出,節(jié)點數(shù)將非常龐大。依據(jù)五子棋的特點,通過仔細 分析可以看出,在這些大量的著法中,其實很多著法都是 沒有必要進行搜索的。因為在五子棋中,博弈的目的是阻 止對方形成五連并盡量使己方形成五連,在實踐中,發(fā)現(xiàn) 最優(yōu)走法應(yīng)該是圍繞在棋盤上已經(jīng)形成的走法周圍, 所以 沒有必要對整個棋盤中的空白位置都進行搜索, 而可以將 棋盤進行剪切,形成一個局

13、部棋盤,對局部棋盤上的空白 位置進行搜索,這樣將大大減少平均分枝因子。如果把棋盤看成是一個以左下角為坐標(biāo)原點, 兩條邊 線為坐標(biāo)軸的坐標(biāo)系,對于每一個要進行搜索的節(jié)點,設(shè) 其為 P , P 中具有最小縱坐標(biāo)的棋子的坐標(biāo)為 min y , P 中 具有最大縱坐標(biāo)的棋子的坐標(biāo)為 max y , P 中具有最小橫坐 標(biāo)的棋子的坐標(biāo)為 min x , P 中具有最大橫坐標(biāo)的棋子的坐標(biāo)為 max x 。可以為 P 產(chǎn)生一個 m ×n 的局部棋盤,其中, 3max min y y m =+, 3max min x x n =+,這個棋盤包含 P中所有的棋子,也就是說產(chǎn)生了一個等同于 P ,但是卻

14、減 少了很多無用分枝著法的棋盤。 對于 P 的著法的產(chǎn)生將在 這個局部棋盤進行,表 1表明該方法的結(jié)果。表 1 采用局部搜索前后平均搜索節(jié)點數(shù)對比平均搜索節(jié)點數(shù) 搜索深度 /層局部搜索前 局部搜索后 減少率 /(%185 51 40 2 963 556 42 3 17 060 5 511 68 4 368 400 35 811 90 57 479 000309 298964.2 靜態(tài)評價啟發(fā)由 Alpha-Beta 搜索算法原理可知, 越早搜索到較優(yōu)著 法,那么剪枝就將越早得發(fā)生, Alpha-Beta 搜索算法的效 率也就越高。 靜態(tài)評價啟發(fā)是本文提出的一種用來優(yōu)化著 法順序的啟發(fā)方法,它使

15、得較優(yōu)的走法能優(yōu)先被搜索,因 此可以簡單而有效地提高 Alpha-Beta 搜索算法的效率。在五子棋博弈中, 當(dāng)前節(jié)點最佳的著法可能不是在多 層搜索的基礎(chǔ)上的最佳的著法, 但是它往往是一個較優(yōu)的 著法。例如,當(dāng)前節(jié)點能產(chǎn)生一個形成活四的著法,那么 這個著法將是一個最優(yōu)的著法, 不管還要進行多少層的搜 索。因此,對于每一個要進行搜索的節(jié)點,設(shè)為 P ,其每 一個著法為 m i ,每一個著法 m i 形成局面 P i ,那么可以對 P i 進行評估,產(chǎn)生其評估值 v i ,如果 P 是極大方,則以 v i188 計 算 機 工 程 2012年 9月 5日為關(guān)鍵字對 m i 進行非遞增排序;如果 P

16、 是極小方,則以 v i 為關(guān)鍵字對 m i 進行非遞減排序。 最終把這個排序的著法 序列 m i 作為 P 的著法搜索順序, 表 2表明了此方法的實 驗結(jié)果。表 2 采用靜態(tài)評價啟發(fā)前后平均搜索節(jié)點數(shù)對比平均搜索節(jié)點數(shù)搜索深度 /層靜態(tài)評價啟發(fā)前靜態(tài)評價啟發(fā)后減少率 /(%151 51 0 2 556 157 71 3 5 511 1 378 74 4 35 811 6 062 83 5309 29847 819844.3 迭代深化在搜索的過程中,針對第 1個要搜索的節(jié)點,為了得 到一個較好的著法作為第 1個著法, 可以采用迭代深化的 方法。當(dāng)對一個節(jié)點進行深度為 d 的搜索時,可以首先對

17、其進行一次 d 1層搜索, 得出的最佳著法作為 d 層搜索的 最先搜索的著法。由于兩層相鄰之間的節(jié)點比較相似,因 此這一著法很有可能便是最佳的著法或者是較優(yōu)的著法。 由此,在搜索過程中,將得到一個較高的剪枝效率 9。在進行 d 層搜索時首先進行 d 1層的搜索看似多進行 了一次搜索,花費了更多的時間,但實際上搜索將變得更 加有效。文獻 1的實驗表明, Alpha-Beta 剪枝搜索 d 層所 需時間大約是 d 1層所需時間的 b 倍,其中, b 為平均分 枝因子。五子棋中平均分枝因子大約為取 b =200,因此, 每多搜一層就會花上原先的 200倍時間。所以,對 d 1層 的搜索大約只有進行

18、d 層搜索的 1/200, 這個代價并不大, 但卻對 d 層的搜索提供了一個較優(yōu)的著法的啟發(fā), 這使剪 枝效率將大大提高,表 3表明了此方法的實驗結(jié)果。表 3 采用迭代深化前后平均搜索節(jié)點數(shù)對比平均搜索節(jié)點數(shù) 搜索深度 /層迭代深化前 迭代深化后 減少率 /(%2 157 118 24 3 1 378 944 31 4 6 062 5 249 13 547 81939 381175 實驗結(jié)果與 實驗結(jié)果與分析 分析選取 10×10的棋盤,進行了 15步著法進行實驗。分 別在表 1中對比了局部搜索前與局部搜索后的實驗結(jié)果; 在表 2中對比了局部搜索與采用靜態(tài)評價啟發(fā)方法的局部 搜索的實

19、驗結(jié)果。 最后將迭代深化和靜態(tài)評價啟發(fā)方法相 結(jié)合, 即對第 1個搜索節(jié)點首先進行迭代深化得到第 1個 著法,然后通過靜態(tài)評價啟發(fā)計算其他著法,表 3中對比 了此結(jié)合方法與僅采用靜態(tài)評價啟發(fā)的方法的實驗結(jié)果。通過實驗可以看出,局部搜索大大減少平均分枝因 子, 從各層平均來看, 減少了需要搜索的節(jié)點數(shù)約 67.2%; 靜態(tài)評價啟發(fā)優(yōu)化著法順序,導(dǎo)致大量剪枝的產(chǎn)生,進一 步減少搜索的節(jié)點數(shù)約 62.4%;最后結(jié)合迭代深化,更進 一步減少了搜索的節(jié)點數(shù)約 17%, Alpha-Beta 搜索算法效 率得到了大大的提高。6 結(jié)束語本文針對五子棋特點分別提出 3種改進方法提高 Alpha-Beta 搜素

20、算法的效率,從實驗結(jié)果可以看出這 3種 方法是非常有效的。但實驗中搜索的層數(shù)只做到了 5層, 這是因為當(dāng)層數(shù)增加時,平均搜索節(jié)點將大大增加,實驗 過程將變得非常緩慢,因此,如何進一步加深搜索的層數(shù) 將是下一步研究的方向。參考文獻1 Knuth D E, Moore R W. An Analysis of Alpha-Beta PruningJ.Artificial Intelligence, 1975, 6(4: 293-326.2 Shannon C E. Programming a Computer for Playing ChessJ.Philosophical Magazine, 1950, 41(314: 256-275. 3 王小春 . PC游戲編程 M. 重慶 : 重慶大學(xué)出版社 , 2002. 4 蔡自興 , 徐光祐 . 人工智能及應(yīng)用 M. 北京 : 清華大學(xué)出版社 ,1996.5 姜 勇 . 五子棋人機對戰(zhàn)系統(tǒng)設(shè)計 D. 成都 : 電子科技大學(xué) ,2010.6 張仰森 . 人工智能原理與應(yīng)用 M. 北京 : 高等教育出版社 ,2002.7 陸汝鈐 . 人工智能上冊 M