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

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

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

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

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

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

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

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