人工智能知識(shí)表示與推理博弈樹搜索

1、2021/8/141人人 工工 智智 能能Artificial Intelligence (AI)2021/8/1422.4 博弈問題的搜索技術(shù)博弈問題的搜索技術(shù) 2.4.1 博弈問題的表達(dá)博弈問題的表達(dá) 2.4.2 極大極小搜索過程極大極小搜索過程 2.4.3 - 剪枝法剪枝法2021/8/1432.4.1 博弈問題的表達(dá)博弈問題的表達(dá) 博弈博弈是一類具有競爭性的智能活動(dòng)是一類具有競爭性的智能活動(dòng)雙人博弈雙人博弈：即兩位選手對壘，輪流依次走步，：即兩位選手對壘，輪流依次走步，其中任何一方都完全知道對方過去已經(jīng)走過的其中任何一方都完全知道對方過去已經(jīng)走過的棋步和今后可能的走步，其結(jié)果是一方贏棋

2、步和今后可能的走步，其結(jié)果是一方贏(而另而另一方則輸一方則輸)，或雙方和局，或雙方和局2021/8/144博弈的例子博弈的例子： 一字棋一字棋 跳棋跳棋 中國象棋中國象棋 圍棋圍棋 五子棋五子棋2021/8/145雙方的智能活動(dòng)，任何一方都不能單獨(dú)控制雙方的智能活動(dòng)，任何一方都不能單獨(dú)控制博弈過程，而是由雙方輪流實(shí)施其控制對策博弈過程，而是由雙方輪流實(shí)施其控制對策的過程的過程博弈的特點(diǎn)博弈的特點(diǎn)：2021/8/146如何根據(jù)當(dāng)前的棋局，選擇對自己最有利的如何根據(jù)當(dāng)前的棋局，選擇對自己最有利的一步棋一步棋 ？！？！人工智能中研究的博弈問題人工智能中研究的博弈問題：2021/8/147用博弈樹來表

3、示，它是一種特殊的與或圖。節(jié)點(diǎn)用博弈樹來表示，它是一種特殊的與或圖。節(jié)點(diǎn)代表博弈的格局（即棋局），相當(dāng)于狀態(tài)空間中代表博弈的格局（即棋局），相當(dāng)于狀態(tài)空間中的狀態(tài)，反映了博弈的信息。的狀態(tài)，反映了博弈的信息。 與節(jié)點(diǎn)、或節(jié)點(diǎn)與節(jié)點(diǎn)、或節(jié)點(diǎn)隔層交替出現(xiàn)隔層交替出現(xiàn)博弈問題的表示博弈問題的表示：2021/8/148假設(shè)博弈雙方為：假設(shè)博弈雙方為：MAX和和MIN在博弈過程中，規(guī)則是雙方輪流走步。在博弈在博弈過程中，規(guī)則是雙方輪流走步。在博弈樹中，相當(dāng)于博弈雙方輪流擴(kuò)展其所屬節(jié)點(diǎn)樹中，相當(dāng)于博弈雙方輪流擴(kuò)展其所屬節(jié)點(diǎn)為什么為什么與節(jié)點(diǎn)與節(jié)點(diǎn)、或節(jié)點(diǎn)或節(jié)點(diǎn)隔層交替出現(xiàn)隔層交替出現(xiàn)？2021/8/149

4、從從MAX方的角度來看方的角度來看： 所有所有MIN方節(jié)點(diǎn)都是方節(jié)點(diǎn)都是與節(jié)點(diǎn)與節(jié)點(diǎn)理由理由：因?yàn)橐驗(yàn)镸IN方必定選擇最方必定選擇最不利于不利于MAX方的方式來方的方式來擴(kuò)展節(jié)點(diǎn)，只要擴(kuò)展節(jié)點(diǎn)，只要MIN方節(jié)點(diǎn)的子節(jié)點(diǎn)中有一個(gè)方節(jié)點(diǎn)的子節(jié)點(diǎn)中有一個(gè)對對MAX方不利，則該節(jié)點(diǎn)就對方不利，則該節(jié)點(diǎn)就對MAX方不利，故方不利，故為為“與節(jié)點(diǎn)與節(jié)點(diǎn)”MIN好招好招2021/8/1410從從MAX方的角度來看方的角度來看： 所有屬于所有屬于MAX方的節(jié)點(diǎn)都是方的節(jié)點(diǎn)都是“或節(jié)點(diǎn)或節(jié)點(diǎn)”理由理由：因?yàn)閿U(kuò)展因?yàn)閿U(kuò)展MAX方節(jié)點(diǎn)時(shí)，方節(jié)點(diǎn)時(shí)，MAX方可選擇擴(kuò)展最方可選擇擴(kuò)展最有利于自己的節(jié)點(diǎn)，只要可擴(kuò)展的子節(jié)

5、點(diǎn)中有有利于自己的節(jié)點(diǎn)，只要可擴(kuò)展的子節(jié)點(diǎn)中有一個(gè)對已有利，一個(gè)對已有利， 則該節(jié)點(diǎn)就對已有利則該節(jié)點(diǎn)就對已有利MAX好招好招2021/8/1411總之總之從從MAX方來說，與節(jié)點(diǎn)、或節(jié)點(diǎn)交替出現(xiàn)；反之，方來說，與節(jié)點(diǎn)、或節(jié)點(diǎn)交替出現(xiàn)；反之，從從MIN方的角度來看，情況正好相反方的角度來看，情況正好相反2021/8/1412在博弈樹中，先行一方的初始狀態(tài)對應(yīng)著樹的在博弈樹中，先行一方的初始狀態(tài)對應(yīng)著樹的根根節(jié)點(diǎn)節(jié)點(diǎn)，而任何一方獲勝的最終格局為目標(biāo)狀態(tài)，而任何一方獲勝的最終格局為目標(biāo)狀態(tài)，對應(yīng)于樹的對應(yīng)于樹的終葉節(jié)點(diǎn)終葉節(jié)點(diǎn)（可解節(jié)點(diǎn)或本原問題）（可解節(jié)點(diǎn)或本原問題）但是，從但是，從MAX的角度

6、出發(fā)，所有使的角度出發(fā)，所有使MAX獲勝的獲勝的狀態(tài)格局都是本原問題，是可解節(jié)點(diǎn)，而使?fàn)顟B(tài)格局都是本原問題，是可解節(jié)點(diǎn)，而使MIN獲勝的狀態(tài)格局是不可解節(jié)點(diǎn)獲勝的狀態(tài)格局是不可解節(jié)點(diǎn)2021/8/1413例例 Grundy博弈：博弈：分配物品的問題分配物品的問題如果有一堆數(shù)目為如果有一堆數(shù)目為N的錢幣，由兩位選手輪流進(jìn)的錢幣，由兩位選手輪流進(jìn)行分配，要求每個(gè)選手每次把其中某一堆分成數(shù)行分配，要求每個(gè)選手每次把其中某一堆分成數(shù)目目不等不等的兩小堆，直至有一選手不能將錢幣分成的兩小堆，直至有一選手不能將錢幣分成不等的兩堆為止，則判定這位選手為輸家不等的兩堆為止，則判定這位選手為輸家2021/8/1

7、414用數(shù)字序列加上一個(gè)說明來表示一個(gè)狀態(tài)：用數(shù)字序列加上一個(gè)說明來表示一個(gè)狀態(tài)： ( (3, 2, 1, 1, MAX) )數(shù)字序列數(shù)字序列：表示不同堆中錢幣的個(gè)數(shù)：表示不同堆中錢幣的個(gè)數(shù)說明說明：表示下一步由誰來分，即取表示下一步由誰來分，即取MAX或或MIN2021/8/1415現(xiàn)在取現(xiàn)在取N7的簡單情況的簡單情況，并由，并由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,MI

8、N)(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)2021/8/1416對于比較復(fù)雜的博弈問題，只能模擬人的思維對于比較復(fù)雜的博弈問題，只能模擬人的思維“向前看幾步向前看幾步”，然后作出決策，選擇最有利自，然后作出決策，選擇最有利自己的一步。即己的一步。即只能給出幾層走法，然后按照一定只能給出幾層走法，然后按照一定的估算辦法，的估算辦法，決定走一好招決定走一好招2021/8/14172.4.2 極大極小過程極大極小過程 對于復(fù)雜的博弈問題，要規(guī)定搜索深度與時(shí)間，對于復(fù)雜

9、的博弈問題，要規(guī)定搜索深度與時(shí)間，以便于博弈搜索能順利進(jìn)行以便于博弈搜索能順利進(jìn)行假設(shè)由假設(shè)由MAX來選擇走一步棋，問題是：來選擇走一步棋，問題是：MAX如何來選擇一步好棋如何來選擇一步好棋？ 2021/8/1418 對于每一格局（棋局）給出（定義或者倒推）對于每一格局（棋局）給出（定義或者倒推）一個(gè)靜態(tài)估價(jià)函數(shù)值。值越大對一個(gè)靜態(tài)估價(jià)函數(shù)值。值越大對MAX越有利，反越有利，反之越不利之越不利極大極小過程的基本思路極大極小過程的基本思路：2021/8/1419 對于給定的格局，對于給定的格局，MAX給出可能的走法，然給出可能的走法，然后后MIN對應(yīng)地給出相應(yīng)的走法，這樣重復(fù)若干次，對應(yīng)地給出相

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

11、局作為MAX要走的一招棋要走的一招棋2021/8/1421例例：向前看一步的兩層博弈樹向前看一步的兩層博弈樹 2021/8/1422定義靜態(tài)函數(shù)定義靜態(tài)函數(shù)e(P)的一般原則的一般原則：0MAXMIN( )0 0MAX MINe P 占優(yōu)，不利勢均力敵不利，占優(yōu)2021/8/1423 OPEN：存放待擴(kuò)展的節(jié)點(diǎn)，此時(shí)為隊(duì)列，存放待擴(kuò)展的節(jié)點(diǎn)，此時(shí)為隊(duì)列，即以寬度優(yōu)先的策略擴(kuò)展節(jié)點(diǎn)即以寬度優(yōu)先的策略擴(kuò)展節(jié)點(diǎn) CLOSED：存放已擴(kuò)展的節(jié)點(diǎn)，此時(shí)為堆棧，存放已擴(kuò)展的節(jié)點(diǎn)，此時(shí)為堆棧，即后擴(kuò)展的節(jié)點(diǎn)先計(jì)算靜態(tài)估價(jià)函數(shù)值即后擴(kuò)展的節(jié)點(diǎn)先計(jì)算靜態(tài)估價(jià)函數(shù)值 符號符號：2021/8/14241、將初始節(jié)點(diǎn)

12、、將初始節(jié)點(diǎn) S 放入放入 OPEN 表中，開始時(shí)搜索表中，開始時(shí)搜索樹樹 T 由初始節(jié)點(diǎn)由初始節(jié)點(diǎn) S 構(gòu)成構(gòu)成2、若、若 OPEN 表為空，則轉(zhuǎn)表為空，則轉(zhuǎn)53、將、將 OPEN 表中第一個(gè)節(jié)點(diǎn)表中第一個(gè)節(jié)點(diǎn) n 移出放入移出放入CLOSED 表的前端表的前端極大極小搜索過程極大極小搜索過程為為：2021/8/14254、若、若 n 可直接判定為贏、輸、或平局，則令對可直接判定為贏、輸、或平局，則令對應(yīng)的應(yīng)的 e(n)=，-或或 0，并轉(zhuǎn)，并轉(zhuǎn)2；否則擴(kuò)展；否則擴(kuò)展 n，產(chǎn)生產(chǎn)生 n 的后繼節(jié)點(diǎn)集的后繼節(jié)點(diǎn)集 ni ，將將 ni 放入搜索樹放入搜索樹 T 中中2021/8/1426此時(shí)，若

13、搜索深度此時(shí)，若搜索深度d ni 小于預(yù)先設(shè)定的深度小于預(yù)先設(shè)定的深度 k，則將則將 ni 放入放入OPEN表的末端，轉(zhuǎn)表的末端，轉(zhuǎn)2；否則，；否則，ni 達(dá)到深度達(dá)到深度k，計(jì)算計(jì)算e ( ni )，并轉(zhuǎn)并轉(zhuǎn)2（續(xù)）（續(xù)）2021/8/14275、若、若CLOSED表為空，則轉(zhuǎn)表為空，則轉(zhuǎn)8；否則取出；否則取出CLOSED表中的第一個(gè)節(jié)點(diǎn)，記為表中的第一個(gè)節(jié)點(diǎn)，記為 npOpen為空，即已經(jīng)擴(kuò)展完節(jié)點(diǎn)為空，即已經(jīng)擴(kuò)展完節(jié)點(diǎn)步步22021/8/14286、若若 np 屬于屬于MAX層，且對于它的屬于層，且對于它的屬于MIN層層的子節(jié)點(diǎn)的子節(jié)點(diǎn) nci 的的 e ( nci )有值，則：有值，則

14、： e ( np ) =max nci 某一個(gè)節(jié)點(diǎn)屬于某一個(gè)節(jié)點(diǎn)屬于MAX的含義的含義是該節(jié)點(diǎn)等待是該節(jié)點(diǎn)等待MAX來擴(kuò)展來擴(kuò)展2021/8/1429（續(xù)）（續(xù)）若若 np 屬于屬于MIN層，且對于它的屬于層，且對于它的屬于MAX層的子層的子節(jié)點(diǎn)節(jié)點(diǎn) nci 的的 e ( nci )有值，則：有值，則： e ( np )=min nci 2021/8/14307、轉(zhuǎn)、轉(zhuǎn)58、根據(jù)、根據(jù) e (S) 的值，標(biāo)記走步或者結(jié)束（的值，標(biāo)記走步或者結(jié)束（-，或或 0）2021/8/1431第一階段第一階段為為1、2、3、4步，用寬度優(yōu)先算法生成步，用寬度優(yōu)先算法生成規(guī)定深度規(guī)定深度 k 的全部博弈樹，

15、然后對其所有端節(jié)點(diǎn)的全部博弈樹，然后對其所有端節(jié)點(diǎn)計(jì)算計(jì)算 e(P)第二階段第二階段為為5、6、7、8步，是自下而上逐級求節(jié)步，是自下而上逐級求節(jié)點(diǎn)的倒推估價(jià)值，直至求出初始節(jié)點(diǎn)的點(diǎn)的倒推估價(jià)值，直至求出初始節(jié)點(diǎn)的 e(S) 為止，為止，再由再由 e(S) 選得相對較好的走法，過程結(jié)束選得相對較好的走法，過程結(jié)束算法分成兩個(gè)階段算法分成兩個(gè)階段：2021/8/1432等對手走出相應(yīng)的棋，再以當(dāng)前的格局等對手走出相應(yīng)的棋，再以當(dāng)前的格局作為初始節(jié)點(diǎn)，重復(fù)此過程，選擇對自作為初始節(jié)點(diǎn)，重復(fù)此過程，選擇對自己有利的走法己有利的走法2021/8/14332021/8/1434例例： 一字棋的極大極小搜

16、索過程一字棋的極大極小搜索過程 約定約定： 每一方只向前看一步每一方只向前看一步 （擴(kuò)展出二層）（擴(kuò)展出二層） 記記MAX的棋子為的棋子為“”，MIN的棋子為的棋子為“O” 規(guī)定規(guī)定MAX先手先手2021/8/1435 若格局若格局 P 對任何一方都不能獲勝，則對任何一方都不能獲勝，則e(P) =（所有空格上都放上所有空格上都放上MAX的棋子后，的棋子后，MAX的三個(gè)棋子所組成的行、列及對角線的總數(shù)的三個(gè)棋子所組成的行、列及對角線的總數(shù)）-（所有空格上都放上所有空格上都放上MIN的棋子后，的棋子后，MIN的三個(gè)的三個(gè)棋子所組成的行、列及對角線的總數(shù)棋子所組成的行、列及對角線的總數(shù)）靜態(tài)估計(jì)函數(shù)

17、靜態(tài)估計(jì)函數(shù)e(P)定義為定義為：2021/8/1436 若若P是是MAX獲勝，則獲勝，則 e(P)=+ 若若P是是MIN獲勝，則獲勝，則 e(P)=2021/8/1437例：例：計(jì)算下列棋局的靜態(tài)估價(jià)函數(shù)值計(jì)算下列棋局的靜態(tài)估價(jià)函數(shù)值 e(P)=6-4=2 棋局棋局O O OOOO OOOO行行=2列列=2對角對角=2行行=2列列=2對角對角=02021/8/1438利用棋盤的對稱性，有些棋局是等價(jià)的利用棋盤的對稱性，有些棋局是等價(jià)的 OOOO2021/8/1439OOOOOOO OOOO O1010-1-10-10-2121-2-11MAXMIN MAXMAX的走步的走步2021/8/14

18、40第二步第二步OXXOXOXXOXXOXXXOOXXOOXXOXOXOXOXOXO213211OOXXOXXOOXXOOXXOOXXO10201OOXX10OOXXOOXXOOXXOXOXOXXOOXXO2231221OOXXOXOXOOXX11001XOXO3MIN2021/8/1441第三步第三步OOXXXOOXXOOXXXOOXXXOOXXXOOXXXXOOOXXXOOXXOXOOXXOXOOXOXOOOXXXOOOXXXOOXXXOOOXXXOOOOXXXOOXXXOOOXXXOOOXXOXOOOXXXOOOXXXOOXXOXOOXOXXOOOXXXOOOXXXOOXXXOOOXOX

19、X- 021- - - 122101- - - 1111112- 112021/8/1442OOMAXMIN2021/8/1443MAXMINOO2021/8/1444上機(jī)實(shí)驗(yàn)作業(yè)上機(jī)實(shí)驗(yàn)作業(yè)：用用C/C+語言編寫語言編寫“一字棋一字棋”的游戲程序，基本要的游戲程序，基本要求：求：必須實(shí)現(xiàn)極大極小過程必須實(shí)現(xiàn)極大極小過程能夠進(jìn)行能夠進(jìn)行“人人-機(jī)機(jī)”對壘、對壘、“機(jī)機(jī)-機(jī)機(jī)”對壘對壘簡單地顯示對壘過程簡單地顯示對壘過程實(shí)驗(yàn)形式：兩人或者一人一組實(shí)驗(yàn)形式：兩人或者一人一組2021/8/1445實(shí)驗(yàn)報(bào)告格式實(shí)驗(yàn)報(bào)告格式：“一字棋一字棋”游戲的計(jì)算機(jī)程序游戲的計(jì)算機(jī)程序?qū)W號：學(xué)號： 姓名：姓名： 專

20、業(yè)：專業(yè)：摘要摘要1 一字棋游戲的文字描述一字棋游戲的文字描述2 一字棋對壘過程的計(jì)算機(jī)描述和實(shí)現(xiàn)一字棋對壘過程的計(jì)算機(jī)描述和實(shí)現(xiàn)3 實(shí)例（人機(jī)對壘的過程、機(jī)機(jī)對壘的過程）實(shí)例（人機(jī)對壘的過程、機(jī)機(jī)對壘的過程）4 體會(huì)體會(huì)5 參考文獻(xiàn)參考文獻(xiàn)附錄：程序使用的簡單說明附錄：程序使用的簡單說明2021/8/1446提交的材料提交的材料：1、文字報(bào)告；、文字報(bào)告；2、程序原代碼、程序原代碼提交的方式提交的方式：以學(xué)號姓名為壓縮文件名（發(fā)送到：以學(xué)號姓名為壓縮文件名（發(fā)送到 提交的時(shí)間提交的時(shí)間：11月月21日日口頭報(bào)告口頭報(bào)告：介紹報(bào)告的主要內(nèi)容和演示程序，特別：介紹報(bào)告的主要內(nèi)容和演示程序，特別是

21、自己覺得有特色的地方。初步時(shí)間是是自己覺得有特色的地方。初步時(shí)間是12月初。月初。2021/8/14472.4.3 - - 剪枝法剪枝法 極大極小搜索過程由兩個(gè)完全分離的兩個(gè)步驟極大極小搜索過程由兩個(gè)完全分離的兩個(gè)步驟組成：組成：1、用寬度優(yōu)先算法生成一棵博弈搜索樹。用寬度優(yōu)先算法生成一棵博弈搜索樹。2、估計(jì)值的倒推計(jì)算。估計(jì)值的倒推計(jì)算。缺點(diǎn)缺點(diǎn)：這種分離使得搜索的效率比較低。：這種分離使得搜索的效率比較低。2021/8/1448改進(jìn)改進(jìn)：在博弈樹生成過程中同時(shí)計(jì)算端節(jié)點(diǎn)：在博弈樹生成過程中同時(shí)計(jì)算端節(jié)點(diǎn)的估計(jì)值及倒推值，以減少搜索的次數(shù)，這就的估計(jì)值及倒推值，以減少搜索的次數(shù)，這就是是-過

22、程的思想，也稱為過程的思想，也稱為-剪枝法。剪枝法。其中，其中，表示表示MAX節(jié)點(diǎn)的估值的節(jié)點(diǎn)的估值的下界下界（已經(jīng)搜（已經(jīng)搜索到的索到的MAX節(jié)點(diǎn)的節(jié)點(diǎn)的最小值最小值）。 表示表示MIN節(jié)點(diǎn)的估值的節(jié)點(diǎn)的估值的上界上界（已經(jīng)搜（已經(jīng)搜索到的索到的MIN節(jié)點(diǎn)節(jié)點(diǎn)的的最大值最大值） 。 2021/8/1449極大極小過程極大極小過程： 采用寬度優(yōu)先的方式來擴(kuò)展節(jié)點(diǎn)采用寬度優(yōu)先的方式來擴(kuò)展節(jié)點(diǎn)-剪枝法剪枝法： 改用改用深度優(yōu)先深度優(yōu)先的策略來擴(kuò)展節(jié)的策略來擴(kuò)展節(jié)2021/8/1450一字棋的左邊部分一字棋的左邊部分 MAXMIN現(xiàn)擴(kuò)展現(xiàn)擴(kuò)展B得到得到C，其值為，其值為-1，則，則B的倒推值小于等的

23、倒推值小于等于于-1，即，即-1。再擴(kuò)展。再擴(kuò)展B的子節(jié)點(diǎn)，的子節(jié)點(diǎn)，B的值也不會(huì)的值也不會(huì)大于大于-1。結(jié)果是。結(jié)果是B比比A差，不用再擴(kuò)展差，不用再擴(kuò)展B的其他子的其他子節(jié)點(diǎn)了。此處，節(jié)點(diǎn)了。此處，MIN節(jié)點(diǎn)節(jié)點(diǎn)B的的值小于等于其先輩值小于等于其先輩MAX節(jié)點(diǎn)節(jié)點(diǎn)S的的值值，停止擴(kuò)展。停止擴(kuò)展。C擴(kuò)展擴(kuò)展S生成生成A, B,.。擴(kuò)。擴(kuò)展展A生成生成5個(gè)子節(jié)點(diǎn)，倒個(gè)子節(jié)點(diǎn)，倒推得到推得到A的值為的值為-1?？?。可以得到以得到 S 的值大于等于的值大于等于 -1，即，即 -1。2021/8/1451更一般的情況更一般的情況MIN節(jié)節(jié)點(diǎn)的點(diǎn)的不大于不大于其先輩其先輩MAX節(jié)節(jié)點(diǎn)的點(diǎn)的值，則值，則

24、可以中可以中止擴(kuò)展止擴(kuò)展MAX節(jié)節(jié)點(diǎn)的點(diǎn)的 不小于不小于其先輩其先輩MIN節(jié)節(jié)點(diǎn)的點(diǎn)的值，則值，則可以中可以中止擴(kuò)展止擴(kuò)展2021/8/1452一般而言，當(dāng)某一個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)倒推值已一般而言，當(dāng)某一個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)倒推值已經(jīng)給定時(shí)，則倒推值的上下界可以被修正。經(jīng)給定時(shí)，則倒推值的上下界可以被修正。注意注意：MAX節(jié)點(diǎn)的節(jié)點(diǎn)的值非減，值非減，MIN節(jié)點(diǎn)的節(jié)點(diǎn)的值非增。值非增。 2021/8/1453、值的計(jì)算方法值的計(jì)算方法：第一第一、一個(gè)、一個(gè)MAX節(jié)點(diǎn)的節(jié)點(diǎn)的值等于其后繼節(jié)點(diǎn)當(dāng)值等于其后繼節(jié)點(diǎn)當(dāng)前前最大最大的最終倒推值。的最終倒推值。第二第二、一個(gè)、一個(gè)MIN節(jié)點(diǎn)的節(jié)點(diǎn)的值等于其后繼節(jié)點(diǎn)當(dāng)

25、值等于其后繼節(jié)點(diǎn)當(dāng)前前最小最小的最終倒推值。的最終倒推值。 2021/8/1454-剪枝的規(guī)則為剪枝的規(guī)則為：1、若任何、若任何MIN結(jié)點(diǎn)的結(jié)點(diǎn)的值值小于或等于小于或等于任何它的任何它的先輩先輩MAX結(jié)點(diǎn)的結(jié)點(diǎn)的值，則可值，則可中止中止該該MIN結(jié)點(diǎn)以下結(jié)點(diǎn)以下的搜索，此時(shí)這個(gè)的搜索，此時(shí)這個(gè)MIN結(jié)點(diǎn)的最終倒推值就是已結(jié)點(diǎn)的最終倒推值就是已得到的得到的值。值。該值與真正的極大極小的搜索結(jié)果該值與真正的極大極小的搜索結(jié)果的倒推值可能不相同，但是對起始結(jié)點(diǎn)而言，倒的倒推值可能不相同，但是對起始結(jié)點(diǎn)而言，倒推值是相同的，使用它選擇的走步也是相同的。推值是相同的，使用它選擇的走步也是相同的。 2021/8/1455 2、若任何、若任何MAX結(jié)點(diǎn)的結(jié)點(diǎn)的值值大于大于或或等于等于它它的的MIN先輩結(jié)點(diǎn)的先輩結(jié)點(diǎn)的值，則可以中止該值，則可以中止該MAX結(jié)點(diǎn)以下的搜索，此時(shí)這個(gè)結(jié)點(diǎn)以下的搜索，此時(shí)這個(gè)MAX結(jié)結(jié)點(diǎn)處的倒推值就是已得到的點(diǎn)處的倒推值就是已得到的值。值。 2021/8/1456當(dāng)搜索用當(dāng)搜索