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

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

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

4、2mdnlPdl22l從當前局面的所有可落子點中隨機選擇一個點落子l重復以上過程l直到勝負可判斷為止l經多次模擬后，選擇勝率最大的點落子15l解決馬爾科夫決策問題的有效方法之一l基本思想與特點：將可能出現的狀態轉移過程用狀態樹表示從初始狀態開始重復抽樣，逐步擴展樹中的節點某個狀態再次被訪問時，可以利用已有的結果，提高了效率在抽樣過程中可以隨時得到行為的評價16l選擇從根節點出發自上而下地選擇一個落子點l擴展向選定的點添加一個或多個子節點l模擬對擴展出的節點用蒙特卡洛方法進行模擬l回溯根據模擬結果依次向上更新祖先節點估計值17l設ni為當前要模擬的節點，為模擬獲得的收益l對ni及其祖先的模擬次數

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

6、訪問信心上界最大的手臂l end while23l其中：l 是手臂j所獲得回報的均值ln是到當前這一時刻為止所訪問的總次數l 是手臂j到目前為止所訪問的次數l上式考慮了“利用”和“探索”間的平衡24)()ln(2nTnXIjjjjX)(nTjl將UCB1算法應用于蒙特卡洛規劃算法中，用于選擇可落子點可落子點不是隨機選擇，而是根據UCB1選擇信心上限值最大的節點實際計算UCB1時，加一個參數c進行調節：25)()ln(2nTncXIjjjl引入符號:lv: 節點，包含以下信息：s(v): v對應的狀態a(v): 來自父節點的行為Q(v): 隨機模擬獲得的收益N(v): v的總訪問次數26l信心上限樹算法（UCT）l function UCTSEARCH(S0)l 以狀態S0創建根節點v0;l while 尚未用完計算時長 do:l vl = TREEPOLICY(v0);l = DEFAULTPOLICY(s(vl);l BACKUP(vl，);l end whilel return a(BESTCHILD(v0