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

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

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

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

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

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

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

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