人工智能導(dǎo)論第二章對抗搜索

人工智能導(dǎo)論第二章對抗搜索1第一頁，共二十八頁，2022年，8月28日2.1博弈問題博弈問題雙人一人一步雙方信息完備零和2第二頁，共二十八頁，2022年，8月28日分錢幣問題（7）（6,1）（5,2）（4,3）（5,1,1）（4,2,1）（3,2,2）（3,3,1）（4,1,1,1）（3,2,1,1）（2,2,2,1）（3,1,1,1,1）（2,2,1,1,1）（2,1,1,1,1,1）對方先走我方必勝3第三頁，共二十八頁，2022年，8月28日中國象棋一盤棋平均走50步，總狀態(tài)數(shù)約為10的161次方。假設(shè)1毫微秒走一步，約需10的145次方年。結(jié)論：不可能窮舉。4第四頁，共二十八頁，2022年，8月28日02.2極小極大過程5-333-3022-30-23541-30689-30-33-3-3-21-36-30316011極大極小ab025第五頁，共二十八頁，2022年，8月28日2.3-剪枝極大節(jié)點的下界為。極小節(jié)點的上界為。剪枝的條件：后輩節(jié)點的值≤祖先節(jié)點的值時，剪枝后輩節(jié)點的值≥祖先節(jié)點的值時，剪枝簡記為：極小≤極大，剪枝極大≥極小，剪枝6第六頁，共二十八頁，2022年，8月28日486-315035-剪枝（續(xù)）-33-3022-30-2309-300-303305411-31661abcdefghijkmn7第七頁，共二十八頁，2022年，8月28日2.4蒙特卡洛博弈方法為什么-剪枝方法在圍棋上失效？-剪枝方法存在的問題依賴于局面評估的準確性局面評估問題大量專家知識知識的統(tǒng)一性問題人工整理8第八頁，共二十八頁，2022年，8月28日圍棋落子模型圍棋對弈過程可以看做一個馬爾科夫過程：五元組：{T，S，A(i)，P(·|i,a)，r(i,a)}T：決策時刻S：狀態(tài)空間，S={i}A(i)：可行動集合（可落子點）P(·|i,a)：狀態(tài)i下選擇行動a的概率r(i,a)：狀態(tài)i下選擇行動a后課獲得的收益9第九頁，共二十八頁，2022年，8月28日蒙特卡洛方法二十世紀40年代中期S.M.烏拉姆和J.馮·諾伊曼提出的一種隨機模擬方法多重積分矩陣求逆線性方程組求解積分方程求解偏微分方程求解隨機性問題模擬10第十頁，共二十八頁，2022年，8月28日蒲豐投針問題1777年法國科學(xué)家蒲豐提出一種計算π的方法：取一張白紙，在上面畫上許多條間距為d的等距平行線，另取一根長度為l（l<d）的針，隨機地向該紙上投擲針，并記錄投擲次數(shù)n以及針與直線相交的次數(shù)m，據(jù)此計算π值。11第十一頁，共二十八頁，2022年，8月28日dlxα(x,α)決定了針的位置針與直線的相交條件：x≤(l/2)·sinα其中：x∈[0,d/2],α∈[0,π]12第十二頁，共二十八頁，2022年，8月28日黃顏色部分與長方形面積之比即為針與直線相交的概率d/2πα013第十三頁，共二十八頁，2022年，8月28日14第十四頁，共二十八頁，2022年，8月28日蒙特卡洛評估從當前局面的所有可落子點中隨機選擇一個點落子重復(fù)以上過程直到勝負可判斷為止經(jīng)多次模擬后，選擇勝率最大的點落子15第十五頁，共二十八頁，2022年，8月28日蒙特卡洛規(guī)劃解決馬爾科夫決策問題的有效方法之一基本思想與特點：將可能出現(xiàn)的狀態(tài)轉(zhuǎn)移過程用狀態(tài)樹表示從初始狀態(tài)開始重復(fù)抽樣，逐步擴展樹中的節(jié)點某個狀態(tài)再次被訪問時，可以利用已有的結(jié)果，提高了效率在抽樣過程中可以隨時得到行為的評價16第十六頁，共二十八頁，2022年，8月28日蒙特卡洛規(guī)劃的步驟選擇從根節(jié)點出發(fā)自上而下地選擇一個落子點擴展向選定的點添加一個或多個子節(jié)點模擬對擴展出的節(jié)點用蒙特卡洛方法進行模擬回溯根據(jù)模擬結(jié)果依次向上更新祖先節(jié)點估計值17第十七頁，共二十八頁，2022年，8月28日更新過程設(shè)ni為當前要模擬的節(jié)點，△為模擬獲得的收益對ni及其祖先的模擬次數(shù)加1ni的收益加△更新ni的祖先的收益，同類節(jié)點加△，非同類節(jié)點減△（這里節(jié)點的類型按照極大極小節(jié)點劃分）18第十八頁，共二十八頁，2022年，8月28日蒙特卡洛規(guī)劃算法流程19第十九頁，共二十八頁，2022年，8月28日選擇落子點的策略兩方面的因素：對尚未充分了解的節(jié)點的探索對當前具有較大希望節(jié)點的利用20第二十頁，共二十八頁，2022年，8月28日多臂老虎機模型21第二十一頁，共二十八頁，2022年，8月28日多臂老虎機模型1952年Robbins提出的一個統(tǒng)計決策模型多臂老虎機多臂老虎機擁有k個手臂，拉動每個手臂所獲得的收益遵循一定的概率且互不相關(guān)，如何找到一個策略，使得拉動手臂獲得的收益最大化用于解決蒙特卡洛規(guī)劃中選擇落子點的問題22第二十二頁，共二十八頁，2022年，8月28日信心上限算法UCB1functionUCB1

foreach手臂j:

訪問該手臂并記錄收益

endfor

while

尚未達到訪問次數(shù)限制do:

計算每個手臂的UCB1信心上界Ij

訪問信心上界最大的手臂

endwhile23第二十三頁，共二十八頁，2022年，8月28日其中：是手臂j所獲得回報的均值n是到當前這一時刻為止所訪問的總次數(shù)是手臂j到目前為止所訪問的次數(shù)上式考慮了“利用”和“探索”間的平衡24第二十四頁，共二十八頁，2022年，8月28日信心上限樹算法UCT將UCB1算法應(yīng)用于蒙特卡洛規(guī)劃算法中，用于選擇可落子點可落子點不是隨機選擇，而是根據(jù)UCB1選擇信心上限值最大的節(jié)點實際計算UCB1時，加一個參數(shù)c進行調(diào)節(jié)：25第二十五頁，共二十八頁，2022年，8月28日引入符號:v:節(jié)點，包含以下信息：s(v):v對應(yīng)的狀態(tài)a(v):來自父節(jié)點的行為Q(v):隨機模擬獲得的收益N(v):v的總訪問次數(shù)26第二十六頁，共二十八頁，2022年，8月28日信心上限樹算法（UCT）

functionUCTSEARCH(S0)

以狀態(tài)S0創(chuàng)建根節(jié)點v0;

while

尚未用完計算時長do:vl=TREEPOLICY(v0);

△=DEFAULTPOLICY(s(vl));