一種改進(jìn)的威脅空間搜索算法

杜思翰, 李 銘

?

一種改進(jìn)的威脅空間搜索算法

杜思翰1, 李 銘2

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

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

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

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

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

1 判重

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

圖1 一顆搜索樹

圖2 改造后的dag

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

2 啟發(fā)式的應(yīng)用

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

加入人下棋時(shí)候的基本策略：

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

b. 如果某個(gè)位置對(duì)手能夠一步獲勝那么必須阻止；

c. 如果某個(gè)位置對(duì)手有諸如.BBBB.這樣的連線, 那么本局是必?cái)【? 所以如果對(duì)手可能造成這樣的局面, 必須要阻止.

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

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

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

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

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

3 威脅空間搜索

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

3.1 相關(guān)定義和知識(shí)

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

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

在圖4中展示黑子可以通過一系列威脅序列獲勝的位置, 該威脅序列僅僅由four組成. 因?yàn)橐粋€(gè)four必須被立即防御, 因此白子移動(dòng)是被強(qiáng)迫的.

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

圖3 威脅

圖4 一個(gè)由four組成的威脅序列

圖5 一個(gè)由three組成的威脅序列

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

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

b. 威脅會(huì)被考慮, 尤其是與棋盤上面已經(jīng)有的, 其他棋子相關(guān)的威脅. 對(duì)方的防御可以完全被忽略；

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

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

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

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

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

3.2 威脅空間搜索的過程

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

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

a. 一個(gè)威脅中的gain方格是由進(jìn)攻方下的方格；

b. 一個(gè)威脅中的cost方格是由防守方下的方格, 是為了應(yīng)對(duì)威脅的；

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

d. 威脅獨(dú)立于威脅, 當(dāng)?shù)哪硞€(gè)rest方格是的gain方格；

e. 威脅的依賴樹是有根和依賴結(jié)點(diǎn)組成, 每個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)是依賴于的威脅；

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

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

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

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

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

4 結(jié)語

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

[1] 劉汝佳, 黃亮. 算法藝術(shù)與信息學(xué)競(jìng)賽[M]. 北京: 清華大學(xué)出版社, 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] 郭瑞杰, 程學(xué)旗, 許洪波, 等. 一種基于動(dòng)態(tài)平衡樹的在線索引快速構(gòu)建方法[J]. 計(jì)算機(jī)研究與發(fā)展, 2008, 45(10): 1769-1777.

[6] 張鈸. 統(tǒng)計(jì)啟發(fā)式搜索算法在函數(shù)優(yōu)化中的應(yīng)用[J]. 計(jì)算機(jī)學(xué)報(bào), 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àn)槿斯ぶ悄?、字符學(xué)組合優(yōu)化等.