人工智能知識(shí)表示與推理博弈樹(shù)搜索復(fù)習(xí)課程課件

1、人 工 智 能Artificial Intelligence (AI)曲維光南京師范大學(xué)計(jì)算機(jī)學(xué)院2022/7/232.4 博弈問(wèn)題的搜索技術(shù) 2.4.1 博弈問(wèn)題的表達(dá) 2.4.2 極大極小搜索過(guò)程 2.4.3 - 剪枝法2022/7/232.4.1 博弈問(wèn)題的表達(dá) 博弈是一類具有競(jìng)爭(zhēng)性的智能活動(dòng)雙人博弈：即兩位選手對(duì)壘，輪流依次走步，其中任何一方都完全知道對(duì)方過(guò)去已經(jīng)走過(guò)的棋步和今后可能的走步，其結(jié)果是一方贏(而另一方則輸)，或雙方和局2022/7/23博弈的例子：一字棋跳棋中國(guó)象棋圍棋五子棋2022/7/23如何根據(jù)當(dāng)前的棋局，選擇對(duì)自己最有利的一步棋 ？！人工智能中研究的博弈問(wèn)題：20

2、22/7/23用博弈樹(shù)來(lái)表示，它是一種特殊的與或圖。節(jié)點(diǎn)代表博弈的格局（即棋局），相當(dāng)于狀態(tài)空間中的狀態(tài)，反映了博弈的信息。 與節(jié)點(diǎn)、或節(jié)點(diǎn)隔層交替出現(xiàn)博弈問(wèn)題的表示：2022/7/23假設(shè)博弈雙方為：MAX和MIN在博弈過(guò)程中，規(guī)則是雙方輪流走步。在博弈樹(shù)中，相當(dāng)于博弈雙方輪流擴(kuò)展其所屬節(jié)點(diǎn)為什么與節(jié)點(diǎn)、或節(jié)點(diǎn)隔層交替出現(xiàn)？2022/7/23從MAX方的角度來(lái)看： 所有MIN方節(jié)點(diǎn)都是與節(jié)點(diǎn)理由：因?yàn)镸IN方必定選擇最不利于MAX方的方式來(lái)擴(kuò)展節(jié)點(diǎn)，只要MIN方節(jié)點(diǎn)的子節(jié)點(diǎn)中有一個(gè)對(duì)MAX方不利，則該節(jié)點(diǎn)就對(duì)MAX方不利，故為“與節(jié)點(diǎn)”MIN好招2022/7/23從MAX方的角度來(lái)看： 所有

3、屬于MAX方的節(jié)點(diǎn)都是“或節(jié)點(diǎn)”理由：因?yàn)閿U(kuò)展MAX方節(jié)點(diǎn)時(shí)，MAX方可選擇擴(kuò)展最有利于自己的節(jié)點(diǎn)，只要可擴(kuò)展的子節(jié)點(diǎn)中有一個(gè)對(duì)已有利， 則該節(jié)點(diǎn)就對(duì)已有利MAX好招2022/7/23總之從MAX方來(lái)說(shuō)，與節(jié)點(diǎn)、或節(jié)點(diǎn)交替出現(xiàn)；反之，從MIN方的角度來(lái)看，情況正好相反2022/7/23在博弈樹(shù)中，先行一方的初始狀態(tài)對(duì)應(yīng)著樹(shù)的根節(jié)點(diǎn)，而任何一方獲勝的最終格局為目標(biāo)狀態(tài)，對(duì)應(yīng)于樹(shù)的終葉節(jié)點(diǎn)（可解節(jié)點(diǎn)或本原問(wèn)題）但是，從MAX的角度出發(fā)，所有使MAX獲勝的狀態(tài)格局都是本原問(wèn)題，是可解節(jié)點(diǎn)，而使MIN獲勝的狀態(tài)格局是不可解節(jié)點(diǎn)2022/7/23例 Grundy博弈：分配物品的問(wèn)題如果有一堆數(shù)目為N的錢

4、幣，由兩位選手輪流進(jìn)行分配，要求每個(gè)選手每次把其中某一堆分成數(shù)目不等的兩小堆，直至有一選手不能將錢幣分成不等的兩堆為止，則判定這位選手為輸家2022/7/23用數(shù)字序列加上一個(gè)說(shuō)明來(lái)表示一個(gè)狀態(tài)： (3, 2, 1, 1, MAX)數(shù)字序列：表示不同堆中錢幣的個(gè)數(shù)說(shuō)明：表示下一步由誰(shuí)來(lái)分，即取MAX或MIN2022/7/23現(xiàn)在取N7的簡(jiǎn)單情況，并由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,MIN)(4,1,1,1,MAX)(

5、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)2022/7/23對(duì)于比較復(fù)雜的博弈問(wèn)題，只能模擬人的思維“向前看幾步”，然后作出決策，選擇最有利自己的一步。即只能給出幾層走法，然后按照一定的估算辦法，決定走一好招2022/7/232.4.2 極大極小過(guò)程 對(duì)于復(fù)雜的博弈問(wèn)題，要規(guī)定搜索深度與時(shí)間，以便于博弈搜索能順利進(jìn)行假設(shè)由MAX來(lái)選擇走一步棋，問(wèn)題是：MAX如何來(lái)選擇一步好棋？ 2022/7/23 對(duì)于每一格局（棋局）給出（定義或者倒推）一個(gè)靜態(tài)估價(jià)函數(shù)值。值越大對(duì)MAX越有利，反之越不利極大

6、極小過(guò)程的基本思路：2022/7/23 對(duì)于給定的格局，MAX給出可能的走法，然后MIN對(duì)應(yīng)地給出相應(yīng)的走法，這樣重復(fù)若干次，得到一組端節(jié)點(diǎn)（必須由MIN走后得到的，由MAX下的棋局）。這一過(guò)程相當(dāng)于節(jié)點(diǎn)擴(kuò)展注：博弈樹(shù)深度或?qū)訑?shù)一定是偶數(shù)2022/7/23 對(duì)于每一個(gè)端節(jié)點(diǎn)，計(jì)算出它們的靜態(tài)估價(jià)函數(shù)，然后自下而上地逐層計(jì)算倒推值，直到MAX開(kāi)始的格局。在MIN下的格局中取估值的最小值，在MAX下格局中取估值的最大值 取估值最大的格局作為MAX要走的一招棋2022/7/23例：向前看一步的兩層博弈樹(shù) 2022/7/23定義靜態(tài)函數(shù)e(P)的一般原則：2022/7/23OPEN：存放待擴(kuò)展的節(jié)點(diǎn)，

7、此時(shí)為隊(duì)列，即以寬度優(yōu)先的策略擴(kuò)展節(jié)點(diǎn)CLOSED：存放已擴(kuò)展的節(jié)點(diǎn)，此時(shí)為堆棧，即后擴(kuò)展的節(jié)點(diǎn)先計(jì)算靜態(tài)估價(jià)函數(shù)值 符號(hào)：2022/7/231、將初始節(jié)點(diǎn) S 放入 OPEN 表中，開(kāi)始時(shí)搜索樹(shù) T 由初始節(jié)點(diǎn) S 構(gòu)成2、若 OPEN 表為空，則轉(zhuǎn)53、將 OPEN 表中第一個(gè)節(jié)點(diǎn) n 移出放入CLOSED 表的前端極大極小搜索過(guò)程為：2022/7/234、若 n 可直接判定為贏、輸、或平局，則令對(duì)應(yīng)的 e(n)=，-或 0，并轉(zhuǎn)2；否則擴(kuò)展 n，產(chǎn)生 n 的后繼節(jié)點(diǎn)集 ni ，將 ni 放入搜索樹(shù) T 中2022/7/23此時(shí)，若搜索深度d ni 小于預(yù)先設(shè)定的深度 k，則將 ni 放入

8、OPEN表的末端，轉(zhuǎn)2；否則，ni 達(dá)到深度k，計(jì)算e ( ni )，并轉(zhuǎn)2（續(xù)）2022/7/235、若CLOSED表為空，則轉(zhuǎn)8；否則取出CLOSED表中的第一個(gè)節(jié)點(diǎn)，記為 npOpen為空，即已經(jīng)擴(kuò)展完節(jié)點(diǎn)步22022/7/236、若 np 屬于MAX層，且對(duì)于它的屬于MIN層的子節(jié)點(diǎn) nci 的 e ( nci )有值，則： e ( np ) =max nci 某一個(gè)節(jié)點(diǎn)屬于MAX的含義是該節(jié)點(diǎn)等待MAX來(lái)擴(kuò)展2022/7/23（續(xù)）若 np 屬于MIN層，且對(duì)于它的屬于MAX層的子節(jié)點(diǎn) nci 的 e ( nci )有值，則： e ( np )=min nci 2022/7/237、

9、轉(zhuǎn)58、根據(jù) e (S) 的值，標(biāo)記走步或者結(jié)束（-，或 0）2022/7/23第一階段為1、2、3、4步，用寬度優(yōu)先算法生成規(guī)定深度 k 的全部博弈樹(shù)，然后對(duì)其所有端節(jié)點(diǎn)計(jì)算 e(P)第二階段為5、6、7、8步，是自下而上逐級(jí)求節(jié)點(diǎn)的倒推估價(jià)值，直至求出初始節(jié)點(diǎn)的 e(S) 為止，再由 e(S) 選得相對(duì)較好的走法，過(guò)程結(jié)束算法分成兩個(gè)階段：2022/7/23等對(duì)手走出相應(yīng)的棋，再以當(dāng)前的格局作為初始節(jié)點(diǎn)，重復(fù)此過(guò)程，選擇對(duì)自己有利的走法2022/7/232022/7/23例： 一字棋的極大極小搜索過(guò)程 約定：每一方只向前看一步 （擴(kuò)展出二層）記MAX的棋子為“”，MIN的棋子為“O”規(guī)定M

10、AX先手2022/7/23 若格局 P 對(duì)任何一方都不能獲勝，則e(P) =（所有空格上都放上MAX的棋子后，MAX的三個(gè)棋子所組成的行、列及對(duì)角線的總數(shù)）-（所有空格上都放上MIN的棋子后，MIN的三個(gè)棋子所組成的行、列及對(duì)角線的總數(shù)）靜態(tài)估計(jì)函數(shù)e(P)定義為：2022/7/23 若P是MAX獲勝，則 e(P)=+ 若P是MIN獲勝，則 e(P)=2022/7/23例：計(jì)算下列棋局的靜態(tài)估價(jià)函數(shù)值 e(P)=6-4=2 棋局OOOOOOOOOO行=2列=2對(duì)角=2行=2列=2對(duì)角=02022/7/23利用棋盤的對(duì)稱性，有些棋局是等價(jià)的 OOOO2022/7/23OOOOOOOOOOOO10

11、10-1-10-10-2121-2-11MAXMIN MAXMAX的走步2022/7/23第二步OXXOXOXXOXXOXXXOOXXOOXXOXOXOXOXOXO213211OOXXOXXOOXXOOXXOOXXO10201OOXX10OOXXOOXXOOXXOXOXOXXOOXXO2231221OOXXOXOXOOXX11001XOXO3MIN2022/7/23第三步OOXXXOOXXOOXXXOOXXXOOXXXOOXXXXOOOXXXOOXXOXOOXXOXOOXOXOOOXXXOOOXXXOOXXXOOOXXXOOOOXXXOOXXXOOOXXXOOOXXOXOOOXXXOOOXXX

12、OOXXOXOOXOXXOOOXXXOOOXXXOOXXXOOOXOXX-021-122101-1111112-112022/7/23OOMAXMIN2022/7/23MAXMINOO2022/7/23上機(jī)實(shí)驗(yàn)作業(yè)：用C/C+語(yǔ)言編寫“一字棋”的游戲程序，基本要求：必須實(shí)現(xiàn)極大極小過(guò)程能夠進(jìn)行“人-機(jī)”對(duì)壘、“機(jī)-機(jī)”對(duì)壘簡(jiǎn)單地顯示對(duì)壘過(guò)程實(shí)驗(yàn)形式：兩人或者一人一組2022/7/23實(shí)驗(yàn)報(bào)告格式：“一字棋”游戲的計(jì)算機(jī)程序?qū)W號(hào)： 姓名： 專業(yè)：摘要1 一字棋游戲的文字描述2 一字棋對(duì)壘過(guò)程的計(jì)算機(jī)描述和實(shí)現(xiàn)3 實(shí)例（人機(jī)對(duì)壘的過(guò)程、機(jī)機(jī)對(duì)壘的過(guò)程）4 體會(huì)5 參考文獻(xiàn)附錄：程序使用的簡(jiǎn)單說(shuō)明2

13、022/7/23提交的材料：1、文字報(bào)告；2、程序原代碼提交的方式：以學(xué)號(hào)姓名為壓縮文件名（發(fā)送到 提交的時(shí)間：11月21日口頭報(bào)告：介紹報(bào)告的主要內(nèi)容和演示程序，特別是自己覺(jué)得有特色的地方。初步時(shí)間是12月初。2022/7/232.4.3 -剪枝法 極大極小搜索過(guò)程由兩個(gè)完全分離的兩個(gè)步驟組成：1、用寬度優(yōu)先算法生成一棵博弈搜索樹(shù)。2、估計(jì)值的倒推計(jì)算。缺點(diǎn)：這種分離使得搜索的效率比較低。2022/7/23改進(jìn)：在博弈樹(shù)生成過(guò)程中同時(shí)計(jì)算端節(jié)點(diǎn)的估計(jì)值及倒推值，以減少搜索的次數(shù)，這就是-過(guò)程的思想，也稱為-剪枝法。其中，表示MAX節(jié)點(diǎn)的估值的下界（已經(jīng)搜索到的MAX節(jié)點(diǎn)的最小值）。 表示MI

14、N節(jié)點(diǎn)的估值的上界（已經(jīng)搜索到的MIN節(jié)點(diǎn)的最大值） 。 2022/7/23極大極小過(guò)程： 采用寬度優(yōu)先的方式來(lái)擴(kuò)展節(jié)點(diǎn)-剪枝法： 改用深度優(yōu)先的策略來(lái)擴(kuò)展節(jié)2022/7/23一字棋的左邊部分 MAXMIN現(xiàn)擴(kuò)展B得到C，其值為-1，則B的倒推值小于等于-1，即-1。再擴(kuò)展B的子節(jié)點(diǎn)，B的值也不會(huì)大于-1。結(jié)果是B比A差，不用再擴(kuò)展B的其他子節(jié)點(diǎn)了。此處，MIN節(jié)點(diǎn)B的值小于等于其先輩MAX節(jié)點(diǎn)S的值，停止擴(kuò)展。C擴(kuò)展S生成A, B,.。擴(kuò)展A生成5個(gè)子節(jié)點(diǎn)，倒推得到A的值為-1。可以得到 S 的值大于等于 -1，即 -1。2022/7/23更一般的情況MIN節(jié)點(diǎn)的不大于其先輩MAX節(jié)點(diǎn)的值，

15、則可以中止擴(kuò)展MAX節(jié)點(diǎn)的 不小于其先輩MIN節(jié)點(diǎn)的值，則可以中止擴(kuò)展2022/7/23一般而言，當(dāng)某一個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)倒推值已經(jīng)給定時(shí)，則倒推值的上下界可以被修正。注意：MAX節(jié)點(diǎn)的值非減，MIN節(jié)點(diǎn)的值非增。 2022/7/23、值的計(jì)算方法：第一、一個(gè)MAX節(jié)點(diǎn)的值等于其后繼節(jié)點(diǎn)當(dāng)前最大的最終倒推值。第二、一個(gè)MIN節(jié)點(diǎn)的值等于其后繼節(jié)點(diǎn)當(dāng)前最小的最終倒推值。 2022/7/23-剪枝的規(guī)則為：1、若任何MIN結(jié)點(diǎn)的值小于或等于任何它的先輩MAX結(jié)點(diǎn)的值，則可中止該MIN結(jié)點(diǎn)以下的搜索，此時(shí)這個(gè)MIN結(jié)點(diǎn)的最終倒推值就是已得到的值。該值與真正的極大極小的搜索結(jié)果的倒推值可能不相同，但是對(duì)

16、起始結(jié)點(diǎn)而言，倒推值是相同的，使用它選擇的走步也是相同的。 2022/7/23 2、若任何MAX結(jié)點(diǎn)的值大于或等于它的MIN先輩結(jié)點(diǎn)的值，則可以中止該MAX結(jié)點(diǎn)以下的搜索，此時(shí)這個(gè)MAX結(jié)點(diǎn)處的倒推值就是已得到的值。 2022/7/23當(dāng)搜索用規(guī)則1終止時(shí)，我們稱進(jìn)行了剪枝，而當(dāng)搜索用規(guī)則2終止時(shí)，我們稱進(jìn)行了剪枝。在搜索過(guò)程中，保存和值，如果出現(xiàn)滿足使用兩條規(guī)則的條件，我們就中止某一些搜索，這一過(guò)程稱為-(剪枝)過(guò)程。 2022/7/23-過(guò)程的主要思想（步驟）:1、采用有界的深度優(yōu)先搜索算法。2、立即計(jì)算端節(jié)點(diǎn)的估值。3、剪枝4、剪枝5、當(dāng)初始節(jié)點(diǎn)的所有后繼節(jié)點(diǎn)的最終倒推值全部給出后，搜索過(guò)程結(jié)束。2022