人工智能導(dǎo)論-第2章對(duì)抗搜索

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

foreach手臂j:

訪問(wèn)該手臂并記錄收益

endfor

while

尚未達(dá)到訪問(wèn)次數(shù)限制do:

計(jì)算每個(gè)手臂的UCB1信心上界Ij

訪問(wèn)信心上界最大的手臂

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

functionUCTSEARCH(S0)

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

while

尚未用完計(jì)算時(shí)長(zhǎng)do:vl=TREEPOLICY(v0);

△=DEFAULTPOLICY(s(vl));BACKUP(vl，△);

endwhile

returna(BESTCHILD(v0，