湖南大學(xué)人工智能課件5

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,#,第五章,對抗搜索,內(nèi)容提要,博弈,-,剪枝,不完美的實(shí)時(shí)決策,隨機(jī)博弈,部分可觀察的博弈,發(fā)展現(xiàn)狀,博弈,競爭環(huán)境中多個(gè),agent,之間的目標(biāo)是有沖突的，稱為,對抗搜索問題,，也稱為,博弈,博弈,有完整信息的，確定的，輪流行動(dòng)的，兩個(gè)游戲者的零和游戲,如國際象棋,難于求解,注重時(shí)間效率,兩個(gè)人之間的游戲,游戲表示成搜索問題,S,0,初始狀態(tài),Player(s),誰行動(dòng),Action(s),狀態(tài)下的合法移動(dòng)集合,Result(s,a),轉(zhuǎn)移模型,Terminal-test(s):,終止測試,Utility(s,p):,效用函數(shù),博弈樹,零和游戲,葉子結(jié)點(diǎn)表示結(jié)果,贏,:1,輸,:-1,和,:0,博弈中的優(yōu)化決策,博弈樹的最優(yōu)策略通過檢查每個(gè)結(jié)點(diǎn)的極大極小值來決定：,minimax(n),Max,喜歡移動(dòng)到有極大值的狀態(tài)，,min,喜歡移動(dòng)到有極小值的狀態(tài),極小極大算法,極小極大算法,3,極小極大算法,完備性？,最優(yōu)性？,時(shí)間復(fù)雜度？,空間復(fù)雜度？,多人博弈,與兩人博弈的不同,用向量值取代單一值,通常選擇使自己效用值最大的行為,聯(lián)盟與破壞聯(lián)盟,-,剪枝,游戲狀態(tài)數(shù)目的增長是指數(shù)級(jí)的,通過剪枝來消除對部分分支的搜索，且被剪掉的分支不影響最終的決策,-,剪枝,-,剪枝,-,剪枝,-,剪枝,-,剪枝的效率很大程度上依賴于檢查后繼狀態(tài)的順序,最佳剪枝情況下可以將時(shí)間復(fù)雜度從極大極小算法的,O(b,m,),減少到,O(b,m/2,),，采用隨機(jī)順序檢查的總結(jié)點(diǎn)數(shù)大約是,O(b,3m/4,),資源限制,當(dāng)遇到大的問題的時(shí)候搜索空間是非常大的,解決問題的方法：,截?cái)鄿y試,限制搜索深度或搜索時(shí)間,評(píng)估函數(shù),評(píng)估當(dāng)前位置的有效性值,評(píng)估函數(shù),評(píng)估函數(shù)的定義準(zhǔn)則：,對于終止?fàn)顟B(tài)的排序應(yīng)該和效用函數(shù)一致,計(jì)算時(shí)間不能太長,對于非終止?fàn)顟B(tài)應(yīng)該和取勝幾率相關(guān),評(píng)估函數(shù),評(píng)估函數(shù)的效率值可能被映射到多個(gè)終止?fàn)顟B(tài),用終止?fàn)顟B(tài)的概率值來表示當(dāng)前狀態(tài)的期望值,0.72*1+0.2*0+0.08*(-1)=0.76,評(píng)估函數(shù),對于國際象棋問題，典型的評(píng)估函數(shù)是線性加權(quán)評(píng)估：,Eval(s)=w,1,f,1,(s)+w,2,f,2,(s)+w,n,f,n,(s),Eg.w,1,=9,f,1,=(,白棋皇后數(shù)量,)-(,黑棋皇后數(shù)量,),線性評(píng)估假定特征之間是獨(dú)立的，然而實(shí)際中特征之間具有關(guān)聯(lián)性，比如國際象棋在殘局中,2,個(gè)象比單個(gè)象的價(jià)值要高出,2,倍,截?cái)嗨阉?Environment:Patient,hospital,staff,Actuators:Screen display(questions,tests,diagnoses,treatments,referrals),Sensors:Keyboard(entry of symptoms,findings,patients answers),在,-,剪枝算法中,Terminal-test,被替換程,cutoff-test(state,depth),Utility,被替換程,eval(state),cutoff-test(state,depth),截?cái)嗖呗裕?當(dāng)大于固定深度是返回,True,根據(jù)游戲允許的時(shí)間來決定深度,截?cái)嗨阉?評(píng)估函數(shù)的近似性會(huì)使截?cái)嗨阉骺赡軐?dǎo)致錯(cuò)誤,評(píng)估函數(shù)只適應(yīng)于靜態(tài)棋局，即不會(huì)很快出現(xiàn)大搖擺的棋局,地平線效應(yīng),22,對方招數(shù)導(dǎo)致我方嚴(yán)重?fù)p失并且理論上基本無法避免,黑棋行棋后，黑象命運(yùn)已定，但是黑方可以通過檢查白王和兵，迫使王吃兵。這樣就將象拉出了地平線，被犧牲掉的兵被搜索算法視為好棋招,前向剪枝,23,無需考慮直接剪枝一些子結(jié)點(diǎn),柱搜索,每一層只考慮最好的,n,步棋,可能導(dǎo)致最佳的行棋被剪掉,Probcut,算法,使用先驗(yàn)的統(tǒng)計(jì)信息在一定程度上保護(hù)最佳行棋不被剪枝掉,首先淺層搜索計(jì)算結(jié)點(diǎn)的,v,值，再根據(jù)經(jīng)驗(yàn)來估計(jì)深度,d,上的值是否在,(,),范圍外,搜索與查表,開局時(shí)的行棋大多依賴于人類的專業(yè)知識(shí),接近尾聲的棋局可能性有限,在開局和尾聲階段可以通過查表的方式來進(jìn)行行棋,隨機(jī)博弈,25,許多博弈存在不確定性的隨機(jī)因素，如擲骰子，我們稱為隨機(jī)博弈,如西洋雙陸棋,結(jié)合了運(yùn)氣和技巧,通過擲骰子決定合法行動(dòng),白方擲骰子,(6-5),將有,4,中合法移動(dòng),隨機(jī)博弈,西洋雙陸棋的博弈樹除了,max,和,min,結(jié)點(diǎn)之外還必須包括隨機(jī)結(jié)點(diǎn),沒有明確的極大極小值，而是期望值,隨機(jī)博弈,27,期望極大極小值,機(jī)會(huì)博弈的評(píng)估函數(shù),評(píng)估函數(shù)應(yīng)該與棋局獲勝的概率成線性變換,時(shí)間復(fù)雜度,(b,m,n,m,),部分可觀察的博弈,軍旗,棋子可以移動(dòng)但對方看不見棋子是什么,使用信念狀態(tài),牌類,隨機(jī)部分可觀察,需要概率推算來制定決策,發(fā)展現(xiàn)狀,30,國際象棋：深藍(lán)打敗世界冠軍。深藍(lán)在,30,個(gè),IBM RS/6000,處理器并行計(jì)算機(jī)上運(yùn)行,-,剪枝。,西洋跳棋：,Chinook,程序,1990,年戰(zhàn)勝了世界冠軍,奧賽羅：也叫翻轉(zhuǎn)棋，,1997,年,6,比,0,擊敗人類世界冠軍,西洋雙陸棋：,1992,年,Gerry Teasuro,使用強(qiáng)化學(xué)習(xí)與神經(jīng)網(wǎng)絡(luò)訓(xùn)練的評(píng)估函數(shù)性能良好。,總結(jié),博弈,-,剪枝,不完美的實(shí)時(shí)決策,隨機(jī)博弈,部分可觀察的博弈,發(fā)展現(xiàn)狀,Qa,？,