人工智能06對(duì)抗搜索課件

《人工智能06對(duì)抗搜索課件》由會(huì)員分享，可在線閱讀，更多相關(guān)《人工智能06對(duì)抗搜索課件（61頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),*,,*,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),*,,*,,,,,,,單擊此處編輯母版標(biāo)題樣式,*,,*,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),人工智能06對(duì)抗搜索,人工智能06對(duì)抗搜索人工智能06對(duì)抗搜索Game Playing博弈博弈被被認(rèn)為是AI研究領(lǐng)域中的一個(gè)很好的難題:– 博弈是不平凡的 ? 玩家需要具備“human-like”般的智能 ? 游戲可能非常復(fù)雜(e.g., Chess, Go) ? 需要在有限時(shí)間內(nèi)作出決策– g

2、ames usually are: ? 定義明確的且可重復(fù)的 ? 完全可觀察的環(huán)境是有限的– 能直接比較humans and computers,人工智能06對(duì)抗搜索人工智能06對(duì)抗搜索人工智能06對(duì)抗搜索,1,Game Playing博弈,博弈被被認(rèn)為是,AI,研究領(lǐng)域中的一個(gè)很好的難題,:,–,博弈是不平凡的,?,玩家需要具備,“human-like”,般的智能,?,游戲可能非常復(fù)雜,(e.g., Chess, Go) ?,需要在有限時(shí)間內(nèi)作出決策,– games usually are: ?,定義明確的且可重復(fù)的,?,完全可觀察的環(huán)境是有限的,–,能直接比較,humans an

3、d computers,Game Playing博弈博弈被被認(rèn)為是AI研究領(lǐng)域中的一,2,Computers Playing Chess,Computers Playing Chess,3,對(duì)戰(zhàn)中的AI,對(duì)戰(zhàn)中的AI,4,Computers Playing Go,Computers Playing Go,5,本章大綱,博弈,博弈中的優(yōu)化決策 — 極小極大值算法 — α-β 剪枝,資源限制和近似評(píng)估,包含幾率因素的游戲,不完整信息的游戲,本章大綱博弈,6,Games vs. search problems,,不可預(yù)測(cè)的對(duì)手,→,解決方案是針對(duì)每一個(gè)可能的對(duì)手回復(fù)的策略,,時(shí)間是有限的,→ 不

4、太可能找到最優(yōu)解，需找到近似解,,游戲?qū)τ诘托视袊?yán)厲的懲罰,,,進(jìn)攻計(jì)劃,:? Computer considers possible lines of play (Babbage, 1846)? Algorithm for perfect play (Zermelo, 1912; Von Neumann, 1944)? Finite horizon, approximate evaluation (Zuse, 1945; Wiener, 1948;Shannon, 1950)?,First chess program,(Turing, 1951)?,Machine learni

5、ng,to improve evaluation accuracy (Samuel, 1952-57)?,Pruning,（剪枝）,to allow deeper search (McCarthy, 1956),Games vs. search problems 不可預(yù)測(cè),7,游戲的種類,確定性的 隨機(jī)的、策略的,游戲的種類確定性的,8,博弈樹(2-player, 確定性的, 輪流出招),博弈樹(2-player, 確定性的, 輪流出招),9,確定性的Two-Player,E.g. 井字棋, 國(guó)際象棋, 跳棋,博弈搜索– 狀態(tài)-空間 搜索樹

6、– 玩家輪流出招–每一層包含一輪行動(dòng)–選擇能獲得最佳效用的行動(dòng),零和游戲– 一個(gè)玩家要最大化效用值– 而另一個(gè)要最小化效用值,確定性的Two-PlayerE.g. 井字棋, 國(guó)際象棋,,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) –comp,11,Minimax,確定性的，完全信息的博弈的最優(yōu)策略,Idea: choose move to positio

7、n with,highest minimax value,= best achievable payoff against best play,在對(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)策略,12,Minimax,確定性的，完全信息的博弈的最優(yōu)策略,Idea: choose move to position with,highest minimax value

8、,= best achievable payoff against best play,在對(duì)手,也使用最優(yōu)策略,的條件下，能導(dǎo)致至少不比其它策略差的結(jié)果,,E.g., 2-ply game:,Minimax 確定性的，完全信息的博弈的最優(yōu)策略,13,Minimax algorithm,Minimax algorithm,14,Minimax 的性能,完整性？？,Minimax 的性能完整性？？,15,Minimax 的性能,完整性？？,,僅當(dāng)博弈樹是有限時(shí),(chess has specific rules for this).,但在一顆無限的博弈樹中也存在有限的策略,~,最優(yōu)性？？,Mini

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

10、弈樹是有限時(shí),,最優(yōu)性？？,Yes,,遇到一個(gè)聰明的對(duì)手。,Otherwise??,,時(shí)間復(fù)雜度？？,O(b,m,),,空間復(fù)雜度？？,,O(bm),(,深度優(yōu)先搜索,),For chess, b≈35, m≈100 for “reasonable" games,→,尋找精確解時(shí)完全不可行的,But do we need to explore every path?,Minimax 的性能完整性？？ Yes,僅當(dāng)博弈樹是有限時(shí),19,α - β 剪枝,?,若與一個(gè)聰明的對(duì)手對(duì)弈，則博弈樹上的一些分枝絕不會(huì)發(fā)生,,? “If you have an idea that is surely ba

11、d, don’t take the time to see how truly awful it is.” -- Pat Winston,,?,剪枝能消除搜索樹的很大一部分分枝,α - β 剪枝? 若與一個(gè)聰明的對(duì)手對(duì)弈，則博弈樹上的一,20,α?β pruning example,α?β pruning example,21,α?β pruning example,α?β pruning example,22,α?β pruning example,α?β pruning example,23,α?β pruning example,α?β pruning example,24,

12、α?β pruning example,α?β pruning example,25,為什么叫α?β,?,,α,is the best value (to MAX) found so far on the current path,到目前為止在路徑上的任意選擇點(diǎn)發(fā)現(xiàn)的,MAX,的最佳（即最大值）選擇,? If,v,is worse than,α,, MAX will avoid it, so can stop considering,v’s,other children,→,prune that branch,? Define,β,,similarly for MIN,為什么叫α?β? α i

13、s the best value (,26,The α?β algorithm,The α?β algorithm,27,α?β,剪枝技術(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,α?β搜索的效率,?,效率很大程

14、度上取決于檢查后繼的順序,;,所以嘗試檢查可能較好的后繼是值得的,?,最壞情況,:–,沒有分枝需要修剪,–,相比于窮舉搜索沒有改進(jìn),?,最好情況,:–,每個(gè)玩家的最佳行動(dòng)都先被檢查,?,在實(shí)踐中，性能接近于最好情況，而不是最壞情況，但要依實(shí)際情況而定,α?β搜索的效率? 效率很大程度上取決于檢查后繼的順序; 所,30,α?β的性能,剪枝,不影響,最終結(jié)果,,好的行動(dòng)順序能提高剪枝的效率,,With “perfect ordering," time complexity =,O(b,d/2,),doubles solvable depth,,不幸的是,,,35,50,,也是有可能的,α?β的

15、性能剪枝不影響最終結(jié)果,31,本章大綱,博弈,博弈中的優(yōu)化決策,—,極小極大值算法,—,α-β,剪枝,資源限制和近似評(píng)估,包含幾率因素的游戲,不完整信息的游戲,本章大綱博弈,32,Resource limits資源限制,標(biāo)準(zhǔn)方法,:,深度有限搜索,Use CUTOFF-TEST (,截?cái)鄿y(cè)試,) instead of TERMINAL-TEST,（終止測(cè)試）,e.g., depth limit (perhaps add quiescence search,靜態(tài)搜索,)Use EVAL instead of UTILITY,用可以估計(jì)棋局效用值的啟發(fā)式評(píng)價(jià)函數(shù),EVAL,取代效用函數(shù),i.e.

16、,,估計(jì)位置期望值的評(píng)價(jià)函數(shù),,假設(shè)我們有,100,seconds,計(jì)算時(shí)間,,,探索速度為,10,4,,nodes/second,→,10,6,nodes per move ≈,35,8/2,,→,α?β,,reaches depth 8,→,pretty good chess program,,4-ply lookahead is a hopeless chess player!– 4-ply ≈ human novice– 8-ply ≈ typical PC, human master– 12-ply ≈ Deep Blue, Kasparov,Resource limits資源

17、限制標(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) = w,1,f,1,(s) + w,2,f,2,(s) +,…,+ w,n,f,n,(s),e.g., for chess, w,1,= 9 withf,1,(s)= (number of white queens) - (number of black queens), etc.,,評(píng)價(jià)函數(shù)? 評(píng)價(jià)非終止?fàn)顟B(tài)的函數(shù)? 理想函數(shù): 返回每個(gè),34,More on 評(píng)價(jià)函數(shù),?,評(píng)價(jià)函數(shù)評(píng)估當(dāng)前局面配置的好壞,,?,一個(gè)線性的評(píng)

18、價(jià)函數(shù)是關(guān)于特征,f,1,, f,2,, f,3,的加權(quán)和,– More important features get more weight,,?,對(duì)弈的質(zhì)量直接依賴于評(píng)價(jià)函數(shù)的質(zhì)量,,?,為了構(gòu)建一個(gè)好的評(píng)價(jià)函數(shù)，必須,:–,利用行業(yè)知識(shí)提取好的特征,–,選擇或?qū)W習(xí)更好的權(quán)重,More on 評(píng)價(jià)函數(shù)? 評(píng)價(jià)函數(shù)評(píng)估當(dāng)前局面配置的好壞,35,題外話: 精確的評(píng)價(jià)函數(shù)并不重要,Behavior is preserved under any monotonic,（單調(diào)的）,transformation of EVAL,題外話: 精確的評(píng)價(jià)函數(shù)并不重要Behavior is pr,36,對(duì)待有

19、限的時(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í)間限制T,37,對(duì)待有限的時(shí)間,?,在實(shí)踐中,,,迭代深入深度優(yōu)先搜索,(IDS),被很好地使用,–,運(yùn)行,alpha-beta search,以深度限制逐漸增加的方式,–,當(dāng)時(shí)間,T,快運(yùn)行完時(shí)，返回最后一次完整的,α?β,搜索的結(jié)果,(i.e., the deepest search that was completed),對(duì)待有

20、限的時(shí)間? 在實(shí)踐中, 迭代深入深度優(yōu)先搜索(IDS),38,現(xiàn)今一些確定性的游戲,Chess(,國(guó)際象棋）,: Deep Blue defeated human world champion Gary Kasparov in a six-game match in 1997. Deep Blue searches 200 million positions per second, uses very sophisticated evaluation, and undisclosed methods for extending some lines of search up to 40 ply

21、,（層、厚度）,.–,計(jì)算機(jī)能夠預(yù)見它的決策中的長(zhǎng)期棋局序列。機(jī)器拒絕走一步有決定性短期優(yōu)勢(shì)的棋,—,顯示了非常類似于人類的對(duì)危險(xiǎn)的感覺。,——Kasparov– Kasparov lost the match 2 wins to 3 wins and 1 tie– Deep Blue played by “brute force” (i.e., raw power from computer speed and memory); it used relatively little that is similar to human intuition and cleverness–,

22、Used minimax, alpha-beta, sophisticated heuristics,現(xiàn)今一些確定性的游戲Chess(國(guó)際象棋） : Deep B,39,現(xiàn)今一些確定性的游戲,Checkers,（西洋跳棋）,:,Chinook,, the World Man-Machine Checkers Champion.? Chinook ended,40-year-reign,of human world champion Marion Tinsley in 1994.? In 2007, checkers was solved: perfect play leads to a d

23、raw.,Chinook cannot ever lose,,使用了一個(gè)提前計(jì)算好的存有,443,748,401,247,個(gè)不多于,8,個(gè)棋子的棋局?jǐn)?shù)據(jù)庫(kù)，使它的殘局,(endgame),走棋沒有缺陷,50 machines working in parallel on the problem,現(xiàn)今一些確定性的游戲Checkers（西洋跳棋） : Chi,40,現(xiàn)今一些確定性的游戲,黑白棋,:,人類冠軍已經(jīng)拒絕同計(jì)算機(jī)比賽了,~,,Go,（圍棋）,: 2016,年以前，人類冠軍拒絕與計(jì)算機(jī)比賽，因?yàn)橛?jì)算機(jī)是個(gè)小學(xué)生棋手。,In go, b > 300,（棋盤為,19x19,）,,,所以大多數(shù)程

24、序使用基于模式識(shí)別的方法來提供一個(gè)貌似可行的解。,Go has became a new benchmark for Artificial Intelligence (,人工智能新的試金石,),,現(xiàn)今一些確定性的游戲黑白棋: 人類冠軍已經(jīng)拒絕同計(jì)算機(jī)比賽了,41,AlphaGo: 第一次打敗人類in 19x19 Go,? Google DeepMind computer go player– deep neural networks,深度神經(jīng)網(wǎng)絡(luò),: ? value networks,價(jià)值網(wǎng)絡(luò),: to evaluate board positions ? policy networks

25、,策略網(wǎng)絡(luò),: to select moves– trained by ? supervised learning,監(jiān)督學(xué)習(xí),? reinforcement learning,（強(qiáng)化學(xué)習(xí)）,by self-play– search algorithm ? Monte-Carlo simulation + value/policy networks,AlphaGo: 第一次打敗人類in 19x19 Go? G,42,AlphaGo: Background,?,減少搜索空間,:–,減少搜索深度,? position evaluation–,減少搜索分枝,? move sampling

26、based on policy ? policy = probability distribution p(a|s),AlphaGo: Background? 減少搜索空間:–,43,Deep Neural Networks in AlphaGo,AlphaGo uses two types of neural networks:– policy network: what is the next move? ? learned from human expert moves– value network: what is the value of a state? ? learn

27、ed from self-play using a policy network,SL = supervised learning, RL = reinforcement learning,Deep Neural Networks in AlphaG,44,包含幾率因素的游戲,西洋雙陸棋,包含幾率因素的游戲西洋雙陸棋,45,非確定性游戲概述,在非確定性的游戲中,,,幾率因素是由擲骰子，抽牌等引起的。,,拋硬幣游戲的簡(jiǎn)化示例,:,非確定性游戲概述在非確定性的游戲中, 幾率因素是由擲骰子，抽,46,非確定性游戲概述,?,權(quán)重取決于事件發(fā)生的概率,,?,將極小極大值推廣為,期望,極小極大值,,? C

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

29、 node thenreturn the highest EXPECTIMINIMAX-VALUE of SUCCESSORS(state),if state is a Min node thenreturn the lowest EXPECTIMINIMAX-VALUE of SUCCESSORS(state),if state is a chance node thenreturn average of EXPECTIMINIMAX-VALUE of SUCCESSORS(state),期望極小極大值算法EXPECTIMINIMAX 類似于MIN,49,隨機(jī)的Two-Player,?

30、,擲骰子增加分枝,b:,兩個(gè)骰子有,21,種可能的擲法,–,西洋雙陸棋,≈ 20,種合法行動(dòng),– Depth 4 = 20 x (21 x 20),3,=1.2 x 10,9,?,當(dāng)深度增加時(shí)，到達(dá)指定節(jié)點(diǎn)的概率會(huì)收窄,–,此時(shí)再向前搜索的價(jià)值會(huì)減少,–,所以限定搜索深度是,OK,的,–,但是剪枝不太可能實(shí)現(xiàn),…,? TDGammon uses depth-2 search + verygood eval function + reinforcementlearning: world-champion level play,隨機(jī)的Two-Player? 擲骰子增加分枝b: 兩個(gè)骰子有,50

31、,題外話：精確的評(píng)價(jià)函數(shù)的重要性,Behaviour is preserved only by positive linear transformation of EVAL,Hence EVAL should be proportional to the expected payoff,評(píng)價(jià)函數(shù)應(yīng)該是棋局的期望效用值的正線性變換,題外話：精確的評(píng)價(jià)函數(shù)的重要性Behaviour is pr,51,本章大綱,博弈,博弈中的優(yōu)化決策,—,極小極大值算法,—,α-β,剪枝,資源限制和近似評(píng)估,包含幾率因素的游戲,不完整信息的游戲,本章大綱博弈,52,不完整信息的游戲,E.g., card games

32、, where opponent's initial cards are unknown,Typically we can calculate a probability for each possible deal,Seems just like having one big dice roll at the beginning of the,Game,,Idea: compute the minimax value of each action in each deal,then choose the action with,highest expected,value over all

33、,Deals,,在評(píng)價(jià)一個(gè)有未知牌的給定行動(dòng)過程時(shí)，首先計(jì)算出每副可能,牌的出牌行動(dòng)的極小極大值，然后再用每副牌的概率來計(jì)算得到,對(duì)所有發(fā)牌情況的期望值。,不完整信息的游戲E.g., card games, wher,53,Example,Example,54,Example,Example,55,Example,Example,56,合理的分析,*所以從直覺上說用所有可能狀態(tài)的平均效用值來評(píng)價(jià)一次行動(dòng)的價(jià)值,is WRONG,,在局部觀察中,,,一個(gè)行動(dòng)的價(jià)值取決于,信度狀態(tài),,這樣可以在信度狀態(tài)中生成和搜索博弈樹,,以下行為可以幫助生成信度狀態(tài)：,,打出一張牌來刺探對(duì)手,,給合伙人發(fā)信號(hào),

34、,靠演技來最小化信息披露,合理的分析*所以從直覺上說用所有可能狀態(tài)的平均效用值來評(píng)價(jià)一,57,Summary,? Games are fun to work on!– perfection is unattainable ? must approximate– Games are to AI as grand prix racing is to automobile design,,? Game playing is best modeled as a search problem– Search trees for games represent alternate computer/

35、opponent moves,? Evaluation functions estimate the quality of a given board configuration for each player,,?,Minimax,is an algorithm that chooses “optimal” moves by assuming that the opponent always chooses their best move,?,Alpha-beta,is an algorithm that can avoid large parts of the search tree, t

36、hus enabling the search to go deeper —,消除無關(guān)的子樹以提高效率,Summary? Games are fun to work,58,Summary of Search,? Uninformed search strategiesBreadth-first search (BFS), Uniform cost search, Depth-first search (DFS),Depth-limited search, Iterative deepening search,,? Informed search strategies– Best-firs

37、t search: greedy, A*– Local search: hill climbing, simulated annealing etc.,,? Constraint satisfaction problems– Backtracking = depth-first search with one variable assigned per node– Enhanced with: Variable ordering and value selection heuristics, forwardchecking, constraint propagation,Summary of Search? Uninformed,59,作業(yè),6.1， 6.3， 6.5,作業(yè)6.1， 6.3， 6.5,60,謝謝！,謝謝！,61,