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

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

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

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

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

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