1、1蒙地卡羅演算法在遊戲的應用蒙地卡羅演算法在遊戲的應用國立東華大學資訊工程系 副教授顏士淨2Monte Carlo Algorithm判斷 n 是否為質數 For ( i = 1; iH九路圍棋85=H象棋160ELPH圍棋400200)n目前沒有好的審局函數11圍棋與西洋棋之比較圍棋西洋棋勝負目標地多為勝吃掉對方國王棋子死活有程度上差異 非生即死分支度約200約4012電腦圍棋設計方法n電腦圍棋的傳統設計法n模擬人類思維；經驗法則nJIMMY程式(since 1994)n2007年UCT出現，奪得奧林匹亞19路圍棋的金牌nUCT:運用蒙地卡羅法為基礎的樹狀搜尋演算法13UCT樹狀搜尋演算法n

2、UCT：一個樹狀搜尋演算法n特性：往較有可能為好點的分支，展開較深，最後會長成一棵不平衡樹n如何決定一個點是否為好點?n蒙地卡羅法n統計許多模擬棋局之結果，進行局面之判斷14Scheme of a Monte-Carlo Tree Search(2007, Herik)教育部大專校院研究人才延攬方案15UCT-不平衡的樹17UCT搜尋方法n進行多次搜尋，每次均由上而下拓展UCT Treen每次如何決定往哪個分支深入拓展?UCBnUCT : UCB for Tree search nUCB : Upper Confidence BoundnUCB原本用來解決吃角子老虎問題18吃角子老虎問題n開發

3、：依照目前經驗決定下一次要選擇的機器n探險：嘗試其他機器19UCT運用在圍棋21UCT搜尋方法n最佳路徑：每次搜尋，均藉由UCB公式找一條由根節點到葉節點的最佳路徑n更新UCT樹：找到最佳路徑後，對葉節點代表之盤面執行模擬棋局，所得的勝負結果更新路徑上所有節點22UCT例子23UCT與傳統圍棋程式JIMMY結合24搜尋樹的裁剪方法n多算勝，少算不勝n分支度的多寡直接影響搜尋樹的深度n如何減少無用子點為一改良重點n三種裁剪法：JIMMY裁剪、一線裁剪、棋塊裁剪25JIMMY裁剪nJIMMY對目前盤面作判斷，給定著手分數nUCT Tree創子點時，排除沒分數之點26JIMMY裁剪效果n未裁剪：第一

4、層子點數量為4080個n裁剪後第一層子點之數量控制在115個左右n大幅排除無用之點，並加深搜尋深度27JIMMY裁剪實驗結果n結果分析nJIMMY裁剪可行28模擬棋局方法n工作：給定盤面，將此局下到終局，計算勝負n意義：作為UCT樹的節點的收益值之來源n影響UCT判斷、選擇最佳路徑之正確性n重點在於選擇下一步的函式n目標：1.快速 2.準確29最簡單的方法：隨機落子n優點：簡單、速度快n缺點：準確性較低，需統計較多棋局n若棋步越有意義，則越準確，但花較多時間n目標：讓電腦所選的著手更具有圍棋上的意義30經驗法則與棋形比對n選擇下一步：根據此盤面下合法著手 的著手機率決定n著手機率：根據經驗法則

5、判斷與棋形比對所的的分數決定，分數越高，機率越高31著手機率分布範例32經驗法則n利用已有的知識，快速判斷著點價值n目前使用的經驗法則：長與提33長與提子的例子34棋形比對n棋形：棋子在棋盤上的分布狀況n可幫助人類棋手在對奕時快速排除無用著手n棋形表達：要下之點置中，周圍是棋子分佈狀態35棋形比對做法n棋形資料庫n來源：約1600個職業與業餘高段棋士之九路棋譜n擷取每一手所產生的棋形，統計出現次數n依照出現次數排序36實驗結果n棋形比對n取棋形資料庫中排名較前的棋形以比對n比對前一手周圍的八個點n棋力增益37電腦圍棋方法結論nUCT嵌在JIMMY決定著手之處n利用JIMMY的開局與佈局資料庫強化UCTn使用JIMMY著手資訊對UCT做裁剪n以從棋譜中擷取的棋形資料庫作為棋形比對之基礎n結合經驗法則與UCT的想法確實可行n2008/10於北京擊敗去年世界冠軍38Gamesn象棋(Chinese Chess)n六子棋(Connect6)n排七(Fantan)n暗棋(Dark Chess)n十三張(Card13)39線上遊戲排行榜1.麻將(MahJong)2.牌七(Fantan)3.大老二(Big Two)4.十三張(Card13)5.梭哈(Showhand)6.暗棋(Dark Chess)