第五章-對抗搜索分析課件

第五章對抗搜索主講：徐縉第五章對抗搜索主講：徐縉第五章、對抗搜索在有其它智能體計劃與我們對抗的世界中如何預(yù)先計劃博弈的概念數(shù)學(xué)中的博弈論把任何多智能體環(huán)境看成是一種博弈游戲，其中每個智能體對其它智能體的影響是“顯著的”，與智能體是合作的還是竟?fàn)幍臒o關(guān)。AI中的博弈通常指有完整信息的、確定性的、輪流行動的、兩個游戲者的零和游戲。游戲因為難解而令人感興趣！第五章、對抗搜索在有其它智能體計劃與我們對抗的世界中如何預(yù)先第五章、對抗搜索博弈中的優(yōu)化決策–剪枝：允許我們忽略那些不影響最后決定的部分搜索樹不完整的實時決策包含幾率因素的游戲部分可觀察博弈博弈程序的當(dāng)前發(fā)展水平第五章、對抗搜索博弈中的優(yōu)化決策例子：MAX和MIN問題的表述：MAX先行，然后兩人輪流出招，直到游戲結(jié)束。在游戲的最后，給優(yōu)勝者加分，給失敗者罰分。初始狀態(tài)，包括棋盤局面和確定該哪個游戲者出招。ACTION(s)后繼函數(shù)，返回(move,state)。TERMINAL-TEST(s)終止測試UTILITY(s,p)效用函數(shù)：對終止?fàn)顟B(tài)給出一個數(shù)值。例子：MAX和MIN問題的表述：MAX先行，然后兩人輪流出招例子：井子棋游戲-博弈樹例子：井子棋游戲-博弈樹最優(yōu)策略最優(yōu)解是導(dǎo)致取勝的終止?fàn)顟B(tài)的一系列招數(shù)但，在游戲中MIN還有發(fā)言權(quán)在對手不犯錯誤時，最優(yōu)策略能夠?qū)е轮辽俨槐热魏纹渌呗圆畹慕Y(jié)果。一顆兩層的博弈樹最優(yōu)策略最優(yōu)解是導(dǎo)致取勝的終止?fàn)顟B(tài)的一系列招數(shù)一顆兩層的博弈最優(yōu)策略的確定通過檢查每個節(jié)點的極小極大值來決定，記為MINMAX-VALUE(n)。最優(yōu)策略的確定通過檢查每個節(jié)點的極小極大值來決定，記為MIN極小極大值的遞歸算法極小極大值的遞歸算法多人游戲中的最優(yōu)決策多人游戲中的最優(yōu)決策第五章、對抗搜索博弈中的優(yōu)化決策–剪枝：允許我們忽略那些不影響最后決定的部分搜索樹不完整的實時決策包含幾率因素的游戲部分可觀察博弈博弈程序的當(dāng)前發(fā)展水平第五章、對抗搜索博弈中的優(yōu)化決策

–剪枝極小極大值搜索的時間復(fù)雜度是O(bm)剪枝：剪裁掉那些不影響最后決策的分支。一般原則：考慮在樹中某處的節(jié)點n，如果游戲者在n的父節(jié)點或上層的任何節(jié)點有一個更好的選擇m，那么在實際的游戲中就永遠(yuǎn)不會到達(dá)n，即n被剪裁掉。

–剪枝極小極大值搜索的時間復(fù)雜度是O(bm)例子例子–剪枝：如果m比n好，我們就不會走到n。–剪枝：如果m比n好，我們就不會走到n。

–剪枝＝到目前為止我們在路徑上的任意選擇點發(fā)現(xiàn)的MAX的最佳選擇＝到目前為止我們在路徑上的任意選擇點發(fā)現(xiàn)的MIN的最佳選擇–剪枝的效率很大程度上取決于檢查后繼的順序如果能夠先檢查那些可能最好的后繼，那么算法的時間復(fù)雜度為O(bd/2)。

–剪枝＝到目前為止我們在路徑上的任意選擇點發(fā)現(xiàn)的MA

–剪枝算法

–剪枝算法處理搜索樹中的重復(fù)狀態(tài)在游戲中重復(fù)狀態(tài)的頻繁出現(xiàn)往往是因為調(diào)換—導(dǎo)致同樣棋局的不同行棋序列的排列例如，[a1,b1,a2,b2]和[a2,b2,a1,b1]都結(jié)束于同樣的棋局。解決辦法：第一次遇見某棋局時將對它的評價存儲在哈希表中（該哈希表稱為調(diào)換表）。處理搜索樹中的重復(fù)狀態(tài)在游戲中重復(fù)狀態(tài)的頻繁出現(xiàn)往往是因為調(diào)第五章、對抗搜索博弈中的優(yōu)化決策–剪枝：允許我們忽略那些不影響最后決定的部分搜索樹不完整的實時決策包含幾率因素的游戲部分可觀察博弈博弈程序的當(dāng)前發(fā)展水平第五章、對抗搜索博弈中的優(yōu)化決策不完整的實時決策：對MINIMAX或–算法的改進(jìn)–算法依然要搜索至少一部分空間直到終止?fàn)顟B(tài)，這樣的搜索不現(xiàn)實。Shannon提出：用估計棋局效用值的啟發(fā)式評價函數(shù)EVAL代替效用函數(shù)用可以決策什么時候運用EVAL的截斷測試取代終止測試不完整的實時決策：對MINIMAX或–算法的改進(jìn)–算不完整的實時決策因此得到如下的啟發(fā)式極小極大值，s為狀態(tài)，d為最大深度：H-MINIMAX(s,d)=不完整的實時決策因此得到如下的啟發(fā)式極小極大值，s為狀態(tài)，d如何設(shè)計評價函數(shù)？應(yīng)該以和真正的效用函數(shù)同樣的方式對終止?fàn)顟B(tài)進(jìn)行排序評價函數(shù)的計算不能花費太多的時間對于非終止?fàn)顟B(tài)，評價函數(shù)應(yīng)該和取勝的實際機(jī)會密切相關(guān)。如何設(shè)計評價函數(shù)？應(yīng)該以和真正的效用函數(shù)同樣的方式對終止?fàn)顟B(tài)評價函數(shù)（續(xù)）在計算能力有限情況下，評價函數(shù)能做到最好的就是猜測最后的結(jié)果大多數(shù)評價函數(shù)的工作方式是計算狀態(tài)的不同，那么對狀態(tài)的一個合理評價是加權(quán)平均值例如，國際象棋中EVAL通常取為加權(quán)線性函數(shù)（假設(shè)每個特征的貢獻(xiàn)獨立于其它特征的值），評價函數(shù)（續(xù)）在計算能力有限情況下，評價函數(shù)能做到最好的就是截斷搜索用ifCUTOFF-TEST(state,depth)thenreturnEVAL(state)代替–算法中TERMINAL-TEST所在的兩行，或使用迭代搜索：當(dāng)時間用完時，程序就返回目前完成最深的搜索所選擇的招數(shù)。由于評價函數(shù)的近似性，上述方法可能導(dǎo)致錯誤。截斷搜索用ifCUTOFF-TEST(state,dep（a）黑棋有1個馬、2個兵的優(yōu)勢，能夠取勝。（b）黑棋會被白棋吃掉皇后，從而失敗。（a）黑棋有1個馬、2個兵的優(yōu)勢，能夠取勝。截斷搜索（續(xù)）需要更為復(fù)雜的截斷測試，評價函數(shù)應(yīng)該只用于那些靜止的棋局（靜態(tài)棋局）。非靜止的棋局可以進(jìn)一步擴(kuò)展直到靜止的棋局，這種額外的搜索稱為靜態(tài)搜索。截斷搜索（續(xù)）需要更為復(fù)雜的截斷測試，評價函數(shù)應(yīng)該只用于那些

截斷搜索（續(xù)）

地平線效應(yīng)：指對手招數(shù)導(dǎo)致我方嚴(yán)重?fù)p失并且從理論上基本無法避免。單步延伸是避免地平線效應(yīng)的一種策略這樣做可能超過深度限制，但由于單步延伸很少，不會增加太多開銷。

截斷搜索（續(xù)）

地平線效應(yīng)：指對手招數(shù)導(dǎo)致我方嚴(yán)重?fù)p失并且對這兩節(jié)所介紹的技術(shù)的總結(jié)假設(shè)已經(jīng)實現(xiàn)：國際象棋的評價函數(shù)使用靜止搜索的合理截斷測試一個很大的調(diào)換表那么在“最新的PC”上可每秒生成和評價約一百萬個節(jié)點，允許我們在標(biāo)準(zhǔn)時間控制下對每步棋可搜索約2億個節(jié)點，而國際象棋的分支因子平均為35，355約為5億。對這兩節(jié)所介紹的技術(shù)的總結(jié)假設(shè)已經(jīng)實現(xiàn)：第五章、對抗搜索博弈中的優(yōu)化決策–剪枝：允許我們忽略那些不影響最后決定的部分搜索樹不完整的實時決策包含幾率因素的游戲部分可觀察博弈博弈程序的當(dāng)前發(fā)展水平第五章、對抗搜索博弈中的優(yōu)化決策例子：西洋雙陸棋目標(biāo)：將自己的棋子全部移出棋盤白棋順時針向25移動黑棋逆時針向0移動每個棋子按照擲出的骰子數(shù)移動到任意位置除非那里有多個對方棋子，如果只有一個，這個棋子就被吃了，要重新開始。例子：西洋雙陸棋目標(biāo)：將自己的棋子全部移出棋盤雙陸棋的博弈樹（包括幾率節(jié)點）兩個骰子總共有21種骰法，其中：6個有相同骰子數(shù)的組合（1/36概率）15個不同骰子數(shù)的組合（1/18概率）雙陸棋的博弈樹（包括幾率節(jié)點）兩個骰子總共有21種骰法，其中極小極大值期望極小極大值極小極大值期望極小極大值有機(jī)率節(jié)點的游戲中的局面評價在保持順序不變的情況下，葉節(jié)點賦值的變換導(dǎo)致了最佳招數(shù)的改變。有機(jī)率節(jié)點的游戲中的局面評價在保持順序不變的情況下，葉節(jié)點賦期望極小極大值的復(fù)雜度算法的時間復(fù)雜度為O(bmnm)，其中n為不同的擲骰子結(jié)果的數(shù)目?？梢詫τ袔茁使?jié)點的博弈樹使用類似-剪枝的技術(shù)嗎？限制效用函數(shù)的取值范圍不用看幾率節(jié)點的子節(jié)點就可以設(shè)置幾率節(jié)點的值的上界期望極小極大值的復(fù)雜度算法的時間復(fù)雜度為O(bmnm)，其中第五章、對抗搜索博弈中的優(yōu)化決策–剪枝：允許我們忽略那些不影響最后決定的部分搜索樹不完整的實時決策包含幾率因素的游戲部分可觀察博弈博弈程序的當(dāng)前發(fā)展水平第五章、對抗搜索博弈中的優(yōu)化決策牌類游戲牌類游戲

牌類游戲考慮未知牌的所有可能應(yīng)對策略假設(shè)應(yīng)對策略s發(fā)生的概率是p(s)若使用蒙特卡洛近似，隨機(jī)采樣N個樣本，設(shè)組合s在樣本中出現(xiàn)的概率與p(s)成正比：

牌類游戲考慮未知牌的所有可能應(yīng)對策略假設(shè)應(yīng)對策略s發(fā)生的第五章、對抗搜索博弈中的優(yōu)化決策–剪枝：允許我們忽略那些不影響最后決定的部分搜索樹不完整的實時決策包含幾率因素的游戲部分可觀察博弈博弈程序的當(dāng)前發(fā)展水平第五章、對抗搜索博弈中的優(yōu)化決策博弈程序發(fā)展現(xiàn)狀國際象棋：IBM深藍(lán)打敗了國際象棋大師西洋跳棋：Chinook在1990年的簡化比賽中戰(zhàn)勝了長久以來的人類冠軍翻轉(zhuǎn)棋：1997年的Logistello程序以6比0擊敗了人類冠軍西洋雙陸棋：TD-GAMMON穩(wěn)定的排在世界前列圍棋：圍棋就有點慘，也就能達(dá)到個業(yè)余選手的水平。博弈程序發(fā)展現(xiàn)狀國際象棋：IBM深藍(lán)打敗了國際象棋大師結(jié)束Thankyou結(jié)束第五章對抗搜索主講：徐縉第五章對抗搜索主講：徐縉第五章、對抗搜索在有其它智能體計劃與我們對抗的世界中如何預(yù)先計劃博弈的概念數(shù)學(xué)中的博弈論把任何多智能體環(huán)境看成是一種博弈游戲，其中每個智能體對其它智能體的影響是“顯著的”，與智能體是合作的還是竟?fàn)幍臒o關(guān)。AI中的博弈通常指有完整信息的、確定性的、輪流行動的、兩個游戲者的零和游戲。游戲因為難解而令人感興趣！第五章、對抗搜索在有其它智能體計劃與我們對抗的世界中如何預(yù)先第五章、對抗搜索博弈中的優(yōu)化決策–剪枝：允許我們忽略那些不影響最后決定的部分搜索樹不完整的實時決策包含幾率因素的游戲部分可觀察博弈博弈程序的當(dāng)前發(fā)展水平第五章、對抗搜索博弈中的優(yōu)化決策例子：MAX和MIN問題的表述：MAX先行，然后兩人輪流出招，直到游戲結(jié)束。在游戲的最后，給優(yōu)勝者加分，給失敗者罰分。初始狀態(tài)，包括棋盤局面和確定該哪個游戲者出招。ACTION(s)后繼函數(shù)，返回(move,state)。TERMINAL-TEST(s)終止測試UTILITY(s,p)效用函數(shù)：對終止?fàn)顟B(tài)給出一個數(shù)值。例子：MAX和MIN問題的表述：MAX先行，然后兩人輪流出招例子：井子棋游戲-博弈樹例子：井子棋游戲-博弈樹最優(yōu)策略最優(yōu)解是導(dǎo)致取勝的終止?fàn)顟B(tài)的一系列招數(shù)但，在游戲中MIN還有發(fā)言權(quán)在對手不犯錯誤時，最優(yōu)策略能夠?qū)е轮辽俨槐热魏纹渌呗圆畹慕Y(jié)果。一顆兩層的博弈樹最優(yōu)策略最優(yōu)解是導(dǎo)致取勝的終止?fàn)顟B(tài)的一系列招數(shù)一顆兩層的博弈最優(yōu)策略的確定通過檢查每個節(jié)點的極小極大值來決定，記為MINMAX-VALUE(n)。最優(yōu)策略的確定通過檢查每個節(jié)點的極小極大值來決定，記為MIN極小極大值的遞歸算法極小極大值的遞歸算法多人游戲中的最優(yōu)決策多人游戲中的最優(yōu)決策第五章、對抗搜索博弈中的優(yōu)化決策–剪枝：允許我們忽略那些不影響最后決定的部分搜索樹不完整的實時決策包含幾率因素的游戲部分可觀察博弈博弈程序的當(dāng)前發(fā)展水平第五章、對抗搜索博弈中的優(yōu)化決策

–剪枝極小極大值搜索的時間復(fù)雜度是O(bm)剪枝：剪裁掉那些不影響最后決策的分支。一般原則：考慮在樹中某處的節(jié)點n，如果游戲者在n的父節(jié)點或上層的任何節(jié)點有一個更好的選擇m，那么在實際的游戲中就永遠(yuǎn)不會到達(dá)n，即n被剪裁掉。

–剪枝極小極大值搜索的時間復(fù)雜度是O(bm)例子例子–剪枝：如果m比n好，我們就不會走到n。–剪枝：如果m比n好，我們就不會走到n。

–剪枝＝到目前為止我們在路徑上的任意選擇點發(fā)現(xiàn)的MAX的最佳選擇＝到目前為止我們在路徑上的任意選擇點發(fā)現(xiàn)的MIN的最佳選擇–剪枝的效率很大程度上取決于檢查后繼的順序如果能夠先檢查那些可能最好的后繼，那么算法的時間復(fù)雜度為O(bd/2)。

–剪枝＝到目前為止我們在路徑上的任意選擇點發(fā)現(xiàn)的MA

–剪枝算法

–剪枝算法處理搜索樹中的重復(fù)狀態(tài)在游戲中重復(fù)狀態(tài)的頻繁出現(xiàn)往往是因為調(diào)換—導(dǎo)致同樣棋局的不同行棋序列的排列例如，[a1,b1,a2,b2]和[a2,b2,a1,b1]都結(jié)束于同樣的棋局。解決辦法：第一次遇見某棋局時將對它的評價存儲在哈希表中（該哈希表稱為調(diào)換表）。處理搜索樹中的重復(fù)狀態(tài)在游戲中重復(fù)狀態(tài)的頻繁出現(xiàn)往往是因為調(diào)第五章、對抗搜索博弈中的優(yōu)化決策–剪枝：允許我們忽略那些不影響最后決定的部分搜索樹不完整的實時決策包含幾率因素的游戲部分可觀察博弈博弈程序的當(dāng)前發(fā)展水平第五章、對抗搜索博弈中的優(yōu)化決策不完整的實時決策：對MINIMAX或–算法的改進(jìn)–算法依然要搜索至少一部分空間直到終止?fàn)顟B(tài)，這樣的搜索不現(xiàn)實。Shannon提出：用估計棋局效用值的啟發(fā)式評價函數(shù)EVAL代替效用函數(shù)用可以決策什么時候運用EVAL的截斷測試取代終止測試不完整的實時決策：對MINIMAX或–算法的改進(jìn)–算不完整的實時決策因此得到如下的啟發(fā)式極小極大值，s為狀態(tài)，d為最大深度：H-MINIMAX(s,d)=不完整的實時決策因此得到如下的啟發(fā)式極小極大值，s為狀態(tài)，d如何設(shè)計評價函數(shù)？應(yīng)該以和真正的效用函數(shù)同樣的方式對終止?fàn)顟B(tài)進(jìn)行排序評價函數(shù)的計算不能花費太多的時間對于非終止?fàn)顟B(tài)，評價函數(shù)應(yīng)該和取勝的實際機(jī)會密切相關(guān)。如何設(shè)計評價函數(shù)？應(yīng)該以和真正的效用函數(shù)同樣的方式對終止?fàn)顟B(tài)評價函數(shù)（續(xù)）在計算能力有限情況下，評價函數(shù)能做到最好的就是猜測最后的結(jié)果大多數(shù)評價函數(shù)的工作方式是計算狀態(tài)的不同，那么對狀態(tài)的一個合理評價是加權(quán)平均值例如，國際象棋中EVAL通常取為加權(quán)線性函數(shù)（假設(shè)每個特征的貢獻(xiàn)獨立于其它特征的值），評價函數(shù)（續(xù)）在計算能力有限情況下，評價函數(shù)能做到最好的就是截斷搜索用ifCUTOFF-TEST(state,depth)thenreturnEVAL(state)代替–算法中TERMINAL-TEST所在的兩行，或使用迭代搜索：當(dāng)時間用完時，程序就返回目前完成最深的搜索所選擇的招數(shù)。由于評價函數(shù)的近似性，上述方法可能導(dǎo)致錯誤。截斷搜索用ifCUTOFF-TEST(state,dep（a）黑棋有1個馬、2個兵的優(yōu)勢，能夠取勝。（b）黑棋會被白棋吃掉皇后，從而失敗。（a）黑棋有1個馬、2個兵的優(yōu)勢，能夠取勝。截斷搜索（續(xù)）需要更為復(fù)雜的截斷測試，評價函數(shù)應(yīng)該只用于那些靜止的棋局（靜態(tài)棋局）。非靜止的棋局可以進(jìn)一步擴(kuò)展直到靜止的棋局，這種額外的搜索稱為靜態(tài)搜索。截斷搜索（續(xù)）需要更為復(fù)雜的截斷測試，評價函數(shù)應(yīng)該只用于那些

截斷搜索（續(xù)）

地平線效應(yīng)：指對手招數(shù)導(dǎo)致我方嚴(yán)重?fù)p失并且從理論上基本無法避免。單步延伸是避免地平線效應(yīng)的一種策略這樣做可能超過深度限制，但由于單步延伸很少，不會增加太多開銷。

截斷搜索（續(xù)）

地平線效應(yīng)：指對手招數(shù)導(dǎo)致我方嚴(yán)重?fù)p失并且對這兩節(jié)所介紹的技術(shù)的總結(jié)假設(shè)已經(jīng)實現(xiàn)：國際象棋的評價函數(shù)使用靜止搜索的合理截斷測試一個很大的調(diào)換表那么在“最新的PC”上可每秒生成和評價約一百萬個節(jié)點，允許我們在標(biāo)準(zhǔn)時間控制下對每步棋可搜索約2億個節(jié)點，而國際象棋的分支因子平均為35，355約為5億。對這兩節(jié)所介紹的技術(shù)的總結(jié)假設(shè)已經(jīng)實現(xiàn)：第五章、對抗搜索博弈中的優(yōu)化決策–剪枝：允許我們忽略那些不影響最后決定的部分搜索樹不完整的實時決策包含幾率因素的游戲部分可觀察博弈博弈程序的當(dāng)前發(fā)展水平第五章、對抗搜索博弈中的優(yōu)化決策例子：西洋雙陸棋目標(biāo)：將自己的棋子全部移出棋盤白棋順時針向25移動黑棋逆時針向0移動每個棋子按照擲出的骰子數(shù)移動到任意位置除非那里有多個對方棋子，如果只有一個，這個棋子就被吃了，要重新開始。例子：西洋雙陸棋目標(biāo)：將自己的棋子全部移出棋盤雙陸棋的博弈樹（包括幾率節(jié)點）兩個骰子總共有21種骰法，其中：6個有相同骰子數(shù)的組合（1/36概率）15個不同骰子數(shù)的組合（1/18概率）雙陸棋的博弈樹（包括幾率節(jié)點）兩個骰子總共有21種骰法，其中極小極