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

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

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

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

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

6、q(m)是所有qi(m)的最小者， 標記實現這個最小值的超弧，如果本次標記與以前的標記不同， 擦去以前的標記， 如果這些超弧指向的所有兒子節點都標記了SOLVED, 則把m也標上SOLVED.12. 如果m標記了SOLVED或者m修改后的費用與以前的費用不同， 則把m通過標記的超弧連接的父親節點加入到S中，13 end14. end人工智能吉林大學珠海學院計算機科學與技術系算法分為兩個階段 1. 4-6 步. 自頂向下的產生候補解圖, 并擴展候補解圖的過程. 2. 7-12, 自底向上修正費用值, 標記弧及的過程.例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, 人工智能吉林大學珠海學院計算機科學與技術系n1n5n41215, n0n1n5n451n2,4n7,03, n04n8,0n6,25, n0n1n5n451n2,4n7,0n8,0n6,2n3, 422一次循環后二次循環后三次循環后四次循環后圖3.5 AO*搜索算法的例子n1n5n41213, n0n34n24人工智能吉林大學珠海學院計算機科學與技術系5, n0n5n41n7,0n8,02搜索得到的解圖人工智能吉林大學珠海學院計算機科學與技術系2.3 博弈樹的搜索博弈樹的搜索 窮盡的極大極小過程。窮盡的極大極小

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

9、院計算機科學與技術系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人工智能吉林大學珠海學院計算機科學與技術系固定深度的極大極小過程。固定深度的極大極小過程。 實際的游戲的狀態空間是非常大的， 例如國際象棋有 10120個狀態， 要想把所有狀態都列出來，

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

11、NMAX: 算法分為兩個階段, 第一階段用寬度優先產生給定深度內的所有節點, 然后對所有葉節點進行狀態估值. 第二階段自低向上倒推估計值, 一層取極小, 一層去極大. 直至求出初始節點的估值.人工智能吉林大學珠海學院計算機科學與技術系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人工智能吉林大學珠海學院計算機科學與技術系4-2=2 3-2=1 5-2=3 3-2=14-2=2 4-2=2人工智能吉林大學珠海學院計算機科學與技術系Alpha-beta Alpha-beta

12、過程過程 在固定深度的極大極小過程中， 對于一個給定的節點， 需要先擴展到給定的深度， 然后對葉節點進行估值，在一層一層地向上返回值， 決定最佳移動。 為提高效率， 我們可以按深度優先方式， 從左邊開始， 先對最左分支擴展到給定深度， 定出極大和極小的取值界限，即alpha值和beta值， 然后一邊擴展一邊估值， 并把估值同alpha值和beta值相比較，這樣就可以省掉許多節點的估值， 當然這些節點也不必產生了， 因此提高了算法的效率， 這就是Alpha-beta 過程。人工智能吉林大學珠海學院計算機科學與技術系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人工智能吉林大學珠海學院計算機科學與技術系Alpha-beta剪枝的原則 1。 在任一個MIN節點， 如果發現了其beta值小于或者等于它的一個MAX祖先節點的alpha值，則可以剪枝 2。 在任一個MAX 節點下， 如果發現