第二章與或圖搜索問題目標(biāo)目標(biāo)初始節(jié)點(diǎn)sabc1第二章與或圖搜索問題目標(biāo)目標(biāo)初始節(jié)點(diǎn)sabc12.1基本概念與或圖是一個(gè)超圖，節(jié)點(diǎn)間通過連接符連接。K-連接符：…...K個(gè)22.1基本概念與或圖是一個(gè)超圖，節(jié)點(diǎn)間通過連接符連接?！?耗散值的計(jì)算k(n,N)=Cn+k(n1,N)+…+k(ni,N)其中：N為終節(jié)點(diǎn)集

Cn為連接符的耗散值…...i個(gè)nn1n2ni3耗散值的計(jì)算…...i個(gè)nn1n2ni3目標(biāo)目標(biāo)初始節(jié)點(diǎn)解圖：4目標(biāo)目標(biāo)初始節(jié)點(diǎn)解圖：4能解節(jié)點(diǎn)終節(jié)點(diǎn)是能解節(jié)點(diǎn)若非終節(jié)點(diǎn)有“或”子節(jié)點(diǎn)時(shí)，當(dāng)且僅當(dāng)其子節(jié)點(diǎn)至少有一能解時(shí)，該非終節(jié)點(diǎn)才能解。若非終節(jié)點(diǎn)有“與”子節(jié)點(diǎn)時(shí)，當(dāng)且僅當(dāng)其子節(jié)點(diǎn)均能解時(shí)，該非終節(jié)點(diǎn)才能解。5能解節(jié)點(diǎn)終節(jié)點(diǎn)是能解節(jié)點(diǎn)5不能解節(jié)點(diǎn)沒有后裔的非終節(jié)點(diǎn)是不能解節(jié)點(diǎn)。若非終節(jié)點(diǎn)有“或”子節(jié)點(diǎn)，當(dāng)且僅當(dāng)所有子節(jié)點(diǎn)均不能解時(shí)，該非終節(jié)點(diǎn)才不能解。若非終節(jié)點(diǎn)有“與”子節(jié)點(diǎn)時(shí)，當(dāng)至少有一個(gè)子節(jié)點(diǎn)不能解時(shí)，該非終節(jié)點(diǎn)才不能解。6不能解節(jié)點(diǎn)沒有后裔的非終節(jié)點(diǎn)是不能解節(jié)點(diǎn)。6普通圖搜索的情況 f(n)=g(n)+h(n) 對(duì)n的評(píng)價(jià)實(shí)際是對(duì)從s到n這條路徑的評(píng)價(jià)ns7普通圖搜索的情況 f(n)=g(n)+h(n)ns7與或圖:對(duì)局部圖的評(píng)價(jià)目標(biāo)目標(biāo)初始節(jié)點(diǎn)abc8與或圖:對(duì)局部圖的評(píng)價(jià)目標(biāo)目標(biāo)初始節(jié)點(diǎn)abc8兩個(gè)過程圖生成過程，即擴(kuò)展節(jié)點(diǎn)從最優(yōu)的局部途中選擇一個(gè)節(jié)點(diǎn)擴(kuò)展計(jì)算耗散值的過程對(duì)當(dāng)前的局部圖從新計(jì)算耗散值9兩個(gè)過程圖生成過程，即擴(kuò)展節(jié)點(diǎn)9AO*算法舉例其中：h(n0)=3h(n1)=2h(n2)=4h(n3)=4h(n4)=1h(n5)=1h(n6)=2h(n7)=0h(n8)=0設(shè)：K連接符的耗散值為K目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5n6n7n810AO*算法舉例其中：目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5n6n7n8初始節(jié)點(diǎn)n0n1(2)n4(1)n5(1)紅色：4黃色：311目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5n6n7n8初始節(jié)點(diǎn)初始節(jié)點(diǎn)n0n4(1)n5(1)紅色：4黃色：6n1n2(4)n3(4)5目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5n6n7n812初始節(jié)點(diǎn)n0n4(1)n5(1)紅色：4n1n2(4)n3(紅色：5黃色：6初始節(jié)點(diǎn)n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)2目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5n6n7n813紅色：5初始節(jié)點(diǎn)n0n4(1)n5(1)n1n2(4)n3(紅色：5黃色：621初始節(jié)點(diǎn)n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5n6n7n814紅色：521初始節(jié)點(diǎn)n0n4(1)n5(1)n1n2(4)n博弈是一類具有競(jìng)爭(zhēng)性的智能活動(dòng)雙人博弈：即兩位選手對(duì)壘，輪流依次走步，其中任何一方都完全知道對(duì)方過去已經(jīng)走過的棋步和今后可能的走步，其結(jié)果是一方贏(而另一方則輸)，或雙方和局2.3博弈樹搜索15博弈是一類具有競(jìng)爭(zhēng)性的智能活動(dòng)2.3博弈樹搜索15博弈的例子：一字棋跳棋中國(guó)象棋圍棋五子棋16博弈的例子：162.3博弈樹搜索博弈問題雙人對(duì)弈，對(duì)壘的雙方輪流走步；信息完備，對(duì)壘雙方所得到的信息是一樣的，不存在一方能看到，而另外一方看不到的情況；零和，即對(duì)一方有利的棋，對(duì)另一方肯定是不利的，不存在對(duì)雙方均有利或均無利的棋，對(duì)弈的結(jié)果是一方贏，而另一方輸，或者雙方和棋。172.3博弈樹搜索博弈問題17雙方的智能活動(dòng)，任何一方都不能單獨(dú)控制博弈過程，而是由雙方輪流實(shí)施其控制對(duì)策的過程。博弈的特點(diǎn)：18雙方的智能活動(dòng)，任何一方都不能單獨(dú)控制博弈過程，而是由雙方輪如何根據(jù)當(dāng)前的棋局，選擇對(duì)自己最有利的一步棋？人工智能中研究的博弈問題：中國(guó)象棋19如何根據(jù)當(dāng)前的棋局，選擇對(duì)自己最有利的一步棋？人工智能中研用博弈樹來表示，它是一種特殊的與或樹。節(jié)點(diǎn)代表博弈的格局（即棋局），相當(dāng)于狀態(tài)空間中的狀態(tài)，反映了博弈的信息，并且與節(jié)點(diǎn)、或節(jié)點(diǎn)隔層交替出現(xiàn)。博弈問題（求解過程）的表示：20用博弈樹來表示，它是一種特殊的與或樹。節(jié)點(diǎn)代表博弈的格局（即假設(shè)博弈雙方為：MAX和MIN在博弈過程中，規(guī)則是雙方輪流走步。在博弈樹中，相當(dāng)于博弈雙方輪流擴(kuò)展其所屬節(jié)點(diǎn)。為什么與節(jié)點(diǎn)、或節(jié)點(diǎn)隔層交替出現(xiàn)？21假設(shè)博弈雙方為：MAX和MIN為什么與節(jié)點(diǎn)、或節(jié)點(diǎn)隔層交替出從MAX方的角度來看：所有MIN方節(jié)點(diǎn)都是與節(jié)點(diǎn)理由：因?yàn)镸IN方必定選擇最不利于MAX方的方式來擴(kuò)展節(jié)點(diǎn)，只要MIN方節(jié)點(diǎn)的子節(jié)點(diǎn)（下出棋局）中有一個(gè)對(duì)MAX方不利，則該節(jié)點(diǎn)就對(duì)MAX方不利，故為“與節(jié)點(diǎn)”。MIN好招22從MAX方的角度來看：MIN好招22從MAX方的角度來看：

所有屬于MAX方的節(jié)點(diǎn)都是或節(jié)點(diǎn)理由：因?yàn)閿U(kuò)展MAX方節(jié)點(diǎn)時(shí)，MAX方可選擇擴(kuò)展最有利于自己的節(jié)點(diǎn)，只要可擴(kuò)展的子節(jié)點(diǎn)中有一個(gè)對(duì)已有利，

則該節(jié)點(diǎn)就對(duì)已有利。MAX好招23從MAX方的角度來看：MAX好招23總之：從MAX方來說，與節(jié)點(diǎn)、或節(jié)點(diǎn)交替出現(xiàn)；反之，從MIN方的角度來看，情況正好相反。24總之：24在博弈樹中，先行一方的初始狀態(tài)對(duì)應(yīng)著樹的根節(jié)點(diǎn)，而任何一方獲勝的最終格局為目標(biāo)狀態(tài)，對(duì)應(yīng)于樹的終葉節(jié)點(diǎn)（可解節(jié)點(diǎn)或本原問題）。但是，從MAX的角度出發(fā)，所有使MAX獲勝的狀態(tài)格局都是本原問題，是可解節(jié)點(diǎn)，而使MIN獲勝的狀態(tài)格局是不可解節(jié)點(diǎn)。25在博弈樹中，先行一方的初始狀態(tài)對(duì)應(yīng)著樹的根節(jié)點(diǎn)，而任何一方獲博弈樹特點(diǎn)(1)博弈的初始狀態(tài)是初始節(jié)點(diǎn)；(2)博弈樹的“與”節(jié)點(diǎn)和“或”節(jié)點(diǎn)是逐層交替出現(xiàn)的；(3)整個(gè)博弈過程始終站在某一方的立場(chǎng)上，所以能使自己一方獲勝的終局都是本原問題，相應(yīng)的節(jié)點(diǎn)也是可解節(jié)點(diǎn)，所有使對(duì)方獲勝的節(jié)點(diǎn)都是不可解節(jié)點(diǎn)。26博弈樹特點(diǎn)(1)博弈的初始狀態(tài)是初始節(jié)點(diǎn)；26例

Grundy博弈：分配物品的問題如果有一堆數(shù)目為N的錢幣，由兩位選手輪流進(jìn)行分配，要求每個(gè)選手每次把其中某一堆分成數(shù)目不等的兩小堆，直至有一選手不能將錢幣分成不等的兩堆為止，則判定這位選手為輸家。27例Grundy博弈：分配物品的問題27用數(shù)字序列加上一個(gè)說明來表示一個(gè)狀態(tài)：(3,2,1,1,MAX)數(shù)字序列：表示不同堆中錢幣的個(gè)數(shù)說明：表示下一步由誰來分，即取MAX或MIN28用數(shù)字序列加上一個(gè)說明來表示一個(gè)狀態(tài)：28現(xiàn)在取N＝7的簡(jiǎn)單情況，并由MIN先分

注：如果MAX走紅箭頭的分法，必定獲勝。所有可能的分法(7,MIN)(6,1,MAX)(5,2,MAX)(4,3,MAX)(5,1,1,MIN)(4,2,1,MIN)(3,2,2,MIN)(3,3,1,MIN)(4,1,1,1,MAX)(3,2,1,1,MAX)(2,2,2,1,MAX)(2,2,1,1,1,MIN)(3,1,1,1,1,MIN)(2,1,1,1,1,1,MAX)29現(xiàn)在取N＝7的簡(jiǎn)單情況，并由MIN先分注：如果MAX走分錢幣問題（7）（6,1）（5,2）（4,3）（5,1,1）（4,2,1）（3,2,2）（3,3,1）（4,1,1,1）（3,2,1,1）（2,2,2,1）（3,1,1,1,1）（2,2,1,1,1）（2,1,1,1,1,1）對(duì)方先走我方必勝30分錢幣問題（7）（6,1）（5,2）（4,3）（5,1,1）對(duì)于比較復(fù)雜的博弈問題，只能模擬人的思維“向前看幾步”，然后作出決策，選擇最有利自己的一步。即只能給出幾層走法，然后按照一定的估算辦法，決定走一好招。31對(duì)于比較復(fù)雜的博弈問題，只能模擬人的思維“向前看幾步”，然后中國(guó)象棋一盤棋平均走50步，總狀態(tài)數(shù)約為10的161次方。假設(shè)1毫微秒走一步，約需10的145次方年。結(jié)論：不可能窮舉。32中國(guó)象棋一盤棋平均走50步，總狀態(tài)數(shù)約為10的161次方。3在人工智能中可以采用搜索方法來求解博弈問題，下面就來討論博弈中兩中最基本的搜索方法。

33在人工智能中可以采用搜索方法來求解博弈問題，下面就來討論博弈對(duì)于復(fù)雜的博弈問題，要規(guī)定搜索深度與時(shí)間，以便于博弈搜索能順利進(jìn)行。假設(shè)由MAX來選擇走一步棋，問題是：MAX如何來選擇一步好棋？

極大極小過程34對(duì)于復(fù)雜的博弈問題，要規(guī)定搜索深度與時(shí)間，以便于博弈搜索能順極大極小過程

極大極小過程是考慮雙方對(duì)弈若干步之后，從可能的走法中選一步相對(duì)好的走法來走，即在有限的搜索深度范圍內(nèi)進(jìn)行求解。需要定義一個(gè)靜態(tài)估價(jià)函數(shù)e,以便對(duì)棋局的態(tài)勢(shì)做出評(píng)估。35極大極小過程極大極小過程是考慮雙方對(duì)弈若干步之后，從可能的①

對(duì)于每一格局（棋局）給出（定義或者倒推）一個(gè)靜態(tài)估價(jià)函數(shù)值。值越大對(duì)MAX越有利，反之越不利；極大極小過程的基本思路：36①對(duì)于每一格局（棋局）給出（定義或者倒推）一個(gè)靜態(tài)估價(jià)函數(shù)②

對(duì)于給定的格局，MAX給出可能的走法，然后MIN對(duì)應(yīng)地給出相應(yīng)的走法，這樣重復(fù)若干次，得到一組端節(jié)點(diǎn)（必須由MIN走后得到的，等待MAX下的棋局）。這一過程相當(dāng)于節(jié)點(diǎn)擴(kuò)展；注：博弈樹深度或?qū)訑?shù)一定是偶數(shù)。37②對(duì)于給定的格局，MAX給出可能的走法，然后MIN對(duì)應(yīng)地給③對(duì)于每一個(gè)端節(jié)點(diǎn)，計(jì)算出它們的靜態(tài)估價(jià)函數(shù)，然后自下而上地逐層計(jì)算倒推值，直到MAX開始的格局。在MIN下的格局中取估值的最小值，在MAX下格局中取估值的最大值；④取估值最大的格局作為MAX要走的一招棋。38③對(duì)于每一個(gè)端節(jié)點(diǎn)，計(jì)算出它們的靜態(tài)估價(jià)函數(shù)，然后自下而上例：向前看一步的兩層博弈樹

39例：向前看一步的兩層博弈樹39定義靜態(tài)函數(shù)e(P)的一般原則：40定義靜態(tài)函數(shù)e(P)的一般原則：40OPEN：存放待擴(kuò)展的節(jié)點(diǎn)，此時(shí)為隊(duì)列，即以寬度優(yōu)先的策略擴(kuò)展節(jié)點(diǎn)。CLOSED：存放已擴(kuò)展的節(jié)點(diǎn)，此時(shí)為堆棧，即后擴(kuò)展的節(jié)點(diǎn)先計(jì)算。

符號(hào)：41OPEN：存放待擴(kuò)展的節(jié)點(diǎn)，此時(shí)為隊(duì)列，即以寬度優(yōu)先的策略擴(kuò)極大極小過程的基本思想：(1)當(dāng)輪到MIN走步的節(jié)點(diǎn)時(shí)，MAX應(yīng)考慮最壞的情況（即f(p)取極小值）；(2)當(dāng)輪到MAX走步的節(jié)點(diǎn)時(shí)，MAX應(yīng)考慮最好的情況（即f(p)取極大值）；(3)評(píng)價(jià)往回倒推時(shí)，相應(yīng)于兩位棋手的對(duì)抗策略，交替使用（1）和（2）兩種方法傳遞倒推值。42極大極小過程的基本思想：421、將初始節(jié)點(diǎn)

S放入

OPEN表中，開始時(shí)搜索樹

T由初始節(jié)點(diǎn)

S構(gòu)成；2、若OPEN表為空（節(jié)點(diǎn)擴(kuò)展結(jié)束），則轉(zhuǎn)5；3、將OPEN

表中第一個(gè)節(jié)點(diǎn)

n移出放入CLOSED表的前端；極大極小搜索過程為：431、將初始節(jié)點(diǎn)S放入OPEN表中，開始時(shí)搜索樹T4、若n可直接判定為贏、輸、或平局，則令對(duì)應(yīng)的e(n)=∞，-∞或0，并轉(zhuǎn)2；否則擴(kuò)展n，產(chǎn)生n的后繼節(jié)點(diǎn)集{ni}，將{ni

}放入搜索樹T中。此時(shí)，若搜索深度d{ni}小于預(yù)先設(shè)定的深度k，則將{ni}放入OPEN表的末端，轉(zhuǎn)2；否則，ni達(dá)到深度k，計(jì)算e(ni)，并轉(zhuǎn)2；444、若n可直接判定為贏、輸、或平局，則令對(duì)應(yīng)的e(n)5、若CLOSED表為空，則轉(zhuǎn)8；否則取出CLOSED表中的第一個(gè)節(jié)點(diǎn)，記為

np；Open為空，即已經(jīng)擴(kuò)展完節(jié)點(diǎn)步2455、若CLOSED表為空，則轉(zhuǎn)8；否則取出CLOSED表中的6、若

np

屬于MAX層，且對(duì)于它的屬于MIN層的子節(jié)點(diǎn)

nci

的

e

(

nci

)有值，則：

e

(

np

)=max{

nci

}466、若np屬于MAX層，且對(duì)于它的屬于MIN層的子節(jié)點(diǎn)（續(xù)）若np屬于MIN層，且對(duì)于它的屬于MAX層的子節(jié)點(diǎn)

nci

的

e(nci

)有值，則：

e(np

)=min{

nci

}47（續(xù)）477、轉(zhuǎn)5；8、根據(jù)

e(S)

的值，標(biāo)記走步或者結(jié)束（-∞，∞或0）。487、轉(zhuǎn)5；48第一階段為1、2、3、4步，用寬度優(yōu)先算法生成規(guī)定深度k的全部博弈樹，然后對(duì)其所有端節(jié)點(diǎn)計(jì)算e(P)；第二階段為5、6、7、8步，是自下而上逐級(jí)求節(jié)點(diǎn)的倒推估價(jià)值，直至求出初始節(jié)點(diǎn)的e(S)為止，再由e(S)選得相對(duì)較好的走法，過程結(jié)束。算法分成兩個(gè)階段：49第一階段為1、2、3、4步，用寬度優(yōu)先算法生成規(guī)定深度k等對(duì)手走出相應(yīng)的棋，再以當(dāng)前的格局作為初始節(jié)點(diǎn)，重復(fù)此過程，選擇對(duì)自己有利的走法。50等對(duì)手走出相應(yīng)的棋，再以當(dāng)前的格局作為初始節(jié)點(diǎn)，重復(fù)此過程，極大極小過程51極大極小過程51例：

一字棋的極大極小搜索過程

約定：每一方只向前看一步（擴(kuò)展出二層）記MAX的棋子為“×”，MIN的棋子為“O”規(guī)定MAX先手52例：一字棋的極大極小搜索過程約定：52①

若格局P對(duì)任何一方都不能獲勝，則e(P)=（所有空格上都放上MAX的棋子后，MAX的三個(gè)棋子所組成的行、列及對(duì)角線的總數(shù)）-（所有空格上都放上MIN的棋子后，MIN的三個(gè)棋子所組成的行、列及對(duì)角線的總數(shù)）靜態(tài)估計(jì)函數(shù)e(P)定義為：53①若格局P對(duì)任何一方都不能獲勝，則靜態(tài)估計(jì)函數(shù)e(P②

若P是MAX獲勝，則e(P)=+∞③

若P是MIN獲勝，則e(P)=－∞54②若P是MAX獲勝，則54例：計(jì)算下列棋局的靜態(tài)估價(jià)函數(shù)值

e(P)=6-4=2

棋局O××O×××××××OOOO×OOOO行=2列=2對(duì)角=2行=2列=2對(duì)角=055例：計(jì)算下列棋局的靜態(tài)估價(jià)函數(shù)值e(P)=6-4=2棋利用棋盤的對(duì)稱性，有些棋局是等價(jià)的

O××OO××O56利用棋盤的對(duì)稱性，有些棋局是等價(jià)的O××OO××O56××××O×O×O×O×OO×O×O×O×O××O×O1010-1-10-10-2121-2-11MAXMINMAXMAX的走步57××××O×O×O×O×OO×O×O×O×O××O×O101第二步OXXOXOXXOXXOXXXOOXXOOXXOXOXOXOXOXO213211OOXXOXXOOXXOOXXOOXXO10201OOXX10OOXXOOXXOOXXOXOXOXXOOXXO2231221OOXXOXOXOOXX1100158第二步OXXOXOXXOXXOXXXOOXXOOXXOXOX第三步OOXXXOOXXOOXXXOOXXXOOXXXOOXXXXOOOXXXOOXXOXOOXXOXOOXOXOOOXXXOOOXXXOOXXXOOOXXXOOOOXXXOOXXXOOOXXXOOOXXOXOOOXXXOOOXXXOOXXOXOOXOXXOOOXXXOOOXXXOOXXXOOOXOXX-021---122101---1111112-1159第三步OOXXXOOXXOOXXXOOXXXOOXXXOOX×OO××MAXMIN60×OO××MAXMIN60MAXMIN×O××O61MAXMIN×O××O61極大極小搜索過程由兩個(gè)完全分離的兩個(gè)步驟組成：第一、用寬度優(yōu)先算法生成一棵博弈搜索樹第二、估計(jì)值的倒推計(jì)算缺點(diǎn)：這種分離使得搜索的效率比較低62極大極小搜索過程由兩個(gè)完全分離的兩個(gè)步驟組成：62極小極大過程05-333-3022-30-23541-30689-30-33-3-3-21-360316011極大極小ab注：用□表示MAX，用○表示MIN，端節(jié)點(diǎn)上的數(shù)字表示它對(duì)應(yīng)的估價(jià)函數(shù)的值。極大極小63極小極大過程05-333-3022-30-23541-306極大極小過程是先生成與/或樹，然后再計(jì)算各節(jié)點(diǎn)的估值，這種生成節(jié)點(diǎn)和計(jì)算估值相分離的搜索方式，需要生成規(guī)定深度內(nèi)的所有節(jié)點(diǎn)，因此搜索效率較低。改進(jìn)：在博弈樹生成過程中同時(shí)計(jì)算端節(jié)點(diǎn)的估計(jì)值及倒推值，以減少搜索的次數(shù)，這就是α-β過程的思想，也稱為α-β剪枝法。剪枝的概念:如果能邊生成節(jié)點(diǎn)邊對(duì)節(jié)點(diǎn)估值，并剪去一些沒用的分枝，這種技術(shù)被稱為α-β剪枝。64極大極小過程是先生成與/或樹，然后再計(jì)算各節(jié)點(diǎn)的估值，這種生-剪枝極大節(jié)點(diǎn)的下界為。極小節(jié)點(diǎn)的上界為。剪枝的條件：后輩節(jié)點(diǎn)的值≤祖先節(jié)點(diǎn)的值時(shí)，剪枝后輩節(jié)點(diǎn)的值≥祖先節(jié)點(diǎn)的值時(shí)，剪枝簡(jiǎn)記為：極小≤極大，剪枝極大≥極小，剪枝65-剪枝極大節(jié)點(diǎn)的下界為。65一個(gè)α-β剪枝的具體例子，如下圖所示。其中最下面一層端節(jié)點(diǎn)旁邊的數(shù)字是假設(shè)的估值。在該圖中，L、M、N的估值推出節(jié)點(diǎn)F的倒推值為4，即F的β值為4，由此可推出節(jié)點(diǎn)C的倒推值≥4。記C的倒推值的下界為4，不可能再比4小，故C的α值為4。

由節(jié)點(diǎn)N的估值推知節(jié)點(diǎn)G的倒推值小于≤1,無論G的其它子節(jié)點(diǎn)的估只是多少，G的倒推值都不可能比1大。因此，1是G的倒推值的上界，所以G的值≦1。另已知C的倒推值≥4，G的其它子節(jié)點(diǎn)又不可能使C的倒推值增大。因此對(duì)G的其它分支不必再搜索，相當(dāng)于把這些分枝剪去。由F、G的倒推值可推出節(jié)點(diǎn)C的倒推值≥4，再由C可推出節(jié)點(diǎn)A的倒推值≤4，即A的β值為4。另外，由節(jié)點(diǎn)P、Q推出的節(jié)點(diǎn)H的倒推值為5，因此D的倒推值

≥5，即D的α值為5。此時(shí)，D的其它子節(jié)點(diǎn)的倒推值無論是多少都不能使D及A的倒推值減少或增大，所以D的其他分枝被減去，并可確定A的倒推值為4。以此類推，最終推出S0的倒推值為4。≥4S0≤4A≦011≥4≥5≥0CDE0-6×IJ4≦1KLN461×FG5P58H×M8β值α值β值α值QR×≤0≦-6S××66一個(gè)α-β剪枝的具體例子，如下圖所示。其中最下面一層86-31453-350-剪枝（續(xù)）3-3022-30-239-300-303305411-31661abcdefghijkmn0

剪枝

剪枝

剪枝

剪枝6786-31453-350-剪枝（續(xù)）3-3022-30--剪枝的其他應(yīng)用故障診斷ABCD風(fēng)險(xiǎn)投資68-剪枝的其他應(yīng)用故障診斷6839、把生活中的每一天，都當(dāng)作生命中的最后一天。

40、機(jī)不可失，時(shí)不再來。

41、就算全世界都否定我，還有我自己相信我。

42、不為模糊不清的未來擔(dān)憂，只為清清楚楚的現(xiàn)在努力。

43、付出才會(huì)杰出。

44、成功不是憑夢(mèng)想和希望，而是憑努力和實(shí)踐。

45、成功這件事，自己才是老板！

46、暗自傷心，不如立即行動(dòng)。

47、勤奮是你生命的密碼，能譯出你一部壯麗的史詩。

48、隨隨便便浪費(fèi)的時(shí)間，再也不能贏回來。

49、不要輕易用過去來衡量生活的幸與不幸！每個(gè)人的生命都是可以綻放美麗的，只要你珍惜。

50、給自己定目標(biāo)，一年，兩年，五年，也許你出生不如別人好，通過努力，往往可以改變%的命運(yùn)。破罐子破摔只能和懦弱做朋友。

51、當(dāng)眼淚流盡的時(shí)候，留下的應(yīng)該是堅(jiān)強(qiáng)。

52、上天完全是為了堅(jiān)強(qiáng)你的意志，才在道路上設(shè)下重重的障礙。

53、沒有播種，何來收獲；沒有辛苦，何來成功；沒有磨難，何來榮耀；沒有挫折，何來輝煌。

54、只要路是對(duì)的，就不怕路遠(yuǎn)。

55、生命對(duì)某些人來說是美麗的，這些人的一生都為某個(gè)目標(biāo)而奮斗。

56、浪花總是著揚(yáng)帆者的路開放的。

74、失敗是什么？沒有什么，只是更走近成功一步；成功是什么？就是走過了所有通向失敗的路，只剩下一條路，那就是成功的路。

75、要改變命運(yùn)，首先改變自己。

76、我們?nèi)粢呀邮茏顗牡?，就再?zèng)]有什么損失。

77、在生活中，我跌倒過。我在嘲笑聲中站起來，雖然衣服臟了，但那是暫時(shí)的，它可以洗凈。

78、沒有壓力的生活就會(huì)空虛；沒有壓力的青春就會(huì)枯萎；沒有壓力的生命就會(huì)黯淡。

79、人生就像一杯沒有加糖的咖啡，喝起來是苦澀的，回味起來卻有久久不會(huì)退去的余香。

80、最困難的時(shí)候，就是距離成功不遠(yuǎn)了。

81、知道自己要干什么，夜深人靜，問問自己，將來的打算，并朝著那個(gè)方向去實(shí)現(xiàn)。而不是無所事事和做一些無謂的事。

82、出路出路，走出去了，總是會(huì)有路的。困難苦難，困在家里就是難。

83、人生最大的喜悅是每個(gè)人都說你做不到，你卻完成它了！

84、勇士搏出驚濤駭流而不沉淪，懦夫在風(fēng)平浪靜也會(huì)溺水。

85、生活不是林黛玉，不會(huì)因?yàn)閼n傷而風(fēng)情萬種。

86、唯有行動(dòng)才能改造命運(yùn)。

87、即使行動(dòng)導(dǎo)致錯(cuò)誤，卻也帶來了學(xué)習(xí)與成長(zhǎng)；不行動(dòng)則是停滯與萎縮。

88、光說不干，事事落空；又說又干，馬到成功。

89、對(duì)于每一個(gè)不利條件，都會(huì)存在與之相對(duì)應(yīng)的有利條件。

90、人的潛能是一座無法估量的豐富的礦藏，只等著我們?nèi)ネ诰颉?/p>

91、要成功，不要與馬賽跑，要騎在馬上，馬上成功。

2、虛心使人進(jìn)步，驕傲使人落后。

3、謙虛是學(xué)習(xí)的朋友，自滿是學(xué)習(xí)的敵人。

4、若要精，人前聽。

5、喜歡吹噓的人猶如一面大鼓，響聲大腹中空。

6、強(qiáng)中更有強(qiáng)中手，莫向人前自夸口。

7、請(qǐng)教別人不折本，舌頭打個(gè)滾。

8、人唯虛，始能知人。滿招損，謙受益。滿必溢，驕必?cái)　?9、把生活中的每一天，都當(dāng)作生命中的最后一天。69第二章與或圖搜索問題目標(biāo)目標(biāo)初始節(jié)點(diǎn)sabc70第二章與或圖搜索問題目標(biāo)目標(biāo)初始節(jié)點(diǎn)sabc12.1基本概念與或圖是一個(gè)超圖，節(jié)點(diǎn)間通過連接符連接。K-連接符：…...K個(gè)712.1基本概念與或圖是一個(gè)超圖，節(jié)點(diǎn)間通過連接符連接?！?耗散值的計(jì)算k(n,N)=Cn+k(n1,N)+…+k(ni,N)其中：N為終節(jié)點(diǎn)集

Cn為連接符的耗散值…...i個(gè)nn1n2ni72耗散值的計(jì)算…...i個(gè)nn1n2ni3目標(biāo)目標(biāo)初始節(jié)點(diǎn)解圖：73目標(biāo)目標(biāo)初始節(jié)點(diǎn)解圖：4能解節(jié)點(diǎn)終節(jié)點(diǎn)是能解節(jié)點(diǎn)若非終節(jié)點(diǎn)有“或”子節(jié)點(diǎn)時(shí)，當(dāng)且僅當(dāng)其子節(jié)點(diǎn)至少有一能解時(shí)，該非終節(jié)點(diǎn)才能解。若非終節(jié)點(diǎn)有“與”子節(jié)點(diǎn)時(shí)，當(dāng)且僅當(dāng)其子節(jié)點(diǎn)均能解時(shí)，該非終節(jié)點(diǎn)才能解。74能解節(jié)點(diǎn)終節(jié)點(diǎn)是能解節(jié)點(diǎn)5不能解節(jié)點(diǎn)沒有后裔的非終節(jié)點(diǎn)是不能解節(jié)點(diǎn)。若非終節(jié)點(diǎn)有“或”子節(jié)點(diǎn)，當(dāng)且僅當(dāng)所有子節(jié)點(diǎn)均不能解時(shí)，該非終節(jié)點(diǎn)才不能解。若非終節(jié)點(diǎn)有“與”子節(jié)點(diǎn)時(shí)，當(dāng)至少有一個(gè)子節(jié)點(diǎn)不能解時(shí)，該非終節(jié)點(diǎn)才不能解。75不能解節(jié)點(diǎn)沒有后裔的非終節(jié)點(diǎn)是不能解節(jié)點(diǎn)。6普通圖搜索的情況 f(n)=g(n)+h(n) 對(duì)n的評(píng)價(jià)實(shí)際是對(duì)從s到n這條路徑的評(píng)價(jià)ns76普通圖搜索的情況 f(n)=g(n)+h(n)ns7與或圖:對(duì)局部圖的評(píng)價(jià)目標(biāo)目標(biāo)初始節(jié)點(diǎn)abc77與或圖:對(duì)局部圖的評(píng)價(jià)目標(biāo)目標(biāo)初始節(jié)點(diǎn)abc8兩個(gè)過程圖生成過程，即擴(kuò)展節(jié)點(diǎn)從最優(yōu)的局部途中選擇一個(gè)節(jié)點(diǎn)擴(kuò)展計(jì)算耗散值的過程對(duì)當(dāng)前的局部圖從新計(jì)算耗散值78兩個(gè)過程圖生成過程，即擴(kuò)展節(jié)點(diǎn)9AO*算法舉例其中：h(n0)=3h(n1)=2h(n2)=4h(n3)=4h(n4)=1h(n5)=1h(n6)=2h(n7)=0h(n8)=0設(shè)：K連接符的耗散值為K目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5n6n7n879AO*算法舉例其中：目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5n6n7n8初始節(jié)點(diǎn)n0n1(2)n4(1)n5(1)紅色：4黃色：380目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5n6n7n8初始節(jié)點(diǎn)初始節(jié)點(diǎn)n0n4(1)n5(1)紅色：4黃色：6n1n2(4)n3(4)5目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5n6n7n881初始節(jié)點(diǎn)n0n4(1)n5(1)紅色：4n1n2(4)n3(紅色：5黃色：6初始節(jié)點(diǎn)n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)2目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5n6n7n882紅色：5初始節(jié)點(diǎn)n0n4(1)n5(1)n1n2(4)n3(紅色：5黃色：621初始節(jié)點(diǎn)n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5n6n7n883紅色：521初始節(jié)點(diǎn)n0n4(1)n5(1)n1n2(4)n博弈是一類具有競(jìng)爭(zhēng)性的智能活動(dòng)雙人博弈：即兩位選手對(duì)壘，輪流依次走步，其中任何一方都完全知道對(duì)方過去已經(jīng)走過的棋步和今后可能的走步，其結(jié)果是一方贏(而另一方則輸)，或雙方和局2.3博弈樹搜索84博弈是一類具有競(jìng)爭(zhēng)性的智能活動(dòng)2.3博弈樹搜索15博弈的例子：一字棋跳棋中國(guó)象棋圍棋五子棋85博弈的例子：162.3博弈樹搜索博弈問題雙人對(duì)弈，對(duì)壘的雙方輪流走步；信息完備，對(duì)壘雙方所得到的信息是一樣的，不存在一方能看到，而另外一方看不到的情況；零和，即對(duì)一方有利的棋，對(duì)另一方肯定是不利的，不存在對(duì)雙方均有利或均無利的棋，對(duì)弈的結(jié)果是一方贏，而另一方輸，或者雙方和棋。862.3博弈樹搜索博弈問題17雙方的智能活動(dòng)，任何一方都不能單獨(dú)控制博弈過程，而是由雙方輪流實(shí)施其控制對(duì)策的過程。博弈的特點(diǎn)：87雙方的智能活動(dòng)，任何一方都不能單獨(dú)控制博弈過程，而是由雙方輪如何根據(jù)當(dāng)前的棋局，選擇對(duì)自己最有利的一步棋？人工智能中研究的博弈問題：中國(guó)象棋88如何根據(jù)當(dāng)前的棋局，選擇對(duì)自己最有利的一步棋？人工智能中研用博弈樹來表示，它是一種特殊的與或樹。節(jié)點(diǎn)代表博弈的格局（即棋局），相當(dāng)于狀態(tài)空間中的狀態(tài)，反映了博弈的信息，并且與節(jié)點(diǎn)、或節(jié)點(diǎn)隔層交替出現(xiàn)。博弈問題（求解過程）的表示：89用博弈樹來表示，它是一種特殊的與或樹。節(jié)點(diǎn)代表博弈的格局（即假設(shè)博弈雙方為：MAX和MIN在博弈過程中，規(guī)則是雙方輪流走步。在博弈樹中，相當(dāng)于博弈雙方輪流擴(kuò)展其所屬節(jié)點(diǎn)。為什么與節(jié)點(diǎn)、或節(jié)點(diǎn)隔層交替出現(xiàn)？90假設(shè)博弈雙方為：MAX和MIN為什么與節(jié)點(diǎn)、或節(jié)點(diǎn)隔層交替出從MAX方的角度來看：所有MIN方節(jié)點(diǎn)都是與節(jié)點(diǎn)理由：因?yàn)镸IN方必定選擇最不利于MAX方的方式來擴(kuò)展節(jié)點(diǎn)，只要MIN方節(jié)點(diǎn)的子節(jié)點(diǎn)（下出棋局）中有一個(gè)對(duì)MAX方不利，則該節(jié)點(diǎn)就對(duì)MAX方不利，故為“與節(jié)點(diǎn)”。MIN好招91從MAX方的角度來看：MIN好招22從MAX方的角度來看：

所有屬于MAX方的節(jié)點(diǎn)都是或節(jié)點(diǎn)理由：因?yàn)閿U(kuò)展MAX方節(jié)點(diǎn)時(shí)，MAX方可選擇擴(kuò)展最有利于自己的節(jié)點(diǎn)，只要可擴(kuò)展的子節(jié)點(diǎn)中有一個(gè)對(duì)已有利，

則該節(jié)點(diǎn)就對(duì)已有利。MAX好招92從MAX方的角度來看：MAX好招23總之：從MAX方來說，與節(jié)點(diǎn)、或節(jié)點(diǎn)交替出現(xiàn)；反之，從MIN方的角度來看，情況正好相反。93總之：24在博弈樹中，先行一方的初始狀態(tài)對(duì)應(yīng)著樹的根節(jié)點(diǎn)，而任何一方獲勝的最終格局為目標(biāo)狀態(tài)，對(duì)應(yīng)于樹的終葉節(jié)點(diǎn)（可解節(jié)點(diǎn)或本原問題）。但是，從MAX的角度出發(fā)，所有使MAX獲勝的狀態(tài)格局都是本原問題，是可解節(jié)點(diǎn)，而使MIN獲勝的狀態(tài)格局是不可解節(jié)點(diǎn)。94在博弈樹中，先行一方的初始狀態(tài)對(duì)應(yīng)著樹的根節(jié)點(diǎn)，而任何一方獲博弈樹特點(diǎn)(1)博弈的初始狀態(tài)是初始節(jié)點(diǎn)；(2)博弈樹的“與”節(jié)點(diǎn)和“或”節(jié)點(diǎn)是逐層交替出現(xiàn)的；(3)整個(gè)博弈過程始終站在某一方的立場(chǎng)上，所以能使自己一方獲勝的終局都是本原問題，相應(yīng)的節(jié)點(diǎn)也是可解節(jié)點(diǎn)，所有使對(duì)方獲勝的節(jié)點(diǎn)都是不可解節(jié)點(diǎn)。95博弈樹特點(diǎn)(1)博弈的初始狀態(tài)是初始節(jié)點(diǎn)；26例

Grundy博弈：分配物品的問題如果有一堆數(shù)目為N的錢幣，由兩位選手輪流進(jìn)行分配，要求每個(gè)選手每次把其中某一堆分成數(shù)目不等的兩小堆，直至有一選手不能將錢幣分成不等的兩堆為止，則判定這位選手為輸家。96例Grundy博弈：分配物品的問題27用數(shù)字序列加上一個(gè)說明來表示一個(gè)狀態(tài)：(3,2,1,1,MAX)數(shù)字序列：表示不同堆中錢幣的個(gè)數(shù)說明：表示下一步由誰來分，即取MAX或MIN97用數(shù)字序列加上一個(gè)說明來表示一個(gè)狀態(tài)：28現(xiàn)在取N＝7的簡(jiǎn)單情況，并由MIN先分

注：如果MAX走紅箭頭的分法，必定獲勝。所有可能的分法(7,MIN)(6,1,MAX)(5,2,MAX)(4,3,MAX)(5,1,1,MIN)(4,2,1,MIN)(3,2,2,MIN)(3,3,1,MIN)(4,1,1,1,MAX)(3,2,1,1,MAX)(2,2,2,1,MAX)(2,2,1,1,1,MIN)(3,1,1,1,1,MIN)(2,1,1,1,1,1,MAX)98現(xiàn)在取N＝7的簡(jiǎn)單情況，并由MIN先分注：如果MAX走分錢幣問題（7）（6,1）（5,2）（4,3）（5,1,1）（4,2,1）（3,2,2）（3,3,1）（4,1,1,1）（3,2,1,1）（2,2,2,1）（3,1,1,1,1）（2,2,1,1,1）（2,1,1,1,1,1）對(duì)方先走我方必勝99分錢幣問題（7）（6,1）（5,2）（4,3）（5,1,1）對(duì)于比較復(fù)雜的博弈問題，只能模擬人的思維“向前看幾步”，然后作出決策，選擇最有利自己的一步。即只能給出幾層走法，然后按照一定的估算辦法，決定走一好招。100對(duì)于比較復(fù)雜的博弈問題，只能模擬人的思維“向前看幾步”，然后中國(guó)象棋一盤棋平均走50步，總狀態(tài)數(shù)約為10的161次方。假設(shè)1毫微秒走一步，約需10的145次方年。結(jié)論：不可能窮舉。101中國(guó)象棋一盤棋平均走50步，總狀態(tài)數(shù)約為10的161次方。3在人工智能中可以采用搜索方法來求解博弈問題，下面就來討論博弈中兩中最基本的搜索方法。

102在人工智能中可以采用搜索方法來求解博弈問題，下面就來討論博弈對(duì)于復(fù)雜的博弈問題，要規(guī)定搜索深度與時(shí)間，以便于博弈搜索能順利進(jìn)行。假設(shè)由MAX來選擇走一步棋，問題是：MAX如何來選擇一步好棋？

極大極小過程103對(duì)于復(fù)雜的博弈問題，要規(guī)定搜索深度與時(shí)間，以便于博弈搜索能順極大極小過程

極大極小過程是考慮雙方對(duì)弈若干步之后，從可能的走法中選一步相對(duì)好的走法來走，即在有限的搜索深度范圍內(nèi)進(jìn)行求解。需要定義一個(gè)靜態(tài)估價(jià)函數(shù)e,以便對(duì)棋局的態(tài)勢(shì)做出評(píng)估。104極大極小過程極大極小過程是考慮雙方對(duì)弈若干步之后，從可能的①

對(duì)于每一格局（棋局）給出（定義或者倒推）一個(gè)靜態(tài)估價(jià)函數(shù)值。值越大對(duì)MAX越有利，反之越不利；極大極小過程的基本思路：105①對(duì)于每一格局（棋局）給出（定義或者倒推）一個(gè)靜態(tài)估價(jià)函數(shù)②

對(duì)于給定的格局，MAX給出可能的走法，然后MIN對(duì)應(yīng)地給出相應(yīng)的走法，這樣重復(fù)若干次，得到一組端節(jié)點(diǎn)（必須由MIN走后得到的，等待MAX下的棋局）。這一過程相當(dāng)于節(jié)點(diǎn)擴(kuò)展；注：博弈樹深度或?qū)訑?shù)一定是偶數(shù)。106②對(duì)于給定的格局，MAX給出可能的走法，然后MIN對(duì)應(yīng)地給③對(duì)于每一個(gè)端節(jié)點(diǎn)，計(jì)算出它們的靜態(tài)估價(jià)函數(shù)，然后自下而上地逐層計(jì)算倒推值，直到MAX開始的格局。在MIN下的格局中取估值的最小值，在MAX下格局中取估值的最大值；④取估值最大的格局作為MAX要走的一招棋。107③對(duì)于每一個(gè)端節(jié)點(diǎn)，計(jì)算出它們的靜態(tài)估價(jià)函數(shù)，然后自下而上例：向前看一步的兩層博弈樹

108例：向前看一步的兩層博弈樹39定義靜態(tài)函數(shù)e(P)的一般原則：109定義靜態(tài)函數(shù)e(P)的一般原則：40OPEN：存放待擴(kuò)展的節(jié)點(diǎn)，此時(shí)為隊(duì)列，即以寬度優(yōu)先的策略擴(kuò)展節(jié)點(diǎn)。CLOSED：存放已擴(kuò)展的節(jié)點(diǎn)，此時(shí)為堆棧，即后擴(kuò)展的節(jié)點(diǎn)先計(jì)算。

符號(hào)：110OPEN：存放待擴(kuò)展的節(jié)點(diǎn)，此時(shí)為隊(duì)列，即以寬度優(yōu)先的策略擴(kuò)極大極小過程的基本思想：(1)當(dāng)輪到MIN走步的節(jié)點(diǎn)時(shí)，MAX應(yīng)考慮最壞的情況（即f(p)取極小值）；(2)當(dāng)輪到MAX走步的節(jié)點(diǎn)時(shí)，MAX應(yīng)考慮最好的情況（即f(p)取極大值）；(3)評(píng)價(jià)往回倒推時(shí)，相應(yīng)于兩位棋手的對(duì)抗策略，交替使用（1）和（2）兩種方法傳遞倒推值。111極大極小過程的基本思想：421、將初始節(jié)點(diǎn)

S放入

OPEN表中，開始時(shí)搜索樹

T由初始節(jié)點(diǎn)

S構(gòu)成；2、若OPEN表為空（節(jié)點(diǎn)擴(kuò)展結(jié)束），則轉(zhuǎn)5；3、將OPEN

表中第一個(gè)節(jié)點(diǎn)

n移出放入CLOSED表的前端；極大極小搜索過程為：1121、將初始節(jié)點(diǎn)S放入OPEN表中，開始時(shí)搜索樹T4、若n可直接判定為贏、輸、或平局，則令對(duì)應(yīng)的e(n)=∞，-∞或0，并轉(zhuǎn)2；否則擴(kuò)展n，產(chǎn)生n的后繼節(jié)點(diǎn)集{ni}，將{ni

}放入搜索樹T中。此時(shí)，若搜索深度d{ni}小于預(yù)先設(shè)定的深度k，則將{ni}放入OPEN表的末端，轉(zhuǎn)2；否則，ni達(dá)到深度k，計(jì)算e(ni)，并轉(zhuǎn)2；1134、若n可直接判定為贏、輸、或平局，則令對(duì)應(yīng)的e(n)5、若CLOSED表為空，則轉(zhuǎn)8；否則取出CLOSED表中的第一個(gè)節(jié)點(diǎn)，記為

np；Open為空，即已經(jīng)擴(kuò)展完節(jié)點(diǎn)步21145、若CLOSED表為空，則轉(zhuǎn)8；否則取出CLOSED表中的6、若

np

屬于MAX層，且對(duì)于它的屬于MIN層的子節(jié)點(diǎn)

nci

的

e

(

nci

)有值，則：

e

(

np

)=max{

nci

}1156、若np屬于MAX層，且對(duì)于它的屬于MIN層的子節(jié)點(diǎn)（續(xù)）若np屬于MIN層，且對(duì)于它的屬于MAX層的子節(jié)點(diǎn)

nci

的

e(nci

)有值，則：

e(np

)=min{

nci

}116（續(xù)）477、轉(zhuǎn)5；8、根據(jù)

e(S)

的值，標(biāo)記走步或者結(jié)束（-∞，∞或0）。1177、轉(zhuǎn)5；48第一階段為1、2、3、4步，用寬度優(yōu)先算法生成規(guī)定深度k的全部博弈樹，然后對(duì)其所有端節(jié)點(diǎn)計(jì)算e(P)；第二階段為5、6、7、8步，是自下而上逐級(jí)求節(jié)點(diǎn)的倒推估價(jià)值，直至求出初始節(jié)點(diǎn)的e(S)為止，再由e(S)選得相對(duì)較好的走法，過程結(jié)束。算法分成兩個(gè)階段：118第一階段為1、2、3、4步，用寬度優(yōu)先算法生成規(guī)定深度k等對(duì)手走出相應(yīng)的棋，再以當(dāng)前的格局作為初始節(jié)點(diǎn)，重復(fù)此過程，選擇對(duì)自己有利的走法。119等對(duì)手走出相應(yīng)的棋，再以當(dāng)前的格局作為初始節(jié)點(diǎn)，重復(fù)此過程，極大極小過程120極大極小過程51例：

一字棋的極大極小搜索過程

約定：每一方只向前看一步（擴(kuò)展出二層）記MAX的棋子為“×”，MIN的棋子為“O”規(guī)定MAX先手121例：一字棋的極大極小搜索過程約定：52①

若格局P對(duì)任何一方都不能獲勝，則e(P)=（所有空格上都放上MAX的棋子后，MAX的三個(gè)棋子所組成的行、列及對(duì)角線的總數(shù)）-（所有空格上都放上MIN的棋子后，MIN的三個(gè)棋子所組成的行、列及對(duì)角線的總數(shù)）靜態(tài)估計(jì)函數(shù)e(P)定義為：122①若格局P對(duì)任何一方都不能獲勝，則靜態(tài)估計(jì)函數(shù)e(P②

若P是MAX獲勝，則e(P)=+∞③

若P是MIN獲勝，則e(P)=－∞123②若P是MAX獲勝，則54例：計(jì)算下列棋局的靜態(tài)估價(jià)函數(shù)值

e(P)=6-4=2

棋局O××O×××××××OOOO×OOOO行=2列=2對(duì)角=2行=2列=2對(duì)角=0124例：計(jì)算下列棋局的靜態(tài)估價(jià)函數(shù)值e(P)=6-4=2棋利用棋盤的對(duì)稱性，有些棋局是等價(jià)的

O××OO××O125利用棋盤的對(duì)稱性，有些棋局是等價(jià)的O××OO××O56××××O×O×O×O×OO×O×O×O×O××O×O1010-1-10-10-2121-2-11MAXMINMAXMAX的走步126××××O×O×O×O×OO×O×O×O×O××O×O101第二步OXXOXOXXOXXOXXXOOXXOOXXOXOXOXOXOXO213211OOXXOXXOOXXOOXXOOXXO10201OOXX10OOXXOOXXOOXXOXOXOXXOOXXO2231221OOXXOXOXOOXX11001127第二步OXXOXOXXOXXOXXXOOXXOOXXOXOX第三步OOXXXOOXXOOXXXOOXXXOOXXXOOXXXXOOOXXXOOXXOXOOXXOXOOXOXOOOXXXOOOXXXOOXXXOOOXXXOOOOXXXOOXXXOOOXXXOOOXXOXOOOXXXOOOXXXOOXXOXOOXOXXOOOXXXOOOXXXOOXXXOOOXOXX-021---122101---1111112-11128第三步OOXXXOOXXOOXXXOOXXXOOXXXOOX×OO××MAXMIN129×OO××MAXMIN60MAXMIN×O××O130MAXMIN×O××O61極大極小搜索過程由兩個(gè)完全分離的兩個(gè)步驟組成：第一、用寬度優(yōu)先算法生成一棵博弈搜索樹第二、估計(jì)值的倒推計(jì)算缺點(diǎn)：這種分離使得搜索的效率比較低131極大極小搜索過程由兩個(gè)完全分離的兩個(gè)步驟組成：62極小極大過程05-333-3022-30-23541-30689-30-33-3-3-21-360316011極大極小ab注：用□表示MAX，用○表示MIN，端節(jié)點(diǎn)上的數(shù)字表示它對(duì)應(yīng)的估價(jià)函數(shù)的值。極大極小132極小極大過程05-333-3022-30-23541-306極大極小過程是先生成與/或樹，然后再計(jì)算各節(jié)點(diǎn)的估值，這種生成節(jié)點(diǎn)和計(jì)算估值相分離的搜索方式，需要生成規(guī)定深度內(nèi)的所有節(jié)點(diǎn)，因此搜索效率較低。改進(jìn)：在博弈樹生成過程中同時(shí)計(jì)算端節(jié)點(diǎn)的估計(jì)值及倒推值，以減少搜索的次數(shù)，這就是α-β過程的思想，也稱為α-β剪枝法。剪枝的概念:如果能邊生成節(jié)點(diǎn)邊對(duì)節(jié)點(diǎn)估值，并剪去一些沒用的分枝，這種技術(shù)被稱為α-β剪枝。133極大極小過程是先生成與/或樹，然后再計(jì)算各節(jié)點(diǎn)的估值，這種生-剪枝極大節(jié)點(diǎn)的下界為。極小節(jié)點(diǎn)的上界為。剪枝的條件：后輩節(jié)點(diǎn)的值≤祖先節(jié)點(diǎn)的值時(shí)，剪枝后輩節(jié)點(diǎn)的值≥祖先節(jié)點(diǎn)的值時(shí)，剪枝簡(jiǎn)記為：極小≤極大，剪枝極大≥極小，剪枝134-剪枝極大節(jié)點(diǎn)的下界為。65一個(gè)α-β剪枝的具體例子，如下圖所示。其中最下面一層端節(jié)點(diǎn)旁邊的數(shù)字是假設(shè)的估值。在該圖中，L、M、N的估值推出節(jié)點(diǎn)F的倒推值為4，即F的β值為4，由此可推出節(jié)點(diǎn)C的倒推值≥4。記C的倒推值的下界為4，不可能再比