本文關(guān)鍵詞：點(diǎn)格棋博弈中UCT算法的研究與實(shí)現(xiàn)，，由筆耕文化傳播整理發(fā)布。

【摘要】：2016年3月谷歌AlphaGo擊敗世界圍棋冠軍李世石九段,使人工智能、機(jī)器博弈再次成為大眾焦點(diǎn)。人工智能是計(jì)算機(jī)科學(xué)的重要研究方向,主要研究用機(jī)器來模擬和執(zhí)行人腦的智力功能,開發(fā)相關(guān)的理論和技術(shù),從而達(dá)到讓機(jī)器可以能像人一樣進(jìn)行學(xué)習(xí)、思考、判斷等各種腦力活動(dòng)的目標(biāo)。機(jī)器博弈因使用計(jì)算機(jī)解決博弈問題而得名,它將博弈思想和計(jì)算機(jī)科學(xué)相融合,希望計(jì)算機(jī)能像人一樣做出理性決策。機(jī)器博弈作為人工智能極具挑戰(zhàn)的分支之一,一直以來都被譽(yù)為人工智能的“果蠅”,機(jī)器博弈的研究對(duì)于人工智能的發(fā)展具有積極的推動(dòng)作用。機(jī)器博弈在國外的發(fā)展較早,并取得了一定的成就；在國內(nèi)的發(fā)展還比較緩慢,以棋類為載體是目前研究機(jī)器博弈的主要方法。點(diǎn)格棋是法國數(shù)學(xué)家愛德華·盧卡斯在1891年提出的二人紙筆游戲。點(diǎn)格棋博弈系統(tǒng)主要由知識(shí)表示、著法生成、搜索算法和估值函數(shù)四部分組成,其中搜索算法是核心。搜索算法根據(jù)當(dāng)前局面生成一顆一定深度的博弈樹,對(duì)博弈樹進(jìn)行向下搜索,傳統(tǒng)的點(diǎn)格棋博弈系統(tǒng)所采用的搜索算法多為α-β剪枝算法,采用α-β剪枝算法存在搜索深度淺、浪費(fèi)時(shí)間等問題。另一方面α-β剪枝算法必須有一個(gè)估值函數(shù)對(duì)棋盤的優(yōu)劣進(jìn)行評(píng)估。目前常采用的估值方法當(dāng)棋盤中不存在安全邊的時(shí)候會(huì)比較準(zhǔn)確,但是如果棋盤中含有安全邊,估值會(huì)由于安全邊占領(lǐng)的順序不同而存在誤差,所以點(diǎn)格棋博弈系統(tǒng)的估值函數(shù)設(shè)計(jì)相對(duì)較難。UCT算法是蒙特卡洛算法的一種延伸算法,根據(jù)大數(shù)定理以多次模擬的方式實(shí)現(xiàn)對(duì)博弈樹中節(jié)點(diǎn)的價(jià)值評(píng)估,同時(shí)將UCB算法應(yīng)用到博弈樹搜索上,通過UCB算法選擇進(jìn)行評(píng)估的節(jié)點(diǎn),引導(dǎo)博弈樹向更好的方向生長,有利于更快的獲得最優(yōu)解。UCT算法根據(jù)大量模擬棋局的結(jié)果以概率的方法進(jìn)行盤面優(yōu)劣的判斷,預(yù)估節(jié)點(diǎn)的好壞,優(yōu)先選擇表現(xiàn)好的節(jié)點(diǎn)。這種方法解決了點(diǎn)格棋目前存在的盤面評(píng)估問題。將UCT算法應(yīng)用到點(diǎn)格棋博弈,最后通過實(shí)驗(yàn)證明采用UCT算法的點(diǎn)格棋博弈系統(tǒng)博弈水平高于α-β剪枝算法。根據(jù)點(diǎn)格棋博弈過程中棋盤會(huì)存在許多價(jià)值相同的邊即等價(jià)邊,這些邊選擇其中任意一條邊進(jìn)行搜索,與對(duì)這些全部進(jìn)行搜索產(chǎn)生的結(jié)果相同,在進(jìn)行博弈樹搜索時(shí)只需要對(duì)其中一條邊進(jìn)行搜索,據(jù)此提出基于等價(jià)邊裁剪的UCT算法在UCT算法拓展節(jié)點(diǎn)階段進(jìn)行等價(jià)邊裁剪。最后通過實(shí)驗(yàn)證明改進(jìn)算法能夠減少博弈樹搜索時(shí)搜索節(jié)點(diǎn)的數(shù)量,大幅度提高UCT算法的博弈水平。在UCT算法模擬棋局階段,為提高模擬棋局結(jié)束后收益值計(jì)算的準(zhǔn)確性,在原有計(jì)算方法的基礎(chǔ)上提出了基于修正值的收益值計(jì)算方法,不僅對(duì)模擬棋局勝負(fù)進(jìn)行了區(qū)分,還對(duì)勝負(fù)的程度進(jìn)行了量化,使收益值更加的精確；其次,為提高模擬棋局的次數(shù),實(shí)現(xiàn)了基于多核CPU的UCT算法的并行化,充分利用了多核CPU的計(jì)算性能,提高棋局的模擬數(shù)量。綜合以上兩點(diǎn)改進(jìn)提出基于修正收益值的并行UCT算法,通過實(shí)驗(yàn)證明基于修正收益值的并行UCT算法可以提高博弈樹搜索深度和模擬棋局?jǐn)?shù)量,使UCT算法的博弈水平更高。本文的創(chuàng)新點(diǎn)如下：1.在認(rèn)真分析點(diǎn)格棋博弈中經(jīng)常使用的搜索算法后,發(fā)現(xiàn)UCT算法相對(duì)于傳統(tǒng)的α-β剪枝算法有著時(shí)間和空間方面的優(yōu)勢,將UCT算法運(yùn)用到點(diǎn)格棋博弈中。2.提出基于等價(jià)邊裁剪的UCT算法：給出等價(jià)邊的定義,在拓展之前進(jìn)行等價(jià)邊裁剪,減少博弈樹的搜索空間,提高博弈水平。3.提出基于修正收益值的并行UCT算法,包括兩個(gè)方面改進(jìn)：第一,提出基于修正值的收益值計(jì)算方法,對(duì)勝負(fù)程度進(jìn)行區(qū)分、量化,提高收益值準(zhǔn)確性；第二,為充分利用了計(jì)算機(jī)性能,提高模擬棋局次數(shù),實(shí)現(xiàn)了UCT算法的并行化。
【關(guān)鍵詞】：點(diǎn)格棋 機(jī)器博弈 UCT算法 等價(jià)邊 修正收益值
【學(xué)位授予單位】：安徽大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：TP18
【目錄】：

• 摘要3-5
• Abstract5-10
• 第一章 緒論10-16
• 1.1 研究背景10-12
• 1.2 研究現(xiàn)狀12-13
• 1.3 研究意義13-14
• 1.4 本文工作14-16
• 1.4.1 研究內(nèi)容14-15
• 1.4.2 論文組織結(jié)構(gòu)15-16
• 第二章 點(diǎn)格棋機(jī)器博弈技術(shù)16-27
• 2.1 點(diǎn)格棋簡介17-21
• 2.1.1 規(guī)則17-18
• 2.1.2 基本概念18-21
• 2.2 重要定理21-23
• 2.3 點(diǎn)格棋博弈系統(tǒng)構(gòu)成要素23-26
• 2.3.1 知識(shí)表示24-25
• 2.3.2 著法生成25
• 2.3.3 搜索算法25
• 2.3.4 估值函數(shù)25-26
• 2.4 本章小結(jié)26-27
• 第三章 點(diǎn)格棋博弈中UCT算法的應(yīng)用27-40
• 3.1 搜索算法介紹27-31
• 3.1.1 博弈樹搜索27-29
• 3.1.2 極大極小算法29-30
• 3.1.3 α-β剪枝算法30-31
• 3.2 傳統(tǒng)搜索算法的局限性31-33
• 3.3 UCT搜索算法原理33-36
• 3.3.1 蒙特卡洛方法33-34
• 3.3.2 UCB算法34-35
• 3.3.3 UCT算法35-36
• 3.4 點(diǎn)格棋博弈中UCT算法的應(yīng)用36-39
• 3.4.1 UCT算法應(yīng)用36-37
• 3.4.2 實(shí)驗(yàn)分析37-39
• 3.5 本章小結(jié)39-40
• 第四章 基于等價(jià)邊裁剪的UCT算法40-49
• 4.1 UCT算法拓展節(jié)點(diǎn)前期處理40-41
• 4.2 UCT算法拓展節(jié)點(diǎn)問題分析41-43
• 4.2.1 UCT算法博弈過程分析41-42
• 4.2.2 拓展節(jié)點(diǎn)問題分析42-43
• 4.3 基于等價(jià)邊裁剪的UCT算法43-46
• 4.3.1 等價(jià)邊43-45
• 4.3.2 算法描述45-46
• 4.4 實(shí)驗(yàn)分析46-48
• 4.4.1 拓展節(jié)點(diǎn)數(shù)量46-47
• 4.4.2 博弈水平實(shí)驗(yàn)47-48
• 4.5 本章小結(jié)48-49
• 第五章 基于修正收益值的并行UCT算法49-57
• 5.1 基于修正值的收益值計(jì)算方法49-51
• 5.1.1 收益值的重要性49-50
• 5.1.2 基于修正值的收益值計(jì)算方法50-51
• 5.2 基于修正收益值的并行UCT算法51-53
• 5.2.1 UCT算法的并行化51-52
• 5.2.2 算法描述52-53
• 5.3 實(shí)驗(yàn)分析53-56
• 5.3.1 參數(shù)優(yōu)化53-54
• 5.3.2 搜索深度實(shí)驗(yàn)54-55
• 5.3.3 模擬棋局?jǐn)?shù)量實(shí)驗(yàn)55-56
• 5.4 本章小結(jié)56-57
• 第六章 點(diǎn)格棋博弈系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)57-62
• 6.1 系統(tǒng)設(shè)計(jì)57-59
• 6.1.1 系統(tǒng)總體結(jié)構(gòu)57-58
• 6.1.2 系統(tǒng)流程圖58-59
• 6.2 系統(tǒng)實(shí)現(xiàn)59-61
• 6.3 本章小結(jié)61-62
• 第七章 總結(jié)與展望62-65
• 7.1 本文的主要貢獻(xiàn)與結(jié)論62-63
• 7.2 未來工作與展望63-65
• 參考文獻(xiàn)65-69
• 致謝69-70
• 攻讀碩士期間的科研項(xiàng)目與獲獎(jiǎng)70

【相似文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前2條

1 蘇黔;;如何調(diào)整彩電的會(huì)聚[J];電氣時(shí)代;1986年02期

2 ;[J];;年期

中國重要報(bào)紙全文數(shù)據(jù)庫 前1條

1 王石川;年輕人稍微出點(diǎn)格，不是壞事[N];東莞日?qǐng)?bào);2014年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前2條

1 劉洋;點(diǎn)格棋博弈中UCT算法的研究與實(shí)現(xiàn)[D];安徽大學(xué);2016年

2 劉慧慧;改性滌綸織物的結(jié)構(gòu)設(shè)計(jì)及性能研究[D];北京服裝學(xué)院;2012年

  本文關(guān)鍵詞：點(diǎn)格棋博弈中UCT算法的研究與實(shí)現(xiàn)，由筆耕文化傳播整理發(fā)布。

本文編號(hào)：363150