“理治棋壯”中國象棋計(jì)算機(jī)博弈引擎關(guān)鍵算法分析與設(shè)計(jì)

《“理治棋壯”中國象棋計(jì)算機(jī)博弈引擎關(guān)鍵算法分析與設(shè)計(jì)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、“理治棋壯”中國象棋計(jì)算機(jī)博弈引擎關(guān)鍵算法分析與設(shè)計(jì)“理治棋壯”中國象棋計(jì)算機(jī)博弈引擎開發(fā)小組在《程序架構(gòu)設(shè)計(jì)與主要算法概述》一文中，我們闡述了中國象棋計(jì)算機(jī)博弈涉及的主要算法。下面就其中的關(guān)鍵算法進(jìn)行深入分析，并說明其設(shè)計(jì)實(shí)現(xiàn)方法。一、核心搜索算法1、PrincipalVariableSearch搜索算法是計(jì)算機(jī)博弈程序的核心算法。如何選擇適合的搜索算法，配以合理的剪枝條件，是決定搜索效率的關(guān)鍵所在。博弈樹不同于一般的搜索樹，它是由對弈雙方共同產(chǎn)生的一種“變性”搜索樹。應(yīng)對這類問題，香農(nóng)(ClaudeShannon)教授早在1950年提出了極大-極小

2、算法（MinimaxAlgorithm）。這種算法常以一種形式上的改進(jìn)——負(fù)極大值算法出現(xiàn)：記我方節(jié)點(diǎn)值為正，對方節(jié)點(diǎn)值為負(fù)，雙方在每一節(jié)點(diǎn)分別選擇其子節(jié)點(diǎn)中絕對值最大的一個(gè)。遞歸深度優(yōu)先遍歷有限層次的樹，找到使起始節(jié)點(diǎn)絕對值最大的一個(gè)葉子節(jié)點(diǎn)，然后回溯找到形成這一葉子節(jié)點(diǎn)的第一層子節(jié)點(diǎn)，作為最優(yōu)解?？梢栽诓┺臉渖疃葍?yōu)先搜索過程中記錄2個(gè)附加值，α：我方搜索到的最好值，任何比它更小的值就沒用了；β：對于對手來說最壞的值。在搜索算法中，如果某個(gè)節(jié)點(diǎn)的結(jié)果小于或等于α，那么它就可以拋棄；如果某個(gè)著法的結(jié)果大于或等于β，那么整個(gè)結(jié)點(diǎn)就作廢了，因?yàn)閷κ植幌Ｍ?/p>

3、到這個(gè)局面。如果某個(gè)節(jié)點(diǎn)值大于α但小于β，那么這個(gè)節(jié)點(diǎn)就是可以考慮走。這便是所謂的α-β剪枝搜索。1由α和β可以形成一個(gè)節(jié)點(diǎn)預(yù)選窗口。如何能夠快速得到一個(gè)盡可能小而又盡可能準(zhǔn)確的窗口？有不少窗口搜索算法被設(shè)計(jì)出來解決這個(gè)問題，如：AspirationSearch、PrincipalVariableSearch、ToleranceSearch等。目前大多數(shù)國際象棋與中國象棋的算法核心青睞速度快而不會(huì)出現(xiàn)錯(cuò)誤剪枝的PrincipalVariableSearch，它的原理是第一個(gè)分枝以完整窗口搜索，產(chǎn)生一個(gè)解v，后繼分枝則以一個(gè)極小窗口(v,v+1)搜索之，

4、旨在建立高效的、極小的搜索樹。本質(zhì)上，極小窗口搜索依賴于后繼節(jié)點(diǎn)的值對于前驅(qū)節(jié)點(diǎn)值微小變化的猜測。如果猜測被證明不準(zhǔn)確，就要以(v+1,β)為窗口重新進(jìn)行搜索。2、迭代深化搜索博弈樹的龐大是可以想象的。對于中國象棋，如果按照每一步平均有45種可行著法，每局棋平均走90步，那從開始局面展開到分出勝負(fù)，則要考慮的局面種數(shù)比地球上的原子數(shù)目還要多，無法完全計(jì)算，因此只能對有限層次展開分析。那么應(yīng)該搜索多少層為佳呢？如果設(shè)定一個(gè)搜索截止層數(shù)，則搜索的時(shí)間會(huì)隨局面上可行著法數(shù)量的變化產(chǎn)生顯著變化。一個(gè)更好的方案是限定搜索截止時(shí)間，讓程序在有限的時(shí)間內(nèi)盡可能深地搜

5、索。用偽代碼表示為：depth=0;while(time

6、估函數(shù)，返回值肯定對紅方有利，但會(huì)引發(fā)無用的兌子。因此有必要加入靜態(tài)局面搜索，將葉子節(jié)點(diǎn)繼續(xù)展開一直延伸到相對靜態(tài)（沒有吃子）的局面。2靜態(tài)搜索實(shí)現(xiàn)起來比較簡單，直接用靜態(tài)搜索函數(shù)替代葉子節(jié)點(diǎn)的評估函數(shù)即可。在實(shí)際應(yīng)用中多采用選擇性延伸，即只對有重要威脅的葉子節(jié)點(diǎn)（將軍、唯一著法、兌子等）進(jìn)行展開，忽略次要的非靜態(tài)葉子節(jié)點(diǎn)。4、循環(huán)檢測中國象棋規(guī)則中禁止連續(xù)三回合以上的循環(huán)著法，比如“長將”和“長不變”要判負(fù)或判和。如果僅使用普通的搜索和剪枝規(guī)則，電腦很可能會(huì)死守一個(gè)對其有利的局面不放，不斷地用循環(huán)的著法與對手周旋，最終被判負(fù)或判和。因此我們有必要在搜

7、索中記錄一個(gè)節(jié)點(diǎn)所有上級節(jié)點(diǎn)的情況，如果它與某個(gè)上級節(jié)點(diǎn)完全相同，則應(yīng)避免這個(gè)著法（但不可以就此剪枝，因?yàn)橛袝r(shí)不得不因?yàn)橹挥幸粭l路可走而走兩個(gè)回合的循環(huán)著法）。在具體實(shí)現(xiàn)時(shí)，不可能記錄一個(gè)節(jié)點(diǎn)（即局面）的全部信息，那樣既浪費(fèi)空間，又難以高效地查找和匹配。通常采用節(jié)點(diǎn)的哈希數(shù)進(jìn)行記錄和查找匹配。記錄的長度應(yīng)與搜索深度相同。綜合以上算法，我們實(shí)現(xiàn)了博弈樹搜索模塊。請參考源文件searcher.cpp。二、局面評估函數(shù)局面評估就是給棋局打分，識(shí)別棋局的好壞，以便在博弈樹搜索時(shí)作為路徑選擇條件尋找最佳著法。可行的辦法就是對局面進(jìn)行量化，通過數(shù)值評判棋局的好壞。

8、由于評估需要大量的象棋知識(shí)，仁者見仁，智者見智，評估函數(shù)的設(shè)計(jì)便成為計(jì)算機(jī)博弈中最為人性化的部