中國象棋搜索算法優(yōu)化

引言
     隨著信息技術的不斷發(fā)展和網(wǎng)絡技術的不斷普及，種 類繁多、迅速便捷的電腦娛樂已然成為人們?nèi)粘Ｉ钪斜夭?可少的重要組成部分。在眾多日常休閑娛樂活動中，電腦休 閑游戲憑借它的快捷性、益智性、互動性、簡單性等眾多優(yōu) 點，成為第一選擇。
作為中華文化博大精深的代表之一，中國象棋不僅流 傳久遠，而且工具簡單，操作方便，是一項很好的智力運 動，可豐富文化生活，陶冶情操，培養(yǎng)品格，開發(fā)智力，啟 迪思維。下中國象棋時，紅色方先走，黑色方后走，之后紅 黑兩方輪流走。當一方的將（帥）被對方的棋子吃掉，又或 者某一步之后將帥互相直接碰面，又或者是被困得已經(jīng)無棋 可走時，即是對方贏棋。雙方下棋時，為了打敗對方，必須 仔細謹慎地思考對方的走法，多揣摩雙方下面幾步，這樣棋 局才會更加精彩好看。雙方斗智斗勇輪流走棋，稱為博弈。

1 極大極小算法(minmax algorithm)
極大極小算法始終站在博弈一方的立場上給棋局估值, 有利于本方的棋局給予一個較高的價值分數(shù)，不利于本方( 有利于對方)的給予一個較低的價值分數(shù)，雙方優(yōu)劣不明顯 的局面則給予一個中間價值分數(shù)。在本方行棋的時候，選擇 價值極大的子節(jié)點走棋，對方行棋則選擇價值極小的子節(jié)點 走棋，這就是一個極大極小過程。為表述方便，我們將實行 極大值搜索的一方稱為max方，另一方稱為min方。Shannon 在1950年首先提出了極大極小算法，從而奠定了計算機博弈的理論基礎。

2  Alpha-Beta搜索算法
Alpha-Beta搜索：通過向子結點傳遞Alpha和Beta值，引 發(fā)剪枝，Alpha表示本方最優(yōu)值，隨著搜索不斷變大，所以 開始一般取無窮大。Beta表示對方最壞值，隨搜索不斷變 小，初始時取正無窮大。剪枝的效率直接影響了Alpha-Beta 搜索效率，剪枝越多，效率越快。如果每個結點在搜索第一 個子結點時就產(chǎn)生剪枝，則搜索的結點數(shù)達到最??；如果剪 枝發(fā)生在每個結點的最后一個子結點上，則等同于沒有剪 枝，搜索的結點數(shù)達到最大。

3 著法排列順序的優(yōu)化
3.1 靜態(tài)著法啟發(fā)
靜 態(tài) 著 法 啟 發(fā) 是 指 不 依 賴 于 搜 索 結 果 的 著 法 排 序 方 式，即程序分析了某個局面后，不經(jīng)過搜索，就大致應該知 道哪些著法應該首先嘗試。在4種著法啟發(fā)中，吃子啟發(fā)是 靜態(tài)著法啟發(fā)，因為吃子著法數(shù)量不多，而且往往很多情況 能立刻得到實惠，所以需要首先考慮。而置換表啟發(fā)、殺手 著法啟發(fā)和歷史表啟發(fā)，都依賴于以前搜索的結果，因此屬 于動態(tài)著法啟發(fā)的范疇。
在文章中，吃子著法是有選擇的，即“表面上立刻能

圖1  著法生成順序
得到實惠”的 著 法 。 因此筆者用 了一個稱為M V V (LVA ) 的策略，在 被 吃 子 有 保 護 的 情 況 下 ， 考 慮 M V V ( 被 吃 子 價 值 ) - L V A ( 攻 擊 子 價 值 ) 的 值，而在被 吃子沒保護 的情況下， 只考慮MVV 的值，然后 對 這 種 策 略 產(chǎn) 生 的M V V (LVA ) 值作排序， 并   選   擇M V V (LVA )大于零的著法首先搜索。
3.2 置換表啟發(fā)和低出(高出)邊界的修正在置換表中保存一個著法，一方面可以利用置換表來
獲得主要變例，但最主要的作用是置換表啟發(fā)。在探測置換 表時，盡管局面命中但深度沒達到要求時，至少可以得到一 個著法，這個著法應該首先搜索，幾乎所有的象棋程序都是 這么做的。哪些著法應該被保存到置換表中呢？實踐證明， PV結點中的最佳著法，以及Beta結點中產(chǎn)生截斷的著法，都 應該被保存到置換表中，而Alpha結點盡管也要保存，但不 需保存著法(置換表著法是空的)，因為Alpha結點的每個著 法都返回Alpha值，我們不知道哪個著法是最好的。
顯然， 當探測置換表找到P V結點或Beta結點(但深度不夠) 時， 就會有需要首先搜索的置換表著法。 那么， 找到Alpha結點時，是否還會有置換表著法呢？中國象棋程序“縱馬奔流”采取了一個稱為“低出(高出)邊界的修正”策
略，使得某些Alpha結點也存在置換表著法。
3.3 殺手著法啟發(fā)
殺手著法啟發(fā)(Killer Heuristic)基于這樣一個思想，搜索 某個結點時首先嘗試著法a1，由a1的后續(xù)著法b1產(chǎn)生截斷， 回到原來的結點時再搜索a1的兄弟結點a2時，如果b1仍舊是 a2的后續(xù)著法，那么b1很有可能也會產(chǎn)生截斷。
采 用 殺 手 著 法 啟 發(fā) 時 ， 需 要 構 造 一 個 稱 為 KillerMoves[MaxPly]的全局數(shù)組。搜索到深度為Ply的結點 時，首先嘗試KillerMoves[Ply]的著法(前提是該著法在當前 局面下是合理的)，搜索完這個結點時，把產(chǎn)生截斷的著法 (如果有的話)記錄到KillerMoves[Ply]。由此產(chǎn)生的效果，就 是當親兄弟結點沒有殺手著法時，會找到堂兄弟結點的殺手 著法。
3.4  著法生成順序
應用本文3.1節(jié)所提出的靜態(tài)評價啟發(fā)，結合置換表啟 發(fā)和殺手啟發(fā)，本文提出了一個較好的著法生成順序，以取 代以往以棋子為主鍵的排列順序。 如圖1所示。
使用啟發(fā)式方法對著法順序進行優(yōu)化后，能大大減少 搜索的節(jié)點數(shù)，實驗結果如表1所示，其中優(yōu)化前的著法順 序指的是以棋子為主鍵的排列順序。從表中可以看出。隨著 搜索深度的增加，優(yōu)化的著法順序所起的效用越來越大, 這 也驗證了剪枝的效率與著法順序高度相關。

4 內(nèi)部迭代加深和優(yōu)化策略
4.1 迭代思想
最初有一個思想，就是一開始只搜索一層，如果搜索的時間比分配的時間少，那么搜索兩層，然后再搜索三層， 等等，直到你用完時間為止，這就是迭代的思想。內(nèi)部迭代 加深優(yōu)化著法順序，內(nèi)部迭代加深是指當對一個節(jié)點進行 深度為d（d相對較大）的搜索時,首先對其進行d-2的淺層搜 索，然后進行剪枝，找出一個最優(yōu)的著法，然后繼續(xù)進行搜 索，如果時間沒有用完同樣搜索到d-2層，否則在時間用完 后中斷搜索。這會極大地提高搜索深度和效率。
4.2  時間策略
時間策略在各個象棋程序中差異很大，有的程序根本 沒有時間策略，只能設定固定的搜索深度，或者在固定的 時間中止思考，例如中國象棋協(xié)議目前就沒有時間策略。UCCI協(xié)議可以把時限規(guī)則告訴引擎，由引擎自動分配時間，時限規(guī)則可以是以下兩種：
(1) 時段制，即在限定時間內(nèi)走完規(guī)定的步數(shù)。
(2) 加時制，即在限定時間內(nèi)走完整盤棋，但每步會加 上幾秒。
不 管 處 理 哪 個 規(guī) 則 ， 都 會 分 配 一 個 合 適 的 時 間
(ProperTime)用來走棋，這個時間是這樣計算的：
(1) 時段制：分配時間 = 剩余時間 / 要走的步數(shù)；
(2) 加時制：分配時間 = 每步增加的時間 + 剩余時間 /
20 (即假設棋局會在20步內(nèi)結束)；
4.3  殺棋策略
是否能找到殺棋和搜索深度有關，某一深度下找不到 殺棋，但深一層搜索就可能找到；但和一般局面不同的是， 如果一定深度能找到殺棋，那么更深的深度會得到同樣的結 果。因此，如果找到殺棋，那么程序要使用不同的策略。對 于處理殺棋局面，往往用到以下幾個策略：
(1) 置換表的存取策略，前面曾經(jīng)介紹過，如果置換表中存儲的某個局面已被確認找到殺棋，那么探測到這樣的局
面時就不需要考慮深度條件。
(2) 根結點做迭代加深時，找到殺棋后搜索就立即停 止。
(3) 給當前局面賦予一個分值區(qū)間(-WIN_VALUE, WIN_ VALUE),如果根結點的所有著法中，除了一個著法可以支 撐(即分值大于-WIN_VALUE)以外，其余著法都會輸?shù)?即 分值都小于-WIN_VALUE)，那么應該立即返回這個唯一著 法。另外如果某個根結點已經(jīng)找到一個著法足夠領先對手巨 大優(yōu)勢(即分值大于WIN_VALUE),其他的著法就不必繼續(xù)搜 索下去，可以直接返回這個著法。

5 結論
針對中國象棋中的著法排列，本文將置換表著法、 靜 態(tài)評價較優(yōu)的著法和殺手著法排在前面，其余著法按歷史得 分依次降序排在后面，從而得到了一個較好的著法生成順 序,使游戲電腦更加智能，增加了游戲趣味性。