機(jī)器博弈搜索技術(shù)分析.pdf

《機(jī)器博弈搜索技術(shù)分析.pdf》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、學(xué)術(shù)研討機(jī)器博弈搜索技術(shù)分析王贈(zèng)凱,呂維先(中國(guó)地質(zhì)大學(xué)信息工程學(xué)院,湖北武漢430074)摘要:計(jì)算機(jī)博弈是人工智能領(lǐng)域最具挑戰(zhàn)性的研究方向之一,機(jī)器博弈的核心思想實(shí)際上就是博弈樹節(jié)點(diǎn)的估值過(guò)程和對(duì)博弈樹搜索過(guò)程的結(jié)合。分析了現(xiàn)今主流的幾種機(jī)器博弈搜索算法及其優(yōu)缺點(diǎn)。關(guān)鍵字:機(jī)器博弈;博弈樹;博弈搜索算法;alpha-beta搜索中圖分類號(hào):TP311文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1672-7800(2007)02-0026-02博弈研究的熱點(diǎn)。可以判斷節(jié)點(diǎn)C的值應(yīng)小于等于16(取1博弈樹極小值);而節(jié)點(diǎn)A的值為節(jié)點(diǎn)

2、Max(B,2基本搜索算法甲乙雙方進(jìn)行對(duì)弈,假定輪到甲走棋,C),為18,也就是說(shuō)不再需要估算節(jié)點(diǎn)C甲可以有若干種走法;對(duì)于甲的任一種走2.1極大極小值算法的其他子節(jié)點(diǎn)如E、F的值就可以得出父法,乙也可以有與之相對(duì)的若干種走法;命名兩個(gè)博弈者為MAX和MIN。目標(biāo)節(jié)點(diǎn)A的值了。這樣將節(jié)點(diǎn)D的后繼兄對(duì)乙的任一走法甲又有若干種與之對(duì)應(yīng)是為MAX尋找最佳走步。假設(shè)MAX先移弟節(jié)點(diǎn)減去的方法稱為alpha剪枝。的走法,如此往復(fù)。顯然,可以構(gòu)造一棵博動(dòng),然后兩個(gè)博弈者輪流移動(dòng)。深度為偶圖2右半部所示極大極小樹的片斷,弈樹(

3、圖1),將所有的走法羅列出來(lái)。博弈數(shù)的節(jié)點(diǎn)對(duì)應(yīng)于MAX下一步移動(dòng)的位節(jié)點(diǎn)B的估值為8,節(jié)點(diǎn)D的估值為18,樹的根節(jié)點(diǎn)是當(dāng)前時(shí)刻的棋局,它的兒子置,稱為MAX(取值大于0)節(jié)點(diǎn);深度為由此可以判斷節(jié)點(diǎn)C的值應(yīng)大于等于18節(jié)點(diǎn)是假設(shè)再行棋一步以后的各種棋局,奇數(shù)的節(jié)點(diǎn)對(duì)應(yīng)于MIN下一步移動(dòng)的位(取極大值);而節(jié)點(diǎn)A的值為節(jié)點(diǎn)Min孫子節(jié)點(diǎn)是從兒子節(jié)點(diǎn)的棋局再行棋一置,稱為MIN(取值小于0)節(jié)點(diǎn)。如果MAX(B,C),為8。也就是說(shuō)不再需要求節(jié)點(diǎn)C步的各種棋局,以此類推,直到可以分出在端節(jié)點(diǎn)之間進(jìn)行選擇,就會(huì)選擇具有

4、最的其他子節(jié)點(diǎn)如E、F的值就可以得出父勝負(fù)的棋局。整棵博弈樹體系非常龐大,大估值的節(jié)點(diǎn)。所以MIN端節(jié)點(diǎn)的父節(jié)節(jié)點(diǎn)A的值了。這樣將節(jié)點(diǎn)D的后繼兄且不同的棋類有所不同,分支因子大的如點(diǎn)(MAX節(jié)點(diǎn))所賦的倒推值等于端節(jié)點(diǎn)弟節(jié)點(diǎn)減去的方法稱為beta剪枝。圍棋的博弈樹顯然要比分支因子小的如估值中的最大值。另一方面,若MIN在端節(jié)國(guó)際象棋的博弈樹要大得多。點(diǎn)之間進(jìn)行選擇,那么會(huì)選擇具有最小估值的節(jié)點(diǎn)。所以,MAX端節(jié)點(diǎn)的父輩節(jié)點(diǎn)(MIN節(jié)點(diǎn))所賦的倒推值等于端節(jié)點(diǎn)估值中的最小值。在所有端節(jié)點(diǎn)的各個(gè)父輩節(jié)點(diǎn)都已賦好倒推值

5、之后,再向上倒推另一級(jí)的值,仍然假設(shè)MAX總是選擇具有最大倒推值的節(jié)點(diǎn),而MIN總是選擇具有圖2剪枝最小倒推值的節(jié)點(diǎn)。與極大極小值算法相比,alpha-beta圖1博弈樹示例2.2alpha-beta剪枝算法剪枝算法通常用較少的搜索就能找到最在極大極小搜索過(guò)程中,遍歷了整棵博弈程序的任務(wù)就是對(duì)博弈樹進(jìn)行佳節(jié)點(diǎn),但它對(duì)于節(jié)點(diǎn)的排列非常敏感。博弈樹,每個(gè)節(jié)點(diǎn)都訪問(wèn)了一次,這樣做搜索以找出當(dāng)前的最佳走步。在這個(gè)過(guò)程對(duì)于同一層上的節(jié)點(diǎn),如果節(jié)點(diǎn)的排列順的缺點(diǎn)是效率低下。與之相比,alpha-beta中,最為重要的是搜索算

6、法,高效的搜索序是從最差到最好,可以使實(shí)際搜索的博剪枝算法就高效得多。算法可以保證用盡量少的時(shí)間和空間損弈樹達(dá)到最小樹;否則,就可能要搜索整圖2左半部所示極大極小樹的片斷,耗來(lái)達(dá)到尋找高價(jià)值的走步,這正是機(jī)器棵的博弈樹。節(jié)點(diǎn)B的值為18,節(jié)點(diǎn)D的值為16,由此作者簡(jiǎn)介:王贈(zèng)凱(1980-),男,中國(guó)地質(zhì)大學(xué)信息工程學(xué)院碩士研究生,研究方向?yàn)槿斯ぶ悄?呂維先(1947-),中國(guó)地質(zhì)大學(xué)信息工程學(xué)院教授,研究方向?yàn)檐浖こ毯腿斯ぶ悄堋?6軟件導(dǎo)刊·2007·2月號(hào)學(xué)術(shù)研討intalphabetaTT(intdepth

7、,intalpha,intalphabeta(inti,intalpha,intbeta);3優(yōu)化的搜索算法beta)//分析第i層3.1渴望搜索{SaveBestAction();//保存最佳節(jié)點(diǎn)在alpha-beta剪枝過(guò)程中,初始的搜value=LookupTT(depth,index);i++;索窗口往往是從-∞(初始的alpha值)到+∞//查詢置換表}(初始的beta值),在搜索進(jìn)行中再不斷縮if(valueisvalid)DoBestAction();小窗口,加大剪枝效果。returnvalue;/

8、/采用最佳行動(dòng)渴望搜索就是渴望從一開始就使用Searchwithalphabeta...}小的窗口,從而在搜索初起,就可以進(jìn)行StoreToTT();//記錄到置換表中尤其在關(guān)鍵的開局和殘局階段,由于大量的剪枝。初始窗口的選定很重要,如果returnvalue;分支較少,迭代深化算法可以進(jìn)行較深層所要尋找的走步就在這個(gè)窗口內(nèi),搜索便}次的搜索?？梢岳^續(xù)進(jìn)行。如果第一步搜索