電腦如何下象棋-國立高雄大學(xué)-資訊工程學(xué)系

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

2、UCT：一個樹狀搜尋演算法n特性：往較有可能為好點的分支，展開較深，最後會長成一棵不平衡樹n如何決定一個點是否為好點?n蒙地卡羅法n統(tǒng)計許多模擬棋局之結(jié)果，進行局面之判斷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開發(fā)

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

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

5、判斷與棋形比對所的的分數(shù)決定，分數(shù)越高，機率越高31著手機率分布範例32經(jīng)驗法則n利用已有的知識，快速判斷著點價值n目前使用的經(jīng)驗法則：長與提33長與提子的例子34棋形比對n棋形：棋子在棋盤上的分布狀況n可幫助人類棋手在對奕時快速排除無用著手n棋形表達：要下之點置中，周圍是棋子分佈狀態(tài)35棋形比對做法n棋形資料庫n來源：約1600個職業(yè)與業(yè)餘高段棋士之九路棋譜n擷取每一手所產(chǎn)生的棋形，統(tǒng)計出現(xiàn)次數(shù)n依照出現(xiàn)次數(shù)排序36實驗結(jié)果n棋形比對n取棋形資料庫中排名較前的棋形以比對n比對前一手周圍的八個點n棋力增益37電腦圍棋方法結(jié)論nUCT嵌在JIMMY決定著手之處n利用JIMMY的開局與佈局資料庫強化UCTn使用JIMMY著手資訊對UCT做裁剪n以從棋譜中擷取的棋形資料庫作為棋形比對之基礎(chǔ)n結(jié)合經(jīng)驗法則與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)