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

1、l對(duì)抗搜索：博弈l博弈問(wèn)題l極小極大方法l-剪枝l蒙特卡洛博弈方法12l博弈問(wèn)題雙人一人一步雙方信息完備零和3（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ì)方先走我方必勝4l一盤(pán)棋平均走50步，總狀態(tài)數(shù)約為10的161次方。l假設(shè)1毫微秒走一步，約需10的145次方年。l結(jié)論：不可能窮舉。505-333-3022-30-23541-30689-30-33-3-3-21-36-30316011極大極小ab026l極大節(jié)點(diǎn)的下界

2、為。l極小節(jié)點(diǎn)的上界為。l剪枝的條件：后輩節(jié)點(diǎn)的值祖先節(jié)點(diǎn)的值時(shí)， 剪枝后輩節(jié)點(diǎn)的 值祖先節(jié)點(diǎn)的值時(shí)， 剪枝l簡(jiǎn)記為：極小極大，剪枝極大極小，剪枝7486-315035-33-3022-30-2309-300-303305411-31661abcdefghijkmnl為什么-剪枝方法在圍棋上失效？-剪枝方法存在的問(wèn)題l依賴(lài)于局面評(píng)估的準(zhǔn)確性局面評(píng)估問(wèn)題l大量專(zhuān)家知識(shí)l知識(shí)的統(tǒng)一性問(wèn)題l人工整理8l圍棋對(duì)弈過(guò)程可以看做一個(gè)馬爾科夫過(guò)程：l五元組：T，S，A(i)，P(|i,a)，r(i,a)T：決策時(shí)刻S：狀態(tài)空間，S=iA(i)：可行動(dòng)集合（可落子點(diǎn)）P(|i,a)：狀態(tài)i下選擇行動(dòng)a的概率r

3、(i,a)：狀態(tài)i下選擇行動(dòng)a后課獲得的收益9l二十世紀(jì)40年代中期S.M.烏拉姆和J.馮諾伊曼提出的一種隨機(jī)模擬方法多重積分矩陣求逆線(xiàn)性方程組求解積分方程求解偏微分方程求解隨機(jī)性問(wèn)題模擬10l1777年法國(guó)科學(xué)家蒲豐提出一種計(jì)算的方法：l取一張白紙，在上面畫(huà)上許多條間距為d的等距平行線(xiàn)，另取一根長(zhǎng)度為l（ld）的針，隨機(jī)地向該紙上投擲針，并記錄投擲次數(shù)n以及針與直線(xiàn)相交的次數(shù)m，據(jù)此計(jì)算值。1112dlxl(x, )決定了針的位置l針與直線(xiàn)的相交條件：x (l/2)sinl其中：x0, d/2, 0, l黃顏色部分與長(zhǎng)方形面積之比即為針與直線(xiàn)相交的概率13d/2014dldPdl2sin20

4、2mdnlPdl22l從當(dāng)前局面的所有可落子點(diǎn)中隨機(jī)選擇一個(gè)點(diǎn)落子l重復(fù)以上過(guò)程l直到勝負(fù)可判斷為止l經(jīng)多次模擬后，選擇勝率最大的點(diǎn)落子15l解決馬爾科夫決策問(wèn)題的有效方法之一l基本思想與特點(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)再次被訪(fǎng)問(wèn)時(shí)，可以利用已有的結(jié)果，提高了效率在抽樣過(guò)程中可以隨時(shí)得到行為的評(píng)價(jià)16l選擇從根節(jié)點(diǎn)出發(fā)自上而下地選擇一個(gè)落子點(diǎn)l擴(kuò)展向選定的點(diǎn)添加一個(gè)或多個(gè)子節(jié)點(diǎn)l模擬對(duì)擴(kuò)展出的節(jié)點(diǎn)用蒙特卡洛方法進(jìn)行模擬l回溯根據(jù)模擬結(jié)果依次向上更新祖先節(jié)點(diǎn)估計(jì)值17l設(shè)ni為當(dāng)前要模擬的節(jié)點(diǎn)，為模擬獲得的收益l對(duì)ni及其祖先的模擬次數(shù)

5、加1lni的收益加l更新ni的祖先的收益，同類(lèi)節(jié)點(diǎn)加，非同類(lèi)節(jié)點(diǎn)減（這里節(jié)點(diǎn)的類(lèi)型按照極大極小節(jié)點(diǎn)劃分）1819l兩方面的因素：對(duì)尚未充分了解的節(jié)點(diǎn)的探索對(duì)當(dāng)前具有較大希望節(jié)點(diǎn)的利用2021l1952年Robbins提出的一個(gè)統(tǒng)計(jì)決策模型l多臂老虎機(jī)多臂老虎機(jī)擁有k個(gè)手臂，拉動(dòng)每個(gè)手臂所獲得的收益遵循一定的概率且互不相關(guān)，如何找到一個(gè)策略，使得拉動(dòng)手臂獲得的收益最大化l用于解決蒙特卡洛規(guī)劃中選擇落子點(diǎn)的問(wèn)題22lfunction UCB1l for each 手臂j:l 訪(fǎng)問(wèn)該手臂并記錄收益l end forl while 尚未達(dá)到訪(fǎng)問(wèn)次數(shù)限制 do:l 計(jì)算每個(gè)手臂的UCB1信心上界Ijl

6、訪(fǎng)問(wèn)信心上界最大的手臂l end while23l其中：l 是手臂j所獲得回報(bào)的均值ln是到當(dāng)前這一時(shí)刻為止所訪(fǎng)問(wèn)的總次數(shù)l 是手臂j到目前為止所訪(fǎng)問(wèn)的次數(shù)l上式考慮了“利用”和“探索”間的平衡24)()ln(2nTnXIjjjjX)(nTjl將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é)：25)()ln(2nTncXIjjjl引入符號(hào):lv: 節(jié)點(diǎn)，包含以下信息：s(v): v對(duì)應(yīng)的狀態(tài)a(v): 來(lái)自父節(jié)點(diǎn)的行為Q(v): 隨機(jī)模擬獲得的收益N(v): v的總訪(fǎng)問(wèn)次數(shù)26l信心上限樹(shù)算法（UCT）l function UCTSEARCH(S0)l 以狀態(tài)S0創(chuàng)建根節(jié)點(diǎn)v0;l while 尚未用完計(jì)算時(shí)長(zhǎng) do:l vl = TREEPOLICY(v0);l = DEFAULTPOLICY(s(vl);l BACKUP(vl，);l end whilel return a(BESTCHILD(v0