人工智能2.4 博弈問題的搜索技術(shù)

2023/10/19人工智能ArtificialIntelligence(AI)2023/10/192.4博弈問題的搜索技術(shù)2.4.1博弈問題的表達(dá)2.4.2極大極小搜索過程2.4.3-剪枝法2023/10/192.4.1博弈問題的表達(dá)

博弈是一類具有競爭性的智能活動雙人博弈：即兩位選手對壘，輪流依次走步，其中任何一方都完全知道對方過去已經(jīng)走過的棋步和今后可能的走步，其結(jié)果是一方贏(而另一方則輸)，或雙方和局2023/10/19博弈的例子：一字棋跳棋中國象棋圍棋五子棋2023/10/19雙方的智能活動，任何一方都不能單獨(dú)控制博弈過程，而是由雙方輪流實施其控制對策的過程博弈的特點(diǎn)：2023/10/19如何根據(jù)當(dāng)前的棋局，選擇對自己最有利的一步棋？！人工智能中研究的博弈問題：2023/10/19用博弈樹來表示，它是一種特殊的與或圖。節(jié)點(diǎn)代表博弈的格局（即棋局），相當(dāng)于狀態(tài)空間中的狀態(tài)，反映了博弈的信息。與節(jié)點(diǎn)、或節(jié)點(diǎn)隔層交替出現(xiàn)博弈問題的表示：2023/10/19假設(shè)博弈雙方為：MAX和MIN在博弈過程中，規(guī)則是雙方輪流走步。在博弈樹中，相當(dāng)于博弈雙方輪流擴(kuò)展其所屬節(jié)點(diǎn)為什么與節(jié)點(diǎn)、或節(jié)點(diǎn)隔層交替出現(xiàn)？2023/10/19從MAX方的角度來看：所有MIN方節(jié)點(diǎn)都是與節(jié)點(diǎn)理由：因為MIN方必定選擇最不利于MAX方的方式來擴(kuò)展節(jié)點(diǎn)，只要MIN方節(jié)點(diǎn)的子節(jié)點(diǎn)中有一個對MAX方不利，則該節(jié)點(diǎn)就對MAX方不利，故為“與節(jié)點(diǎn)”MIN好招2023/10/19從MAX方的角度來看：

所有屬于MAX方的節(jié)點(diǎn)都是“或節(jié)點(diǎn)”理由：因為擴(kuò)展MAX方節(jié)點(diǎn)時，MAX方可選擇擴(kuò)展最有利于自己的節(jié)點(diǎn)，只要可擴(kuò)展的子節(jié)點(diǎn)中有一個對已有利，

則該節(jié)點(diǎn)就對已有利MAX好招2023/10/19總之從MAX方來說，與節(jié)點(diǎn)、或節(jié)點(diǎn)交替出現(xiàn)；反之，從MIN方的角度來看，情況正好相反2023/10/19在博弈樹中，先行一方的初始狀態(tài)對應(yīng)著樹的根節(jié)點(diǎn)，而任何一方獲勝的最終格局為目標(biāo)狀態(tài)，對應(yīng)于樹的終葉節(jié)點(diǎn)（可解節(jié)點(diǎn)或本原問題）但是，從MAX的角度出發(fā)，所有使MAX獲勝的狀態(tài)格局都是本原問題，是可解節(jié)點(diǎn)，而使MIN獲勝的狀態(tài)格局是不可解節(jié)點(diǎn)2023/10/19例

Grundy博弈：分配物品的問題如果有一堆數(shù)目為N的錢幣，由兩位選手輪流進(jìn)行分配，要求每個選手每次把其中某一堆分成數(shù)目不等的兩小堆，直至有一選手不能將錢幣分成不等的兩堆為止，則判定這位選手為輸家2023/10/19用數(shù)字序列加上一個說明來表示一個狀態(tài)：

(3,2,1,1,MAX)數(shù)字序列：表示不同堆中錢幣的個數(shù)說明：表示下一步由誰來分，即取MAX或MIN2023/10/19現(xiàn)在取N＝7的簡單情況，并由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)(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)2023/10/19對于比較復(fù)雜的博弈問題，只能模擬人的思維“向前看幾步”，然后作出決策，選擇最有利自己的一步。即只能給出幾層走法，然后按照一定的估算辦法，決定走一好招2023/10/192.4.2極大極小過程

對于復(fù)雜的博弈問題，要規(guī)定搜索深度與時間，以便于博弈搜索能順利進(jìn)行假設(shè)由MAX來選擇走一步棋，問題是：MAX如何來選擇一步好棋？

2023/10/19①

對于每一格局（棋局）給出（定義或者倒推）一個靜態(tài)估價函數(shù)值。值越大對MAX越有利，反之越不利極大極小過程的基本思路：2023/10/19②

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

取估值最大的格局作為MAX要走的一招棋2023/10/19例：向前看一步的兩層博弈樹

2023/10/19定義靜態(tài)函數(shù)e(P)的一般原則：2023/10/19OPEN：存放待擴(kuò)展的節(jié)點(diǎn)，此時為隊列，即以寬度優(yōu)先的策略擴(kuò)展節(jié)點(diǎn)CLOSED：存放已擴(kuò)展的節(jié)點(diǎn)，此時為堆棧，即后擴(kuò)展的節(jié)點(diǎn)先計算靜態(tài)估價函數(shù)值

符號：2023/10/191、將初始節(jié)點(diǎn)S放入OPEN表中，開始時搜索樹T由初始節(jié)點(diǎn)S構(gòu)成2、若OPEN表為空，則轉(zhuǎn)53、將OPEN

表中第一個節(jié)點(diǎn)n移出放入CLOSED表的前端極大極小搜索過程為：2023/10/194、若n可直接判定為贏、輸、或平局，則令對應(yīng)的

e(n)=∞，-∞或0，并轉(zhuǎn)2；否則擴(kuò)展n，產(chǎn)生n的后繼節(jié)點(diǎn)集{ni}，將{ni

}放入搜索樹T

中2023/10/19此時，若搜索深度d{ni}小于預(yù)先設(shè)定的深度k，則將{ni}放入OPEN表的末端，轉(zhuǎn)2；否則，ni

達(dá)到深度k，計算e(ni)，并轉(zhuǎn)2（續(xù)）2023/10/195、若CLOSED表為空，則轉(zhuǎn)8；否則取出CLOSED表中的第一個節(jié)點(diǎn)，記為npOpen為空，即已經(jīng)擴(kuò)展完節(jié)點(diǎn)步22023/10/196、若np

屬于MAX層，且對于它的屬于MIN層的子節(jié)點(diǎn)nci

的e

(nci

)有值，則：

e(np

)=max{nci

}某一個節(jié)點(diǎn)屬于MAX的含義是該節(jié)點(diǎn)等待MAX來擴(kuò)展2023/10/19（續(xù)）若np屬于MIN層，且對于它的屬于MAX層的子節(jié)點(diǎn)nci

的e(nci

)有值，則：

e(np

)=min{nci

}2023/10/197、轉(zhuǎn)58、根據(jù)e(S)

的值，標(biāo)記走步或者結(jié)束（-∞，∞或0）2023/10/19第一階段為1、2、3、4步，用寬度優(yōu)先算法生成規(guī)定深度k

的全部博弈樹，然后對其所有端節(jié)點(diǎn)計算e(P)第二階段為5、6、7、8步，是自下而上逐級求節(jié)點(diǎn)的倒推估價值，直至求出初始節(jié)點(diǎn)的e(S)

為止，再由e(S)

選得相對較好的走法，過程結(jié)束算法分成兩個階段：2023/10/19等對手走出相應(yīng)的棋，再以當(dāng)前的格局作為初始節(jié)點(diǎn)，重復(fù)此過程，選擇對自己有利的走法2023/10/192023/10/19例：

一字棋的極大極小搜索過程

約定：每一方只向前看一步（擴(kuò)展出二層）記MAX的棋子為“×”，MIN的棋子為“O”規(guī)定MAX先手2023/10/19①

若格局P

對任何一方都不能獲勝，則e(P)=（所有空格上都放上MAX的棋子后，MAX的三個棋子所組成的行、列及對角線的總數(shù)）-（所有空格上都放上MIN的棋子后，MIN的三個棋子所組成的行、列及對角線的總數(shù)）靜態(tài)估計函數(shù)e(P)定義為：2023/10/19②

若P是MAX獲勝，則e(P)=+∞③

若P是MIN獲勝，則e(P)=－∞2023/10/19例：計算下列棋局的靜態(tài)估價函數(shù)值

e(P)=6-4=2

棋局O××O×××××××OOOO×OOOO行=2列=2對角=2行=2列=2對角=02023/10/19利用棋盤的對稱性，有些棋局是等價的

O××OO××O2023/10/19××××O×O×O×O×OO×O×O×O×O××O×O1010-1-10-10-2121-2-11MAXMINMAXMAX的走步2023/10/19第二步OXXOXOXXOXXOXXXOOXXOOXXOXOXOXOXOXO213211OOXXOXXOOXXOOXXOOXXO10201OOXX10OOXXOOXXOOXXOXOXOXXOOXXO2231221OOXXOXOXOOXX11001XOXO3MIN2023/10/19第三步OOXXXOOXXOOXXXOOXXXOOXXXOOXXXXOOOXXXOOXXOXOOXXOXOOXOXOOOXXXOOOXXXOOXXXOOOXXXOOOOXXXOOXXXOOOXXXOOOXXOXOOOXXXOOOXXXOOXXOXOOXOXXOOOXXXOOOXXXOOXXXOOOXOXX-021---122101---1111112-112023/10/19×OO××MAXMIN2023/10/19MAXMIN×O××O2023/10/19上機(jī)實驗作業(yè)：用C/C++語言編寫“一字棋”的游戲程序，基本要求：必須實現(xiàn)極大極小過程能夠進(jìn)行“人-機(jī)”對壘、“機(jī)-機(jī)”對壘簡單地顯示對壘過程實驗形式：兩人或者一人一組2023/10/19實驗報告格式：“一字棋”游戲的計算機(jī)程序?qū)W號：姓名：專業(yè)：摘要1

一字棋游戲的文字描述2

一字棋對壘過程的計算機(jī)描述和實現(xiàn)3

實例（人機(jī)對壘的過程、機(jī)機(jī)對壘的過程）4體會5

參考文獻(xiàn)附錄：程序使用的簡單說明2023/10/19提交的材料：1、文字報告；2、程序原代碼提交的方式：以學(xué)號姓名為壓縮文件名（發(fā)送到wgqu提交的時間：11月21日口頭報告：介紹報告的主要內(nèi)容和演示程序，特別是自己覺得有特色的地方。初步時間是12月初。2023/10/192.4.3

-

剪枝法

極大極小搜索過程由兩個完全分離的兩個步驟組成：1、用寬度優(yōu)先算法生成一棵博弈搜索樹。2、估計值的倒推計算。缺點(diǎn)：這種分離使得搜索的效率比較低。2023/10/19改進(jìn)：在博弈樹生成過程中同時計算端節(jié)點(diǎn)的估計值及倒推值，以減少搜索的次數(shù)，這就是α-β過程的思想，也稱為α-β剪枝法。其中，α表示MAX節(jié)點(diǎn)的估值的下界（已經(jīng)搜索到的MAX節(jié)點(diǎn)的最小值）。

β表示MIN節(jié)點(diǎn)的估值的上界（已經(jīng)搜索到的MIN節(jié)點(diǎn)的最大值）

。

2023/10/19極大極小過程：采用寬度優(yōu)先的方式來擴(kuò)展節(jié)點(diǎn)α-β剪枝法：改用深度優(yōu)先的策略來擴(kuò)展節(jié)2023/10/19一字棋的左邊部分

MAXMIN現(xiàn)擴(kuò)展B得到C，其值為-1，則B的倒推值小于等于-1，即β≤-1。再擴(kuò)展B的子節(jié)點(diǎn)，B的值也不會大于-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個子節(jié)點(diǎn)，倒推得到A的值為-1?？梢缘玫絊

的值大于等于-1，即α≥-1。2023/10/19更一般的情況MIN節(jié)點(diǎn)的β不大于其先輩MAX節(jié)點(diǎn)的α值，則可以中止擴(kuò)展MAX節(jié)點(diǎn)的α

不小于其先輩MIN節(jié)點(diǎn)的β值，則可以中止擴(kuò)展2023/10/19一般而言，當(dāng)某一個節(jié)點(diǎn)的后繼節(jié)點(diǎn)倒推值已經(jīng)給定時，則倒推值的上下界可以被修正。注意：MAX節(jié)點(diǎn)的α值非減，MIN節(jié)點(diǎn)的β值非增。

2023/10/19α、β值的計算方法：第一、一個MAX節(jié)點(diǎn)的α值等于其后繼節(jié)點(diǎn)當(dāng)前最大的最終倒推值。第二、一個MIN節(jié)點(diǎn)的β值等于其后繼節(jié)點(diǎn)當(dāng)前最小的最終倒推值。

2023/10/19α-β剪枝的規(guī)則為：1、若任何MIN結(jié)點(diǎn)的β值小于或等于任何它的先輩MAX結(jié)點(diǎn)的α值，則可中止該MIN結(jié)點(diǎn)以下的搜索，此時這個MIN結(jié)點(diǎn)的最終倒推值就是已得到的β值。該值與真正的極大極小的搜索結(jié)果的倒推值可能不相同，但是對起始結(jié)點(diǎn)而言，倒推值是相同的，使