1、清華大學 秦岳本講旨在講解OI算法在奇妙問題中的有趣簡單的應用來幫助大家放松心情，愉悅身心，準備考試1、泊松圖像編輯&高斯消元，線性代數2、游戲AI設計 &不可描述泊松圖像融合改變天氣無中生有改變天氣改變表情去除高光融合紋理Fx(x,y)=Ax,y-Ax-1,yFy(x,y)=Ax,y-Ax,y-1(Fx,Fy)構成梯度向量Div(x,y)=Fx(x+1,y)-Fx(x,y) + Fy(x,y+1)-Fy(x,y) =Ax-1,y+Ax+1,y +Ax,y-1+Ax,y+1-4*Ax,yDiv定義了每個像素點的散度值已知像素6/7/10/11的div但不知具體顏色值？V(2)+

2、V(5)+V(7)+V(10)-4*V(6)=div(6)V(3)+V(6)+V(8)+V(11)-4*V(7)=div(7)V(6)+V(9)+V(11)+V(14)-4*V(10)=div(10)V(7)+V(10)+V(12)+V(15)-4*V(11)=div(11)N個變量的線性方程組！方程組形式：思路1：將目標的梯度場”替換”背景圖的梯度場，根據散度線性方程組解像素顏色值。一點小問題混合策略：選擇模長較大的梯度值(保留兩者細節)另一個問題，變量過多！(求解25W個變量的線性方程組，高斯消元O(n3)一點小思路，迭代求解：根據散度公式用周邊的像素值確定新的值(三重for循環)6257

3、102571064(6)(6)4xAAxxdivAAxxdivx迭代0/1/10/100/1000/10000次：一階定常迭代法：B是矩陣,f是常向量核心目標:構造一個B、f使得Ax=b的解與迭代公式吻合雅克比迭代法(Jacobi)高斯賽德爾迭代法(Gauss-Seidel)逐次超松弛迭代法(SOR)1kkxBxf按行進行雅克比迭代時，直接使用新一輪的x進行原地迭代一階定常迭代理論公式：111()()kkxDLUxDLb在G-S迭代中使用w松弛因子進行加權平均：減緩/加速變化速度，加快收斂一階定常迭代理論公式：11(1)kkkxxx11111() (1)()kkxDLDU xDLb考慮 的一般

4、形式設Ax=b的準確解為x*迭代近似解誤差由于x*滿足方程x*=Bx*+f，有故能否收斂取決于是否直觀感受：只要B作用任何一個向量模長都變小則必定收斂1kkxBxf*kkexx11*()()()kkkkkexxBxfBxfB xxBe0lim0nnB e不可約矩陣：作為鄰接矩陣對應的有向圖強連通嚴格對角占優：每行對角線上的元素大于同行其他元素的和不嚴格對角占優：每行對角線上的元素大于等于同行其他元素的和幾點結論：若矩陣A嚴格對角占優，或者是不可約的若對角占優矩陣，則Jacobi、G-S、0w=1的SOR算法必定收斂。擴展：泊松方程的FFT解法一些更有趣的東西patchmatch.mp4評估函數

5、f我方執子選擇分數最高的方案敵方執子選擇使我分數最低的方案0-33-3-3-21-36-30316011極大極大極小極小ab05-33 3-30 2 2-30-23 5 4 1-30 6 8 9-30 2極大節點的下界為極大節點的下界為 。極小節點的上界為極小節點的上界為 。剪枝的條件：剪枝的條件：后輩節點的后輩節點的 值值祖先節點的祖先節點的 值時，值時， 剪枝剪枝后輩節點的后輩節點的 值值祖先節點的祖先節點的 值時，值時， 剪枝剪枝簡記為：簡記為：極小極小極大，剪枝極大，剪枝極大極大極小，剪枝極小，剪枝486-315035-33-30 2 2-30-2309-300-303305411-3

6、1661abcdefghijkmn黑先手必勝？先手必勝！VCF/VCT狀態壓縮與置換表VC求解模塊為什么為什么 - 剪枝方法在圍棋上失效？剪枝方法在圍棋上失效？ - 剪枝方法存在的問題剪枝方法存在的問題 依賴于局面評估的準確性依賴于局面評估的準確性局面評估問題局面評估問題 大量專家知識大量專家知識 知識的統一性問題知識的統一性問題 人工整理人工整理從當前局面的所有可落子點中隨機選擇一從當前局面的所有可落子點中隨機選擇一個點落子個點落子重復以上過程重復以上過程直到勝負可判斷為止直到勝負可判斷為止經多次模擬后，選擇勝率最大的點落子經多次模擬后，選擇勝率最大的點落子選擇、擴展、模擬、反向轉播1952

7、年年Robbins提出的一個統計決策模型提出的一個統計決策模型多臂老虎機多臂老虎機多臂老虎機擁有多臂老虎機擁有k個手臂，拉動每個手臂所獲得個手臂，拉動每個手臂所獲得的收益遵循一定的概率且互不相關，如何找到的收益遵循一定的概率且互不相關，如何找到一個策略，使得拉動手臂獲得的收益最大化一個策略，使得拉動手臂獲得的收益最大化用于解決蒙特卡洛規劃中選擇落子點的問用于解決蒙特卡洛規劃中選擇落子點的問題題Upper Confidence Bound Algorithmfunction UCB1 for each 手臂手臂j: 訪問該手臂并記錄收益訪問該手臂并記錄收益 end for while 尚未達到訪

8、問次數限制尚未達到訪問次數限制 do: 計算每個手臂的計算每個手臂的UCB1信心上界信心上界Ij 訪問信心上界最大的手臂訪問信心上界最大的手臂 end while其中其中： 是手臂是手臂j所獲得回報的均值所獲得回報的均值n是到當前這一時刻為止所訪問的總次數是到當前這一時刻為止所訪問的總次數 是手臂是手臂j到目前為止所訪問的次數到目前為止所訪問的次數上式考慮了上式考慮了“利用利用”和和“探索探索”間的平衡間的平衡)()ln(2nTnXIjjjjX)(nTj由于蒙特卡羅規劃方法在沒有知識的指導由于蒙特卡羅規劃方法在沒有知識的指導時樹的擴展層數較少，不利于最優解的獲時樹的擴展層數較少，不利于最優解的

9、獲取，取，將將UCB1算法應用于蒙特卡洛規劃算法算法應用于蒙特卡洛規劃算法中，用于選擇可落子點中，用于選擇可落子點可落子點不是隨機可落子點不是隨機選擇，而是根據選擇，而是根據UCB1選擇選擇信心上限值最大的節點信心上限值最大的節點實際計算實際計算UCB1時，加一個參數時，加一個參數c進行調節：進行調節：)()ln(2nTncXIjjj模擬模擬 勝勝(1, 1)(1, -1)模擬模擬 負負(1, -1)(2, 0)模擬模擬 負負(1, -1)(2, 2)(3, -1)模擬模擬 負負(1, -1)(3, 3)(4, -2)到時！到時！Googles DeepMind AI Just Taught Itself To Walk.mp4SIGGRAPH 2018- DeepMimic paper (main video).mp4狀態狀態(state)、動作動作(action)、獎賞獎賞(reward)智能體智能體(Agent)根據當前狀態來采取動作，獲得相應的獎賞之后，再去改進這些動作，使得下次再到相同狀態