人工智能06對抗搜索人工智能06對抗搜索1GamePlaying博弈博弈被被認為是AI研究領域中的一個很好的難題:

–博弈是不平凡的

?玩家需要具備“human-like”般的智能

?游戲可能非常復雜(e.g.,Chess,Go)

?需要在有限時間內作出決策

–gamesusuallyare:

?定義明確的且可重復的

?完全可觀察的環境是有限的

–能直接比較humansandcomputersGamePlaying博弈博弈被被認為是AI研究領域中的一2ComputersPlayingChessComputersPlayingChess3對戰中的AI對戰中的AI4ComputersPlayingGoComputersPlayingGo5本章大綱博弈博弈中的優化決策

—極小極大值算法

—α-β剪枝資源限制和近似評估包含幾率因素的游戲不完整信息的游戲本章大綱博弈6Gamesvs.searchproblems

不可預測的對手→解決方案是針對每一個可能的對手回復的策略

時間是有限的→不太可能找到最優解，需找到近似解

游戲對于低效率有嚴厲的懲罰

進攻計劃:

?Computerconsiderspossiblelinesofplay(Babbage,1846)

?Algorithmforperfectplay(Zermelo,1912;VonNeumann,1944)

?Finitehorizon,approximateevaluation(Zuse,1945;Wiener,1948;

Shannon,1950)

?Firstchessprogram(Turing,1951)

?Machinelearningtoimproveevaluationaccuracy(Samuel,1952-57)

?Pruning（剪枝）toallowdeepersearch(McCarthy,1956)Gamesvs.searchproblems 不可預測7游戲的種類確定性的隨機的、策略的游戲的種類確定性的8博弈樹(2-player,確定性的,輪流出招)博弈樹(2-player,確定性的,輪流出招)9確定性的Two-PlayerE.g.井字棋,國際象棋,跳棋博弈搜索

–狀態-空間搜索樹

–玩家輪流出招

–每一層包含一輪行動

–選擇能獲得最佳效用的行動零和游戲

–一個玩家要最大化效用值

–而另一個要最小化效用值確定性的Two-PlayerE.g.井字棋,國際象棋,10極小極大值原理假設兩位玩家都按照最佳策略行動

–computer假設在其行動以后，其對手會選擇效用值最小的狀態來移動

–computer在選擇其最佳行動方案時要同時考慮自己以及對手的最佳行動從max的角度顯示效用值極小極大值原理假設兩位玩家都按照最佳策略行動

–comp11Minimax確定性的，完全信息的博弈的最優策略Idea:choosemovetopositionwithhighestminimaxvalue

=bestachievablepayoffagainstbestplay

在對手也使用最優策略的條件下，能導致至少不比其它策略差的結果

假設兩個游戲者都按照最優策略進行，那么節點的極小極大值就是對應狀態的效用值（對于MAX）

?MAX優先選擇有極大值的狀態

?MIN優先選擇有極小值的狀態Minimax確定性的，完全信息的博弈的最優策略12Minimax確定性的，完全信息的博弈的最優策略Idea:choosemovetopositionwithhighestminimaxvalue

=bestachievablepayoffagainstbestplay

在對手也使用最優策略的條件下，能導致至少不比其它策略差的結果E.g.,2-plygame:Minimax確定性的，完全信息的博弈的最優策略13MinimaxalgorithmMinimaxalgorithm14Minimax的性能完整性？？Minimax的性能完整性？？15Minimax的性能完整性？？

僅當博弈樹是有限時(chesshasspecificrulesforthis).

但在一顆無限的博弈樹中也存在有限的策略~最優性？？Minimax的性能完整性？？僅當博弈樹是有限時(che16Minimax的性能完整性？？Yes,僅當博弈樹是有限時最優性？？Yes,遇到一個聰明的對手。Otherwise??時間復雜度？？

Minimax的性能完整性？？Yes,僅當博弈樹是有限時17Minimax的性能完整性？？Yes,僅當博弈樹是有限時最優性？？Yes,遇到一個聰明的對手。Otherwise??時間復雜度？？O(bm)空間復雜度？？

Minimax的性能完整性？？Yes,僅當博弈樹是有限時18Minimax的性能完整性？？Yes,僅當博弈樹是有限時最優性？？Yes,遇到一個聰明的對手。Otherwise??時間復雜度？？O(bm)空間復雜度？？

O(bm)(深度優先搜索)Forchess,b≈35,m≈100for“reasonable"games →尋找精確解時完全不可行的

Butdoweneedtoexploreeverypath?

Minimax的性能完整性？？Yes,僅當博弈樹是有限時19α-β剪枝?若與一個聰明的對手對弈，則博弈樹上的一些分枝絕不會發生?“Ifyouhaveanideathatissurelybad,don’ttakethetimetoseehowtrulyawfulitis.”

--PatWinston?剪枝能消除搜索樹的很大一部分分枝α-β剪枝?若與一個聰明的對手對弈，則博弈樹上的一20α?βpruningexampleα?βpruningexample21α?βpruningexampleα?βpruningexample22α?βpruningexampleα?βpruningexample23α?βpruningexampleα?βpruningexample24α?βpruningexampleα?βpruningexample25為什么叫α?β?αisthebestvalue(toMAX)foundsofaronthecurrentpath

到目前為止在路徑上的任意選擇點發現的MAX的最佳（即最大值）選擇?Ifvisworsethanα,MAXwillavoidit,socanstopconsideringv’sotherchildren→prunethatbranch?DefineβsimilarlyforMIN為什么叫α?β?αisthebestvalue(26Theα?βalgorithmTheα?βalgorithm27α?β剪枝技術對于一個MAX節點來說，它取值稱為α值對于一個MIN節點來說，它取值稱為β值β剪枝：任何MAX節點x的α值如果不能降低其父節點的β值，則對節點x以下的分枝可停止搜索。α剪枝：任何MIN節點x的β值如果不能升高其父節點的α值，則對節點x以下的分枝可停止搜索。α?β剪枝技術對于一個MAX節點來說，它取值稱為α值28α?β剪枝案例α?β剪枝案例29α?β搜索的效率?效率很大程度上取決于檢查后繼的順序;所以嘗試檢查可能較好的后繼是值得的?最壞情況:

–沒有分枝需要修剪

–相比于窮舉搜索沒有改進?最好情況:

–每個玩家的最佳行動都先被檢查?在實踐中，性能接近于最好情況，而不是最壞情況，但要依實際情況而定α?β搜索的效率?效率很大程度上取決于檢查后繼的順序;所30α?β的性能剪枝不影響最終結果好的行動順序能提高剪枝的效率With“perfectordering,"timecomplexity=O(bd/2)

doublessolvabledepth不幸的是,3550

也是有可能的α?β的性能剪枝不影響最終結果31本章大綱博弈博弈中的優化決策

—極小極大值算法

—α-β剪枝資源限制和近似評估包含幾率因素的游戲不完整信息的游戲本章大綱博弈32Resourcelimits資源限制標準方法:深度有限搜索

UseCUTOFF-TEST(截斷測試)insteadofTERMINAL-TEST（終止測試）

e.g.,depthlimit(perhapsaddquiescencesearch靜態搜索)

UseEVALinsteadofUTILITY

用可以估計棋局效用值的啟發式評價函數EVAL取代效用函數

i.e.,估計位置期望值的評價函數假設我們有100seconds計算時間,探索速度為104nodes/second

→106nodespermove≈358/2

→α?β

reachesdepth8→prettygoodchessprogram4-plylookaheadisahopelesschessplayer!

–4-ply≈humannovice

–8-ply≈typicalPC,humanmaster

–12-ply≈DeepBlue,KasparovResourcelimits資源限制標準方法:深度有限搜33評價函數?評價非終止狀態的函數

?理想函數:返回每個位置的效用值?在實踐中:加權線性函數:

Eval(s)=w1f1(s)+w2f2(s)+…+wnfn(s)

e.g.,forchess,w1=9with

f1(s)=(numberofwhitequeens)-(numberofblackqueens),etc.

評價函數?評價非終止狀態的函數

?理想函數:返回每個34Moreon評價函數?評價函數評估當前局面配置的好壞?一個線性的評價函數是關于特征f1,f2,f3的加權和

–Moreimportantfeaturesgetmoreweight?對弈的質量直接依賴于評價函數的質量?為了構建一個好的評價函數，必須:

–利用行業知識提取好的特征

–選擇或學習更好的權重Moreon評價函數?評價函數評估當前局面配置的好壞35題外話:精確的評價函數并不重要Behaviorispreservedunderanymonotonic（單調的）transformationofEVAL

題外話:精確的評價函數并不重要Behaviorispr36對待有限的時間?在實際游戲中，通常對每一步有時間限制T?我們如何考慮這個問題?

–所以，我們可以設置一個保守的深度有限，以保證在T時間內決定一次行動

–但是，搜索可能提前結束，更多搜索的機會被浪費了對待有限的時間?在實際游戲中，通常對每一步有時間限制T37對待有限的時間?在實踐中,迭代深入深度優先搜索(IDS)被很好地使用

–運行alpha-betasearch以深度限制逐漸增加的方式

–當時間T快運行完時，返回最后一次完整的α?β搜索的結果(i.e.,thedeepestsearchthatwascompleted)

對待有限的時間?在實踐中,迭代深入深度優先搜索(IDS)38現今一些確定性的游戲Chess(國際象棋）:DeepBluedefeatedhumanworldchampionGaryKasparovinasix-gamematchin1997.DeepBluesearches200millionpositionspersecond,usesverysophisticatedevaluation,andundisclosedmethodsforextendingsomelinesofsearchupto40ply（層、厚度）.

–計算機能夠預見它的決策中的長期棋局序列。機器拒絕走一步有決定性短期優勢

的棋—顯示了非常類似于人類的對危險的感覺。——Kasparov

–Kasparovlostthematch2winsto3winsand1tie

–DeepBlueplayedby“bruteforce”(i.e.,rawpowerfromcomputerspeedandmemory);itusedrelativelylittlethatissimilartohumanintuitionandcleverness

–Usedminimax,alpha-beta,sophisticatedheuristics現今一些確定性的游戲Chess(國際象棋）:DeepB39現今一些確定性的游戲Checkers（西洋跳棋）:Chinook,theWorldMan-MachineCheckersChampion.

?Chinookended40-year-reignofhumanworldchampionMarionTinsleyin1994.

?In2007,checkerswassolved:perfectplayleadstoadraw.

Chinookcannoteverlose

使用了一個提前計算好的存有443,748,401,247個不多于8個棋子的棋局數據庫，使它的殘局(endgame)走棋沒有缺陷

50machinesworkinginparallelontheproblem

現今一些確定性的游戲Checkers（西洋跳棋）:Chi40現今一些確定性的游戲黑白棋:人類冠軍已經拒絕同計算機比賽了~Go（圍棋）:2016年以前，人類冠軍拒絕與計算機比賽，因為計算機是個小學生棋手。Ingo,b>300（棋盤為19x19）,所以大多數程序使用基于模式識別的方法來提供一個貌似可行的解。GohasbecameanewbenchmarkforArtificialIntelligence(人工智能新的試金石)

現今一些確定性的游戲黑白棋:人類冠軍已經拒絕同計算機比賽了41AlphaGo:第一次打敗人類in19x19Go?GoogleDeepMindcomputergoplayer

–deepneuralnetworks深度神經網絡:

?valuenetworks價值網絡:toevaluateboardpositions

?policynetworks策略網絡:toselectmoves

–trainedby

?supervisedlearning監督學習

?reinforcementlearning（強化學習）byself-play

–searchalgorithm

?Monte-Carlosimulation+value/policynetworksAlphaGo:第一次打敗人類in19x19Go?G42AlphaGo:Background?減少搜索空間:

–減少搜索深度

?positionevaluation

–減少搜索分枝

?movesamplingbasedonpolicy

?policy=probabilitydistributionp(a|s)AlphaGo:Background?減少搜索空間:

–43DeepNeuralNetworksinAlphaGoAlphaGousestwotypesofneuralnetworks:

–policynetwork:whatisthenextmove?

?learnedfromhumanexpertmoves

–valuenetwork:whatisthevalueofastate?

?learnedfromself-playusingapolicynetworkSL=supervisedlearning,RL=reinforcementlearningDeepNeuralNetworksinAlphaG44包含幾率因素的游戲西洋雙陸棋包含幾率因素的游戲西洋雙陸棋45非確定性游戲概述在非確定性的游戲中,幾率因素是由擲骰子，抽牌等引起的。

拋硬幣游戲的簡化示例:

非確定性游戲概述在非確定性的游戲中,幾率因素是由擲骰子，抽46非確定性游戲概述?權重取決于事件發生的概率?將極小極大值推廣為期望極小極大值?Choosemovewithhighest

expectedvalue非確定性游戲概述?權重取決于事件發生的概率47期望效用最大化?為什么我們要計算平均效用值?為什么不計算極小極大值??期望效用最大化原則:一個智能體基于其給定的知識庫，會根據期望效用最大化來選擇行動方式?決策的一般性原則?經常作為理性的定義?我們會在本課程中反復看到該觀點!期望效用最大化?為什么我們要計算平均效用值?為什么不計算48期望極小極大值算法EXPECTIMINIMAX類似于MINIMAX，多考慮一個幾率節點

ifstateisaMaxnodethen

returnthehighestEXPECTIMINIMAX-VALUEofSUCCESSORS(state)ifstateisaMinnodethen

returnthelowestEXPECTIMINIMAX-VALUEofSUCCESSORS(state)ifstateisachancenodethen

returnaverageofEXPECTIMINIMAX-VALUEofSUCCESSORS(state)

期望極小極大值算法EXPECTIMINIMAX類似于MIN49隨機的Two-Player?擲骰子增加分枝b:兩個骰子有21種可能的擲法

–西洋雙陸棋≈20種合法行動

–Depth4=20x(21x20)3=1.2x109?當深度增加時，到達指定節點的概率會收窄

–此時再向前搜索的價值會減少

–所以限定搜索深度是OK的

–但是剪枝不太可能實現…?TDGammonusesdepth-2search+very

goodevalfunction+reinforcement

learning:world-championlevelplay隨機的Two-Player?擲骰子增加分枝b:兩個骰子有50題外話：精確的評價函數的重要性BehaviourispreservedonlybypositivelineartransformationofEVALHenceEVALshouldbeproportionaltotheexpectedpayoff

評價函數應該是棋局的期望效用值的正線性變換題外話：精確的評價函數的重要性Behaviourispr51本章大綱博弈博弈中的優化決策

—極小極大值算法

—α-β剪枝資源限制和近似評估包含幾率因素的游戲不完整信息的游戲本章大綱博弈52不完整信息的游戲E.g.,cardgames,whereopponent'sinitialcardsareunknownTypicallywecancalculateaprobabilityforeachpossibledealSeemsjustlikehavingonebigdicerollatthebeginningoftheGameIdea:computetheminimaxvalueofeachactionineachdeal,

thenchoosetheactionwithhighestexpectedvalueoverallDeals在評價一個有未知牌的給定行動過程時，首先計算出每副可能牌的出牌行動的極小極大值，然后再用每副牌的概率來計算得到對所有發牌情況的期望值。

不完整信息的游戲E.g.,cardgames,wher53ExampleExample54ExampleExample55ExampleExample56合理的分析*所以從直覺上說用所有可能狀態的平均效用值來評價一次行動的價值isWRONG

在局部觀察中,一個行動的價值取決于信度狀態

這樣可以在信度狀態中生成和搜索博弈樹

以下行為可以幫助生成信度狀態：

打出一張牌來刺探對手

給合伙人發信號

靠演技來最小化信息披露合理的分析*所以從直覺上說用所有可能狀態的平均效用值來評價一57Summary?Gamesarefuntoworkon!

–perfectionisunattainablemustapproximate

–GamesaretoAIasgrandprix