個(gè)人衛(wèi)生習(xí)慣-皮膚病頭虱的預(yù)防

人工智能06對(duì)抗搜索人工智能06對(duì)抗搜索1GamePlaying博弈博弈被被認(rèn)為是AI研究領(lǐng)域中的一個(gè)很好的難題:

–博弈是不平凡的

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

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

?需要在有限時(shí)間內(nèi)作出決策

–gamesusuallyare:

?定義明確的且可重復(fù)的

?完全可觀察的環(huán)境是有限的

–能直接比較humansandcomputersGamePlaying博弈博弈被被認(rèn)為是AI研究領(lǐng)域中的一2ComputersPlayingChessComputersPlayingChess3對(duì)戰(zhàn)中的AI對(duì)戰(zhàn)中的AI4ComputersPlayingGoComputersPlayingGo5本章大綱博弈博弈中的優(yōu)化決策

—極小極大值算法

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

不可預(yù)測的對(duì)手→解決方案是針對(duì)每一個(gè)可能的對(duì)手回復(fù)的策略

時(shí)間是有限的→不太可能找到最優(yōu)解，需找到近似解

游戲?qū)τ诘托视袊?yán)厲的懲罰

進(jìn)攻計(jì)劃:

?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 不可預(yù)測7游戲的種類確定性的隨機(jī)的、策略的游戲的種類確定性的8博弈樹(2-player,確定性的,輪流出招)博弈樹(2-player,確定性的,輪流出招)9確定性的Two-PlayerE.g.井字棋,國際象棋,跳棋博弈搜索

–狀態(tài)-空間搜索樹

–玩家輪流出招

–每一層包含一輪行動(dòng)

–選擇能獲得最佳效用的行動(dòng)零和游戲

–一個(gè)玩家要最大化效用值

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

–computer假設(shè)在其行動(dòng)以后，其對(duì)手會(huì)選擇效用值最小的狀態(tài)來移動(dòng)

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

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

=bestachievablepayoffagainstbestplay

在對(duì)手也使用最優(yōu)策略的條件下，能導(dǎo)致至少不比其它策略差的結(jié)果

假設(shè)兩個(gè)游戲者都按照最優(yōu)策略進(jìn)行，那么節(jié)點(diǎn)的極小極大值就是對(duì)應(yīng)狀態(tài)的效用值（對(duì)于MAX）

?MAX優(yōu)先選擇有極大值的狀態(tài)

?MIN優(yōu)先選擇有極小值的狀態(tài)Minimax確定性的，完全信息的博弈的最優(yōu)策略12Minimax確定性的，完全信息的博弈的最優(yōu)策略Idea:choosemovetopositionwithhighestminimaxvalue

=bestachievablepayoffagainstbestplay

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

僅當(dāng)博弈樹是有限時(shí)(chesshasspecificrulesforthis).

但在一顆無限的博弈樹中也存在有限的策略~最優(yōu)性？？Minimax的性能完整性？？僅當(dāng)博弈樹是有限時(shí)(che16Minimax的性能完整性？？Yes,僅當(dāng)博弈樹是有限時(shí)最優(yōu)性？？Yes,遇到一個(gè)聰明的對(duì)手。Otherwise??時(shí)間復(fù)雜度？？

Minimax的性能完整性？？Yes,僅當(dāng)博弈樹是有限時(shí)17Minimax的性能完整性？？Yes,僅當(dāng)博弈樹是有限時(shí)最優(yōu)性？？Yes,遇到一個(gè)聰明的對(duì)手。Otherwise??時(shí)間復(fù)雜度？？O(bm)空間復(fù)雜度？？

Minimax的性能完整性？？Yes,僅當(dāng)博弈樹是有限時(shí)18Minimax的性能完整性？？Yes,僅當(dāng)博弈樹是有限時(shí)最優(yōu)性？？Yes,遇到一個(gè)聰明的對(duì)手。Otherwise??時(shí)間復(fù)雜度？？O(bm)空間復(fù)雜度？？

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

Butdoweneedtoexploreeverypath?

Minimax的性能完整性？？Yes,僅當(dāng)博弈樹是有限時(shí)19α-β剪枝?若與一個(gè)聰明的對(duì)手對(duì)弈，則博弈樹上的一些分枝絕不會(huì)發(fā)生?“Ifyouhaveanideathatissurelybad,don’ttakethetimetoseehowtrulyawfulitis.”

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

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

–沒有分枝需要修剪

–相比于窮舉搜索沒有改進(jìn)?最好情況:

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

doublessolvabledepth不幸的是,3550

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

—極小極大值算法

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

UseCUTOFF-TEST(截?cái)鄿y試)insteadofTERMINAL-TEST（終止測試）

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

UseEVALinsteadofUTILITY

用可以估計(jì)棋局效用值的啟發(fā)式評(píng)價(jià)函數(shù)EVAL取代效用函數(shù)

i.e.,估計(jì)位置期望值的評(píng)價(jià)函數(shù)假設(shè)我們有100seconds計(jì)算時(shí)間,探索速度為104nodes/second

→106nodespermove≈358/2

→α?β

reachesdepth8→prettygoodchessprogram4-plylookaheadisahopelesschessplayer!

–4-ply≈humannovice

–8-ply≈typicalPC,humanmaster

–12-ply≈DeepBlue,KasparovResourcelimits資源限制標(biāo)準(zhǔn)方法:深度有限搜33評(píng)價(jià)函數(shù)?評(píng)價(jià)非終止?fàn)顟B(tài)的函數(shù)

?理想函數(shù):返回每個(gè)位置的效用值?在實(shí)踐中:加權(quán)線性函數(shù):

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

e.g.,forchess,w1=9with

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

評(píng)價(jià)函數(shù)?評(píng)價(jià)非終止?fàn)顟B(tài)的函數(shù)

?理想函數(shù):返回每個(gè)34Moreon評(píng)價(jià)函數(shù)?評(píng)價(jià)函數(shù)評(píng)估當(dāng)前局面配置的好壞?一個(gè)線性的評(píng)價(jià)函數(shù)是關(guān)于特征f1,f2,f3的加權(quán)和

–Moreimportantfeaturesgetmoreweight?對(duì)弈的質(zhì)量直接依賴于評(píng)價(jià)函數(shù)的質(zhì)量?為了構(gòu)建一個(gè)好的評(píng)價(jià)函數(shù)，必須:

–利用行業(yè)知識(shí)提取好的特征

–選擇或?qū)W習(xí)更好的權(quán)重Moreon評(píng)價(jià)函數(shù)?評(píng)價(jià)函數(shù)評(píng)估當(dāng)前局面配置的好壞35題外話:精確的評(píng)價(jià)函數(shù)并不重要Behaviorispreservedunderanymonotonic（單調(diào)的）transformationofEVAL

題外話:精確的評(píng)價(jià)函數(shù)并不重要Behaviorispr36對(duì)待有限的時(shí)間?在實(shí)際游戲中，通常對(duì)每一步有時(shí)間限制T?我們?nèi)绾慰紤]這個(gè)問題?

–所以，我們可以設(shè)置一個(gè)保守的深度有限，以保證在T時(shí)間內(nèi)決定一次行動(dòng)

–但是，搜索可能提前結(jié)束，更多搜索的機(jī)會(huì)被浪費(fèi)了對(duì)待有限的時(shí)間?在實(shí)際游戲中，通常對(duì)每一步有時(shí)間限制T37對(duì)待有限的時(shí)間?在實(shí)踐中,迭代深入深度優(yōu)先搜索(IDS)被很好地使用

–運(yùn)行alpha-betasearch以深度限制逐漸增加的方式

–當(dāng)時(shí)間T快運(yùn)行完時(shí)，返回最后一次完整的α?β搜索的結(jié)果(i.e.,thedeepestsearchthatwascompleted)

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

–計(jì)算機(jī)能夠預(yù)見它的決策中的長期棋局序列。機(jī)器拒絕走一步有決定性短期優(yōu)勢

的棋—顯示了非常類似于人類的對(duì)危險(xiǎn)的感覺。——Kasparov

–Kasparovlostthematch2winsto3winsand1tie

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

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

?Chinookended40-year-reignofhumanworldchampionMarionTinsleyin1994.

?In2007,checkerswassolved:perfectplayleadstoadraw.

Chinookcannoteverlose

使用了一個(gè)提前計(jì)算好的存有443,748,401,247個(gè)不多于8個(gè)棋子的棋局?jǐn)?shù)據(jù)庫，使它的殘局(endgame)走棋沒有缺陷

50machinesworkinginparallelontheproblem

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

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

–deepneuralnetworks深度神經(jīng)網(wǎng)絡(luò):

?valuenetworks價(jià)值網(wǎng)絡(luò):toevaluateboardpositions

?policynetworks策略網(wǎng)絡(luò):toselectmoves

–trainedby

?supervisedlearning監(jiān)督學(xué)習(xí)

?reinforcementlearning（強(qiáng)化學(xué)習(xí)）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非確定性游戲概述?權(quán)重取決于事件發(fā)生的概率?將極小極大值推廣為期望極小極大值?Choosemovewithhighest

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

ifstateisaMaxnodethen

returnthehighestEXPECTIMINIMAX-VALUEofSUCCESSORS(state)ifstateisaMinnodethen

returnthelowestEXPECTIMINIMAX-VALUEofSUCCESSORS(state)ifstateisachancenodethen

returnaverageofEXPECTIMINIMAX-VALUEofSUCCESSORS(state)

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

–西洋雙陸棋≈20種合法行動(dòng)

–Depth4=20x(21x20)3=1.2x109?當(dāng)深度增加時(shí)，到達(dá)指定節(jié)點(diǎn)的概率會(huì)收窄

–此時(shí)再向前搜索的價(jià)值會(huì)減少

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

–但是剪枝不太可能實(shí)現(xiàn)…?TDGammonusesdepth-2search+very

goodevalfunction+reinforcement

learning:world-championlevelplay隨機(jī)的Two-Player?擲骰子增加分枝b:兩個(gè)骰子有50題外話：精確的評(píng)價(jià)函數(shù)的重要性BehaviourispreservedonlybypositivelineartransformationofEVALHenceEVALshouldbeproportionaltotheexpectedpayoff

評(píng)價(jià)函數(shù)應(yīng)該是棋局的期望效用值的正線性變換題外話：精確的評(píng)價(jià)函數(shù)的重要性Behaviourispr51本章大綱博弈博弈中的優(yōu)化決策

—極小極大值算法

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

thenchoosetheactionwithhighestexpectedvalueoverallDeals在評(píng)價(jià)一個(gè)有未知牌的給定行動(dòng)過程時(shí)，首先計(jì)算出每副可能牌的出牌行動(dòng)的極小極大值，然后再用每副牌的概率來計(jì)算得到對(duì)所有發(fā)牌情況的期望值。

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

在局部觀察中,一個(gè)行動(dòng)的價(jià)值取決于信度狀態(tài)

這樣可以在信度狀態(tài)中生成和搜索博弈樹

以下行為可以幫助生成信度狀態(tài)：

打出一張牌來刺探對(duì)手

給合伙人發(fā)信號(hào)

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

–perfectionisunattainablemustapproximate

–GamesaretoAIasgrandprix