人工智能ArtificialIntelligence(AI)2022/12/10人工智能2022/12/1012.4博弈問題的搜索技術2.4.1博弈問題的表達2.4.2極大極小搜索過程2.4.3-剪枝法2022/12/102.4博弈問題的搜索技術2022/12/1022.4.1博弈問題的表達

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

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

則該節點就對已有利MAX好招2022/12/10從MAX方的角度來看：MAX好招2022/12/1010總之從MAX方來說，與節點、或節點交替出現；反之，從MIN方的角度來看，情況正好相反2022/12/10總之2022/12/1011在博弈樹中，先行一方的初始狀態對應著樹的根節點，而任何一方獲勝的最終格局為目標狀態，對應于樹的終葉節點（可解節點或本原問題）但是，從MAX的角度出發，所有使MAX獲勝的狀態格局都是本原問題，是可解節點，而使MIN獲勝的狀態格局是不可解節點2022/12/10在博弈樹中，先行一方的初始狀態對應著樹的根節點，而任何一方獲12例

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

(3,2,1,1,MAX)數字序列：表示不同堆中錢幣的個數說明：表示下一步由誰來分，即取MAX或MIN2022/12/10用數字序列加上一個說明來表示一個狀態：2022/12/1014現在取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)2022/12/10現在取N＝7的簡單情況，并由MIN先分注：如果MAX走紅箭15對于比較復雜的博弈問題，只能模擬人的思維“向前看幾步”，然后作出決策，選擇最有利自己的一步。即只能給出幾層走法，然后按照一定的估算辦法，決定走一好招2022/12/10對于比較復雜的博弈問題，只能模擬人的思維“向前看幾步”，然后162.4.2極大極小過程

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

2022/12/102.4.2極大極小過程對于復雜的博弈問題，要規定搜索深17①

對于每一格局（棋局）給出（定義或者倒推）一個靜態估價函數值。值越大對MAX越有利，反之越不利極大極小過程的基本思路：2022/12/10①對于每一格局（棋局）給出（定義或者倒推）一個靜態估價函數18②

對于給定的格局，MAX給出可能的走法，然后MIN對應地給出相應的走法，這樣重復若干次，得到一組端節點（必須由MIN走后得到的，由MAX下的棋局）。這一過程相當于節點擴展注：博弈樹深度或層數一定是偶數2022/12/10②對于給定的格局，MAX給出可能的走法，然后MIN對應地給19③對于每一個端節點，計算出它們的靜態估價函數，然后自下而上地逐層計算倒推值，直到MAX開始的格局。在MIN下的格局中取估值的最小值，在MAX下格局中取估值的最大值④

取估值最大的格局作為MAX要走的一招棋2022/12/10③對于每一個端節點，計算出它們的靜態估價函數，然后自下而上20例：向前看一步的兩層博弈樹

2022/12/10例：向前看一步的兩層博弈樹2022/12/1021定義靜態函數e(P)的一般原則：2022/12/10定義靜態函數e(P)的一般原則：2022/12/1022OPEN：存放待擴展的節點，此時為隊列，即以寬度優先的策略擴展節點CLOSED：存放已擴展的節點，此時為堆棧，即后擴展的節點先計算靜態估價函數值

符號：2022/12/10OPEN：存放待擴展的節點，此時為隊列，即以寬度優先的策略擴231、將初始節點S放入OPEN表中，開始時搜索樹T由初始節點S構成2、若OPEN表為空，則轉53、將OPEN

表中第一個節點n移出放入CLOSED表的前端極大極小搜索過程為：2022/12/101、將初始節點S放入OPEN表中，開始時搜索樹T244、若n可直接判定為贏、輸、或平局，則令對應的

e(n)=∞，-∞或0，并轉2；否則擴展n，產生n的后繼節點集{ni}，將{ni

}放入搜索樹T

中2022/12/104、若n可直接判定為贏、輸、或平局，則令對應的e(n)25此時，若搜索深度d{ni}小于預先設定的深度k，則將{ni}放入OPEN表的末端，轉2；否則，ni

達到深度k，計算e(ni)，并轉2（續）2022/12/10此時，若搜索深度d{ni}小于預先設定的深度k，則將{265、若CLOSED表為空，則轉8；否則取出CLOSED表中的第一個節點，記為npOpen為空，即已經擴展完節點步22022/12/105、若CLOSED表為空，則轉8；否則取出CLOSED表中的276、若np

屬于MAX層，且對于它的屬于MIN層的子節點nci

的e

(nci

)有值，則：

e(np

)=max{nci

}某一個節點屬于MAX的含義是該節點等待MAX來擴展2022/12/106、若np屬于MAX層，且對于它的屬于MIN層的子節點28（續）若np屬于MIN層，且對于它的屬于MAX層的子節點nci

的e(nci

)有值，則：

e(np

)=min{nci

}2022/12/10（續）2022/12/10297、轉58、根據e(S)

的值，標記走步或者結束（-∞，∞或0）2022/12/107、轉52022/12/1030第一階段為1、2、3、4步，用寬度優先算法生成規定深度k

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

為止，再由e(S)

選得相對較好的走法，過程結束算法分成兩個階段：2022/12/10第一階段為1、2、3、4步，用寬度優先算法生成規定深度k31等對手走出相應的棋，再以當前的格局作為初始節點，重復此過程，選擇對自己有利的走法2022/12/10等對手走出相應的棋，再以當前的格局作為初始節點，重復此過程，322022/12/102022/12/1033例：

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

約定：每一方只向前看一步（擴展出二層）記MAX的棋子為“×”，MIN的棋子為“O”規定MAX先手2022/12/10例：一字棋的極大極小搜索過程約定：2022/12/1034①

若格局P

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

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

若P是MIN獲勝，則e(P)=－∞2022/12/10②若P是MAX獲勝，則2022/12/1036例：計算下列棋局的靜態估價函數值

e(P)=6-4=2

棋局O××O×××××××OOOO×OOOO行=2列=2對角=2行=2列=2對角=02022/12/10例：計算下列棋局的靜態估價函數值e(P)=6-4=2棋37利用棋盤的對稱性，有些棋局是等價的

O××OO××O2022/12/10利用棋盤的對稱性，有些棋局是等價的O××OO××O202238××××O×O×O×O×OO×O×O×O×O××O×O1010-1-10-10-2121-2-11MAXMINMAXMAX的走步2022/12/10××××O×O×O×O×OO×O×O×O×O××O×O10139第二步OXXOXOXXOXXOXXXOOXXOOXXOXOXOXOXOXO213211OOXXOXXOOXXOOXXOOXXO10201OOXX10OOXXOOXXOOXXOXOXOXXOOXXO2231221OOXXOXOXOOXX11001XOXO3MIN2022/12/10第二步OXXOXOXXOXXOXXXOOXXOOXXOXOX40第三步OOXXXOOXXOOXXXOOXXXOOXXXOOXXXXOOOXXXOOXXOXOOXXOXOOXOXOOOXXXOOOXXXOOXXXOOOXXXOOOOXXXOOXXXOOOXXXOOOXXOXOOOXXXOOOXXXOOXXOXOOXOXXOOOXXXOOOXXXOOXXXOOOXOXX-021---122101---1111112-112022/12/10第三步OOXXXOOXXOOXXXOOXXXOOXXXOOX41×OO××MAXMIN2022/12/10×OO××MAXMIN2022/12/1042MAXMIN×O××O2022/12/10MAXMIN×O××O2022/12/1043上機實驗作業：用C/C++語言編寫“一字棋”的游戲程序，基本要求：必須實現極大極小過程能夠進行“人-機”對壘、“機-機”對壘簡單地顯示對壘過程實驗形式：兩人或者一人一組2022/12/10上機實驗作業：2022/12/1044實驗報告格式：“一字棋”游戲的計算機程序學號：姓名：專業：摘要1

一字棋游戲的文字描述2

一字棋對壘過程的計算機描述和實現3

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

參考文獻附錄：程序使用的簡單說明2022/12/10實驗報告格式：2022/12/1045提交的材料：1、文字報告；2、程序原代碼提交的方式：以學號姓名為壓縮文件名（發送到wgqu@提交的時間：11月21日口頭報告：介紹報告的主要內容和演示程序，特別是自己覺得有特色的地方。初步時間是12月初。2022/12/10提交的材料：1、文字報告；2、程序原代碼2022/12/10462.4.3

-剪枝法

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

β表示MIN節點的估值的上界（已經搜索到的MIN節點的最大值）

。

2022/12/10改進：在博弈樹生成過程中同時計算端節點的估計值及倒推值，以減48極大極小過程：采用寬度優先的方式來擴展節點α-β剪枝法：改用深度優先的策略來擴展節2022/12/10極大極小過程：2022/12/1049一字棋的左邊部分

MAXMIN現擴展B得到C，其值為-1，則B的倒推值小于等于-1，即β≤-1。再擴展B的子節點，B的值也不會大于-1。結果是B比A差，不用再擴展B的其他子節點了。此處，MIN節點B的β值小于等于其先輩MAX節點S的α值，停止擴展。C擴展S生成A,B,….。擴展A生成5個子節點，倒推得到A的值為-1。可以得到S

的值大于等于-1，即α≥-1。2022/12/10一字棋的左邊部分MAXMIN現擴展B得到C，其值為-1，則50更一般的情況MIN節點的β不大于其先輩MAX節點的α值，則可以中止擴展MAX節點的α

不小于其先輩MIN節點的β值，則可以中止擴展2022/12/10更一般的情況MIN節點的β不大于其先輩MAX節點的α值，則可51一般而言，當某一個節點的后繼節點倒推值已經給定時，則倒推值的上下界可以被修正。注意：MAX節點的α值非減，MIN節點的β值非增。

2022/12/10一般而言，當某一個節點的后繼節點倒推值已經給定時，則倒推值的52α、β值的計算方法：第一、一個MAX節點的α值等于其后繼節點當前最大的最終倒推值。第二、一個MIN節點的β值等于其后繼節點當前最小的最終倒推值。

2022/12/10α、β值的計算方法：2022/12/1053α-β剪枝的規則為：1、若任何MIN結點的β值小于或等于任何它的先輩MAX結點的α值，則可中止該MIN結點以下的搜索，此時這個MIN結點的最終倒推值就是已得到的β值。該值與真正的極大極小的搜索結果的倒推值可能不相同，但是對起始結點而言，倒推值是相同的，使用它選擇的走步也是相同的。

2022/12/10α-β剪枝的規則為：2022/12/1054

2、若任何MAX結點的α值大于或等于它的MIN先輩結點的β值，則可以中止該MAX結點以下的搜索，此時這個MAX結點處的倒推值就是已得到的α值。

2022/12/102、若任何MAX結點的α值大于或等于它的MIN先輩結點的β55當搜索用規則1終止時，我們稱進行了α剪枝，而當搜索用規則2終止時，我們稱進行了β剪枝。在搜索過程中，保存α和β值，如果出現滿足使用兩條規則的條件，我們就中止某一些搜索，這一過程稱為α-β(剪枝)過程。

2022/12/10當搜索用規則1終止時，我們稱進行了α剪枝，而當搜索用規則2終56α-β過程的主要思想（步驟）:1、采用有界的深度優先搜索算法。2、立即計算端節點的估值。3、α剪枝4、β剪枝5、當初始節點的所有后繼節點的最終倒推值全部給出后，搜索過程結束。2022/12/10α-β過程的主要思想（步驟）:2022/12/1057例：圖中矩形表示MAX的節點，圓圈表示MIN的節點，多個畫線表示被修剪的枝。原來有38個節點，現在只有22個節點必須估值。每一次擴展一個節點。

2022/12/10例：2022/12/1058MAXMAXMAXMINMIN2022/12/10MAXMAXMAXMINMIN2022/12/1059經常不斷地學習,你就什么都知道。你知道得越多,你就越有力量StudyConstantly,AndYouWillKnowEverything.TheMoreYouKnow,TheMorePowerfulYouWillBe學習總結經常不斷地學習,你就什么都知道。你知道得越多,你就越有力量學60結束語當你盡了自己的最大努力時，失敗也是偉大的，所以不要放棄，堅持就是正確的。WhenYouDoYourBest,FailureIsGreat,SoDon'TGiveUp,StickToTheEnd演講人：XXXXXX

時間：XX年XX月XX日

結束語61人工智能ArtificialIntelligence(AI)2022/12/10人工智能2022/12/10622.4博弈問題的搜索技術2.4.1博弈問題的表達2.4.2極大極小搜索過程2.4.3-剪枝法2022/12/102.4博弈問題的搜索技術2022/12/10632.4.1博弈問題的表達

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

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

則該節點就對已有利MAX好招2022/12/10從MAX方的角度來看：MAX好招2022/12/1071總之從MAX方來說，與節點、或節點交替出現；反之，從MIN方的角度來看，情況正好相反2022/12/10總之2022/12/1072在博弈樹中，先行一方的初始狀態對應著樹的根節點，而任何一方獲勝的最終格局為目標狀態，對應于樹的終葉節點（可解節點或本原問題）但是，從MAX的角度出發，所有使MAX獲勝的狀態格局都是本原問題，是可解節點，而使MIN獲勝的狀態格局是不可解節點2022/12/10在博弈樹中，先行一方的初始狀態對應著樹的根節點，而任何一方獲73例

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

(3,2,1,1,MAX)數字序列：表示不同堆中錢幣的個數說明：表示下一步由誰來分，即取MAX或MIN2022/12/10用數字序列加上一個說明來表示一個狀態：2022/12/1075現在取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)2022/12/10現在取N＝7的簡單情況，并由MIN先分注：如果MAX走紅箭76對于比較復雜的博弈問題，只能模擬人的思維“向前看幾步”，然后作出決策，選擇最有利自己的一步。即只能給出幾層走法，然后按照一定的估算辦法，決定走一好招2022/12/10對于比較復雜的博弈問題，只能模擬人的思維“向前看幾步”，然后772.4.2極大極小過程

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

2022/12/102.4.2極大極小過程對于復雜的博弈問題，要規定搜索深78①

對于每一格局（棋局）給出（定義或者倒推）一個靜態估價函數值。值越大對MAX越有利，反之越不利極大極小過程的基本思路：2022/12/10①對于每一格局（棋局）給出（定義或者倒推）一個靜態估價函數79②

對于給定的格局，MAX給出可能的走法，然后MIN對應地給出相應的走法，這樣重復若干次，得到一組端節點（必須由MIN走后得到的，由MAX下的棋局）。這一過程相當于節點擴展注：博弈樹深度或層數一定是偶數2022/12/10②對于給定的格局，MAX給出可能的走法，然后MIN對應地給80③對于每一個端節點，計算出它們的靜態估價函數，然后自下而上地逐層計算倒推值，直到MAX開始的格局。在MIN下的格局中取估值的最小值，在MAX下格局中取估值的最大值④

取估值最大的格局作為MAX要走的一招棋2022/12/10③對于每一個端節點，計算出它們的靜態估價函數，然后自下而上81例：向前看一步的兩層博弈樹

2022/12/10例：向前看一步的兩層博弈樹2022/12/1082定義靜態函數e(P)的一般原則：2022/12/10定義靜態函數e(P)的一般原則：2022/12/1083OPEN：存放待擴展的節點，此時為隊列，即以寬度優先的策略擴展節點CLOSED：存放已擴展的節點，此時為堆棧，即后擴展的節點先計算靜態估價函數值

符號：2022/12/10OPEN：存放待擴展的節點，此時為隊列，即以寬度優先的策略擴841、將初始節點S放入OPEN表中，開始時搜索樹T由初始節點S構成2、若OPEN表為空，則轉53、將OPEN

表中第一個節點n移出放入CLOSED表的前端極大極小搜索過程為：2022/12/101、將初始節點S放入OPEN表中，開始時搜索樹T854、若n可直接判定為贏、輸、或平局，則令對應的

e(n)=∞，-∞或0，并轉2；否則擴展n，產生n的后繼節點集{ni}，將{ni

}放入搜索樹T

中2022/12/104、若n可直接判定為贏、輸、或平局，則令對應的e(n)86此時，若搜索深度d{ni}小于預先設定的深度k，則將{ni}放入OPEN表的末端，轉2；否則，ni

達到深度k，計算e(ni)，并轉2（續）2022/12/10此時，若搜索深度d{ni}小于預先設定的深度k，則將{875、若CLOSED表為空，則轉8；否則取出CLOSED表中的第一個節點，記為npOpen為空，即已經擴展完節點步22022/12/105、若CLOSED表為空，則轉8；否則取出CLOSED表中的886、若np

屬于MAX層，且對于它的屬于MIN層的子節點nci

的e

(nci

)有值，則：

e(np

)=max{nci

}某一個節點屬于MAX的含義是該節點等待MAX來擴展2022/12/106、若np屬于MAX層，且對于它的屬于MIN層的子節點89（續）若np屬于MIN層，且對于它的屬于MAX層的子節點nci

的e(nci

)有值，則：

e(np

)=min{nci

}2022/12/10（續）2022/12/10907、轉58、根據e(S)

的值，標記走步或者結束（-∞，∞或0）2022/12/107、轉52022/12/1091第一階段為1、2、3、4步，用寬度優先算法生成規定深度k

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

為止，再由e(S)

選得相對較好的走法，過程結束算法分成兩個階段：2022/12/10第一階段為1、2、3、4步，用寬度優先算法生成規定深度k92等對手走出相應的棋，再以當前的格局作為初始節點，重復此過程，選擇對自己有利的走法2022/12/10等對手走出相應的棋，再以當前的格局作為初始節點，重復此過程，932022/12/102022/12/1094例：

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

約定：每一方只向前看一步（擴展出二層）記MAX的棋子為“×”，MIN的棋子為“O”規定MAX先手2022/12/10例：一字棋的極大極小搜索過程約定：2022/12/1095①

若格局P

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

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

若P是MIN獲勝，則e(P)=－∞2022/12/10②若P是MAX獲勝，則2022/12/1097例：計算下列棋局的靜態估價函數值

e(P)=6-4=2

棋局O××O×××××××OOOO×OOOO行=2列=2對角=2行=2列=2對角=02022/12/10例：計算下列棋局的靜態估價函數值e(P)=6-4=2棋98利用棋盤的對稱性，有些棋局是等價的

O××OO××O2022/12/10利用棋盤的對稱性，有些棋局是等價的O××OO××O202299××××O×O×O×O×OO×O×O×O×O××O×O1010-1-10-10-2121-2-11MAXMINMAXMAX的走步2022/12/10××××O×O×O×O×OO×O×O×O×O××O×O101100第二步OXXOXOXXOXXOXXXOOXXOOXXOXOXOXOXOXO213211OOXXOXXOOXXOOXXOOXXO10201OOXX10OOXXOOXXOOXXOXOXOXXOOXXO2231221OOXXOXOXOOXX11001XOXO3MIN2022/12/10第二步OXXOXOXXOXXOXXXOOXXOOXXOXOX101第三步OOXXXOOXXOOXXXOOXXXOOXXXOOXXXXOOOXXXOOXXOXOOXXOXOOXOXOOOXXXOOOXXXOOXXXOOOXXXOOOOXXXOOXXXOOOXXXOOOXXOXOOOXXXOOOXXXOOXXOXOOXOXXOOOXXXOOOXXXOOXXXOOOXOXX-021---122101---1111112-112022/12/10第三步OOXXXOOXXOOXXXOOXXXOOXXXOOX102×OO××MAXMIN2022/12/10×OO××MAXMIN2022/12/10103MAXMIN×O××O2022/12/10MAXMIN×O××O2022/12/10104上機實驗作業：用C/C++語言編寫“一字棋”的游戲程序，基本要求：必須實現極大極小過程能夠進行“人-機”對壘、“機-機”對壘簡單地顯示對壘過程實驗形式：兩人或者一人一組2022/12/10上機實驗作業：2022/12/10105實驗報告格式：“一字棋”游戲的計算機程序學號：姓名：專業：摘要1

一字棋游戲的文字描述2

一字棋對壘過程的計算機描述和實現3

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

參考文獻附錄：程序使用的簡單說明2022/12/10實驗報告格式：2022/12/10106提交的材料：1、文字報告；2、程序原代碼提交的方式：以學號姓名為壓縮文件名（發送到wgqu@提交的時間：11月21日口頭報告：介紹報告的主要內容和演示程序，特別是自己覺得有特色的地方。初步時間是12月初。2022/12/10提交的材料：1、文字報告；2、程序原代碼2022/12/101072.4.3

-剪枝法

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

β表示MIN節點的估值的上界（已經搜索到的MIN節點的最大值）

。

2022/12/10改進：在博弈樹生成過程中同時計算端節點的估計值及倒推值，以減109極大極小過程：采用寬度優先的方式來擴展節點α-β剪枝法：改用深度優先的策略來擴展節2022/12/10極大極小過程：2022/12/10110一字棋的左邊部分

MAXMIN現擴展B得到C，其值為-1，則B的倒推值小于等于-1，即β≤-1。再擴展B的子節點，B的值也不會大于-1。結果是B比A差，不用再擴展B的其