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

第五章

對抗搜索

第五章

對抗搜索

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

Qa？

第五章

對抗搜索

第五章

對抗搜索

2015年1月湖南大學(xué)信息科學(xué)與工程學(xué)院內(nèi)容提要博弈α-β剪枝不完美的實時決策隨機(jī)博弈部分可觀察的博弈發(fā)展現(xiàn)狀內(nèi)容提要博弈34博弈競爭環(huán)境中多個agent之間的目標(biāo)是有沖突的，稱為對抗搜索問題，也稱為博弈博弈有完整信息的，確定的，輪流行動的，兩個游戲者的零和游戲,如國際象棋難于求解注重時間效率博弈競爭環(huán)境中多個agent之間的目標(biāo)是有沖突的，稱為對抗搜35兩個人之間的游戲游戲表示成搜索問題S0初始狀態(tài)Player(s)誰行動Action(s)狀態(tài)下的合法移動集合Result(s,a)轉(zhuǎn)移模型Terminal-test(s):終止測試Utility(s,p):效用函數(shù)兩個人之間的游戲游戲表示成搜索問題36博弈樹零和游戲葉子結(jié)點表示結(jié)果贏:1輸:-1和:0博弈樹零和游戲37博弈中的優(yōu)化決策博弈樹的最優(yōu)策略通過檢查每個結(jié)點的極大極小值來決定：minimax(n)Max喜歡移動到有極大值的狀態(tài)，min喜歡移動到有極小值的狀態(tài)博弈中的優(yōu)化決策博弈樹的最優(yōu)策略通過檢查每個結(jié)點的極大極小值38極小極大算法極小極大算法39極小極大算法3極小極大算法340極小極大算法完備性？最優(yōu)性？時間復(fù)雜度？空間復(fù)雜度？極小極大算法完備性？41多人博弈與兩人博弈的不同用向量值取代單一值通常選擇使自己效用值最大的行為聯(lián)盟與破壞聯(lián)盟多人博弈與兩人博弈的不同42α-β剪枝游戲狀態(tài)數(shù)目的增長是指數(shù)級的通過剪枝來消除對部分分支的搜索，且被剪掉的分支不影響最終的決策α-β剪枝游戲狀態(tài)數(shù)目的增長是指數(shù)級的43α-β剪枝α-β剪枝44α-β剪枝α-β剪枝45α-β剪枝α-β剪枝46α-β剪枝α-β剪枝的效率很大程度上依賴于檢查后繼狀態(tài)的順序最佳剪枝情況下可以將時間復(fù)雜度從極大極小算法的O(bm)減少到O(bm/2)，采用隨機(jī)順序檢查的總結(jié)點數(shù)大約是O(b3m/4)α-β剪枝α-β剪枝的效率很大程度上依賴于檢查后繼狀態(tài)的順序47資源限制當(dāng)遇到大的問題的時候搜索空間是非常大的解決問題的方法：截斷測試限制搜索深度或搜索時間評估函數(shù)評估當(dāng)前位置的有效性值資源限制當(dāng)遇到大的問題的時候搜索空間是非常大的48評估函數(shù)評估函數(shù)的定義準(zhǔn)則：對于終止?fàn)顟B(tài)的排序應(yīng)該和效用函數(shù)一致計算時間不能太長對于非終止?fàn)顟B(tài)應(yīng)該和取勝幾率相關(guān)評估函數(shù)評估函數(shù)的定義準(zhǔn)則：49評估函數(shù)評估函數(shù)的效率值可能被映射到多個終止?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評估函數(shù)評估函數(shù)的效率值可能被映射到多個終止?fàn)顟B(tài)50評估函數(shù)對于國際象棋問題，典型的評估函數(shù)是線性加權(quán)評估：Eval(s)=w1f1(s)+w2f2(s)+…+wnfn(s)Eg.w1=9,f1=(白棋皇后數(shù)量)-(黑棋皇后數(shù)量)線性評估假定特征之間是獨立的，然而實際中特征之間具有關(guān)聯(lián)性，比如國際象棋在殘局中2個象比單個象的價值要高出2倍評估函數(shù)對于國際象棋問題，典型的評估函數(shù)是線性加權(quán)評估：51截斷搜索Environment:Patient,hospital,staffActuators:Screendisplay(questions,tests,diagnoses,treatments,referrals)Sensors:Keyboard(entryofsymptoms,findings,patient'sanswers)在α-β剪枝算法中Terminal-test被替換程cutoff-test(state,depth)Utility被替換程eval(state)cutoff-test(state,depth)截斷策略：當(dāng)大于固定深度是返回True根據(jù)游戲允許的時間來決定深度截斷搜索Environment:Patient,ho52截斷搜索評估函數(shù)的近似性會使截斷搜索可能導(dǎo)致錯誤評估函數(shù)只適應(yīng)于靜態(tài)棋局，即不會很快出現(xiàn)大搖擺的棋局截斷搜索評估函數(shù)的近似性會使截斷搜索可能導(dǎo)致錯誤53地平線效應(yīng)54對方招數(shù)導(dǎo)致我方嚴(yán)重?fù)p失并且理論上基本無法避免黑棋行棋后，黑象命運已定，但是黑方可以通過檢查白王和兵，迫使王吃兵。這樣就將象拉出了地平線，被犧牲掉的兵被搜索算法視為好棋招地平線效應(yīng)22對方招數(shù)導(dǎo)致我方嚴(yán)重?fù)p失并且理論上基本無法避免前向剪枝55無需考慮直接剪枝一些子結(jié)點柱搜索每一層只考慮最好的n步棋可能導(dǎo)致最佳的行棋被剪掉Probcut算法使用先驗的統(tǒng)計信息在一定程度上保護(hù)最佳行棋不被剪枝掉首先淺層搜索計算結(jié)點的v值，再根據(jù)經(jīng)驗來估計深度d上的值是否在(α,β)范圍外前向剪枝23無需考慮直接剪枝一些子結(jié)點搜索與查表開局時的行棋大多依賴于人類的專業(yè)知識接近尾聲的棋局可能性有限在開局和尾聲階段可以通過查表的方式來進(jìn)行行棋搜索與查表開局時的行棋大多依賴于人類的專業(yè)知識56隨機(jī)博弈57許多博弈存在不確定性的隨機(jī)因素，如擲骰子，我們稱為隨機(jī)博弈如西洋雙陸棋結(jié)合了運氣和技巧通過擲骰子