杜思翰, 李 銘

?

一種改進的威脅空間搜索算法

杜思翰1, 李 銘2

(1.湖南大學 軟件學院, 湖南 長沙，410082; 2. 湖南文理學院 土木工程學院, 湖南 常德, 415000 )

研究了五子棋游戲開發(fā)中極大極小搜索框架計算量太大, 無用計算太多等問題. 在傳統(tǒng)經典極大極小搜索和alpha-beta剪枝基礎上采用了判重, 加入啟發(fā)式的優(yōu)化, 每次選擇最有“前途”的若干個決策搜索以減少搜索量, 再加入基于五子棋專業(yè)棋手下棋策略, 改進威脅空間搜索算法. 使得計算機的搜索過程更像人的思考過程, 算法復雜度大幅降低. 經過測試最終編寫的程序具備高響應度和智能性.

極大極小搜索；alpha-beta剪枝；判重；啟發(fā)式；威脅空間搜索

五子棋的算法發(fā)展了多年, 先后有基于深度優(yōu)先敵對搜索的極大極小搜索[1-2], 優(yōu)點是編程復雜度低, 但是計算量太大無法接受. 之后伴隨著alpha-beta剪枝[1-2]的出現(xiàn)搜索量有了顯著的減小, 對于connect-four和tic-toe-tac等游戲已經能很快的完美解決. 但是由于五子棋搜索的branch-factor(分枝因子)太大(平均約為200). 所以還是不能高效地解決五子棋. 之后出現(xiàn)的SSS*[3]基于廣度優(yōu)先搜索的框架將搜索量進一步減小, 但由于空間復雜度太高一直沒有得以應用. 之后伴隨著算法的進一步發(fā)展, proof-number search[4]和遺傳算法[4]等從根本上改進算法復雜度的優(yōu)秀算法出現(xiàn)了. 但這些算法的共同特點是編程復雜度太高和不成熟, 使得它們也沒有廣泛地應用起來. 五子棋真正的優(yōu)秀算法, 是要在編程復雜度、時間復雜度、空間復雜度上得到一個極好的平衡同時能夠保證搜索質量. 筆者在極大極小搜索和alpha-beta剪枝加入了判重[5]、啟發(fā)式加權排序[6]、威脅空間搜索.

判重能夠避免重復搜索, 而啟發(fā)式加權排序能夠同時提高alpha-beta剪枝的效果和進一步減少無用搜索. 為了更好地提高效率和智能, 引入了威脅空間搜索. 在每次搜索前調用一個復雜度較小的：“二次搜索”來減少無用計算.

1 判重

如圖1所示的搜索樹, 數(shù)字代表狀態(tài)編號, 由于該極大極小搜索采用深度優(yōu)先實現(xiàn), 所以會做很多重復的搜索. 如圖1, 設搜索的結點順序為1→2→4→5→3, 而假設3之后的局面為4, 5, 那么這時可以發(fā)現(xiàn)4和5在之前已經搜索過的, 不需要再次搜索. 所以產生了重復計算. 故可以保存每次搜索之后的結果, 這樣下次訪問該節(jié)點時若已經搜索過直接取結果. 事實上經過如此改造, 搜索的圖形其實已經變成了一個有向無環(huán)圖(dag, directed acycl- elic graph), 滿足無后效性質, 搜索的本質變成了動態(tài)規(guī)劃. 一顆搜索樹經過判重改造后如圖2所示.

圖1 一顆搜索樹

圖2 改造后的dag

這樣搜索量將會大減, 判重實現(xiàn)可以采用平衡樹((logn))或者rk等hash算法(期望復雜度(1)), 或者采用字典樹, 每個狀態(tài)最多只有3個子結點, 也可以針對實現(xiàn)的語言調用相關的模板庫(如C++就可以用stl).

2 啟發(fā)式的應用

首先從游戲本身著手優(yōu)化, 加入經典的五子棋棋譜. 類似于圍棋, 五子棋也有很多經典棋譜, 若將若干棋譜建造一個“數(shù)據(jù)庫”, 則當前殘局如果在數(shù)據(jù)庫中, 馬上選擇相應的對策.

加入人下棋時候的基本策略：

a. 如果某個位置能讓自己獲勝那么馬上選擇該位置；

b. 如果某個位置對手能夠一步獲勝那么必須阻止；

c. 如果某個位置對手有諸如.BBBB.這樣的連線, 那么本局是必敗局. 所以如果對手可能造成這樣的局面, 必須要阻止.

還有其他策略諸如下棋的時候一般會盡量選擇靠近棋盤中央的空區(qū)域, 盡量讓自己“一舉多得”. 連線加權概念：

a. “WBBBB.”, “B.BBB.”算做第1類,記8分；

b. “WBBB.”, “B.BB.”算做第2類, 記3分；

c. “BB.”, “B.B”算做第3類, 記1分.

放置棋子時, 希望其所在的4個方向(水平, 豎直, 主對角線, 副對角線)得分之和盡可能多, 且盡量靠近中間棋盤. 所以將決策排序, 第1關鍵字分數(shù)從大到小, 第2關鍵字與棋盤中央的邁哈頓距離從小到大. 可以更好的發(fā)揮alpha-beta剪枝的作用. 同時可以只搜索排序后靠前的幾個決策, 根據(jù)是基于這樣一個假設：在當前階段看似沒有“前途”的決策很難產生比看似更有“前途”的決策更好的最終結果.

3 威脅空間搜索

威脅空間搜索是模擬人對于“威脅”這個概念的對策以及從五子棋本身的特點入手進行優(yōu)化, 將棋手下棋中的套路公式化提高搜索效率.

3.1 相關定義和知識

在五子棋中, 威脅是一個重要的概念；主要種類的名字：four(圖3a)是5個方塊, 第5個方塊位置為空；straight four(圖3b)是直線上6個方塊, 進攻方占據(jù)了中間4個方塊位置, 外部2個方塊位置為空；three(圖3c或圖3d)是直線上7個位置, 中間3個位置被占據(jù), 其余4個位置為空, 或者直線上6個位置, 中央4個相連位置中3個位置被進攻方占據(jù), 其余3個位置為空；broken three(圖3e)是直線6個位置, 進攻方占據(jù)中央4個位置不相連的3個位置, 其他3個位置為空. 如果某方創(chuàng)造了一個four, 他無疑會在下一次行動中產生威脅. 因此必須被立即防御. 如果創(chuàng)造一個straight four, 防守方就太遲了, 因為進攻方在下次行動中有兩個位置可以下子. 如果創(chuàng)造了一個three, 進攻方在下一回合將威脅產生一個straight four. 因此即使該威脅的深度為2, 它也必須立即被防御. 如果兩邊都能被擴展(圖3c), 那樣便有兩種防御策略：都是與進攻方石子相鄰. 如果只有一個擴展則3種防御策略可行(圖3d). 并且對于broken three而言, 存在3種防御策略(圖3e).

為了贏得游戲必須創(chuàng)建一個double treat(雙重威脅). 威脅序列由威脅構成的一系列移動, 在雙重威脅創(chuàng)造出來之前必須被創(chuàng)建. 一個導致雙重威脅的威脅序列叫做勝利威脅序列. 序列中的每個威脅迫使防御方防御該威脅, 因此防御方的可能性是被限制的.

在圖4中展示黑子可以通過一系列威脅序列獲勝的位置, 該威脅序列僅僅由four組成. 因為一個four必須被立即防御, 因此白子移動是被強迫的.

在圖5中展示了一個黑子可以通過一個完全由three組成的威脅序列獲勝的例子. 在游戲中他可以創(chuàng)造2個four, 然而他還是不能避免地要輸?shù)粲螒? 我們標記出黑子方的威脅序列是獨立白子方的防守策略的.

圖3 威脅

圖4 一個由four組成的威脅序列

圖5 一個由three組成的威脅序列

一個專家棋手能夠很快發(fā)現(xiàn)威脅序列可以被分為如下步驟:

a. 棋盤某個部分的形狀看上去對進攻選手有利. 看是否有足夠的石子能夠合作可以使得能夠搜索出一個威脅序列, 這依靠“感覺”, 是通過長期觀察棋型訓練出來的；

b. 威脅會被考慮, 尤其是與棋盤上面已經有的, 其他棋子相關的威脅. 對方的防御可以完全被忽略；

c. 一旦發(fā)現(xiàn)進攻方可以聯(lián)合他的石子組成一個雙重威脅, 將馬上調查防守方如何防御這個可能獲勝的威脅序列. 當對手有多于一種可能的防守策略時, 將檢查是否該威脅序列在所有情況都能奏效, 并且調查對手能否創(chuàng)造一個或者多個four來中和進攻方；

d. 如果只有某些異樣不能通過同樣的威脅序列獲勝, 檢查剩余位置能否通過其他威脅序列獲勝；

e. 在現(xiàn)實游戲中, 一個獲勝的威脅序列通常由單方面組成, 與防守方的策略無關；

f. 特別的, 搜索空間通過進攻方第一次搜索顯著改善. 當且僅當潛在的獲勝威脅序列被發(fā)現(xiàn), 防守方的影響才被調查. 這個分析過程由Sakata和Ikawa兩位日本選手于1981年發(fā)表.

在沒有獲勝威脅序列的位置, 選手更愿意下的位置創(chuàng)造威脅的可能性更大, 或者不管任何時候防御被忽略, 被選擇的移動將降低對手創(chuàng)造威脅的可能性. 選手評估局面可能性通?；趦煞矫? a)直接計算可能性; b)一個好的形狀(石子能更好地合作的形狀).

3.2 威脅空間搜索的過程

一個獲勝的威脅序列由威脅組成. 因此我們關注威脅空間. 空間的大小通常由數(shù)百萬位置組成. 因此重點放在: a)減小空間大小; b)在剩余空間盡可能地高效搜索.

一個重大的改善來自決定與威脅相關的防守. 五子棋專家通常選擇和對手無關的策略. 與在防守策略中選擇其一不同, 我們允許對手在同一時間執(zhí)行所有可能的防守策略. 如果我們還能找到一個獲勝威脅序列, 那么可以確定對手的移動無關緊要. 簡要來說, 將搜索空間減少到只要搜索攻擊移動(威脅), 它們之中任何一種存在相應的防守策略. 為了更加準確描述威脅空間搜索, 這里介紹6個概念.

a. 一個威脅中的gain方格是由進攻方下的方格；

b. 一個威脅中的cost方格是由防守方下的方格, 是為了應對威脅的；

c. 一個威脅中的rest方格是可能包含威脅的方格, 除掉gain方格；

d. 威脅獨立于威脅, 當?shù)哪硞€rest方格是的gain方格；

e. 威脅的依賴樹是有根和依賴結點組成, 每個結點的子結點是依賴于的威脅；

f. 兩個依賴樹相沖突, 如果在依賴樹中存在威脅或者在依賴樹中存在威脅, 在這種情況下:的gain方格是的cost方格, 或者相反, 或者的一個花費格也是的一個花費格.

威脅空間搜索可以由以下兩個原則描述.

a. 威脅獨立于威脅當且僅當不允許出現(xiàn)在威脅的搜索樹中；

b. 在威脅空間搜索樹中只包括進攻方的威脅, 在一個潛在的威脅序列被發(fā)現(xiàn)之后, 將調查該序列能否承受任何防御.

這兩個原則描述了威脅空間搜索算法的核心和過程, 每次搜索一個分枝之前調用以上兩個原則構成的威脅空間搜索, 將大幅減少無用計算. 這樣實現(xiàn)程序的智能和效率都大大提高了, 歸根結底因為這樣將人的策略和思維方式加入到了程序中.

4 結語

雖然五子棋搜索是個不確定多項式問題, 不存在嚴格多項式復雜度算法, 但經過如此實現(xiàn)的程序, 在加入判重之后避免了重復搜索. 搜索的結點數(shù)目經過測試平均不足去掉判重的1/2, 而如果實現(xiàn)的時候引入部分棋譜, 當局面變成棋譜對應的經典局面之后便是索引的復雜度. 對于若干明顯的局面引入特判(如自己一步能贏就必然下該步, 對手一步能贏必然要阻止等). 加入部分棋譜啟發(fā)式估價過程每次搜索將分枝因子數(shù)目限制為至多10(事實上可以放寬數(shù)目限制, 這樣實現(xiàn)的程序智能就更高了). 對于原來若有個結點, 分枝因子平均為200的情況下, 計算量最壞為(200). 而加入該優(yōu)化之后計算量最壞為(10). 當然事實上由于alpha-beta剪枝該計算量不可能達到. 同時配合強力的威脅空間搜索將棋手下棋的很多“套路”公式化之后加入程序每次搜索提前判斷, 大幅減少不用分枝搜索, 經過筆者測試最后對于每個局面搜索的分枝數(shù)平均不到2, 實際計算量約為(1.3), 實現(xiàn)的程序能在平均不到一秒的速度下做出高效反應.

[1] 劉汝佳, 黃亮. 算法藝術與信息學競賽[M]. 北京: 清華大學出版社, 2004.

[2] Knuth D E, Moore R W. An Analysis of Alpha-Beta Pruning[J]. Artificial Intelligence, 1975, 6(11): 293-326.

[3] Donald Knuth, Ronald W Moore. Alpha-beta pruning. [EB/OL]. http://en.wikipedia.org/wiki/Alpha-beta_pruni- ng, 2002.

[4] Allis L V. Games and Artificial Intelligence[D]. Maast- richt Netherlands: Department of Computer Science, 1994.

[5] 郭瑞杰, 程學旗, 許洪波, 等. 一種基于動態(tài)平衡樹的在線索引快速構建方法[J]. 計算機研究與發(fā)展, 2008, 45(10): 1769-1777.

[6] 張鈸. 統(tǒng)計啟發(fā)式搜索算法在函數(shù)優(yōu)化中的應用[J]. 計算機學報, 1997, 20(8): 673-680.

An improved treat-space search algorithm

DU Si-han1, LI Ming2

(1. Software College, Hunan University, Changsha 410082,China; 2. Hunan University of Arts And Science, Changde 415000, China)

The problems was studied in the convetional minmax search and alpha-beta pruning, ranging from too much computation to too much useless computation. Then it was enhanced with judging duplicate search and heuristic. Only the best several strategies was selected to reduce the search work. Then further enhanced it with threat-space search, which was based on the strategies of professional players. After these work, making the computer’ thinking more like human’s can tremendousely reduce the complexity. In conclusion, after the test, the implemented program has high intelligence and give excellent respond to the players’ move quickly.

minmax search; alpha-beta pruning; judging duplicate search;heuristic; treat-space search

TP 301.6

A

1672-6146(2010)03-0073-04

10.3969/j.issn.1672-6146.2010.03.019

2010-05-08

杜思翰(1987-), 男, 研究方向為人工智能、字符學組合優(yōu)化等.