經(jīng)典中國(guó)象棋博弈原理(徐心和)

中國(guó)象棋

計(jì)算機(jī)博弈原理中國(guó)象棋計(jì)算機(jī)博弈原理棋局表示著法生成評(píng)估函數(shù)博弈搜索開(kāi)局庫(kù)與殘局庫(kù)系統(tǒng)建模根本約定立足紅方向上進(jìn)攻狀態(tài)演化方程：

——棋譜(紅方)(黑方)中國(guó)象棋棋局演化過(guò)程棋局狀態(tài)展開(kāi)示意圖紅方紅方紅方黑方黑方Depth1Depth3Depth4Depth2Depth0紅方走棋時(shí)展開(kāi)深度為4的博弈樹(shù)

棋局表示

BoardRepresentation通常我們使用狀態(tài)集合來(lái)表示n

時(shí)刻的棋局狀態(tài)。即——棋局狀態(tài)矩陣——棋子狀態(tài)矩陣——棋子位置矩陣——比特棋盤(pán)矩陣棋盤(pán)表示與棋盤(pán)矩陣

矩陣元素為數(shù)偶，表示棋盤(pán)坐標(biāo)值。行向路向棋子表示法國(guó)際象棋KingRookKnightQueenBishopPawn中國(guó)象棋KingRookHorseCannonGuardElephantPawn紅子帥車(chē)馬炮仕相兵Null字母代號(hào)krhcbep兵種編碼12345670象棋明星兵種編碼020408060c0a0e黑子將車(chē)(硨)馬(碼)炮(砲)士象卒字母代號(hào)KRHCBEP兵種編碼－1－2－3－4－5－6－7象棋明星兵種編碼121418161c1a1e黑子中的硨、碼、砲將在不便區(qū)分車(chē)、馬、炮的紅黑方時(shí)使用初始棋局狀態(tài)的表示兵種紅帥紅車(chē)紅馬紅炮紅士紅相紅兵無(wú)子編碼１２３４５６７０兵種黑將黑車(chē)黑馬黑炮黑士黑象黑兵編碼－１－２－３－４－５－６－７行向路向初始棋子狀態(tài)的表示編碼12345678910111213141516棋子黑將黑車(chē)黑馬黑炮黑士黑象黑兵編碼17181920212223242526272829303132棋子紅帥紅車(chē)紅馬紅炮紅士紅相紅兵棋子位置矩陣表示法k12345678910111213141516黑將黑車(chē)黑馬黑炮黑士黑象黑兵k17181920212223242526272829303132紅帥紅車(chē)紅馬紅炮紅士紅相紅兵第1行表示編號(hào)為k的棋子在棋盤(pán)矩陣中的行號(hào)，第2行表示編號(hào)為k的棋子在棋盤(pán)矩陣中的列〔路〕號(hào)。對(duì)于初始棋局比特棋盤(pán)表示法路向比特向量

(Vertical）行向比特向量

(Horizon)注意：#表示計(jì)算比特向量〔二進(jìn)制數(shù)〕對(duì)應(yīng)的十進(jìn)制整數(shù)行向路向比特棋盤(pán)與棋局的布爾條件比特棋盤(pán)用以記錄棋局的某些布爾條件。如果比特棋盤(pán)中對(duì)應(yīng)某一格的位是“1”，那么這一格上的條件就是“真”；如果是“0”那么對(duì)應(yīng)的條件就是假。布爾條件就是在“哪些格子上符合你所定義的條件”。比方，“棋盤(pán)哪些位置有棋子？”“棋盤(pán)哪些位置有紅棋棋子？”“棋盤(pán)哪些位置有車(chē)？”……這給計(jì)算機(jī)上的表示帶來(lái)很大方便：12個(gè)字節(jié)，96位便可以表示一種條件〔高6位為0〕。比特棋盤(pán)預(yù)置表法在著法生成中具有重要的地位，而且在評(píng)估中可以方便地判斷棋子相互的聯(lián)系和威脅。初始行、路比特向量對(duì)應(yīng)數(shù)值#B——比特向量索引值一個(gè)10位〔9位〕比特向量B可以表示一路〔行〕棋子的分布，它又可以有一個(gè)正整數(shù)#B作為索引，這將為今后的棋盤(pán)分析帶來(lái)巨大方便；表示路向棋子全部可行分布情況的索引值范圍為0—210-1=1023；表示行向棋子全部可行分布情況的索引值范圍為0—29-1=511；這樣通過(guò)索引值就可以找到相應(yīng)棋子的分布情況。棋局的哈希數(shù)(H)與哈希變換黑將黑車(chē)黑馬黑炮黑士黑象黑兵k12345678910111213141516kM-1-2-2-3-3-4-4-5-5-6-6-7-7-7-7-7紅帥紅車(chē)紅馬紅炮紅士紅相紅兵k17181920212223242526272829303132kM1223344556677777對(duì)應(yīng)64位隨機(jī)數(shù)哈希變換棋局的哈希數(shù)(H)與哈希變換為異或算符，H為64位數(shù)形成哈希數(shù)（值）由當(dāng)前棋局PM生成64位隨機(jī)數(shù)H

便構(gòu)成當(dāng)前棋局的索引值，與棋局形成單向?qū)?yīng)， 即由P

可以生成H，但由H

無(wú)法產(chǎn)生P。

哈希變換沒(méi)有反變換！著法生成原理

MoveGeneration著法生成是博弈樹(shù)展開(kāi)的關(guān)鍵環(huán)節(jié)著法的表示相對(duì)著法：馬八進(jìn)七，炮5平2——非完整信息，需要與當(dāng)前局面結(jié)合著法算子的運(yùn)算功能：提-動(dòng)-落-吃提址——from即此著的出發(fā)位置；動(dòng)子——moved〔chessmanmoved〕即走動(dòng)的棋子；落址——to即著法的到達(dá)位置；吃子——killed〔chessmanCaptured〕即吃掉的棋子。對(duì)著法的要求：合法性、完整性、有序性著法生成的棋盤(pán)掃描法確定走動(dòng)的棋子〔moved〕找到該棋子的當(dāng)前位置〔from〕根據(jù)象棋規(guī)那么，掃描棋盤(pán)，逐個(gè)找到全部合理落址〔to〕〔考慮制約條件、有效區(qū)域、本方占位、對(duì)方占位等〕如果落址為本方棋子，那么不可行；假設(shè)為對(duì)方棋子，那么可以吃子〔Captured〕如果到達(dá)落址，構(gòu)成“將軍”〔叫殺〕，那么應(yīng)該給對(duì)方以提示——“將！”著法生成的棋盤(pán)掃描規(guī)那么區(qū)域定義：定義棋盤(pán)有效區(qū)域定義紅方半?yún)^(qū)定義黑方半?yún)^(qū)定義紅方九宮定義黑方九宮

字符說(shuō)明：A-area,R-red,B-black,P-palace提址(from)為(i,j)的動(dòng)子著法生成規(guī)那么Captured提址(from)為(i,j)的動(dòng)子著法生成規(guī)那么Captured提址(from)為(i,j)的動(dòng)子著法生成規(guī)那么Captured棋盤(pán)掃描法遇到的問(wèn)題雖然在著法的表達(dá)上，棋盤(pán)掃描法最為直觀、簡(jiǎn)潔，但實(shí)戰(zhàn)意義不強(qiáng)。因?yàn)閽呙柽^(guò)程大量耗時(shí)：掃描動(dòng)子、提址、制約條件、合理區(qū)域、雙方占位、吃子等都是動(dòng)態(tài)生成的，尤其區(qū)域判斷和棋子種類檢測(cè)等，時(shí)間開(kāi)銷巨大。對(duì)于吃子著法和非吃子著法無(wú)法分別生成，只能全部生成，再做篩選。模板匹配法

可以為某些動(dòng)子設(shè)計(jì)“模板”，只要匹配到提址，便可以迅速找到落址。通過(guò)單項(xiàng)比特矩陣比對(duì)，實(shí)現(xiàn)“本方子那么止，對(duì)方子那么吃”，完成“提-動(dòng)-落-吃”內(nèi)容確實(shí)定。比較適合使用模板的動(dòng)子為馬和相〔象〕。走馬匹配模板預(yù)置表法棋盤(pán)狀態(tài)確定之后，各子的可行著法是確定的。預(yù)置表的思想是把某種棋子在棋盤(pán)每個(gè)合理位置上，所有可能的棋盤(pán)狀態(tài)下的合理著法預(yù)先存儲(chǔ)起來(lái)，生成一個(gè)小型數(shù)據(jù)表集合。在生成著法時(shí)，通過(guò)查詢，取代各種計(jì)算。預(yù)置表的實(shí)質(zhì)是用空間換時(shí)間，即犧牲一定的內(nèi)存空間加速程序的運(yùn)行速度。預(yù)置表初始化很費(fèi)時(shí)，但只需在程序開(kāi)始運(yùn)行時(shí)初始化一次，而且占用內(nèi)存空間不大。預(yù)置表法棋子布局的布爾行向量形式 [101000010]非吃子著法的落址為 [000110100]可能的吃子著法的落址為 [100000000]炮行著法預(yù)置表項(xiàng)舉例動(dòng)子為炮提址為〔i,6〕炮著法的預(yù)置表總的空間占用計(jì)算每一行棋子的可行排列數(shù)恰好對(duì)應(yīng)于9位二進(jìn)制數(shù)〔有子為1，無(wú)子為0〕，即29=512種情況〔項(xiàng)〕?？紤]到炮在行向的9種可能位置，預(yù)置表的規(guī)模即為 9*512項(xiàng)。分別考慮吃子著法與非吃子著法〔2倍〕考慮路向情況，那么總表規(guī)模為2*9*512+2*10*1024=29696項(xiàng)每項(xiàng)占用4字節(jié)，那么總空間占用量為116k預(yù)置表的使用動(dòng)子〔炮〕的提址〔i,j〕由第i行的比特向量和炮在第j位置查找對(duì)應(yīng)的預(yù)置表項(xiàng)，分別得到吃子著法的比特向量和非吃子著法的比特向量；吃子著法僅為“可能”，還要判斷“本方子那么止，對(duì)方子那么吃”；查找該行本方棋子比特向量，與吃子著法比特向量“與”，輸出為1那么為非法著法；查找該行對(duì)方棋子比特向量，與吃子著法比特向量“與”，輸出為1那么為合法吃子著法，得到落址；由該落址便可以得到“吃子”。評(píng)估函數(shù)在難以判斷輸贏的情況下識(shí)別棋局的好壞，可行的方法就是對(duì)局面進(jìn)行量化通過(guò)為棋局“打分”，評(píng)判棋局的好壞。由于評(píng)估需要大量的象棋知識(shí)，仁者見(jiàn)仁，智者見(jiàn)智；評(píng)估函數(shù)的設(shè)計(jì)便成為機(jī)器博弈中最為人性化和模糊化的局部。目前對(duì)于評(píng)估函數(shù)取得共識(shí)的觀點(diǎn)，應(yīng)該包括如下局部：

固定子力評(píng)估值—e1(m)

車(chē)-600，炮-285，馬-270相-120，士-125兵、卒-20帥、將無(wú)窮大值，具體數(shù)值可以給6000紅方為正值，黑方為負(fù)值

棋子位置評(píng)估值—e2(m,i,j)

各兵種在棋盤(pán)的不同位置上權(quán)值不同可由三維數(shù)組給出：三維數(shù)組可以按兵種分解為假設(shè)干個(gè)二維數(shù)組，而且要區(qū)分紅方和黑方x分別為各兵種代碼紅車(chē)位置評(píng)估值(m=r)車(chē)坐大堂分值最高！馬窩心和馬臥槽大不相同！紅馬位置評(píng)估值(m=h)當(dāng)頭炮分值較高！紅炮位置評(píng)估值(m=c)紅兵位置評(píng)估值(m=p)可見(jiàn)進(jìn)入九宮的兵頂大車(chē)！棋子靈活度評(píng)估值—e3對(duì)各兵種而言，每多一個(gè)可走位置就加上一定分值。如設(shè)定：兵 15 士 1 象 1 車(chē) 6 馬 12 炮 6 將 0

棋子配合評(píng)估值—e4重點(diǎn)是車(chē)馬炮的配合與牽制。過(guò)河兵牽手可加120分。連環(huán)馬、擔(dān)子炮、霸王車(chē)等都可以考慮加分。將帥平安評(píng)估值—e5此項(xiàng)多從盤(pán)勢(shì)上加以考慮。多子歸邊、空頭炮、當(dāng)頭炮、沉底炮、將帥位置等，都要給予一定的懲罰或獎(jiǎng)勵(lì)分。評(píng)估函數(shù)的計(jì)算本方為正值，對(duì)方為負(fù)值，其代數(shù)和即為當(dāng)前局面評(píng)估值。顯然，總值為正對(duì)我方有利，負(fù)值對(duì)對(duì)方有利。絕對(duì)值的大小說(shuō)明雙方棋勢(shì)的差距。不難看出，評(píng)估函數(shù)中涉及到的權(quán)值系數(shù)可能多達(dá)上千個(gè)，都需要認(rèn)真選擇與權(quán)衡?！到y(tǒng)開(kāi)發(fā)難點(diǎn)。博弈搜索引擎

〔Gamesearchengine)博弈搜索引擎搜索策略—廣度優(yōu)先〔Breadth-firstsearch〕 深度優(yōu)先〔Depth-firstsearch〕 迭代深化〔Iterativesearch〕搜索技巧—截?cái)?剪枝〔cut-off〕 剪枝〔pruning〕 擴(kuò)展/延伸〔extended〕搜索結(jié)果—返回值/倒推值/局面評(píng)估值最正確路徑/當(dāng)前著法〔Thebestmove〕廣度優(yōu)先搜索——近根為先深度優(yōu)先搜索——遠(yuǎn)根為先博弈樹(shù)分析博弈樹(shù)上的每一個(gè)節(jié)點(diǎn)都代表一個(gè)棋局，棋手就是要在眾多的葉子節(jié)點(diǎn)上挑選一個(gè)“最正確的路徑與局面”作為自己的選擇，從而反推到當(dāng)前的著法。中國(guó)象棋博弈樹(shù)的龐大是可以想象的。如果按照每一步平均有45種可行著法，每局棋平均走90步，那從開(kāi)始局面展開(kāi)到分出勝負(fù)，那么要考慮種局面。據(jù)說(shuō)，這一天文數(shù)字要比地球上的原子數(shù)目還要多，即使用世界上最快的計(jì)算機(jī)進(jìn)行計(jì)算，直到地球消滅也無(wú)法算出第一步的著法。搜索法是求解此類圖模型的根本方法無(wú)法搜索到最終的勝負(fù)狀態(tài)，只能靠評(píng)估。搜索的目標(biāo)——如何在有限深度的博弈樹(shù)中找到評(píng)估值“最正確”而又不劇烈波動(dòng)的最正確棋局——目標(biāo)狀態(tài)。最正確路徑〔Principalcontinuation〕——從當(dāng)前狀態(tài)出發(fā)到達(dá)最正確狀態(tài)的路徑，它代表著理智雙方精彩對(duì)弈的系列著法。最正確著法〔Thebestmove——Rootmove〕——最正確路徑上的第1步棋。所謂“不劇烈波動(dòng)”就是說(shuō)最正確棋局不是在進(jìn)行子力交換與劇烈拼殺的過(guò)程當(dāng)中。搜索策略的劃分A類——窮盡搜索〔Exhaustivesearch〕B類——選擇性搜索〔Selectivesearch〕C類——目標(biāo)導(dǎo)向搜索〔Goaloriented search〕“一著不慎，滿盤(pán)皆輸”于是，看得遠(yuǎn)〔搜索的深〕，看得準(zhǔn)〔真正找到指定深度內(nèi)的最正確的平穩(wěn)棋局〕，便成為搜索算法的根本著眼點(diǎn)。顯然窮盡搜索成為人們首選的搜索策略。蠻力搜索〔Brutesearch〕一般采用廣度優(yōu)先搜索一層層展開(kāi)，一層層搜索，因?yàn)椤案F盡”而沒(méi)有風(fēng)險(xiǎn)，不會(huì)漏掉展開(kāi)深度內(nèi)的最優(yōu)解。假設(shè)計(jì)算機(jī)搜索節(jié)點(diǎn)速率為1M/秒，中國(guó)象棋B=45〔分枝因子B=40~50〕下表為在不同的給定時(shí)間內(nèi)到達(dá)的搜索層數(shù)。給定時(shí)間1秒1分1小時(shí)1天1年10年100年搜索層數(shù)3.634.705.786.628.178.779.36出路在哪里？由于完整的博弈樹(shù)過(guò)于龐大，盲目搜索所能到達(dá)的層數(shù)十分有限，在象棋博弈中幾乎沒(méi)有實(shí)用價(jià)值。假設(shè)想在指定時(shí)間內(nèi)將搜索深度加以提高，一方面需要改進(jìn)硬件與優(yōu)化程序代碼，提高單位時(shí)間內(nèi)搜索的節(jié)點(diǎn)數(shù)；另一方面就需要像人類棋手一樣有選擇性地進(jìn)行搜索，即對(duì)博弈樹(shù)進(jìn)行必要的裁剪〔cut-off/pruning〕。奠基者——香儂教授香儂(ClaudeShannon)教授早在1950年首先提出了極大-極小算法〔MinimaxAlgorithm〕，從而奠定了計(jì)算機(jī)博弈的理論根底。

Shannon,ClaudeE.,Programmingacomputerforplayingchess[J],PhilosophicalMagazine, Vol.41:256-275,1950.博弈樹(shù)特點(diǎn)分析博弈樹(shù)不同于一般的搜索樹(shù)，它是由對(duì)弈雙方共同產(chǎn)生的一種“變性”搜索樹(shù)。紅方為走棋方，它在偶數(shù)層的著法選擇是要在其全部子節(jié)點(diǎn)中找到評(píng)估值最大的一個(gè)，即實(shí)行“Max搜索”。紅方稱為MAX方。而其應(yīng)對(duì)方——黑方在奇數(shù)層的著法選擇那么是在其全部子節(jié)點(diǎn)中要找到評(píng)估值最小的一個(gè)，即實(shí)行“Min搜索”。黑方稱為MIN方。紅方紅方紅方黑方黑方Depth1Depth3Depth4Depth2Depth0紅方走棋時(shí)展開(kāi)深度為4的博弈樹(shù)極大極小搜索〔Min-MaxSearch〕MAXMAXMIN1298765433213由此產(chǎn)生最正確路徑和最正確著法MAXMAXMIN5298761431244MaxMin搜索〔2〕由此產(chǎn)生最正確路徑和最正確著法α-β剪枝搜索一種基于剪枝〔α-βcut-off〕的深度優(yōu)先搜索〔depth-firstsearch〕。將走棋方定為MAX方，因?yàn)樗x擇著法時(shí)總是對(duì)其子節(jié)點(diǎn)的評(píng)估值取極大值，即選擇對(duì)自己最為有利的著法；將應(yīng)對(duì)方定為MIN方，因?yàn)樗咂鍟r(shí)需要對(duì)其子節(jié)點(diǎn)的評(píng)估值取極小值，即選擇對(duì)走棋方最為不利的、最有鉗制作用的著法。MAXMAXMIN45682434α剪枝〔1〕由此產(chǎn)生最正確路徑和最正確著法

α=4在對(duì)博弈樹(shù)采取深度優(yōu)先的搜索策略時(shí)，從左路分枝的葉節(jié)點(diǎn)倒推得到某一層MAX節(jié)點(diǎn)的值，可表示到此為止得以“落實(shí)”的著法最正確值，記為α。顯然此值可作為MAX方著法指標(biāo)的下界。在搜索此MAX節(jié)點(diǎn)的其它子節(jié)點(diǎn)，即探討另一著法時(shí)，如果發(fā)現(xiàn)一個(gè)回合〔2步棋〕之后評(píng)估值變差，即孫節(jié)點(diǎn)評(píng)估值低于下界α值，那么便可以剪掉此枝〔以該子節(jié)點(diǎn)為根的子樹(shù)〕，即不再考慮此“軟著”的延伸。此類剪枝稱為α剪枝。MAXMAXMIN13682154α剪枝〔2〕7491224由此產(chǎn)生最正確路徑和最正確著法

α=4剪枝效果差異很大不難發(fā)現(xiàn)，和最正確著法關(guān)系密切什么是最正確著法？怎樣找到最正確著法？〔1〕〔2〕β-剪枝〔1〕174298MAXMINMIN77由此產(chǎn)生最正確路徑和最正確著法β=7同理，由左路分枝的葉節(jié)點(diǎn)倒推得到某一層MIN節(jié)點(diǎn)的值，可表示到此為止對(duì)方著法的鉗制值，記為β。顯然此β值可作為MAX方無(wú)法實(shí)現(xiàn)著法指標(biāo)的上界。在搜索該MIN節(jié)點(diǎn)的其它子節(jié)點(diǎn)，即探討另外著法時(shí)，如果發(fā)現(xiàn)一個(gè)回合之后鉗制局面減弱，即孫節(jié)點(diǎn)評(píng)估值高于上界β值，那么便可以剪掉此枝，即不再考慮此“軟著”的延伸。此類剪枝稱為β剪枝。β-剪枝〔2〕835791MAXMINMIN8426由此產(chǎn)生最正確路徑和最正確著法448β=4β剪枝和α剪枝具有同樣規(guī)律剪枝效果與最正確著法的位置密切相關(guān) 與博弈樹(shù)展開(kāi)的順序密切相關(guān)〔1〕〔2〕需要指出的是α-β剪枝是根據(jù)極大-極小搜索規(guī)那么進(jìn)行的，雖然它沒(méi)有遍歷某些子樹(shù)的大量節(jié)點(diǎn)，但它仍不失為窮盡搜索的本性。α-β剪枝技巧的發(fā)現(xiàn)，一下便為博弈樹(shù)搜索效率的提高開(kāi)創(chuàng)了嶄新的局面。Knuth和Moore重要奉獻(xiàn)1975年給出了α-β算法正確性的數(shù)學(xué)證明。α-β剪枝算法的效率與子節(jié)點(diǎn)擴(kuò)展的先后順序相關(guān)。在最理想情況下〔極小樹(shù)〕，其生成的節(jié)點(diǎn)數(shù)目為（D為偶數(shù)）（D為奇數(shù)）而蠻力搜索（D為搜索深度）可見(jiàn)不做任何剪枝僅能搜索到一半深度如何才能得到極小樹(shù)？不難看出，如果最左路的分枝就是最正確路徑，亦即理智雙方最為精彩的對(duì)弈著法序列，那么就可以將右路各分枝陸續(xù)剪掉，從而使α-β搜索的節(jié)點(diǎn)數(shù)僅為極大樹(shù)的。為了得到最好的節(jié)點(diǎn)擴(kuò)展順序，許多搜索算法在著法〔節(jié)點(diǎn)擴(kuò)展的分枝〕排序上給予特別的關(guān)注。比方在著法生成〔節(jié)點(diǎn)擴(kuò)展〕時(shí)，先生成吃子著法，尤其先生成吃分值高的“大子”著法，因?yàn)橛纱水a(chǎn)生著法更有可能是最正確的。面向著法排序的算法圍繞著法排序，已經(jīng)出現(xiàn)許多優(yōu)秀的搜索算法與舉措。如：同形表法〔Transpositiontable〕吃子走法的SEE排序殺手走法〔Killerheuristic〕未吃子走法的歷史啟發(fā)排序〔Historicheuristic〕類比法〔Methodofanalogies〕等。有人將α-β剪枝作用延伸到多個(gè)回合之后，于是又出現(xiàn)了深層α-β剪枝〔Deepα-βcut-off〕算法。也取得很好效果。α-β窗口搜索

〔α-βwindowssearch〕從α-β剪枝原理中得知：α值可作為MAX方可實(shí)現(xiàn)著法指標(biāo)的下界β值可作為MAX方無(wú)法實(shí)現(xiàn)著法指標(biāo)的上界于是由α和β可以形成一個(gè)MAX方候選著法的窗口也便出現(xiàn)了各種各樣的α-β窗口搜索算法。α-β窗口的搜索算法圍繞如何能夠快速得到一個(gè)盡可能小而又盡可能準(zhǔn)確的窗口，也便出現(xiàn)了各種各樣的α-β窗口搜索算法。如Fail-SoftAlpha-BetaAspirationSearch〔渴望搜索〕MinimalWindowSearch〔最小窗口搜索〕PrincipalVariableSearch〔PVS搜索〕Negascout搜索寬容搜尋〔Tolerancesearch〕等。迭代深化搜索

〔Iterativedeepeningsearch〕不難想像，深度為D－1層的最正確路徑，最有可能成為深度為D層博弈樹(shù)的最正確路徑。Knuth和Moore分析說(shuō)明，對(duì)于分枝因子為B的博弈樹(shù)，利用剪枝搜索D層所需時(shí)間大約是搜索D-1層所需時(shí)間的倍。如果取B=36，每多搜一層就要花上原先的6倍時(shí)間。迭代深化搜索于是CHESS4.6和DUCHENSS課題組開(kāi)始采用逐層加深搜索算法。先花1/6的時(shí)間做D-1層的搜索，找到最正確路徑；同時(shí)記載同形表、歷史啟發(fā)表、殺手表等有價(jià)值的著法評(píng)估信息；以求到達(dá)D層最好的剪枝效果。目前機(jī)器博弈引擎普遍采用迭代深化搜索策略。迭代深化的時(shí)間復(fù)雜度深度優(yōu)先的迭代深化搜索D層搜索的總結(jié)點(diǎn)數(shù)為所以深度優(yōu)先的迭代深化的時(shí)間復(fù)雜度為值得關(guān)注的是，由于一系列剪枝算法的使用，使得此時(shí)的平均分枝度可以數(shù)量級(jí)地減小。許多算法已經(jīng)做到

B=2~5啟發(fā)式搜索〔Heuristicsearch〕具體問(wèn)題的領(lǐng)域決定了初始狀態(tài)、算符和目標(biāo)狀態(tài)，進(jìn)而決定了搜索空間。因此，具體問(wèn)題領(lǐng)域的信息常常可以用來(lái)簡(jiǎn)化搜索。此種信息叫做啟發(fā)信息，而把利用啟發(fā)信息的搜索方法叫做啟發(fā)性搜索方法。利用象棋的領(lǐng)域知識(shí)〔啟發(fā)信息〕設(shè)計(jì)博弈搜索的啟發(fā)式算法或方法，在著法排序中就有許多成功的應(yīng)用。這里需要特別提及的那么是平靜搜索、空著搜索和兌子搜索等。平靜搜索〔QuiescentSearch〕α-β搜索使用的是給定深度搜索，當(dāng)局面變化劇烈的時(shí)候，雖然已經(jīng)到達(dá)搜索的最大深度，但此時(shí)評(píng)估函數(shù)的返回值并不能準(zhǔn)確地表示當(dāng)前局面的情況。舉個(gè)簡(jiǎn)單的例子，某個(gè)葉節(jié)點(diǎn)上紅車(chē)吃掉了黑炮，但是下一步紅車(chē)會(huì)被黑方吃掉。如果在此葉節(jié)點(diǎn)調(diào)用評(píng)估函數(shù)，返回值肯定對(duì)紅方十分有利，但會(huì)引起判斷失誤。平靜搜索判斷局面是否劇烈振蕩的準(zhǔn)那么是走棋方是否還有吃子走法，一直延伸到走棋方無(wú)吃子走法，也就是相對(duì)平靜的局面。將軍延伸〔CheckExtension〕是指當(dāng)本方受到對(duì)方將軍時(shí)所進(jìn)行的擴(kuò)展。由于逃避對(duì)方對(duì)本帥攻擊的解將著法不多，所以我們可以對(duì)當(dāng)前節(jié)點(diǎn)的搜索深度增加一層，以更準(zhǔn)確地評(píng)估攻擊的危險(xiǎn)性。唯一著法延伸〔One_ReplyExtension〕。當(dāng)本方受對(duì)方將軍的時(shí)候，并且解將著法只有一步，這時(shí)候由于搜索量不大，我們?cè)趯④娧由熘?，還要對(duì)其進(jìn)行額外的延伸。啟發(fā)式搜索兌子延伸〔RecaptureExtension〕。搜索過(guò)程中，如果出現(xiàn)A棋子吃掉對(duì)方的B棋子，隨即Ａ棋子又被對(duì)方吃掉，那么也要對(duì)這樣的局面進(jìn)行延伸，以保證對(duì)兌子進(jìn)行準(zhǔn)確的評(píng)估?？罩阉鳌睳ullMove〕是在1993年由ChrillyDonninger最先提出的。NullMove的思想是放棄本方的走棋權(quán)利，讓對(duì)方連續(xù)走棋，如果得到的分值還大于原先的值，說(shuō)明對(duì)方?jīng)]有“硬著”可施，于是在此分枝下搜索的意義已經(jīng)不大，免于搜索。NullMove危險(xiǎn)性比較小，實(shí)現(xiàn)較為簡(jiǎn)單，剪枝效果明顯，現(xiàn)已被棋類博弈廣泛采用。負(fù)極大值算法

〔NegaMaxalgorithm〕博弈搜索是一種“變性”搜索。在偶數(shù)層進(jìn)行“Max搜索”，而在奇數(shù)層進(jìn)行“Min搜索”。這無(wú)疑給算法的實(shí)現(xiàn)帶來(lái)一大堆麻煩。Knuth和Moore充分利用了“變性”搜索的內(nèi)在規(guī)律，在1975年提出了意義重大的負(fù)極大值算法。它的思想是：父節(jié)點(diǎn)的值是各子節(jié)點(diǎn)值的變號(hào)極大值，從而防止奇數(shù)層取極小而偶數(shù)層取極大的為難局面。MAXMAXMIN1298765433213Min-Max搜索由此產(chǎn)生最正確路徑和最正確著法-3-2-1NegaMaxNegaMaxNegaMax搜索負(fù)極大值算法

〔NegaMaxalgorithm〕此時(shí)需要特別注意的那么是，如果葉節(jié)點(diǎn)是紅方〔走棋方〕走棋，評(píng)估函數(shù)返回RedValue-BlackValue，如果是黑方〔應(yīng)對(duì)方〕走棋，那么返回BlackValue-RedValue。另外，由于負(fù)極大值計(jì)算等價(jià)于“Min搜索”，所以這里只進(jìn)行β剪枝，非常有利于編程實(shí)現(xiàn)和提高搜索速度。開(kāi)局庫(kù)設(shè)計(jì)〔Openingbook〕象棋博弈三大階段：開(kāi)局、中局、殘局。雖然有時(shí)在中局就決出了勝負(fù)而沒(méi)有殘局，但所有的對(duì)局都必須有開(kāi)局。開(kāi)局是開(kāi)始的10～20個(gè)回合，對(duì)戰(zhàn)雙方各自展開(kāi)子力，占據(jù)棋盤(pán)的有利位置。中國(guó)象棋講究的是快速出動(dòng)子力，各棋子協(xié)調(diào)作戰(zhàn)，并且盡早占據(jù)中心位置。從開(kāi)始就進(jìn)行搜索，容易犯戰(zhàn)略性錯(cuò)誤。借助成熟的開(kāi)局棋譜，建立開(kāi)局庫(kù)。開(kāi)局庫(kù)設(shè)計(jì)開(kāi)局庫(kù)中通常存放了數(shù)以十萬(wàn)計(jì)甚至更多的棋局；如何能夠快速準(zhǔn)確地搜索到對(duì)應(yīng)的棋局成為開(kāi)局庫(kù)設(shè)計(jì)的關(guān)鍵技術(shù)之一。國(guó)際象棋的成功經(jīng)驗(yàn)說(shuō)明，開(kāi)局庫(kù)最好是采用Zobrist哈希技術(shù)加以實(shí)現(xiàn)；開(kāi)局庫(kù)作為棋局的索引值，記載常用著法；可以采用的著法，常常不止一個(gè)，每個(gè)著法都對(duì)應(yīng)有輸贏統(tǒng)計(jì)比率、作者偏好權(quán)重等，以便使用時(shí)選擇。一般還應(yīng)該具有自學(xué)習(xí)的功能，將新的對(duì)弈結(jié)果補(bǔ)充進(jìn)來(lái)，并且不斷自行調(diào)整比率與權(quán)重值。為異或算符，H為64位數(shù)形成哈希數(shù)（值）殘局庫(kù)〔Endga