《人工智能06對抗搜索課件》由會員分享，可在線閱讀，更多相關《人工智能06對抗搜索課件（61頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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

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

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

4、太可能找到最優(yōu)解，需找到近似解,,游戲對于低效率有嚴厲的懲罰,,,進攻計劃,:? 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 不可預測,7,游戲的種類,確定性的 隨機的、策略的,游戲的種類確定性的,8,博弈樹(2-player, 確定性的, 輪流出招),博弈樹(2-player, 確定性的, 輪流出招),9,確定性的Two-Player,E.g. 井字棋, 國際象棋, 跳棋,博弈搜索– 狀態(tài)-空間 搜索樹

6、– 玩家輪流出招–每一層包含一輪行動–選擇能獲得最佳效用的行動,零和游戲– 一個玩家要最大化效用值– 而另一個要最小化效用值,確定性的Two-PlayerE.g. 井字棋, 國際象棋,,10,極小極大值原理,假設兩位玩家都按照最佳策略行動,–computer,假設在其行動以后，其對手會選擇效用值最小的狀態(tài)來移動,–computer,在選擇其最佳行動方案時要同時考慮自己以及對手的最佳行動,從max的角度顯示效用值,極小極大值原理假設兩位玩家都按照最佳策略行動 –comp,11,Minimax,確定性的，完全信息的博弈的最優(yōu)策略,Idea: choose move to positio

7、n with,highest minimax value,= best achievable payoff against best play,在對手,也使用最優(yōu)策略,的條件下，能導致至少不比其它策略差的結果,,,假設兩個游戲者都按照最優(yōu)策略進行，那么節(jié)點的極小極大值就是對應狀態(tài)的效用值（對于,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,在對手,也使用最優(yōu)策略,的條件下，能導致至少不比其它策略差的結果,,E.g., 2-ply game:,Minimax 確定性的，完全信息的博弈的最優(yōu)策略,13,Minimax algorithm,Minimax algorithm,14,Minimax 的性能,完整性？？,Minimax 的性能完整性？？,15,Minimax 的性能,完整性？？,,僅當博弈樹是有限時,(chess has specific rules for this).,但在一顆無限的博弈樹中也存在有限的策略,~,最優(yōu)性？？,Mini

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

10、弈樹是有限時,,最優(yōu)性？？,Yes,,遇到一個聰明的對手。,Otherwise??,,時間復雜度？？,O(b,m,),,空間復雜度？？,,O(bm),(,深度優(yōu)先搜索,),For chess, b≈35, m≈100 for “reasonable" games,→,尋找精確解時完全不可行的,But do we need to explore every path?,Minimax 的性能完整性？？ Yes,僅當博弈樹是有限時,19,α - β 剪枝,?,若與一個聰明的對手對弈，則博弈樹上的一些分枝絕不會發(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,,?,剪枝能消除搜索樹的很大一部分分枝,α - β 剪枝? 若與一個聰明的對手對弈，則博弈樹上的一,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,到目前為止在路徑上的任意選擇點發(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,α?β,剪枝技術,對于一個,MAX,節(jié)點來說，它取值稱為,α,值,對于一個,MIN,節(jié)點來說，它取值稱為,β,值,,β,剪枝：任何,MAX,節(jié)點,x,的,α,值如果不能降低其父節(jié)點的,β,值，則對節(jié)點,x,以下的分枝可停止搜索。,α,剪枝：任何,MIN,節(jié)點,x,的,β,值如果不能升高其父節(jié)點的,α,值，則對節(jié)點,x,以下的分枝可停止搜索。,,α?β剪枝技術對于一個MAX節(jié)點來說，它取值稱為α值,28,α?β,剪枝案例,α?β剪枝案例,29,α?β搜索的效率,?,效率很大程

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

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

16、,,估計位置期望值的評價函數(shù),,假設我們有,100,seconds,計算時間,,,探索速度為,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、限制標準方法: 深度有限搜,33,評價函數(shù),?,評價非終止狀態(tài)的函數(shù),,?,理想函數(shù),:,返回每個位置的效用值,?,在實踐中,:,加權線性函數(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.,,評價函數(shù)? 評價非終止狀態(tài)的函數(shù)? 理想函數(shù): 返回每個,34,More on 評價函數(shù),?,評價函數(shù)評估當前局面配置的好壞,,?,一個線性的評

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

19、限的時間,?,在實際游戲中，通常對每一步有時間限制,T,?,我們?nèi)绾慰紤]這個問題,?–,所以，我們可以設置一個保守的深度有限，以保證在,T,時間內(nèi)決定一次行動,–,但是，搜索可能提前結束，更多搜索的機會被浪費了,對待有限的時間? 在實際游戲中，通常對每一步有時間限制T,37,對待有限的時間,?,在實踐中,,,迭代深入深度優(yōu)先搜索,(IDS),被很好地使用,–,運行,alpha-beta search,以深度限制逐漸增加的方式,–,當時間,T,快運行完時，返回最后一次完整的,α?β,搜索的結果,(i.e., the deepest search that was completed),對待有

20、限的時間? 在實踐中, 迭代深入深度優(yōu)先搜索(IDS),38,現(xiàn)今一些確定性的游戲,Chess(,國際象棋）,: 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、,（層、厚度）,.–,計算機能夠預見它的決策中的長期棋局序列。機器拒絕走一步有決定性短期優(yōu)勢的棋,—,顯示了非常類似于人類的對危險的感覺。,——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(國際象棋） : 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,,使用了一個提前計算好的存有,443,748,401,247,個不多于,8,個棋子的棋局數(shù)據(jù)庫，使它的殘局,(endgame),走棋沒有缺陷,50 machines working in parallel on the problem,現(xiàn)今一些確定性的游戲Checkers（西洋跳棋） : Chi,40,現(xiàn)今一些確定性的游戲,黑白棋,:,人類冠軍已經(jīng)拒絕同計算機比賽了,~,,Go,（圍棋）,: 2016,年以前，人類冠軍拒絕與計算機比賽，因為計算機是個小學生棋手。,In go, b > 300,（棋盤為,19x19,）,,,所以大多數(shù)程

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

25、,策略網(wǎng)絡,: to select moves– trained by ? supervised learning,監(jiān)督學習,? reinforcement learning,（強化學習）,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,非確定性游戲概述,在非確定性的游戲中,,,幾率因素是由擲骰子，抽牌等引起的。,,拋硬幣游戲的簡化示例,:,非確定性游戲概述在非確定性的游戲中, 幾率因素是由擲骰子，抽,46,非確定性游戲概述,?,權重取決于事件發(fā)生的概率,,?,將極小極大值推廣為,期望,極小極大值,,? C

28、hoose move with highestexpected value,非確定性游戲概述? 權重取決于事件發(fā)生的概率,47,期望效用最大化,?,為什么我們要計算平均效用值,?,為什么不計算極小極大值,?,,?,期望效用最大化原則,:,一個智能體基于其給定的知識庫，會根據(jù),期望效用最大化,來選擇行動方式,,?,決策的一般性原則,?,經(jīng)常作為理性的定義,?,我們會在本課程中反復看到該觀點,!,期望效用最大化? 為什么我們要計算平均效用值? 為什么不計算,48,期望極小極大值算法,EXPECTIMINIMAX,類似于,MINIMAX,，多考慮一個幾率節(jié)點,,,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,隨機的Two-Player,?

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

31、,題外話：精確的評價函數(shù)的重要性,Behaviour is preserved only by positive linear transformation of EVAL,Hence EVAL should be proportional to the expected payoff,評價函數(shù)應該是棋局的期望效用值的正線性變換,題外話：精確的評價函數(shù)的重要性Behaviour is pr,51,本章大綱,博弈,博弈中的優(yōu)化決策,—,極小極大值算法,—,α-β,剪枝,資源限制和近似評估,包含幾率因素的游戲,不完整信息的游戲,本章大綱博弈,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,,在評價一個有未知牌的給定行動過程時，首先計算出每副可能,牌的出牌行動的極小極大值，然后再用每副牌的概率來計算得到,對所有發(fā)牌情況的期望值。,不完整信息的游戲E.g., card games, wher,53,Example,Example,54,Example,Example,55,Example,Example,56,合理的分析,*所以從直覺上說用所有可能狀態(tài)的平均效用值來評價一次行動的價值,is WRONG,,在局部觀察中,,,一個行動的價值取決于,信度狀態(tài),,這樣可以在信度狀態(tài)中生成和搜索博弈樹,,以下行為可以幫助生成信度狀態(tài)：,,打出一張牌來刺探對手,,給合伙人發(fā)信號,

34、,靠演技來最小化信息披露,合理的分析*所以從直覺上說用所有可能狀態(tài)的平均效用值來評價一,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 —,消除無關的子樹以提高效率,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,