《人工智能與或圖搜索.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《人工智能與或圖搜索.ppt（35頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

第四章與或圖搜索 4 1問(wèn)題歸約法4 2與或圖4 3與或圖搜索4 4AO 算法4 5博弈樹(shù)的搜索 4 1問(wèn)題歸約法 當(dāng)問(wèn)題復(fù)雜時(shí) 可把初始問(wèn)題分解成若干簡(jiǎn)單的子問(wèn)題 若子問(wèn)題仍復(fù)雜 可再進(jìn)一步分解 直到這些子問(wèn)題的解可直接得到 這種問(wèn)題的描述和求解方法 稱為問(wèn)題歸約法 可直接解答的問(wèn)題稱為本原問(wèn)題 它是不必證明的 自然成立的 歸約法的問(wèn)題表示可由下列三部分組成 1 一個(gè)初始問(wèn)題的描述 2 一組把問(wèn)題變成子問(wèn)題的算子 3 一組本原問(wèn)題的描述問(wèn)題歸約由問(wèn)題出發(fā) 運(yùn)用操作算子產(chǎn)生一些子問(wèn)題 對(duì)子問(wèn)題再運(yùn)用操作算子產(chǎn)生子問(wèn)題的一些子問(wèn)題 一直進(jìn)行到產(chǎn)生的子問(wèn)題都為本原問(wèn)題 則問(wèn)題得解 由于一問(wèn)題所產(chǎn)生的若干子問(wèn)題內(nèi)的關(guān)系是并列的 同時(shí)的 所以 用與或圖便能表示問(wèn)題歸約的狀態(tài)空間 即對(duì)問(wèn)題歸約的描述可以很方便地用一個(gè)與或圖的結(jié)構(gòu)來(lái)表示它 4 2與或圖 與節(jié)點(diǎn) 一個(gè)歸約算子能夠把單個(gè)問(wèn)題變?yōu)閹讉€(gè)子問(wèn)題組成的集合 這時(shí)只有當(dāng)所有子問(wèn)題都有解 該父輩節(jié)點(diǎn)才有解 這種關(guān)系稱為 與 關(guān)系 對(duì)應(yīng)的節(jié)點(diǎn)稱為與節(jié)點(diǎn) 或節(jié)點(diǎn) 幾個(gè)算子適用于同一個(gè)問(wèn)題 從而產(chǎn)生不同的后繼問(wèn)題集合 這時(shí)只要有一個(gè)后繼集合有解 則意味該父輩問(wèn)題有解 此時(shí)關(guān)系是 或 關(guān)系 對(duì)應(yīng)節(jié)點(diǎn)稱為或節(jié)點(diǎn) 與節(jié)點(diǎn)由與運(yùn)算連接 如圖 a 中Q和R 并用一條弧線將相關(guān)的邊連接起來(lái) 這種弧線及所相關(guān)的邊被稱為超弧 或節(jié)點(diǎn)由或運(yùn)算連接 如圖4 1 b 中Q和R 與或圖是一種普遍圖 這種圖被稱為超圖 也就是說(shuō) 超圖是存在超弧的圖 一超弧所相關(guān)的邊數(shù) K 被稱為該超弧的度 實(shí)現(xiàn)的連接為K 連接 K 連接符 假設(shè)節(jié)點(diǎn)N被某個(gè)算子歸約為一個(gè)包含K個(gè)子問(wèn)題的替換集合 K 1 我們用一個(gè)叫做K 連接符的超弧線把它們和節(jié)點(diǎn)N連接起來(lái) 每個(gè)K 連接符從一個(gè)父節(jié)點(diǎn)指向一個(gè)含有K個(gè)后繼節(jié)點(diǎn)的集合 并說(shuō)N有一個(gè)外向連接符K 問(wèn)題歸約描述對(duì)應(yīng)的結(jié)構(gòu)就是一個(gè)與或圖 原始問(wèn)題描述對(duì)應(yīng)于起始節(jié)點(diǎn) 或根節(jié)點(diǎn) 本原問(wèn)題所對(duì)應(yīng)的節(jié)點(diǎn)叫做葉節(jié)點(diǎn) 在某些特殊情況下 不出現(xiàn)任何與節(jié)點(diǎn) 所有超弧的度都為1 此時(shí)的圖成了普通圖 問(wèn)題歸約描述也就成為狀態(tài)空間描述 從圖4 2所示的與或圖中 節(jié)點(diǎn)n0有兩個(gè)連接符 1 連接符指向節(jié)點(diǎn)n1 2 連接符指向節(jié)點(diǎn)集合 n4 n5 對(duì)于節(jié)點(diǎn)n0來(lái)講 n1可稱為或節(jié)點(diǎn) n4 n5可稱為與節(jié)點(diǎn) 圖4 2 與或圖 4 3與或圖搜索 在與或圖上執(zhí)行搜索的過(guò)程 其目的在于表明起始節(jié)點(diǎn)是有解的 也就是說(shuō) 搜索不是去尋找目標(biāo)節(jié)點(diǎn) 而是尋找一個(gè)解圖 一個(gè)節(jié)點(diǎn)被稱為是能解節(jié)點(diǎn) SOLVED 其遞歸定義為 1 終節(jié)點(diǎn)是能解節(jié)點(diǎn) 直接與本原問(wèn)題相關(guān)聯(lián) 2 若非終節(jié)點(diǎn)有 或 子節(jié)點(diǎn)時(shí) 當(dāng)且僅當(dāng)其子節(jié)點(diǎn)至少有一個(gè)能解 該非終節(jié)點(diǎn)才能解 3 若非終節(jié)點(diǎn)有 與 子節(jié)點(diǎn)時(shí) 當(dāng)且僅當(dāng)其子節(jié)點(diǎn)均能解 該非終節(jié)點(diǎn)才能解 一個(gè)節(jié)點(diǎn)被稱為是不能解節(jié)點(diǎn) UNSOLVED 其遞歸定義為 1 沒(méi)有后裔的非終節(jié)點(diǎn)是不能解的節(jié)點(diǎn) 2 若非終節(jié)點(diǎn)有 或 子節(jié)點(diǎn)時(shí) 當(dāng)且僅當(dāng)所有子節(jié)點(diǎn)均不能解時(shí) 該非終節(jié)點(diǎn)才不能解 3 若非終節(jié)點(diǎn)有 與 子節(jié)點(diǎn)時(shí) 當(dāng)至少有一子節(jié)點(diǎn)不能解時(shí) 該非終節(jié)點(diǎn)才不能解 一個(gè)解圖就是那些能解節(jié)點(diǎn)的子圖 是包含一節(jié)點(diǎn) n 到目的節(jié)點(diǎn)集合 N 的 連通的能解節(jié)點(diǎn)的子圖 其定義如下 一個(gè)與或圖G中 從節(jié)點(diǎn)n到節(jié)點(diǎn)集N的解圖記為G G 是G的子圖 1 若n是N的一個(gè)元素 則G 由單個(gè)節(jié)點(diǎn)n組成 2 若n有一個(gè)指向節(jié)點(diǎn)集 n1 nk 的外向連接符K 使得從每一個(gè)節(jié)點(diǎn)ni到N有一個(gè)解圖 i 1 k 則G 由節(jié)點(diǎn)n 連接符K 以及 n1 nk 中的每一個(gè)節(jié)點(diǎn)到N的解圖所組成 3 否則n到N不存在解圖 如果n s為初始節(jié)點(diǎn) 則此解圖即為所求解問(wèn)題的解圖 在對(duì)普通圖的解路求解或搜索中 一般須計(jì)算或估計(jì)其路徑代價(jià) 同樣地 在搜索與或圖解圖的過(guò)程中 也需要進(jìn)行耗散值的計(jì)算 設(shè)連接符的耗散值規(guī)定為 k 連接符的耗散值 k 若解圖的耗散值記為k n N 則可遞歸計(jì)算如下 1 若n是N的一個(gè)元素 則k n N 0 2 若n有一個(gè)外向連接符指向后繼節(jié)點(diǎn)集合 n1 ni 并設(shè)該連接符的耗散值為Cn 則k n N Cn k n1 N k ni N 具有最小耗散值的解圖稱為最佳解圖 其值也用h n 標(biāo)記 求解問(wèn)題的解圖的值為h s 解圖的求法是 從節(jié)點(diǎn)n開(kāi)始 正確選擇一個(gè)外向連接符 如此進(jìn)行下去直到由此產(chǎn)生的每一個(gè)后繼節(jié)點(diǎn)成為集合N中的一個(gè)元素為止 圖4 3給出了上圖所示與或圖中n0 n7 n8 的三個(gè)解圖 解圖的耗散值分別為8 7 5 圖4 3 三個(gè)解圖 與或圖搜索與狀態(tài)空間圖搜索的不同 搜索目的是證明起始節(jié)點(diǎn)是否可解 而可解節(jié)點(diǎn)是遞歸定義的 取決于后繼節(jié)點(diǎn)是否可解 即搜索是否找到可解的葉節(jié)點(diǎn) 因此 搜索有可解標(biāo)示過(guò)程和不可解標(biāo)示過(guò)程 初始節(jié)點(diǎn)被標(biāo)示為可解 則搜索成功結(jié)束 初始節(jié)點(diǎn)被標(biāo)示為不可解 則搜索失敗 一旦發(fā)現(xiàn)不可解節(jié)點(diǎn) 應(yīng)把該節(jié)點(diǎn)從圖中刪去 4 4AO 算法 假設(shè) 估價(jià)函數(shù)q n h n G為當(dāng)前擴(kuò)展生成的與或圖 G 為一后選局部解圖 是G的一個(gè)子圖 h n 是節(jié)點(diǎn)n的啟發(fā)函數(shù) 而q n 是節(jié)點(diǎn)n的估價(jià)函數(shù) 是從節(jié)點(diǎn)n到一組終葉節(jié)點(diǎn)的一個(gè)最優(yōu)解圖的一個(gè)代價(jià)估計(jì) 過(guò)程AO 1 建立一個(gè)搜索圖G G s 計(jì)算q s h s IFGOAL s THENM s SOLVED 開(kāi)始時(shí)圖G只包括s 耗散值估計(jì)為h s 若s是終節(jié)點(diǎn) 則標(biāo)記上能解 2 Untils已標(biāo)記為SOLVED do 3 Begin4 G FIND G 根據(jù)連接符標(biāo)記 指針 找出一個(gè)待擴(kuò)展的局部解圖G G的連接符將在第11步中標(biāo)記 5 n G 中的任一非終節(jié)點(diǎn) 選一個(gè)非終節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn) 6 EXPAND n 生成子節(jié)點(diǎn)集 ni G ADD ni G 計(jì)算q ni h ni 如果ni G IFGOAL ni THENM ni SOLVED 對(duì)G中原未出現(xiàn)的n的子節(jié)點(diǎn)添加到G中 并計(jì)算其耗散值 若n的子節(jié)點(diǎn)為終節(jié)點(diǎn)則加能解標(biāo)記 7 S n 建立含n的單一節(jié)點(diǎn)集合S 待修正的節(jié)點(diǎn)集合 8 UntilS為空 do 9 begin10 REMOVE m S 當(dāng)mc S 從集合S中移出一節(jié)點(diǎn)m 要求這個(gè)m在圖G中的子節(jié)點(diǎn)mc 不出現(xiàn)在S中 從底層開(kāi)始修正 11 根據(jù)下面方法修改m的耗散值q m 對(duì)m指向節(jié)點(diǎn)集 n1i n2i nki 的每一個(gè)連接符i分別計(jì)算qi qi m Ci q n1i q nki q m minqi m 對(duì)m的i個(gè)k 連接符 取計(jì)算結(jié)果最小的那個(gè)連接符的耗散值為節(jié)點(diǎn)m的q m 加指針到minqi m 的連接符上 或把指針修改到minqi m 的連接符上 即原來(lái)指針與新確定的不一致時(shí)應(yīng)刪去 IFM nji SOLVED THENM m SOLVED j 1 2 k 若該連接符的所有子節(jié)點(diǎn)都是能解的 則m也標(biāo)上能解 12 IFM m SOLVED q m q0 m THENADD ma S m能解或修正的耗散值與原先估算q0不同 則把m的所有先輩節(jié)點(diǎn)ma 添加到S中 修正向上傳遞 13 end14 end AO 搜索算法可以理解為兩個(gè)主要過(guò)程的重復(fù) 首先 是一個(gè)自上而下的圖生長(zhǎng)過(guò)程 4 6步 先通過(guò)有標(biāo)記的連接符 找到目前為止最好的一個(gè)局部解圖 然后對(duì)其中一個(gè)非終節(jié)點(diǎn)進(jìn)行擴(kuò)展 并對(duì)其后繼節(jié)點(diǎn)賦估計(jì)耗散值和加能解標(biāo)記 第2過(guò)程是一個(gè)自下而上的估價(jià)函數(shù)值的修正 連接符的標(biāo)記和SOLVED的標(biāo)注過(guò)程 耗散值的修正從剛被擴(kuò)展的節(jié)點(diǎn)n開(kāi)始 其修正耗散值q n 取對(duì)h n 的所有估計(jì)值中最小的一個(gè) 然后根據(jù)耗散值遞歸計(jì)算公式逐級(jí)向上修正其先輩節(jié)點(diǎn)的耗散值 只有下層節(jié)點(diǎn)耗散值修正后 才可能影響到上一層節(jié)點(diǎn)的耗散值 因此必須自底向上一直修正到初始節(jié)點(diǎn) 假設(shè)各節(jié)點(diǎn)的啟發(fā)函數(shù)值分別為 h n0 3 h n1 2 h n2 4 h n3 4 h n4 1 h n5 1 h n6 2 h n7 h n8 0 目標(biāo)節(jié)點(diǎn) k 連接符的耗散值 k 應(yīng)用AO 算法 經(jīng)過(guò)四個(gè)循環(huán) 可找到解圖 在第一次循環(huán)中 擴(kuò)展節(jié)點(diǎn)n0 下一次循環(huán)擴(kuò)展節(jié)點(diǎn)n1 接著擴(kuò)展節(jié)點(diǎn)n5 最后擴(kuò)展節(jié)點(diǎn)n4 在節(jié)點(diǎn)n4被擴(kuò)展之后 節(jié)點(diǎn)n0便被標(biāo)注SOLVED 此時(shí) 通過(guò)向下跟蹤有標(biāo)記的連接符 便獲得了此狀態(tài)空間的解圖 圖4 4 AO 搜索過(guò)程每個(gè)節(jié)點(diǎn)旁邊標(biāo)記的是啟發(fā)函數(shù)h n 值 不帶括號(hào) 或估價(jià)函數(shù)q n 的修正值 帶括號(hào) 短箭頭用來(lái)標(biāo)記連接符 標(biāo)明侯選局部解圖 已經(jīng)標(biāo)注SOLVED的節(jié)點(diǎn)用實(shí)心圓來(lái)表示 4 5博弈樹(shù)的搜索 博弈一直是啟發(fā)式搜索的一個(gè)重要應(yīng)用領(lǐng)域 早在20世紀(jì)60年代就已經(jīng)出現(xiàn)若干個(gè)博弈系統(tǒng) 美國(guó)IBM公司的 深藍(lán) 系統(tǒng)已達(dá)到了國(guó)際特級(jí)大師級(jí)的水平 97年勝了卡斯帕羅夫 2001年 德國(guó)的 更弗里茨 軟件擊敗了世界排名10位中的9位 本節(jié)所指博弈問(wèn)題是指二人完備博弈 1 由二人對(duì)壘 二人嚴(yán)格地輪流走步 自己的走步自己選擇 2 任何一方都完全知道對(duì)方過(guò)去的走步情況和今后可能的走步 不包括碰運(yùn)氣的情況 由于在決定自己走步時(shí)只需考慮對(duì)自己有利的一步 或 而考察對(duì)方時(shí) 則應(yīng)考慮對(duì)方所有可能的走步 與 因此 能夠利用與或圖搜索算法來(lái)解決博弈問(wèn)題 另外 由于兩人嚴(yán)格地輪流走步 使博弈狀態(tài)圖呈現(xiàn)出嚴(yán)格的與或圖的交替層次 所以 可設(shè)計(jì)特殊的與或圖搜索算法 博弈樹(shù)搜索算法 使搜索更有效 4 5 1Grundy博弈 例 假設(shè)桌上放有一堆 7個(gè) 錢(qián)幣 由兩人輪流進(jìn)行分堆 要求每人每次只把其中某堆錢(qián)幣分成數(shù)目不相等的兩小堆 最后不能分下去的人為負(fù) 該問(wèn)題的描述 綜合數(shù)據(jù)庫(kù) 用無(wú)序數(shù)字序列x1 x2 xn表示n堆錢(qián)幣不同的個(gè)數(shù) 再用兩個(gè)說(shuō)明符號(hào)MIN方和MAX方代表選手 無(wú)序數(shù)列和符號(hào)M組合 x1 x2 xn M 就代表該由某個(gè)選手走步的狀態(tài) MAX方代表努力贏的一方 或盡力將其贏的幾率最大化的一方 而MIN方代表力圖使MAX方偏離取勝目標(biāo)的另一方 博弈雙方總是偏向最有利于自己的狀態(tài)前進(jìn) 反過(guò)來(lái)說(shuō) 也就是MIN方和MAX方總是移向最不利于對(duì)方的狀態(tài) 規(guī)則 圖4 5 Grundy博弈問(wèn)題狀態(tài)空間圖 設(shè)初始狀態(tài)為 7 MIN 則該問(wèn)題的狀態(tài)空間圖如圖4 5所示 圖中所有終節(jié)點(diǎn)均表示要走步的選手必輸?shù)那闆r 取勝方的目標(biāo)是設(shè)法使棋局發(fā)展為結(jié)束在對(duì)方走步時(shí)的終節(jié)點(diǎn)上 因此節(jié)點(diǎn)A是MAX的搜索目標(biāo) 而節(jié)點(diǎn)B C則為MIN的搜索目標(biāo) 搜索策略要考慮的問(wèn)題是 以MAX方的角度 對(duì)MIN走步后的每一個(gè)MAX節(jié)點(diǎn) 該狀態(tài)由MIN控制 必須證明MAX對(duì)MIN所有可能走的每一個(gè)棋局對(duì)弈后都能夠獲勝 即MAX必須考慮應(yīng)付MIN的所有招法 這是一個(gè)與的含義 因此含有MAX符號(hào)的節(jié)點(diǎn)可看成與節(jié)點(diǎn) 對(duì)MAX走步后的每一個(gè)MIN節(jié)點(diǎn) 該狀態(tài)由MAX控制 只需要證明MAX有一步能走贏就可以 即MAX只要考慮能走出一步棋使MIN無(wú)法招架就成 因此含有MIN符號(hào)的節(jié)點(diǎn)可看成或節(jié)點(diǎn) 于是對(duì)弈過(guò)程的搜索圖就呈現(xiàn)出與或圖表示的形式 從搜索圖可以看出 MAX方存在完全取勝的策略 圖中所示部分就代表了這種策略 這時(shí)不論MIN怎么走 MAX方均可取勝 因而尋找MAX的取勝的策略便和求與或圖的解圖 能解 能勝 一致起來(lái) 即MAX要獲勝 必須對(duì)所有與節(jié)點(diǎn)取勝 但只需對(duì)一個(gè)或節(jié)點(diǎn)取勝 這就是一個(gè)解圖 因此實(shí)現(xiàn)一種取勝的策略就是搜索一個(gè)解圖的問(wèn)題 解圖就代表一種完整的博弈策略 4 5 2博弈樹(shù)的極大極小搜索法 極大極小搜索法是考慮雙方對(duì)弈若干步之后 從可能的走步中選一步相對(duì)好的走步來(lái)走 即在有限的搜索深度范圍內(nèi)進(jìn)行求解 這需定義一個(gè)評(píng)價(jià)函數(shù)f 以便對(duì)棋局的勢(shì)態(tài) 節(jié)點(diǎn) 作出優(yōu)劣估值 一般規(guī)定有利于MAX的勢(shì)態(tài) f n 取正值 有利于MIN的勢(shì)態(tài) f n 取負(fù)值 勢(shì)均力敵 f n 0 若f n 表示MAX方獲勝 若f n 表示MIN方獲勝 假定開(kāi)始由MAX選擇走一步棋 如何選擇一步好棋 首先 對(duì)給定的格局MAX給出可能的走法 然后MIN對(duì)MAX的每一步走法 又給出可能的走法 這樣進(jìn)行若干次 一定深度 得到一組端節(jié)點(diǎn) 每個(gè)端節(jié)點(diǎn)有相應(yīng)的靜態(tài)函數(shù)值 然后由底向上逐級(jí)計(jì)算倒推估值 在MIN處取其下層估值中最小者 在MAX處取其下層估值最大者 一直到MAX的開(kāi)始棋局 取其下層估值中最大的格局作為要走的第一步 圖4 6是一個(gè)表示考慮兩步棋的例子 圖中端節(jié)點(diǎn)的數(shù)字是用靜態(tài)函數(shù)f n 計(jì)算得到 其他節(jié)點(diǎn)應(yīng)用倒推的方法取值 圖中A B C是MIN方要走步的節(jié)點(diǎn) MAX方應(yīng)考慮其最壞的情況 故其估值應(yīng)分別取其子節(jié)點(diǎn)估值中最小者 而s是MAX走步的節(jié)點(diǎn) 可考慮最好的情況 故其估值應(yīng)取A B C值中最大者 這樣 確定了f s 2 也就是說(shuō) 相對(duì)較優(yōu)的走步是走向B 因?yàn)閺腂出發(fā) 對(duì)手不可能產(chǎn)生比f(wàn) s 2更差的效果 當(dāng)用端節(jié)點(diǎn)的靜態(tài)估計(jì)函數(shù)值求倒推值時(shí) 兩位選手應(yīng)采用不同的策略 從下往上逐層交替使用極大和極小的選值方法 故稱為極大極小過(guò)程 圖4 6 f n 求值過(guò)程 下面說(shuō)明極大極小過(guò)程MINLMAX 思維過(guò)程 1 T s MAX OPEN s CLOSED 開(kāi)始時(shí)樹(shù)由初始節(jié)點(diǎn)構(gòu)成 OPEN表只含有S 2 LOOP1 IFOPEN THENGOLOOP2 3 n FIRST OPEN REMOVE n OPEN ADD n CLOSED 將n放到CLOSED表的前面 使第5步操作時(shí)深度大的節(jié)點(diǎn)優(yōu)先被取出 OPEN表先進(jìn)先出 CLOSED表后進(jìn)先出 4 IFn可直接判定為贏 輸或平局THENf n 0 GOLOOP1ELSEEXPAND n ni ADD ni T IFd ni kTHENADD ni OPEN GOLOOP1ELSE計(jì)算f ni ni達(dá)到深度k 計(jì)算各端節(jié)點(diǎn)f值 5 LOOP2 IFCLOSED NIL THENGOLOOP3ELSEnd FIRST CLOSED 6 IF nd MAX f nci MIN 有值 THENf nd max f nci REMOVE nd CLOSED GOLOOP2 若MAX所有子節(jié)點(diǎn)均有值 則該MAX取其極大值 ELSEIF nd MIN f nci MAX 有值 THENf nd min f nci REMOVE nd CLOSED GOLOOP2 若MIN所有子節(jié)點(diǎn)均有值 則該MIN取其極小值 7 ELSEGOLOOP1 若有子節(jié)點(diǎn)的值待確定 進(jìn)入其它分支繼續(xù)進(jìn)行節(jié)點(diǎn)的擴(kuò)展 8 LOOP3 IFf s NILTHENEXIT END M Move T s有值 或則結(jié)束或標(biāo)記走步 例 在九宮格棋盤(pán)上 甲乙 MAX和MIN 二人輪流在空格中放入自己的棋子 一次一枚 誰(shuí)先使自己的三子成一線就獲勝 設(shè)甲先走用 表示 乙用 表示 p表示某種格局 f p 表示對(duì)格局的評(píng)價(jià)值 為便于討論 將棋盤(pán)的整行 整列或整條對(duì)角線稱為贏線 如果一條贏線上只有 方的棋子或?yàn)榭?而沒(méi)有對(duì)方的棋子 那么這條贏線就稱為 方的贏線 f p 定義如下 1 MAX勝 f p 2 MIN勝 f p 3 若p不是可定勝負(fù)的格局 則f p fMAX p fMIN p 其中 fMAX p 表示當(dāng)前棋局所有空格都放上MAX的棋子后 MAX的三個(gè)棋子成線的總數(shù) 同理 fMIN p 表示當(dāng)前棋局所有空格都放上MIN的棋子后 MIN的三個(gè)棋子成線的總數(shù) 設(shè)考慮走兩步的搜索過(guò)程 利用棋盤(pán)對(duì)稱性的條件 則第一次調(diào)用算法產(chǎn)生的搜索樹(shù)如圖4 7所示 圖中端節(jié)點(diǎn)下面是計(jì)算的f p 值 非端節(jié)點(diǎn)的倒推值標(biāo)記在圓圈內(nèi) 為了使初始節(jié)點(diǎn)具有最大的倒推值 可以看出第1步的最好走法是把棋子下到中央位置 圖4 7 一字棋第1階段的搜索樹(shù) 設(shè)MAX走完第一步后 MAX的對(duì)手是在 上的格子下子 這時(shí)MAX就要在新的格局下調(diào)用算法 第2次產(chǎn)生的搜索樹(shù)如圖4 8所示 圖4 8 一字棋第2階段的搜索樹(shù) 類(lèi)似地第3次的搜索樹(shù)如圖4 9所示 至此MAX走完最好的走步后 不論MIN怎么走 都無(wú)法挽回?cái)【?因此只好認(rèn)輸了 否則還要進(jìn)行下面的搜索 圖4 9 一字棋第3階段的搜索樹(shù) 4 5 3 搜索過(guò)程 在極大極小過(guò)程中 把生成樹(shù)和棋局估值兩個(gè)過(guò)程完全分離 即先生成全部的搜索樹(shù) 然后再進(jìn)行端節(jié)點(diǎn)靜態(tài)估值和倒推值計(jì)算 這使效率大大降低 如圖4 9中 其中一個(gè)MIN節(jié)點(diǎn)要全部生成A B C D四個(gè)節(jié)點(diǎn) 然后還要逐個(gè)計(jì)算其靜態(tài)估值 最后在求倒推值階段 才賦給這個(gè)MIN節(jié)點(diǎn)的倒推值 若兩個(gè)過(guò)程同時(shí)進(jìn)行 再根據(jù)一定的條件判斷 有可能盡早剪掉一些無(wú)用的分支 那么就可能減少搜索工作量 這是 搜索過(guò)程的基本思想 如 生成節(jié)點(diǎn)A后 馬上進(jìn)行靜態(tài)估值 得知f A 后 就可以斷定再生成其余節(jié)點(diǎn)及進(jìn)行靜態(tài)計(jì)算是多余的 可以馬上對(duì)MIN節(jié)點(diǎn)賦倒推值 絲毫不會(huì)影響MAX的最好優(yōu)先走步的選擇 為了使生成和估值過(guò)程緊密結(jié)合 采用有界深度優(yōu)先策略進(jìn)行搜索 這樣當(dāng)生成達(dá)到規(guī)定深度的節(jié)點(diǎn)時(shí) 就立即計(jì)算其靜態(tài)估值函數(shù) 而一旦某個(gè)非端節(jié)點(diǎn)有條件確定其倒推值時(shí)就立即計(jì)算賦值 圖4 10 一字棋第1階段 剪枝方法 從圖4 10中標(biāo)記的節(jié)點(diǎn)生成順序號(hào) 也表示節(jié)點(diǎn)編號(hào) 看出 生成并計(jì)算完第6個(gè)節(jié)點(diǎn)后 第1個(gè)節(jié)點(diǎn)倒推值完全確定 可立即賦給倒推值 1 這時(shí)對(duì)初始節(jié)點(diǎn)來(lái)說(shuō) 雖然其他子節(jié)點(diǎn)尚未生成 但由于S屬極大值層 可以推斷其倒推值不會(huì)小于 1 我們稱極大值層的這個(gè)下界值為 即可以確定S的 1 這說(shuō)明S實(shí)際的倒推值絕不會(huì)比 1更小 具體的取值還取決于其他后繼節(jié)點(diǎn)的倒推值 因此繼續(xù)生成搜索樹(shù) 當(dāng)?shù)?個(gè)節(jié)點(diǎn)生成出來(lái)并計(jì)算得靜態(tài)估值為 1后 就可以斷定第7個(gè)節(jié)點(diǎn)的倒推值不可能大于 1 我們稱極小值層的這個(gè)上界值為 即可確定節(jié)點(diǎn)7的 1 有了極小值層的 值 很容易發(fā)現(xiàn)若 時(shí) 節(jié)點(diǎn)7的其他子節(jié)點(diǎn)不必再生成 這不影響高一層極大值的選取 因S的極大值不可能比這個(gè) 值還小 再生成無(wú)疑是多余的 因此可以進(jìn)行剪枝 于是 在搜索過(guò)程中通過(guò)記錄并比較倒推值的上下界并進(jìn)行比較 就可以實(shí)現(xiàn)修剪操作 稱這種操作為 剪枝 類(lèi)似的還有 剪枝 統(tǒng)稱為 剪枝技術(shù) 在實(shí)際修剪中 還可以隨時(shí)修正 但極大值層的倒推值下界值 永不下降 實(shí)際的倒推值取其后繼節(jié)點(diǎn)最終確定的倒推值中最大的一個(gè)倒推值 而極小值層的倒推值上界值 永不上升 其倒推值取其后繼節(jié)點(diǎn)最終確定的倒推值中最小的一個(gè)倒推值 總結(jié)上述敘述 在一個(gè)分支上進(jìn)行 剪枝的規(guī)則描述如下 1 剪枝 若任一極小值層節(jié)點(diǎn)的 值小于或等于它任一先輩極大值層節(jié)點(diǎn)的 值 即 先輩層 后繼層 則可以終止該極小值層中這個(gè)MIN節(jié)點(diǎn)以下的搜索 并設(shè)置這個(gè)MIN節(jié)點(diǎn)的最終的倒推值為 極小值層節(jié)點(diǎn)的剪枝 2 剪枝 若任一極大值層節(jié)點(diǎn)的 值大于或等于它任一先輩極小值層節(jié)點(diǎn)的 值 即 后繼層 先輩層 則可以終止該極大值層中這個(gè)MAX節(jié)點(diǎn)以下的搜索過(guò)程 并設(shè)置這個(gè)MAX節(jié)點(diǎn)的最終倒推值為 極大值層節(jié)點(diǎn)的剪枝 過(guò)程 保存 和 值 并且當(dāng)滿足條件時(shí)便進(jìn)行剪枝 當(dāng)初始節(jié)點(diǎn)的全部后繼節(jié)點(diǎn)的最終倒推值都給出時(shí) 過(guò)程即結(jié)束 而最好的優(yōu)先走步就是走向具有最高倒推值的那個(gè)后繼節(jié)點(diǎn) 顯然剪枝后選得的最好優(yōu)先走步 其結(jié)果與不剪枝的MAXMIN方法所得的完全相同 因而 過(guò)程具有較高的效率 比較是在極大值層節(jié)點(diǎn)和極小值層節(jié)點(diǎn)間進(jìn)行的 比較時(shí)是與先輩層節(jié)點(diǎn) 已經(jīng)有了值的那些節(jié)點(diǎn) 不僅限于父輩 只有一個(gè)節(jié)點(diǎn)的值固定以后 其值才能夠向其父節(jié)點(diǎn)傳遞 剪枝搜索得到的最佳走步與極大極小方法得到的結(jié)果一致 但效率會(huì)提高 生成搜索圖和剪枝過(guò)程同時(shí)進(jìn)行 注意幾個(gè)問(wèn)題 圖4 11給出了d 4的博弈樹(shù)的 搜索過(guò)程 其中括號(hào)中的數(shù)字表示求靜態(tài)估值及倒推值過(guò)程的次序編號(hào) 該圖詳細(xì)表示出 剪枝過(guò)程的若干細(xì)節(jié) 初始節(jié)點(diǎn)的最終倒推值是1 該值等于某一個(gè)端節(jié)點(diǎn)的靜態(tài)估值 圖4 11 搜索過(guò)程的博弈樹(shù) 剪枝 剪枝 剪枝 剪枝