問題求解基本原理ppt課件

1、北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 1問題求解根本原理問題求解根本原理博博 弈：被以為高智能行為游戲弈：被以為高智能行為游戲; ; 不斷為不斷為AI研討提出新課題，推進(jìn)研討提出新課題，推進(jìn)AI研討的開展。研討的開展。搜搜 索索 技技 術(shù)術(shù) ( 三三 )博博 弈弈 搜搜 索索北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 2基于博弈搜索的搜索戰(zhàn)略基于博弈搜索的搜索戰(zhàn)略n 博弈問題及博弈樹概念博弈問題及博弈樹概念n 博弈搜索控制戰(zhàn)略博弈搜索控制戰(zhàn)略n 博弈搜索算法及其運(yùn)用實(shí)例博弈搜索算法

2、及其運(yùn)用實(shí)例n 博弈樹的博弈樹的 - - 剪枝剪枝 北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 3博弈問題及博弈樹概念博弈問題及博弈樹概念n 博弈問題：博弈問題：n對(duì)抗的雙方參與博弈，取勝的要素不僅取決對(duì)抗的雙方參與博弈，取勝的要素不僅取決于一方的如意算盤，還需充分思索對(duì)方的應(yīng)于一方的如意算盤，還需充分思索對(duì)方的應(yīng)付戰(zhàn)略，一字棋、國(guó)際象棋、打撲克、中付戰(zhàn)略，一字棋、國(guó)際象棋、打撲克、中國(guó)象棋、圍棋。國(guó)象棋、圍棋。 雙人完備信息：雙人完備信息：對(duì)壘的雙方輪番走步，對(duì)弈的條件和走步規(guī)那對(duì)壘的雙方輪番走步，對(duì)弈的條件和走步規(guī)那么完全一樣。每一方不

3、僅知道對(duì)方已走過的一么完全一樣。每一方不僅知道對(duì)方已走過的一切棋步，而且還能估計(jì)出對(duì)方未來能夠走的棋切棋步，而且還能估計(jì)出對(duì)方未來能夠走的棋步。步。北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 4博弈問題及博弈樹概念博弈問題及博弈樹概念n 博弈問題描畫：n 棋局描畫；n 棋局走步規(guī)那么。 博弈搜索過程：博弈搜索過程： 搜索棋局走步規(guī)那么，隱含生成一棵特搜索棋局走步規(guī)那么，隱含生成一棵特殊的與或樹殊的與或樹博弈問題求解：博弈問題求解：北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 5博弈問題及博

4、弈樹概念博弈問題及博弈樹概念與或節(jié)點(diǎn)分層交替出現(xiàn)的與或樹與或節(jié)點(diǎn)分層交替出現(xiàn)的與或樹從甲的立場(chǎng)出發(fā)從甲的立場(chǎng)出發(fā)或節(jié)點(diǎn)或節(jié)點(diǎn)與節(jié)點(diǎn)與節(jié)點(diǎn)或節(jié)點(diǎn)或節(jié)點(diǎn)完全取勝解完全取勝解 圖圖甲走步甲走步北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 6博弈問題及博弈樹概念博弈問題及博弈樹概念n判別走步的極小判別走步的極小- -極大原那么：極大原那么：v 思索對(duì)方走步時(shí)與節(jié)點(diǎn)：假定對(duì)手不會(huì)犯錯(cuò)誤，他總是選擇對(duì)本人最有利，對(duì)我方最不利的棋步走。因此，我方不能采取任何冒險(xiǎn)行動(dòng),視對(duì)手將走出的棋局為極小值；v思索我方走步時(shí)或節(jié)點(diǎn)：應(yīng)在對(duì)方呵斥的思索我方走步時(shí)或節(jié)點(diǎn)：應(yīng)

5、在對(duì)方呵斥的最壞的局勢(shì)中盡能夠地選擇最好的棋著走，視本人最壞的局勢(shì)中盡能夠地選擇最好的棋著走，視本人能夠走出的棋局為極大值。能夠走出的棋局為極大值。北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 7基于博弈搜索的搜索戰(zhàn)略基于博弈搜索的搜索戰(zhàn)略n 博弈問題及博弈樹博弈問題及博弈樹n 博弈搜索控制戰(zhàn)略博弈搜索控制戰(zhàn)略n 博弈搜索算法及其運(yùn)用實(shí)例博弈搜索算法及其運(yùn)用實(shí)例n 博弈樹的博弈樹的 - - 剪枝剪枝 w 完好的博弈搜索戰(zhàn)略盲目搜索戰(zhàn)略完好的博弈搜索戰(zhàn)略盲目搜索戰(zhàn)略w 有界深度博弈搜索戰(zhàn)略有界深度博弈搜索戰(zhàn)略北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)

6、實(shí)驗(yàn)室北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 8完好的博弈搜索戰(zhàn)略完好的博弈搜索戰(zhàn)略n中心思想：中心思想：n從博弈的初始格局開場(chǎng)，輪番思索本人與對(duì)從博弈的初始格局開場(chǎng)，輪番思索本人與對(duì)方能夠的一切走步，生成出棋局的各個(gè)格局方能夠的一切走步，生成出棋局的各個(gè)格局，直到到達(dá)分出勝負(fù)勝負(fù)的終止格局為止，直到到達(dá)分出勝負(fù)勝負(fù)的終止格局為止，此搜索過程產(chǎn)生的一棵完好的博弈樹。此搜索過程產(chǎn)生的一棵完好的博弈樹。北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 9完好的博弈搜索戰(zhàn)略完好的博弈搜索戰(zhàn)略n博弈問題實(shí)例：博弈問題實(shí)例：n有一堆數(shù)目為有

7、一堆數(shù)目為N N的錢幣，甲、乙二人輪番分堆。要求每人每次的錢幣，甲、乙二人輪番分堆。要求每人每次挑選其中某一堆錢幣，將其分成數(shù)目不等的兩小堆。分堆過挑選其中某一堆錢幣，將其分成數(shù)目不等的兩小堆。分堆過程繼續(xù)，直至其中一人無法再將任一堆錢幣分成數(shù)目不等的程繼續(xù)，直至其中一人無法再將任一堆錢幣分成數(shù)目不等的兩堆時(shí)，那么認(rèn)輸。兩堆時(shí)，那么認(rèn)輸。 博弈問題描畫：博弈問題描畫： 分堆格局分堆格局( (形狀形狀): (x1,x2,xn,M), ): (x1,x2,xn,M), 其中，其中， xi: xi: 第第 i i 堆錢幣的個(gè)數(shù)；堆錢幣的個(gè)數(shù)； M: M: 當(dāng)前走步人編號(hào)當(dāng)前走步人編號(hào) - -MAX,

8、 MINMAX, MIN 走步規(guī)那么：走步規(guī)那么： IF (x1,x2,xn,M) (xi = Y+Z) (Y IF (x1,x2,xn,M) (xi = Y+Z) (Y Z)Z) THEN (x1,x2,xi-1, Y, Z, xi+1, , xn, THEN (x1,x2,xi-1, Y, Z, xi+1, , xn, M)M)北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 10完好的博弈搜索戰(zhàn)略完好的博弈搜索戰(zhàn)略站在站在MAX立場(chǎng)立場(chǎng)與節(jié)點(diǎn)與節(jié)點(diǎn)或節(jié)點(diǎn)或節(jié)點(diǎn)與節(jié)點(diǎn)與節(jié)點(diǎn)完全取勝的完完全取勝的完備戰(zhàn)略備戰(zhàn)略北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重

9、點(diǎn)實(shí)驗(yàn)室北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 11n特點(diǎn)：特點(diǎn)：n 搜索戰(zhàn)略簡(jiǎn)單，易于控制，可用于簡(jiǎn)單的博弈或一搜索戰(zhàn)略簡(jiǎn)單，易于控制，可用于簡(jiǎn)單的博弈或一個(gè)復(fù)雜博弈的殘局；個(gè)復(fù)雜博弈的殘局；完好的博弈搜索戰(zhàn)略完好的博弈搜索戰(zhàn)略w不適宜復(fù)雜的博弈問題搜索不適宜復(fù)雜的博弈問題搜索 - 指數(shù)爆炸。指數(shù)爆炸。w 例，中國(guó)象棋：例，中國(guó)象棋：w 設(shè)每種格局有設(shè)每種格局有40種走法，一盤棋雙方平均走種走法，一盤棋雙方平均走50步，步，w 完好的博弈搜索完好的博弈搜索-w 搜索節(jié)點(diǎn)數(shù)搜索節(jié)點(diǎn)數(shù)40250 10160，搜索深度達(dá)，搜索深度達(dá)100層。層。 有必要引入有界深度博弈搜索戰(zhàn)略。北

10、京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 12基于博弈搜索的搜索戰(zhàn)略基于博弈搜索的搜索戰(zhàn)略n 博弈問題及博弈樹博弈問題及博弈樹n 博弈搜索控制戰(zhàn)略博弈搜索控制戰(zhàn)略w 完好的博弈搜索戰(zhàn)略盲目搜索戰(zhàn)略w 有界深度博弈搜索戰(zhàn)略啟發(fā)式搜索戰(zhàn)略北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 13有界深度搜索戰(zhàn)略有界深度搜索戰(zhàn)略n 中心思想：中心思想：n根據(jù)對(duì)方已走出的棋步，構(gòu)造出具有一定深度根據(jù)對(duì)方已走出的棋步，構(gòu)造出具有一定深度的博弈樹，并從此部分博弈樹中選擇相對(duì)好的的博弈樹，并從此部分博弈樹中選擇

11、相對(duì)好的棋著走。棋著走。 需處理的關(guān)鍵問題：需處理的關(guān)鍵問題：定義估計(jì)終結(jié)棋局優(yōu)劣的評(píng)價(jià)函數(shù)；定義估計(jì)終結(jié)棋局優(yōu)劣的評(píng)價(jià)函數(shù)；給出棋局優(yōu)劣性傳送的計(jì)算方法。給出棋局優(yōu)劣性傳送的計(jì)算方法。北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 14定義棋局的評(píng)價(jià)函數(shù)定義棋局的評(píng)價(jià)函數(shù)設(shè)設(shè) P P 為有界博弈樹中棋局；為有界博弈樹中棋局；(P): (P): 棋局優(yōu)劣的評(píng)價(jià)函數(shù)。棋局優(yōu)劣的評(píng)價(jià)函數(shù)。 例例1 1：從當(dāng)前棋局到離我方最后取勝的差距：從當(dāng)前棋局到離我方最后取勝的差距： 勝利在望勝利在望 (P)(P)值較大，敗局顯露值較大，敗局顯露 (P)(P)值

12、較??；值較小； 例例2 2：從當(dāng)前棋局到到某個(gè)明顯有利于我方棋局的差距：從當(dāng)前棋局到到某個(gè)明顯有利于我方棋局的差距： 吃掉對(duì)方一子吃掉對(duì)方一子, , 或者或者 “叫吃。叫吃。v (P)MAX(P)MAX贏贏 = = (P)MIN(P)MIN輸輸 = + = + v (P)MAX(P)MAX輸輸 = = (P)MIN(P)MIN贏贏 = - = - v (P)(P)平平 = 0 = 0v (P) (P) 任一終葉棋局優(yōu)劣的評(píng)價(jià)函數(shù)的定義原那么任一終葉棋局優(yōu)劣的評(píng)價(jià)函數(shù)的定義原那么：北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 15計(jì)算棋局的評(píng)價(jià)

13、函數(shù)計(jì)算棋局的評(píng)價(jià)函數(shù)有界博弈樹中任一棋局節(jié)點(diǎn)評(píng)價(jià)函數(shù)值的計(jì)算：有界博弈樹中任一棋局節(jié)點(diǎn)評(píng)價(jià)函數(shù)值的計(jì)算：w 對(duì)于終葉節(jié)點(diǎn)：賦靜態(tài)評(píng)價(jià)函數(shù)值對(duì)于終葉節(jié)點(diǎn)：賦靜態(tài)評(píng)價(jià)函數(shù)值(P);(P);w 對(duì)于非終葉節(jié)點(diǎn)：按極小對(duì)于非終葉節(jié)點(diǎn)：按極小- -極大走步原那么，采極大走步原那么，采用倒推的方法，自下而上地由子節(jié)點(diǎn)計(jì)算父節(jié)點(diǎn)的用倒推的方法，自下而上地由子節(jié)點(diǎn)計(jì)算父節(jié)點(diǎn)的動(dòng)態(tài)評(píng)價(jià)函數(shù)值動(dòng)態(tài)評(píng)價(jià)函數(shù)值(P)(P)。北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 16站在站在MAX立場(chǎng)立場(chǎng)基于極小基于極小- -極大原那么的評(píng)價(jià)函數(shù)計(jì)算實(shí)例極大原那么的評(píng)價(jià)函數(shù)

14、計(jì)算實(shí)例靜態(tài)啟發(fā)式靜態(tài)啟發(fā)式評(píng)價(jià)函數(shù)值評(píng)價(jià)函數(shù)值動(dòng)態(tài)評(píng)價(jià)函動(dòng)態(tài)評(píng)價(jià)函數(shù)值數(shù)值北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 17基于博弈搜索的搜索戰(zhàn)略基于博弈搜索的搜索戰(zhàn)略n 博弈問題及博弈樹博弈問題及博弈樹n 博弈搜索控制戰(zhàn)略博弈搜索控制戰(zhàn)略n 有界深度搜索算法及其運(yùn)用實(shí)例有界深度搜索算法及其運(yùn)用實(shí)例n 博弈樹的博弈樹的 - - 剪枝剪枝北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 18有界深度搜索算法及其運(yùn)用實(shí)例有界深度搜索算法及其運(yùn)用實(shí)例 針對(duì)當(dāng)前對(duì)方給出的棋局針對(duì)當(dāng)前對(duì)方給出的棋局 s

15、 ： 1、按寬度優(yōu)先法自上而下地生成規(guī)定深度的博弈樹；、按寬度優(yōu)先法自上而下地生成規(guī)定深度的博弈樹； 2、為有界深度博弈樹的一切葉節(jié)點(diǎn)賦靜態(tài)評(píng)價(jià)函數(shù)估計(jì)值、為有界深度博弈樹的一切葉節(jié)點(diǎn)賦靜態(tài)評(píng)價(jià)函數(shù)估計(jì)值 3、根據(jù)極小、根據(jù)極小-極大走步原那么自下而上地逐級(jí)計(jì)算各非終葉極大走步原那么自下而上地逐級(jí)計(jì)算各非終葉節(jié)點(diǎn)的動(dòng)態(tài)評(píng)價(jià)函數(shù)估計(jì)值，直至求到起始節(jié)點(diǎn)的評(píng)價(jià)函數(shù)值節(jié)點(diǎn)的動(dòng)態(tài)評(píng)價(jià)函數(shù)估計(jì)值，直至求到起始節(jié)點(diǎn)的評(píng)價(jià)函數(shù)值 (s)為止。為止。 比較我方可走的各棋局的評(píng)價(jià)函數(shù)估計(jì)值，從中選擇最好的比較我方可走的各棋局的評(píng)價(jià)函數(shù)估計(jì)值，從中選擇最好的棋步走。棋步走。 再根據(jù)對(duì)方走出的棋局再根據(jù)對(duì)方走出的棋

16、局 s，反復(fù)上述過程。，反復(fù)上述過程。北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 19有界深度搜索算法及其運(yùn)用實(shí)例有界深度搜索算法及其運(yùn)用實(shí)例一字棋站在一字棋站在MAXMAX的立場(chǎng)的立場(chǎng) 定義特殊棋局估計(jì)函數(shù)定義特殊棋局估計(jì)函數(shù)h1(P)h1(P) h1(P)MAX h1(P)MAX贏贏 = + = + h1(P)MAX h1(P)MAX輸輸 = - = - h1(P) h1(P)平平 = = h1(P)MAX贏 = +h1(P)MAX輸 = -h1(P)平 = 北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)

17、實(shí)驗(yàn)室 Slide 20有界深度搜索算法及其運(yùn)用實(shí)例有界深度搜索算法及其運(yùn)用實(shí)例n一字棋站在一字棋站在MAXMAX的立場(chǎng)的立場(chǎng)n定義棋局評(píng)價(jià)函數(shù)：定義棋局評(píng)價(jià)函數(shù)：n將整行、整列或整條對(duì)角線稱為將整行、整列或整條對(duì)角線稱為贏線。假設(shè)一條贏線上只需贏線。假設(shè)一條贏線上只需方的棋子或?yàn)榭?，而沒有方的棋子或?yàn)榭眨鴽]有方的棋子，那么稱此方的棋子，那么稱此贏線稱為方的贏線贏線稱為方的贏線。 n設(shè)方恣意棋局的靜態(tài)評(píng)價(jià)設(shè)方恣意棋局的靜態(tài)評(píng)價(jià)函數(shù)函數(shù) h1(P) h1(P) ：n(P) = (P) = 的贏線數(shù)的贏線數(shù)的贏線數(shù)的贏線數(shù)h(p)MAX = 6 4 = 2h(p)M = 4 6 = - 2北京航

18、空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 21v MAX走棋第一步走棋第一步( 深度為深度為2 )：MAXMAX走步走步有界深度搜索算法及其運(yùn)用實(shí)例有界深度搜索算法及其運(yùn)用實(shí)例北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 22有界深度搜索算法及其運(yùn)用實(shí)例有界深度搜索算法及其運(yùn)用實(shí)例v MAX走棋第二步走棋第二步：v MAX走棋第三步走棋第三步：MAX走步走步MAX走步走步北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 23基于博弈搜索的搜索戰(zhàn)略

19、基于博弈搜索的搜索戰(zhàn)略問題：?jiǎn)栴}： 啟發(fā)式博弈搜索戰(zhàn)略啟發(fā)式博弈搜索戰(zhàn)略 - - 將擴(kuò)展生成博弈樹的過將擴(kuò)展生成博弈樹的過程與計(jì)算、評(píng)價(jià)及確定最優(yōu)走步的過程完全分開進(jìn)展程與計(jì)算、評(píng)價(jià)及確定最優(yōu)走步的過程完全分開進(jìn)展，導(dǎo)致了搜索效率的低下。，導(dǎo)致了搜索效率的低下。對(duì)策：對(duì)策： - 剪枝技術(shù)剪枝技術(shù) - 在生成博弈樹同時(shí)計(jì)算和評(píng)價(jià)棋局節(jié)點(diǎn)，對(duì)在生成博弈樹同時(shí)計(jì)算和評(píng)價(jià)棋局節(jié)點(diǎn)，對(duì)不用要展開的節(jié)點(diǎn)進(jìn)展剪枝，可減少許多不用要節(jié)點(diǎn)的生成和不用要展開的節(jié)點(diǎn)進(jìn)展剪枝，可減少許多不用要節(jié)點(diǎn)的生成和計(jì)算任務(wù)量，提高搜索效率。計(jì)算任務(wù)量，提高搜索效率。北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室北京航空航天大學(xué)軟件

20、開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 24基于博弈搜索的搜索戰(zhàn)略基于博弈搜索的搜索戰(zhàn)略n 博弈問題及博弈樹博弈問題及博弈樹n 博弈搜索控制戰(zhàn)略博弈搜索控制戰(zhàn)略n 有界深度搜索算法及其運(yùn)用實(shí)例有界深度搜索算法及其運(yùn)用實(shí)例n 博弈樹的博弈樹的 - - 剪枝剪枝北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 25博弈樹的博弈樹的 - - 剪枝剪枝h(3) 17h(3) 25北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 26nn1n1博弈樹的博弈樹的 - - 剪枝剪枝n 值：值：n 設(shè)博弈樹中某節(jié)點(diǎn)設(shè)博

21、弈樹中某節(jié)點(diǎn) n n 屬屬于極大層。它左邊第一個(gè)于極大層。它左邊第一個(gè)子節(jié)點(diǎn)子節(jié)點(diǎn) n1 n1的評(píng)價(jià)函數(shù)值的評(píng)價(jià)函數(shù)值 h(n1)h(n1)可視為節(jié)點(diǎn)可視為節(jié)點(diǎn) n n 的下的下界值，或稱為界值，或稱為 值，節(jié)值，節(jié)點(diǎn)點(diǎn) n n 的評(píng)價(jià)函數(shù)值的評(píng)價(jià)函數(shù)值 h(n) h(n)決不會(huì)小于此決不會(huì)小于此 值。值。n n 的的值值北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 27nn1n1博弈樹的博弈樹的 - - 剪枝剪枝 值：值： 設(shè)博弈樹中某節(jié)點(diǎn)設(shè)博弈樹中某節(jié)點(diǎn) n n 屬于極小層。它左屬于極小層。它左邊第一個(gè)子節(jié)點(diǎn)邊第一個(gè)子節(jié)點(diǎn) n1 n1的的

22、評(píng)價(jià)函數(shù)值評(píng)價(jià)函數(shù)值 h(n1) h(n1)可視可視為節(jié)點(diǎn)為節(jié)點(diǎn) n n 的上界值，的上界值，或稱為或稱為 值，節(jié)點(diǎn)值，節(jié)點(diǎn) n n 的的 h(n) h(n)決不會(huì)大于此決不會(huì)大于此 值。值。 n n 的的值值北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 28m博弈樹的博弈樹的 - - 剪枝剪枝n 剪枝：剪枝：n 假設(shè)任一極小層假設(shè)任一極小層節(jié)點(diǎn)節(jié)點(diǎn) m m 的的 值值小于或等于其位于小于或等于其位于極大層的父節(jié)點(diǎn)的極大層的父節(jié)點(diǎn)的 值，即值，即 ，那么可終止該，那么可終止該極小層中節(jié)點(diǎn)極小層中節(jié)點(diǎn) m m 以下的搜索過程。以下的搜索過程。 值值 值值北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 29m博弈樹的博弈樹的 - - 剪枝剪枝 值值 值值 剪枝：剪枝： 假設(shè)任一極大層節(jié)點(diǎn)假設(shè)任一極大層節(jié)點(diǎn) m m 的的 值大于或等于其值大于或等于其位于極小層的父節(jié)點(diǎn)的位于極小層的父節(jié)點(diǎn)的 值，即值，即 ，那么，那么可終止該極大層中節(jié)點(diǎn)可終止該極大層