【正文】 3/11/2023 90 產生式系統(tǒng)表示及其搜索方法基本內容 ? 產生式系統(tǒng)概念 基本工作過程（ Procedure PRODUCTION） ? 產生式系統(tǒng)工作方式：正向、反向、雙向 ? 產生式系統(tǒng)控制策略 不可撤回式：爬山函數 試探式： 回溯： BACKTRACK、 BACKTRACK1 圖搜索： GRAPHSEARCH、 A算法、 A*算法 ? 特殊產生式系統(tǒng) 可交換、可分解 (Procedure SPLIT) ? 可分解產生式系統(tǒng)的搜索策略： 與或圖的啟發(fā)式搜索算法 AO* 博弈樹搜索 MINIMAX過程、 αβ過程 3/11/2023 91 演講完畢，謝謝觀看！ 。例如，假設有一個終止狀態(tài)的效用值向量是（ vA=1000,vB=1000)，并且 1000對于兩個游戲者都是最高的可能效用值。在另一些情況下，違反盟約會損害社會聲譽，所以游戲者要在毀約得到直接利益和被認為不可信任而帶來的長期弊端之間進行權衡。當然一旦 C在聯合攻擊下被削弱，聯盟就失去了價值，于是 A或 B就會破壞協議。那么對于 A和 B而言，他們一起進攻 C比等C逐個消滅它們要好，這樣通常是最優(yōu)的。我們如何去理解這種行為呢？是否在多人游戲中對每一個游戲者來說聯盟是最優(yōu)策略的一個自然結果？看起來可能是這樣的。多人游戲通常會涉及在游戲者之間出現正式的聯盟的情況。 1， 2， 6 1， 2， 6 1， 2， 6 1， 5， 2 6， 1， 2 1， 5， 2 5， 4， 5 1， 2， 6 6， 1， 2 4， 2， 3 7， 4， 1 5， 1， 1 1， 5， 2 5， 4， 5 7， 7， 1 行棋方 A B C A 圖 有三個游戲者 (A,B,C)的博弈樹中的前三層，節(jié)點標有從每個游戲者出發(fā)的值。兩種選擇導致的終止狀態(tài)的效用值向量分別為(vA=1,vB=2,vC=6)和 (vA=4,vB=2,vC=3)。 3/11/2023 87 考慮在中的博弈樹上標為 X的節(jié)點。對于終止狀態(tài)，這個向量給出了從每個人角度出發(fā)得到的狀態(tài)效用值（在二人零和游戲中，由于效用值總是正好相反，所以二維向量可以簡化為一個單一值）。 首先我們需要把每一個上的單一值替換成一個向量值。讓我們來看看如何把極小極大思想推廣到多人游戲中。 MINIMAX就是按這種思想建立的過程，而 αβ過程是 MINIMAX過程的改進，并可提高效率。 小結 3/11/2023 85 3．博弈問題可用產生式系統(tǒng)來描述，求解過程也是一個對與 /或圖進行搜索的問題。解圖及其費用值可由遞歸定義給出。 3/11/2023 84 1．用可分解產生式系統(tǒng)求解問題時，求解過程可歸結為對一個隱含的與 /或圖進行搜索。再一點就是選手的棋風問題。此外有些博弈過程，在一個短時期內短兵相接，進攻和防御的戰(zhàn)術變化劇烈，這些情況如何在搜索策略中加以考慮。但是這些方法還不能全面反映人們弈棋過程實際所使用的一切推理技術，也未涉及棋局的表示和啟發(fā)函數問題。 進行 αβ剪枝注意的問題： 3/11/2023 82 若以最理想的情況進行搜索，即對 MIN節(jié)點先擴展最低估值的節(jié)點（若從左向右順序進行，則設節(jié)點估計值從左向右遞增排序）， MAX先擴展最高估值的節(jié)點（設估計值從左向右遞減排序），則當搜索樹深度為 D，分枝因數為B時，若不使用 αβ剪枝技術，搜索樹的端節(jié)點數 BD；若使用 αβ剪枝技術．可以證明理想條件下生成的端節(jié)點數最少，有 ND=2BD/21（ D為偶數） ND=B(D+1)/2+B(D1)/21（ D為奇數） 比較后得出最佳 αβ搜索技術所生成深度為 D處的端節(jié)點數約等于不用 αβ搜索技術所生成深度為 D／ 2處的端節(jié)點數。在實際程序實現時，首先規(guī)定一個搜索深度，然后按照類似于深度優(yōu)先搜索的方式，生成節(jié)點。 （ 5）在實際搜索時，并不是先生成指定深度的搜索圖，再在搜索圖上進行剪枝。 （ 3）當只有一個節(jié)點的 固定 以后，其值才能夠向其父節(jié)點傳遞。 （ 2）在比較時注意是與 “祖先層 節(jié)點比較，不只是與父輩節(jié)點比較。 （ 2） β剪枝： 如果一個 MAX節(jié)點的 α值大于或者等于它的某一個 MIN祖先節(jié)點的 β值，則剪枝發(fā)生在該 MAX節(jié)點之下． 中止這個 MAX節(jié)點以下的搜索過程。 3/11/2023 76 某博弈問題示意圖 3/11/2023 77 圖 3/11/2023 78 圖 一字棋第一階段 α β 剪枝方法 3/11/2023 79 （ 1） α剪枝： 如果一個 MIN節(jié)點的 β值小于或等于它的某一個 MAX祖先節(jié)點的 α值，則剪枝發(fā)生在該 MIN節(jié)點之下： 中止這個 MIN節(jié)點以下的搜索過程。 ? 1982年 Pearl證明了 αβ搜索 在所有固定深度的博弈樹搜索算法中是漸進最優(yōu)的。 ? αβ搜索 也被用 John McCarthy的一個學生寫的 Kotok國際象棋程序中。Slagle,1963b)。 ? 描述 αβ搜索 的論文最早發(fā)表于 20世紀 60年代（ Hart和Edwards,1961。 ? 1958年 Newell等人開發(fā)的國際象棋程序 NSS使用了一個簡化版本的 αβ搜索 ，它是第一個使用 αβ搜索 的國際象棋程序。 ? 解決方法：讓搜索樹的產生過程與靜態(tài)估值與返回值的過程同時進行， 在搜索深度不變的情況下，利用已有的搜索信息減少生成的節(jié)點數 ，從而使搜索效率大為提高。利用棋盤對稱性的條件，則第一次調用算法產生的搜索樹如圖 . 3/11/2023 71 圖 3/11/2023 72 圖 一字棋第二階段搜索樹 3/11/2023 73 圖 3/11/2023 74 極小極大過程的問題 ? 把搜索的產生過程與尖端節(jié)點的靜態(tài)估值過程完全分開．在搜索樹完全產生之后，才開始對尖端節(jié)點的估值．這種分開進行的方式導致博弈樹搜索的低效率：節(jié)點數將隨著搜索深度的增加呈指數增長。 靜態(tài)估計函數 e(p)： (1)若 p是 MAX獲勝的格局，則 e(p)＝ ∞； (2)若 p是 MIN獲勝的格局，則 e(p)＝－ ∞。 3/11/2023 69 在九宮格棋盤上，兩位選手輪流在棋盤上擺各自的棋子（每次一枚），誰先取得三子一線的結果就取勝。 IF np∈ MIN，且對 np的任意子節(jié)點 nci， e（ nci）都有值 THEN e（ np） :＝ min{e（ nci） }， REMOVE（ np， CLOSED）； 若 MIN所有子節(jié)點均有值，則該 MIN取其極小值。 ② LOOP1:IF OPEN＝（ ）， THEN GO LOOP2； ③ n:＝ FIRST（ OPEN）， REMOVE（ n， OPEN）， ADD（ n， CLOSED）； ④ IF n可直接判定為贏、輸或平局 THEN e(n):＝ ∞∨ － ∞∨ 0， GO LOOP1 ELSE EXPAND（ n） →{n i}， ADD（ {ni}， T） IF d（ ni）＜ L, THEN ADD（ {ni}， OPEN）， GO LOOP1 ELSE計算 e(ni)， GO LOOP1； ni達到深度 L，計算各端節(jié)點 e值。實現該倒推值的走步就是相對好的走步。 L層節(jié)點的函數值。 3/11/2023 65 ? 極小極大原則 MAX節(jié)點在其 MIN子節(jié)點的倒推值中選 max； MIN節(jié)點在其 MAX子節(jié)點的倒推值中選 min ? 倒推值 在極小極大過程中，第 i層節(jié)點根據第 i+1層節(jié)點的值使用極小極大原則而獲得的值。一直到計算出根節(jié)點的值為止。 3/11/2023 64 極小極大過程基本思想： 當輪到我方走棋時，首先按照一定的搜索深度生成出給定深度以內的所有狀態(tài)，計算所有葉節(jié)點的靜態(tài)估值函數值。 如果對自己不利，則取負值．越小，表示對我方越不利。 對在一定深度處的節(jié)點所代表的局面 進行評價優(yōu)劣的估計值． ? 靜態(tài)估值函數因游戲而異． 如果對自己（ MAX）有利，則取正值，越大，表示對我方越有利。 下面的討論規(guī)定：頂節(jié)點深度 d＝ 0， MAX代表程序方， MIN代表對手方，且 MAX先走。 3/11/2023 62 二、極小極大過程