第五章-對(duì)抗搜索分析課件

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

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

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

–剪枝＝到目前為止我們?cè)诼窂缴系娜我膺x擇點(diǎn)發(fā)現(xiàn)的MAX的最佳選擇＝到目前為止我們?cè)诼窂缴系娜我膺x擇點(diǎn)發(fā)現(xiàn)的MIN的最佳選擇–剪枝的效率很大程度上取決于檢查后繼的順序如果能夠先檢查那些可能最好的后繼，那么算法的時(shí)間復(fù)雜度為O(bd/2)。

–剪枝＝到目前為止我們?cè)诼窂缴系娜我膺x擇點(diǎn)發(fā)現(xiàn)的MA

–剪枝算法

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

截?cái)嗨阉鳎ɡm(xù)）

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

截?cái)嗨阉鳎ɡm(xù)）

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

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

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

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

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

–剪枝＝到目前為止我們?cè)诼窂缴系娜我膺x擇點(diǎn)發(fā)現(xiàn)的MAX的最佳選擇＝到目前為止我們?cè)诼窂缴系娜我膺x擇點(diǎn)發(fā)現(xiàn)的MIN的最佳選擇–剪枝的效率很大程度上取決于檢查后繼的順序如果能夠先檢查那些可能最好的后繼，那么算法的時(shí)間復(fù)雜度為O(bd/2)。

–剪枝＝到目前為止我們?cè)诼窂缴系娜我膺x擇點(diǎn)發(fā)現(xiàn)的MA

–剪枝算法

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

截?cái)嗨阉鳎ɡm(xù)）

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

截?cái)嗨阉鳎ɡm(xù)）

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