一種新的博弈樹迭代向前剪枝搜索*

孫若瑩， 宮義山， 趙 剛

(1. 北京信息科技大學 信息管理學院， 北京 100192； 2. 沈陽工業大學 信息科學與工程學院， 沈陽 110870)

一種新的博弈樹迭代向前剪枝搜索*

孫若瑩1， 宮義山2， 趙 剛1

(1. 北京信息科技大學 信息管理學院， 北京 100192； 2. 沈陽工業大學 信息科學與工程學院， 沈陽 110870)

針對博弈樹迭代加深搜索和向前剪枝搜索中誤剪最佳分支的弱點，利用向前剪枝搜索與預評估搜索間的雙重迭代調用，提出了一種新的博弈樹迭代向前剪枝搜索方法.預評估搜索通過節點排序及調整剪枝比率可以更加準確地選取排序在前的最佳分支，進而使迭代向前剪枝搜索實現在預評估所保留的最佳分支方向進行深度搜索，二者迭代相互調用以提高向前剪枝搜索的有效性及效率.定性分析與中國象棋計算機博弈實驗結果表明，迭代向前剪枝搜索提高了實時行棋決策的效率和效果，與α-β剪枝搜索相比，提高的搜索效率超過160倍，同時取得了勝負比近7倍的博弈效果.

人工智能； 博弈樹搜索；α-β剪枝； 向前剪枝搜索； 迭代加深搜索； 評估函數； 中國象棋博弈； 實時行棋決策

眾多博弈游戲深受人們喜愛，計算機博弈模型使用博弈樹搜索與評估函數相結合的方式實現博弈游戲，計算機博弈的基礎是博弈樹搜索技術，博弈樹搜索深度是決定其棋力高低的重要因素[1-4].中國象棋和國際象棋具有許多類似之處，但中國象棋計算機博弈的空間復雜度和博弈樹復雜度比國際象棋略高，按照每一棋局平均有45種可行著法、每局平均行棋90著計算，其完全捜索博弈樹的復雜度大約為10[5].二十世紀七十年代末我國學者開始了中國象棋計算機博弈的研究工作，其研究工作的開展落后于國際象棋，八十年代初開發出個人計算機象棋程序，進而相繼出現了中山大學的“縱馬奔流”和東北大學的“棋天大圣”等象棋程序.

博弈樹搜索技術與眾多機器學習方法[6-9]始終是人工智能領域的核心問題和研究熱點，直接關系著人工智能系統的性能和效率.自Claude Shannon提出國際象棋計算機博弈方案以來，博弈樹搜索技術經歷了從最大最小搜索到α-β剪枝搜索，再到啟發式迭代加深搜索，直至概率向前剪枝搜索等若干階段，人工智能領域研究者不斷提出各種搜索技術，提高博弈樹搜索的效果和效率[10-12].目前的主要博弈樹搜索技術多數以迭代加深搜索及概率向前剪枝搜索為基礎.然而，由于迭代加深搜索與向前剪枝搜索在向前剪枝過程中使用概率剪枝方法，對于非終止狀態存在一定概率剪掉最佳行棋，可能導致錯誤行棋，從而影響對弈結果.

本文深入討論了迭代加深搜索和概率向前剪枝搜索算法，在此基礎上為進一步提高博弈樹的搜索效率，并針對計算局限導致博弈樹搜索結果不確定性的弱點，提出了迭代向前剪枝搜索算法，并將其應用于中國象棋計算機博弈游戲，定性地分析了所提高的搜索效率，通過計算機對弈實驗的結果驗證迭代向前剪枝搜索算法的效率及效果.

1 相關工作

1.1 中國象棋計算機博弈基本流程

完整的中國象棋計算機博弈一般包括6個部分：棋盤表示、局面評估函數、博弈樹、搜索算法、開局庫和殘局庫，其狀態演化流程示意圖如圖1所示.

圖1 象棋博弈狀態演化過程

棋局狀態是在著法算子作用下演化的，對應的狀態轉移方程為

(1)

式中：s0為象棋的初始局面；ak+1為第k+1步的著法算子；sk+1為k+1步后的棋局.完整博弈展開后，則有

sF=s0a1a2…aF=s0A

(2)

式中：sF為終局，或紅勝、或黑勝、或和棋；A={a1，a2，a3，…，aF}為著法序列，記載著博弈過程，其單數項記載著紅方著法序列，偶數項記載著黑方著法序列.每步著法都是博弈者的決策，博弈者通過前瞻若干步形成其當前決策.圖2給出了博弈思維過程的計算機實現示意圖.

圖2 計算機博弈思維過程

1.2 博弈樹搜索

計算機象棋博弈按照圖2“思維”方式在弈棋過程中展開一棵根在上、葉在下的博弈樹.博弈樹搜索的任務是在弈棋當前局面下，搜索符合象棋規則的著法，得到一個當前局面下的最佳著子決策.

極大極小搜索是基于深度優先的博弈樹搜索，任一時刻只考慮樹中某一路徑上的節點.在象棋博弈中，MAX先行，弈棋雙方輪流著子，直到博弈結束.效用函數定義博弈者在終止狀態SF下的數值，對應勝、平、負一般可以賦予數值+1、0、-1.

極大極小搜索始終站在博弈MAX一方的立場上評估棋局，有利于MAX的棋局給予較高估值，不利于MAX的棋局給予較低估值.弈棋過程中，MAX行棋時選擇估值極大的子節點著子，MIN行棋時則選擇估值極小的子節點擴展.為避免極大極小搜索中總要檢查哪一方取極大值、哪一方取極小值而造成執行不同的動作，1975年Knuth等提出了負極大值算法，其搜索效果與極大極小搜索完全等效.極大極小搜索一般需要檢查O(bm)個節點，b為搜索寬度，m為截斷深度.

在極大極小搜索過程中，存在極大值冗余和極小值冗余2種明顯的冗余現象，圖3給出了冗余示例，圖3a表示極大值冗余及對應的α剪枝，圖3b表示極小值冗余及對應的β剪枝.α-β剪枝搜索實現了對極大極小搜索中冗余現象的優化.

圖3 α剪枝和β剪枝

α-β剪枝搜索在路徑上回傳的2個參數值：α為到目前為止路徑上發現的MAX的最佳選擇；β為到目前為止路徑上發現的MIN的最佳選擇.對于d層的節點n，α-β(n)=max{mini(zj)}，j=1，2，…，b，zj屬于由d+1層節點展開的、在d+2層上對應的分支節點，i=1，2，…，b，mini(zj)屬于由d層節點n展開的、在d+1層上對應的分支節點.α-β剪枝搜索不斷更新α-β值，當某個節點的值分別比目前的MAX的α或MIN的β值更差時，就剪去此節點剩下的分支.α-β剪枝搜索如果首先調用評估函數檢查到的后繼節點是可能的最佳后繼，則其最高效率只需調用評估函數檢查O(bm/2)個節點.如果α-β剪枝搜索后繼狀態采用隨機順序，則需檢查的總節點約為O(b3m/4)個.α-β剪枝搜索節省了大量開銷而不失窮盡搜索的本性.

極大極小搜索生成整個博弈空間，α-β搜索剪裁掉其中的一大部分，然而，仍然需要搜索部分空間直到終止狀態.一般博弈游戲通常要在合理的時間，如幾分鐘內確定行棋.ClaudeShannon在1950年提出盡早截斷搜索，將啟發式評估函數用于評價搜索中的狀態，有效地將非終止狀態節點轉變為截斷終止節點，用啟發式評估函數取代效用函數，用階段測試取代終止測試.截斷搜索的啟發式評估函數的一般形式為

(3)

式中：CUTOFF_TEST(si，d，m)==TRUE為節點si當前深度d到達截斷深度m(即dm-dc=m，dm為當前節點深度；dc為評估節點深度)；E(·)為評估函數.

實時行棋決策根據博弈規則許可的時間決定截斷深度m，常見的2種實時行棋策略分別為截斷搜索和向前剪枝搜索.截斷搜索中較為優秀的方法是迭代加深搜索，迭代加深搜索可以幫助行棋排序.逐層加深搜索比固定深度截斷搜索更加適合于對弈過程的時間控制.逐層加深搜索在進行d層搜索時記錄得到的最佳行棋，當進入d+1層搜索時優先搜索d層記錄下來的最佳行棋.d層的最佳行棋與d+1層的最佳行棋存在很大程度的相似，d層搜索可被d+1層搜索利用并提供啟發信息，因此，迭代加深搜索比非迭代加深搜索效率更高.多數博弈程序都采用迭代加深搜索，并在迭代加深中加入置換表、歷史表和殺手列表等啟發信息，利用不同窗口搜索技術產生更好的行棋排序效果，不斷提高搜索效率，為象棋博弈實時行棋決策提供有力的支撐.

實時行棋決策的另一種方法是向前剪枝搜索，又稱為基于概率的剪枝方法，Buro將此技術應用于Othello取得了良好的效果，在搜索效率方面具有優勢.該方法使用先驗經驗的統計信息，在一定程度上保護最佳行棋不被剪掉.這種算法首先通過淺層搜索計算得到節點的倒推估值，如果倒推估值在當前的α-β窗口之外，則對此棋面不進行更深的搜索，否則進行更深搜索以得到更好的α-β值.而利用淺層搜索對深層搜索進行估算所產生的開銷相比深層搜索的開銷而言可以忽略不計，從而節省大量搜索時間，進一步提高了搜索效率.然而，向前剪枝搜索與迭代加深搜索相同，可能剪掉非終止狀態的最佳行棋，從而出現錯誤行棋，最終導致結果的不確定性.

2 迭代向前剪枝搜索

2.1 評估函數

評估函數在人工智能和模式識別領域有著廣泛的應用.象棋行棋局面評估就是利用經驗知識給棋局賦分，通過數值評估棋局的好壞.一般來說，象棋評估函數包括5個方面的要素，分別為子力估值、棋子位置估值、棋子靈活度估值、棋子配合估值、威脅與保護估值.每一方面估值又由許多值構成，如子力估值包括7類棋子的分值，棋子配合估值中擔子炮、連環馬等都需要考慮增加分值.評估函數的設計需要遵從3個基本原則：1)評估函數對終止狀態的排序應該與真正的效用函數排序的結果一致，即勝局狀態的評估值一定好于平局狀態的評估值，平局狀態的評估值一定好于負局狀態的評估值；2)評估函數的計算不能花費太長時間；3)對于非終止狀態，評估函數應該與獲勝幾率密切相關.

本文中的獲勝幾率并不是指幾率博弈，而是指在搜索過程中絕大多數的截斷節點只能發生在非終止狀態，從而導致搜索對這些狀態的最后結果是不確定的.引入這種不確定性的原因是計算局限性，而不是信息受限.

按上述基本原則，本文設計了子力估值e1、棋子位置估值e2、棋子靈活度估值e3、棋子配合估值e4、威脅與保護估值e5等5個部分，表1、2分別給出了部分估值示例，利用5個估值要素的線性加權wk評估棋局狀態si，評估函數為

(4)

表1 子力估值

表2 車的位置估值

2.2 iProbcut搜索

向前剪枝搜索在效率上與其他搜索方法相比具有明顯優勢，鑒于此，本文提出了一種新的迭代向前剪枝搜索算法iProbcut，并將其應用于中國象棋博弈.

iProbcut搜索的基本思想是利用向前剪枝搜索截斷層m與預評估層m-l節點間的迭代調用，通過多層預評估實現高效的多層向前剪枝搜索.iProbcut搜索與迭代加深搜索及現有的向前剪枝搜索Probcut相比，能夠實現更深層次的深度優先預評估，從而提高搜索效率和向前剪枝搜索的效果.

本文定義iProbcut迭代向前剪枝搜索函數f和預評估向前剪枝搜索函數g的迭代調用公式分別為

(5)

(6)

式中：arg rank(n，pk)g為f調用g時對預評估層m-l內節點實施預評估向前剪枝搜索，并對其進行排序，取最佳值對應的前n個節點，arg rank(n，pk)為以概率pk選取max或min值排序最佳的前n個節點；max和min分別定義了對排序后的節點實施迭代向前剪枝搜索的評估值.

在迭代向前剪枝搜索函數f和預評估向前剪枝搜索函數g的相互迭代調用過程中，對預評估層節點同樣執行基于α-β的向前剪枝，對剪枝后的節點實施排序，從而利用預評估排序得到的優勢節點進一步展開迭代向前剪枝搜索.在迭代向前剪枝搜索過程中，迭代向前剪枝搜索函數f通過調整預評估向前剪枝排序后的前n個節點的概率pk取值系數k，對預評估向前剪枝搜索迭代過程中的遠端節點增加選取概率，從而達到在變化棋局時增加參與迭代向前剪枝搜索節點數量的目的，以此增強iProbcut對應變化棋局的搜索效果，降低非終止狀態下誤剪最佳行棋的幾率，提高向前剪枝搜索的效果.因此，在保證iProbcut搜索中的預評估向前剪枝搜索對比α-β搜索更加高效的同時，進一步保證對比迭代加深搜索實現更深層次的預評估，而且能夠降低向前剪枝搜索在非終止狀態下誤剪最佳行棋的幾率，實現提高向前剪枝搜索效率和效果的設計目標.

3 實驗與分析

α-β剪枝搜索不失極大極小搜索對棋局評估的本性，在截斷層數相同的情況下，其對弈效果優于迭代加深搜索或向前剪枝搜索.因此，本文在進行對弈結果的比較時，采用iProbcut迭代向前剪枝搜索與α-β剪枝搜索的對弈實驗.在搜索效率方面，通過比較各棋局調用節點評估函數的次數，驗證iProbcut搜索的執行效率.

實驗將α-β剪枝搜索的截斷層數m設為6，為了在對等的條件下進行結果比較，iProbcut搜索的截斷層數m設為8，預評估層數m-l設為2，也就是說，iProbcut搜索中的α-β搜索截斷層數為6，不使其優于α-β搜索，pk的參數k隨m-l調整，由于預評估中存在排序剪枝，故而iProbcut搜索在其α-β搜索截斷層數6中保留的節點數目遠少于α-β搜索的節點數目.iProbcut搜索與α-β剪枝搜索在同一計算機上對弈20局，輪流采用相同的先手開局形式.實驗運行環境為Intel Pentium Dual 1.80 GHz處理器，4 GB內存，32位Windows 7操作系統，Microsoft Visual Studio 2015開發環境.本文測試的主要目的是驗證iProbcut搜索的效果和效率，因此省略了圖形可視化界面，采用console方式展現對弈棋局，棋局截圖如圖4所示.運行環境對本文實驗結果并不產生影響，主要目的是說明iProbcut可在普通個人計算機上執行.

圖4 棋局截圖

表3給出了上述設置下的對弈結果，其中iProbcut搜索勝13局、平5局、負2局，取得了很好的效果.表3中“終盤著數”表示每局雙方一共用的著數，采用300著無勝負判和棋，其中勝局中的最多著數出現在局12，220著，最少著數為局4，58著，平均著數為113著.“節點數目倍數列1”表示iProbcut搜索調用評估函數的次數與同一著中α-β剪枝搜索調用評估函數次數的倍數值，“最大值”表示各局中最大的倍數值，“平均值”表示各局中倍數值的平均數.最大倍數值出現在平局的局16中，最小倍數值出現在勝局的局12中，平均倍數值約為15，說明iProbcut搜索能夠將調用評估函數次數的變化控制在穩定的區間內.本文中的α-β剪枝搜索截斷層數m為6，iProbcut搜索截斷層數m為8，中國象棋每著平均45分支，按此計算，截斷層數為8與截斷層數為6相比，其調用評估函數次數的倍數值平均約為2 500倍.可知iProbcut搜索與α-β剪枝搜索調用評估函數次數的倍數值之比約為15∶2 500，說明iProbcut搜索在提高了對弈效果的同時具有良好的搜索效率.作為參考，“節點數目倍數列2”給出了6層截斷α-β剪枝搜索調用評估函數次數與iProbcut搜索中α-β剪枝搜索6層截斷時調用評估函數次數的倍數值.

表3 對弈結果

圖5給出了代表性棋局各回合中調用評估函數次數的倍數值，其中棋局4、7、12、16分別對應勝局中的最少著數局、最多著數局、平均著數局、以及調用評估函數次數的最大倍數值所出現的平局局16中.可以看出，勝局中調用評估函數次數的倍數值基本上是穩定的；而調用評估函數次數的倍數值的增大出現在雙方進入對弈后期，增大pk的系數k后，在最大限定時間內剪枝數目明顯降低的階段.圖6給出了代表性棋局中iProbcut調用評估函數的次數，與圖5相結合可以看出，調用評估函數次數的倍數值并不是隨著調用次數的增大而增大，調用評估函數次數增大時，調用評估函數次數的倍數值變化基本平穩，調用評估函數次數的倍數值增大時，調用評估函數的次數相對數值不大且比較穩定.圖6中棋局7與棋局12在對弈開局階段出現調用評估函數近1億次的大的波動，主要原因在于開局階段pk的系數k相對較小，出現概率性淺層迭代調用頻次突增.對比圖5可以看出，調用評估函數次數的倍數值保持穩定，滿足實時行棋的要求.另外，調用評估函數次數及倍數值的大的波動主要出現在開局和殘局階段，主要原因在于本文主要目的是進行搜索效率及效果的比較，沒有引入通常的開局庫和殘局庫.代表性棋局中調用評估函數次數及倍數值的結果分析進一步說明了iProbcut搜索具有良好搜索效率.

圖5 調用評估函數次數的倍數值

圖6 iProbcut調用評估函數的次數

4 結 論

本文基于向前剪枝搜索與預評估搜索間的雙重迭代，提出了博弈樹迭代向前剪枝搜索方法iProbcut.iProbcut通過迭代更新預評估節點的排序，動態增加預評估搜索中遠端節點選取的概率，增大最佳節點的保留幾率，改進了基于先驗經驗的向前剪枝搜索中非終止狀態的最佳行棋剪枝策略，進一步加深了迭代向前搜索在有效方向上的搜索深度，故而提高了向前剪枝搜索的效果.iProbcut迭代向前剪枝搜索函數f和預評估向前剪枝搜索函數g的迭代調用，利用淺層搜索對深層搜索進行估算所產生的開銷對比深層搜索的開銷可以忽略不計的特性，迭代更新預評估節點，增加參與迭代向前剪枝搜索有效節點，進一步保證對比迭代加深搜索實現更深層次的預評估，從而提高向前剪枝搜索的效率.20局對等棋局的中國象棋對弈實驗中，iProbcut對比α-β剪枝搜索取得了13勝、5平、2負的良好效果.結果與分析表明，截斷層數相同為8的情況下，α-β剪枝搜索調用評估函數次數大約是iProbcut搜索調用評估函數次數的160倍，iProbcut搜索提高了搜索效率，保證了搜索的穩定性，實現了提高迭代向前剪枝搜索效率和效果的目標.

[1]王亞杰，邱虹坤，吳燕燕，等.計算機博弈的研究與發展 [J].智能系統學報，2016，11(6)：788-798.

(WANG Ya-jie，QIU Hong-kun，WU Yan-yan，et al.Research and development of computer games [J].CAAI Transactions on Intelligent System，2016，11(6)：788-798.)

[2]李學俊，王小龍，吳蕾，等.六子棋中基于局部“路”掃描方式的博弈樹生成算法 [J].智能系統學報，2015，10(2)：267-272.

(LI Xue-jun，WANG Xiao-long，WU Lei，et al.Game tree generation algorithm based on local-road scanning method for connect 6 [J].CAAI Transactions on Intelligent System，2015，10(2)：267-272.)

[3]Silver D，Huang A，Maddison C J，et al.Mastering the game of Go with deep neural networks and tree search [J].Nature，2016，529(7587)：484-489.

[4]李煥哲，吳志健，郭肇祿.兩階段多峰優化算法求解納什均衡 [J].武漢大學學報(理學版)，2016，62(5)：444-450.

(LI Huan-zhe，WU Zhi-jian，GUO Zhao-lu.Two-stage multimodel optimization algorithm for solving nash equilibrium [J].Journal of Wuhan University(Natural Science)，2016，62(5)：444-450.)

[5]蔡屾.一種中國象棋機器博弈剪枝策略的改進方法 [J].國外電子測量技術，2016，35(3)：47-49.

(CAI Shen.Improved pruning strategy of Chinese chess machine game [J].Foreign Electronic Measurement Technology，2016，35(3)：47-49.)

[6]王溪波，王彬，趙海，等.基于HOG特征的優化區域模板匹配檢測 [J].沈陽工業大學學報，2016，38(6)：667-673.

(WANG Xi-bo，WANG Bin，ZHAO Hai，et al.Template matching detection for optimized region based on HOG features [J].Journal of Shenyang University of Technology，2016，38(6)：667-673.)

[7]Nijssen J A M，Winands M H M.Search policies in multi-player games [J].International Computer Chess Association Journal，2013，36(1)：3-21.

[8]呂艷輝，宮瑞敏.計算機博弈中估值算法與博弈訓練的研究 [J].計算機工程，2012，38(11)：163-166.

(Lü Yan-hui，GONG Rui-min.Study on valuation algorithm and game training in computer game [J].Computer Engineering，2012，38(11)：163-166.)

[9]劉子正，盧超，張瑞友.基于蒙特卡羅樹搜索的“2048”游戲優化算法 [J].控制工程，2016，23(4)：550-555.

(LIU Zi-zheng，LU Chao，ZHANG Rui-you.An algorithm for the game of 2048 based on Monte Carlo tree search [J].Control Engineering of China，2016，23(4)：550-555.)

[10]張海峰，劉當一，李文新.通用對弈游戲：一個探索機器游戲智能的領域 [J].軟件學報，2016，27(11)：2814-2827.

(ZHANG Hai-feng，LIU Dang-yi，LI Wen-xin.Ge-neral game playing：a research field for exploring machine intelligence in games [J].Journal of Software，2016，27(11)：2814-2827.)

[11]岳金朋，馮速.中國象棋Alpha-Beta搜索算法的研究與改進 [J].北京師范大學學報(自然科學版)，2009，45(2)：156-160.

(YUE Jin-peng，FENG Su.Improvement on Alpha-Beta search algorithm in Chinese chess [J].Journal of Beijing Normal University(Natural Science)，2009，45(2)：156-160.)

[12]蘇攀，王熙照，李艷.基于不平衡學習的分類器博弈模型及其在中國象棋中的應用 [J].計算機研究與發展，2011，48(5)：841-847.

(SU Pan，WANG Xi-zhao，LI Yan.Modeling chess strategy by classifier based on imbalance learning and application in computer Chinese chess [J].Journal of Computer Research and Development，2011，48(5)：841-847.)

(責任編輯：鐘 媛 英文審校：尹淑英)

A new iterative forward-pruning search for game tree

SUN Ruo-ying1, GONG Yi-shan2, ZHAO Gang1

(1. School of Information Management, Beijing Information and Technology University, Beijing 100192, China; 2. School of Information Science and Engineering, Shenyang University of Technology, Shenyang 110870, China)

Aiming at the weakness of incorrectly pruning the optimal subtrees in the iterative deepening-search and forward-pruning search for game-tree, a new iterative forward-pruning search method for game tree was proposed through adopting the reciprocal iterative calls between the forward-pruning search and pre-estimation search. The optimal subtrees with high priority could be selected more exactly through ordering the node and adjusting the pruning ratio in the pre-estimation search, which made the iterative forward-pruning search realize the deep research in the direction of optimal subtrees preserved with the pre-estimation search, and both methods could iteratively call each other to improve the effectiveness and efficiency of forward-pruning search. The qualitative analysis and the experimental results of Chinese chess computer game show that the effectiveness and efficiency of real time move decision can be improved with the iterative forward-pruning search. Compared with theα-βpruning search, the search efficiency gets improved more than 160 times, and the game effect with the win-lost ratio of nearly 7 times is obtained.

artificial intelligence; game-tree search;α-βpruning; forward-pruning search; iterative-deepening search; evaluation function; Chinese chess game; real time move decision

2017-03-01.

國家自然科學基金資助項目(61572079)； 北京市教委科技重點項目(KZ201411232036).

孫若瑩(1963-)，女，遼寧沈陽人，副教授，博士，主要從事人工智能和電子商務等方面的研究.

10.7688/j.issn.1000-1646.2017.03.12

TP 391

A

1000-1646(2017)03-0304-07

*本文已于2017-05-08 20∶25在中國知網優先數字出版. 網絡出版地址： http：∥www.cnki.net/kcms/detail/21.1189.T.20170508.2025.020.html