1、人工智能吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系2.1 與或圖(AND/OR Graph)的搜索為嚴(yán)格描述AND/OR圖，我們先推廣弧的概念。在有向圖中的弧是從一個父親節(jié)點(diǎn)指向它的兒子節(jié)點(diǎn)的。 在AND/OR圖中使用的弧叫做超弧，一個超弧可以把一個父親節(jié)點(diǎn)和k個兒子節(jié)點(diǎn)同時連接起來，這樣的弧也叫做kAND/OR圖中，k連弧用弧線連接起來。當(dāng)k=1 k連弧退化成通常的有向圖中的弧。 人工智能吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系k連弧一般的弧人工智能吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系n7n6n3n0n1n4n2n5n8與或圖人工智能吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系n5n1n3n6n7n8n5n0n7n8

2、n4n0三個解圖n5n7n8n4n0人工智能吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系在定義中假定AND/OR圖不含回路，即是說， 圖中不存在一個節(jié)點(diǎn)的后裔也是這個節(jié)點(diǎn)的祖先的情形。 不含回路保證了節(jié)點(diǎn)間具有部分序關(guān)系， 從而保證了下面定義的合理性。設(shè)N是AND/OR圖G的目標(biāo)節(jié)點(diǎn)集合， 從圖中任意一個節(jié)點(diǎn)n出發(fā)到N的一個解圖是AND/OR圖G的一個子圖， 用G表示， 遞歸定義如下：如果n是N中的一個節(jié)點(diǎn)， 則G只包括n.如果n有一條從n出發(fā)的k連弧ai, 這個k連弧連接的兒子節(jié)點(diǎn)是n1, n2, ., nk, 則解圖G由節(jié)點(diǎn)n, k連弧ai, 和由n1, n2, ., nk出發(fā)的解圖構(gòu)成。否則， G

3、沒有從n出發(fā)到N的解圖。人工智能吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系與或圖 設(shè)從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)集合N的費(fèi)用用c(n, N)表示， 則c(n, N)定義如下： 如果n是N中的一個節(jié)點(diǎn)， 則c(n, N)=0， 如果n有一條從n出發(fā)的k連弧ai, 這個k連弧連接的兒子節(jié)點(diǎn)是n1, n2, ., nk, 則解圖G由節(jié)點(diǎn)n, k連弧ai, 和由n1, n2, ., nk出發(fā)的解圖構(gòu)成。這時，解圖G的費(fèi)用定義為 c(n, N)= c(ai)+ c(n, n1)+ c(n, nk), 其中c(ai)是k連弧ai的費(fèi)用. 否則， G沒有從n出發(fā)到N的解圖。設(shè)其費(fèi)用為無窮大.。 例如，如果假定k連弧的費(fèi)用是k

4、, 則圖3.4 所示的 AND/OR圖的兩個解圖中，左圖的費(fèi)用是8， 右圖的費(fèi)用是7。 人工智能吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系2.2 與或圖的啟發(fā)式搜索AND/OR圖的啟發(fā)搜索過程AO*1. 建立一個只由根節(jié)點(diǎn)s構(gòu)成的搜索圖G, 設(shè)從s 出發(fā)的解圖的費(fèi)用為q(s)=h(s), 如果s是目標(biāo)節(jié)點(diǎn)， 用SOLVED標(biāo)記s.2. until s 被標(biāo)上SOLVED, do:3. begin4. 通過跟蹤從s出發(fā)的有標(biāo)記的超弧計(jì)算候選解圖G(這些標(biāo)記在后 面的步驟11中給出)5. 在G中選一個不是目標(biāo)節(jié)點(diǎn)的葉節(jié)點(diǎn)n,6. 擴(kuò)展節(jié)點(diǎn)n, 產(chǎn)生節(jié)點(diǎn)n的所有兒子n1, n2, ., nk, 并把這些兒子

5、連到圖G上,對于每一個不曾在G中出現(xiàn)的兒子nj, 設(shè)q(nj)=h(nj), 如果這些兒子節(jié)點(diǎn)中的某些節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn),則把這些節(jié)點(diǎn)標(biāo)記為SOLVED.人工智能吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系7. 建立一個由n構(gòu)成的單元素集合S.8. 直到 S變空, do:9. begin10. 從S中刪除其兒子節(jié)點(diǎn)不在S中的節(jié)點(diǎn), 記此節(jié)點(diǎn)為m. 按以下步驟修改m的費(fèi)用q(m), 對于每一個從m出發(fā)的 指向節(jié)點(diǎn)集合ni1, ni2, ., nik超弧ai，計(jì)算qi(m)= c(ai)+ q(ni1)+ q(nik), 這里的q( nij)或者是在本循環(huán)內(nèi)部的前面步驟計(jì)算出的值，或者是在步驟6中指定的值。 設(shè)

6、q(m)是所有qi(m)的最小者， 標(biāo)記實(shí)現(xiàn)這個最小值的超弧，如果本次標(biāo)記與以前的標(biāo)記不同， 擦去以前的標(biāo)記， 如果這些超弧指向的所有兒子節(jié)點(diǎn)都標(biāo)記了SOLVED, 則把m也標(biāo)上SOLVED.12. 如果m標(biāo)記了SOLVED或者m修改后的費(fèi)用與以前的費(fèi)用不同， 則把m通過標(biāo)記的超弧連接的父親節(jié)點(diǎn)加入到S中，13 end14. end人工智能吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系算法分為兩個階段 1. 4-6 步. 自頂向下的產(chǎn)生候補(bǔ)解圖, 并擴(kuò)展候補(bǔ)解圖的過程. 2. 7-12, 自底向上修正費(fèi)用值, 標(biāo)記弧及的過程.例H(n0)=3, H(n1)=2, H(n2)=4, H(n3)=4, H(n

7、4)=1, H(n5)=1, H(n6)=2, H(n7)=0, H(n8)=0, 人工智能吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系n1n5n41215, n0n1n5n451n2,4n7,03, n04n8,0n6,25, n0n1n5n451n2,4n7,0n8,0n6,2n3, 422一次循環(huán)后二次循環(huán)后三次循環(huán)后四次循環(huán)后圖3.5 AO*搜索算法的例子n1n5n41213, n0n34n24人工智能吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系5, n0n5n41n7,0n8,02搜索得到的解圖人工智能吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系2.3 博弈樹的搜索博弈樹的搜索 窮盡的極大極小過程。窮盡的極大極小

8、過程。 兩個游戲者分別為MAX 和MIN, MAX想取得高的分?jǐn)?shù)， 而MIN想取得低的分?jǐn)?shù)，把整個棋的狀態(tài)以及所有可能的移動都用一個有與或圖表示出來， 對于某一游戲者求出他的解圖，就是為游戲者制定的贏的策略。 Nim 游戲，桌子上有 7 枚硬幣， 由MAX 和MIN兩個人分別把一堆硬幣分成不相等的兩堆，誰不能繼續(xù)做下去，誰就算輸， 為MAX制定一個贏的策略。 知識表示， 二元組s, p,其中s為一集合， 表示桌面上各堆的硬幣數(shù)， p表示對當(dāng)前狀態(tài)應(yīng)該移動的游戲者。例如 （2，3，2， MAX）表示現(xiàn)在桌面上有 3 堆硬幣， 分別為2， 3， 2個， 此時應(yīng)掄到MAX移動。人工智能吉林大學(xué)珠海學(xué)

9、院計(jì)算機(jī)科學(xué)與技術(shù)系7, M IN6, 1, M A X5, 2, M A X4, 3, M A X5, 1, 1,M IN3, 3, 1,M IN3, 2, 2,M IN4, 2, 1,M IN4, 1, 1, 1,M A X2, 2, 2, 1,M A X3, 2, 1, 1,M A X3, 1, 1, 1,1, M IN2, 2, 1, 1,1, M IN2, 1, 1, 1, 1, 1, M A X1人工智能吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系固定深度的極大極小過程。固定深度的極大極小過程。 實(shí)際的游戲的狀態(tài)空間是非常大的， 例如國際象棋有 10120個狀態(tài)， 要想把所有狀態(tài)都列出來，

10、實(shí)際上是做不到的， 改進(jìn)的處理方法是在當(dāng)前狀態(tài)下把游戲擴(kuò)展到某一固定的深度， 對這個深度的樹的葉節(jié)點(diǎn)進(jìn)行狀態(tài)估值，然后分別逐層地以取極大和取極小的方式上傳， 最終給出對游戲者移動的最佳建議 例； 九宮游戲 估值函數(shù)： MAX所能占據(jù)的行， 列和對角線數(shù) - MAX所能占據(jù)的行， 列和對角線數(shù)如果MAX贏， 為無窮大如果MIN贏， 為05-4=1人工智能吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系兩步棋的例子SJIHGFEDABCMAX取極大值MIM取極小值MAX(-2)(-2)(0)(0)(-6)(9)(-4)(-3)(-4)(-2)(-6)MAX的移動人工智能吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系過程MI

11、NMAX: 算法分為兩個階段, 第一階段用寬度優(yōu)先產(chǎn)生給定深度內(nèi)的所有節(jié)點(diǎn), 然后對所有葉節(jié)點(diǎn)進(jìn)行狀態(tài)估值. 第二階段自低向上倒推估計(jì)值, 一層取極小, 一層去極大. 直至求出初始節(jié)點(diǎn)的估值.人工智能吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系MINMAX6-5=1, 5-5=0, 6-5=1, 5-5=0,4-5=-15-6=-1, 5-5=0, 5-6=-1, 6-6=0,4-6=-25-4=1 6-4=2人工智能吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系4-2=2 3-2=1 5-2=3 3-2=14-2=2 4-2=2人工智能吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系A(chǔ)lpha-beta Alpha-beta

12、過程過程 在固定深度的極大極小過程中， 對于一個給定的節(jié)點(diǎn)， 需要先擴(kuò)展到給定的深度， 然后對葉節(jié)點(diǎn)進(jìn)行估值，在一層一層地向上返回值， 決定最佳移動。 為提高效率， 我們可以按深度優(yōu)先方式， 從左邊開始， 先對最左分支擴(kuò)展到給定深度， 定出極大和極小的取值界限，即alpha值和beta值， 然后一邊擴(kuò)展一邊估值， 并把估值同alpha值和beta值相比較，這樣就可以省掉許多節(jié)點(diǎn)的估值， 當(dāng)然這些節(jié)點(diǎn)也不必產(chǎn)生了， 因此提高了算法的效率， 這就是Alpha-beta 過程。人工智能吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系M INM A X5-6=-1, 5-5=0, 5-6=-1, 6-6=0,4-6=-26-5=1 6-4=2A l pha = -1bet a =-16-5=1, 5-5=0, 6-5=1, 5-5=0,4-5=-1人工智能吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系A(chǔ)lpha-beta剪枝的原則 1。 在任一個MIN節(jié)點(diǎn)， 如果發(fā)現(xiàn)了其beta值小于或者等于它的一個MAX祖先節(jié)點(diǎn)的alpha值，則可以剪枝 2。 在任一個MAX 節(jié)點(diǎn)下， 如果發(fā)現(xiàn)