




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
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目前沒有好的審局函數(shù)11圍棋與西洋棋之比較圍棋西洋棋勝負(fù)目標(biāo)地多為勝吃掉對(duì)方國(guó)王棋子死活有程度上差異 非生即死分支度約200約4012電腦圍棋設(shè)計(jì)方法n電腦圍棋的傳統(tǒng)設(shè)計(jì)法n模擬人類思維;經(jīng)驗(yàn)法則nJIMMY程式(since 1994)n2007年UCT出現(xiàn),奪得奧林匹亞19路圍棋的金牌nUCT:運(yùn)用蒙地卡羅法為基礎(chǔ)的樹狀搜尋演算法13UCT樹狀搜尋演算法n
2、UCT:一個(gè)樹狀搜尋演算法n特性:往較有可能為好點(diǎn)的分支,展開較深,最後會(huì)長(zhǎng)成一棵不平衡樹n如何決定一個(gè)點(diǎn)是否為好點(diǎn)?n蒙地卡羅法n統(tǒng)計(jì)許多模擬棋局之結(jié)果,進(jìn)行局面之判斷14Scheme of a Monte-Carlo Tree Search(2007, Herik)教育部大專校院研究人才延攬方案15UCT-不平衡的樹17UCT搜尋方法n進(jìn)行多次搜尋,每次均由上而下拓展UCT Treen每次如何決定往哪個(gè)分支深入拓展?UCBnUCT : UCB for Tree search nUCB : Upper Confidence BoundnUCB原本用來解決吃角子老虎問題18吃角子老虎問題n開發(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樹:找到最佳路徑後,對(duì)葉節(jié)點(diǎn)代表之盤面執(zhí)行模擬棋局,所得的勝負(fù)結(jié)果更新路徑上所有節(jié)點(diǎn)22UCT例子23UCT與傳統(tǒng)圍棋程式JIMMY結(jié)合24搜尋樹的裁剪方法n多算勝,少算不勝n分支度的多寡直接影響搜尋樹的深度n如何減少無用子點(diǎn)為一改良重點(diǎn)n三種裁剪法:JIMMY裁剪、一線裁剪、棋塊裁剪25JIMMY裁剪nJIMMY對(duì)目前盤面作判斷,給定著手分?jǐn)?shù)nUCT Tree創(chuàng)子點(diǎn)時(shí),排除沒分?jǐn)?shù)之點(diǎn)26JIMMY裁剪效果n未裁剪:第一
4、層子點(diǎn)數(shù)量為4080個(gè)n裁剪後第一層子點(diǎn)之?dāng)?shù)量控制在115個(gè)左右n大幅排除無用之點(diǎn),並加深搜尋深度27JIMMY裁剪實(shí)驗(yàn)結(jié)果n結(jié)果分析nJIMMY裁剪可行28模擬棋局方法n工作:給定盤面,將此局下到終局,計(jì)算勝負(fù)n意義:作為UCT樹的節(jié)點(diǎn)的收益值之來源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ù)此盤面下合法著手 的著手機(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棋形:棋子在棋盤上的分布狀況n可幫助人類棋手在對(duì)奕時(shí)快速排除無用著手n棋形表達(dá):要下之點(diǎn)置中,周圍是棋子分佈狀態(tài)35棋形比對(duì)做法n棋形資料庫(kù)n來源:約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ì)前一手周圍的八個(gè)點(diǎn)n棋力增益37電腦圍棋方法結(jié)論nUCT嵌在JIMMY決定著手之處n利用JIMMY的開局與佈局資料庫(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)
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 山東第一醫(yī)科大學(xué)《熱學(xué)》2023-2024學(xué)年第二學(xué)期期末試卷
- 林權(quán)抵押貸款合同范例二零二五年
- 二零二五借款協(xié)議合同書標(biāo)準(zhǔn)范例
- 2025國(guó)內(nèi)銷售合同范本模板
- 2025實(shí)驗(yàn)室裝修改造合同
- 2025停車位租賃合同模板
- 某電廠2×600mw超臨界機(jī)組煙氣脫硫工程施工組織設(shè)計(jì)-典尚設(shè)計(jì)-三維動(dòng)畫效果圖
- 戒毒作文500字六年級(jí)
- 吉林省松原市前郭縣西部學(xué)區(qū)2024~2025學(xué)年度下學(xué)期九年級(jí)第二次模擬檢測(cè) 語文(含答題卡、答案)
- 中國(guó)第二十冶金建設(shè)公司綜合學(xué)校高中分校高二下學(xué)期期中考試英語試題
- 第11課 為實(shí)現(xiàn)中國(guó)夢(mèng)而努力奮斗 (教案)-2024~2025學(xué)年八年級(jí)歷史下冊(cè)新課標(biāo)教學(xué)設(shè)計(jì)(人教部編版)
- 醬酒銷售技巧培訓(xùn)
- 關(guān)于防范第三方施工破壞燃?xì)夤艿拦芾磙k法(暫行)
- 2025屆遼寧省錦州市凌海市市級(jí)名校中考化學(xué)模擬試卷含解析
- 教師如何使用AI開展教學(xué)DeepSeek使用指南人工智能 課件
- 導(dǎo)數(shù)大題題型分類
- 【計(jì)量指南】中國(guó)森林生態(tài)系統(tǒng)碳儲(chǔ)量-生物量方程
- 2024年上海奉賢區(qū)招錄儲(chǔ)備人才筆試真題
- 《新能源材料與器件專業(yè)生產(chǎn)實(shí)習(xí)》課程教學(xué)大綱
- 《copd疾病知識(shí)》課件
- 北京市東城區(qū)2024-2025學(xué)年高三(上)期末思想政治試卷(含答案)
評(píng)論
0/150
提交評(píng)論