电脑如何下象棋-国立高雄大学-资讯工程学系.ppt

1,蒙地卡羅演算法在遊戲的應用,國立東華大學資訊工程系副教授顏士淨,2,MonteCarloAlgorithm,判斷n是否為質數For(i=1;i200)目前沒有好的審局函數,11,圍棋與西洋棋之比較,12,電腦圍棋設計方法,電腦圍棋的傳統設計法模擬人類思維；經驗法則JIMMY程式(since1994)2007年UCT出現，奪得奧林匹亞19路圍棋的金牌UCT:運用蒙地卡羅法為基礎的樹狀搜尋演算法,13,UCT樹狀搜尋演算法,UCT：一個樹狀搜尋演算法特性：往較有可能為好點的分支，展開較深，最後會長成一棵不平衡樹如何決定一個點是否為好點?蒙地卡羅法統計許多模擬棋局之結果，進行局面之判斷,14,SchemeofaMonte-CarloTreeSearch(2007,Herik),教育部大專校院研究人才延攬方案,15,UCT-不平衡的樹,17,UCT搜尋方法,進行多次搜尋，每次均由上而下拓展UCTTree每次如何決定往哪個分支深入拓展?UCBUCT:UCBforTreesearchUCB:UpperConfidenceBoundUCB原本用來解決吃角子老虎問題,18,吃角子老虎問題,開發：依照目前經驗決定下一次要選擇的機器探險：嘗試其他機器,19,UCT運用在圍棋,21,UCT搜尋方法,最佳路徑：每次搜尋，均藉由UCB公式找一條由根節點到葉節點的最佳路徑更新UCT樹：找到最佳路徑後，對葉節點代表之盤面執行模擬棋局，所得的勝負結果更新路徑上所有節點,22,UCT例子,23,UCT與傳統圍棋程式JIMMY結合,24,搜尋樹的裁剪方法,多算勝，少算不勝分支度的多寡直接影響搜尋樹的深度如何減少無用子點為一改良重點三種裁剪法：JIMMY裁剪、一線裁剪、棋塊裁剪,25,JIMMY裁剪,JIMMY對目前盤面作判斷，給定著手分數UCTTree創子點時，排除沒分數之點,26,JIMMY裁剪效果,未裁剪：第一層子點數量為4080個裁剪後第一層子點之數量控制在115個左右大幅排除無用之點，並加深搜尋深度,27,JIMMY裁剪實驗結果,結果分析JIMMY裁剪可行,28,模擬棋局方法,工作：給定盤面，將此局下到終局，計算勝負意義：作為UCT樹的節點的收益值之來源影響UCT判斷、選擇最佳路徑之正確性重點在於選擇下一步的函式目標：1.快速2.準確,29,最簡單的方法：隨機落子,優點：簡單、速度快缺點：準確性較低，需統計較多棋局若棋步越有意義，則越準確，但花較多時間目標：讓電腦所選的著手更具有圍棋上的意義,30,經驗法則與棋形比對,選擇下一步：根據此盤面下合法著手的著手機率決定著手機率：根據經驗法則判斷與棋形比對所的的分數決定，分數越高，機率越高,31,著手機率分布範例,32,經驗法則,利用已有的知識，快速判斷著點價值目前使用的經驗法則：長與提,33,長與提子的例子,34,棋形比對,棋形：棋子在棋盤上的分布狀況可幫助人類棋手在對奕時快速排除無用著手棋形表達：要下之點置中，周圍是棋子分佈狀態,35,棋形比對做法,棋形資料庫來源：約1600個職業與業餘高段棋士之九路棋譜擷取每一手所產生的棋形，統計出現次數依照出現次數排序,36,實驗結果,棋形比對取棋形資料庫中排名較前的棋形以比對比對前一手周圍的八個點棋力增益,37,電腦圍棋方法結論,UCT嵌在JIMMY決定著手之處利用JIMMY的開局與佈局資料庫強化UCT使用JIMMY著手資訊對UCT做裁剪以從棋譜中擷取的棋形資料庫作為棋形比對之基礎結合經驗法則與UCT的想法確實可行2008/10於北京擊敗去年世界冠軍,38,Games,象棋(ChineseChess)六子棋(Connect6)排七(Fantan)暗棋(DarkChess)十三張(Card13),39,線上遊戲排行榜,麻將(MahJong)牌七(Fantan)大老二(BigTwo)十三張(Card13)梭哈(Showhand)暗棋(DarkChes