點(diǎn)格棋博弈中uct算法的研究與實(shí)現(xiàn)

《點(diǎn)格棋博弈中uct算法的研究與實(shí)現(xiàn)》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、？：、Ａ乂ｉ《批西Ｋ去ｌ＾一ｔ＇‘．－＇■１．‘．：ｉ：、、，Ｖ、．＇■＇，－．－Ｉ．：ａ巧級！■保密期限：掌務(wù)乂爹碩±學(xué)位論文點(diǎn)格棋博弈中ＵＣＴ算法的研究與實(shí)現(xiàn)ＲｅｓｅａｒｃｈａｎｄＩｍｐｌｅｍｅｎｔａｔｉｏｎｏｆＵＣＴＡｌｇｏｒｉｔｈｍｉｎＤｏｔｓａｎｄＢｏｘｅｓＣｏｍｐｕｔｅｒＧａｍｅ’；Ｖ．ｉ學(xué)號Ｅ１４３０１０８９姓名劉洋學(xué)位類別工程碩±計(jì)算機(jī)技術(shù)江程領(lǐng)域）指導(dǎo)

2、教師李學(xué)俊副教授完成時(shí)間２０１６年４月答辯委員會＾７１主席簽名／心．．？Ｉ．．．．．，，？‘豐＇？■．，－＇．■．＇？：，獨(dú)創(chuàng)性聲明本人聲明所呈交的學(xué)位論文是本人在導(dǎo)師揖導(dǎo)下進(jìn)行的研究工作及取得的研究成果。據(jù)我所知，除了文中特別加Ｗ標(biāo)注和致謝的地方外，論文中不包含其他人巴經(jīng)發(fā)表或撰寫過的研究成果，也不包含為獲得安徽大學(xué)或其他教育機(jī)構(gòu)的學(xué)位或證書而使用過的材料一同工作的同志對本研究所做的任何貢獻(xiàn)均己。與我在論文中作了明確的

3、說明并表示謝意。：／學(xué)位論文作者簽名；簽字日期＞９備年玉月日＾學(xué)位論文版權(quán)使巧授權(quán)書本學(xué)位論文作者完全了解安徽大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定，有權(quán)保留并向國家有關(guān)部口或機(jī)構(gòu)送交論文的復(fù)印件和磁盤，允許論文被查閱和借閱。本人授權(quán)安徽大學(xué)可Ｗ將學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，、可?。迊V采用影印、縮取或擔(dān)描尊復(fù)制手段保存、匯編凈位論文。（保密的學(xué)位論文在解密后適用本授權(quán)書）學(xué)位論文作者簽名；刮４導(dǎo)師簽名；信絞。／簽字日期：７＾年ＪＴ月日簽字日期：年王月＾ｉｍ

4、摘要２０１６年３月谷歌ＡｌｐｈａＧｏ擊敗世界圍棋冠軍李世石九段，使人工智能、機(jī)器博弈再次成為大眾焦點(diǎn)，主要研究用。人工智能是計(jì)算機(jī)科學(xué)的重要研究方向機(jī)器來模擬和執(zhí)行人腦的智力功能，開發(fā)相關(guān)的理論和技術(shù)，從而達(dá)到讓機(jī)器可Ｗ能像人一樣進(jìn)行學(xué)習(xí)、思考、判斷等各種腦力活動的目標(biāo)。機(jī)器博弈因使用計(jì)算機(jī)解決博弈問題而得名，它將博弈思想和計(jì)算機(jī)科學(xué)相融合，希望汁算機(jī)能像一一一人樣做出理性決策。機(jī)器博弈作為人工智能極具挑戰(zhàn)的分支之，直Ｗ來都＂＂被譽(yù)為人工智能的果幡，機(jī)器博弈的研充對于人工智能的發(fā)展具有積極的推一

5、動作用，；。機(jī)器博弈在國外的發(fā)展較早并取得了定的成就在國內(nèi)的發(fā)展還比較緩慢，Ｗ棋類為載體是目前研究機(jī)器博弈的主要方法。？點(diǎn)格棋是法國數(shù)學(xué)家愛德華盧卡斯在１８９１年提出的二人紙筆游戲。點(diǎn)格棋、博弈系統(tǒng)主要由知識表示、著法生成搜索算法和估值函數(shù)四部分組成，其中搜一一、索算法是核屯。搜索算法根據(jù)當(dāng)前局面生成顆定深度的博弈樹，對博弈樹進(jìn)ａ－行向下捜索，傳統(tǒng)的點(diǎn)格棋博弈系統(tǒng)所采用的搜索算法多為０剪枝算法，采一ａ－ａ－用目剪枝算法存在搜索深度淺、浪費(fèi)時(shí)間等問題。另方面目剪枝算法必須有一個估值函數(shù)對棋盤的優(yōu)劣進(jìn)行

6、評估。目前常采用的估值方法當(dāng)棋盤中不存在安全邊的時(shí)候會比較準(zhǔn)確，但是如果棋盤中含有安全邊，估值會由于安全邊占領(lǐng)的順序不同而存在誤差，所Ｗ點(diǎn)格棋博弈系統(tǒng)的估值函數(shù)設(shè)計(jì)相對較難。ＵＣＴ一算法是蒙特卡洛算法的種延伸算法，根據(jù)大數(shù)定理多次模擬的方式實(shí)現(xiàn)對博弈樹中節(jié)點(diǎn)的價(jià)值評估，同時(shí)將ＵＣＢ算法應(yīng)用到博弈樹搜索上，通＇過ＵＣＢ算法選擇進(jìn)行評估的節(jié)點(diǎn)，引導(dǎo)博弈樹向更好的方向生長，有利于更快的獲得最優(yōu)解。ＵＣＴ算法根據(jù)大量模擬棋局的結(jié)果Ｗ概率的方法進(jìn)行盤面優(yōu)劣的判斷，預(yù)估節(jié)點(diǎn)的好壞，優(yōu)先選擇表現(xiàn)好的節(jié)點(diǎn)。這種方法

7、解決了點(diǎn)格棋目前存在的盤面評估問題，。將ＵＣＴ算法應(yīng)用到點(diǎn)格棋博弈最后通過實(shí)驗(yàn)證明采用ＵＣＴ算法的點(diǎn)格棋博弈系統(tǒng)博弈水平高于ａ－目剪枝算法。根據(jù)點(diǎn)格棋博弈過程中棋盤會存在許多價(jià)值相同的邊即等價(jià)邊，這些邊選擇一其中任意條邊進(jìn)行搜索，與對送些全部進(jìn)行捜索產(chǎn)生的結(jié)果相同，在進(jìn)行博弈一樹搜索時(shí)只需要對其中條邊進(jìn)行搜索，據(jù)此提出基于等價(jià)邊裁剪的ＵＣＴ算法Ｉ點(diǎn)格棋博弈中ＵＣＴ算法的研巧與實(shí)現(xiàn)在ＵＣＴ算法拓展節(jié)點(diǎn)階段進(jìn)行等價(jià)邊裁剪。最后通過實(shí)驗(yàn)證明改進(jìn)算法能夠減少博弈樹捜索時(shí)捜索節(jié)點(diǎn)的數(shù)量，大幅度提

8、高ＵＣＴ算法的博弈水平。在ＵＣＴ算法模擬棋局階段，為提高模擬棋局結(jié)束后收益值計(jì)算的準(zhǔn)確性，在原有計(jì)算方法的基礎(chǔ)上提出了基于修正值的收益值計(jì)算方法，不僅對模擬棋局勝負(fù)進(jìn)行了區(qū)分，還對勝負(fù)的程度進(jìn)行了量化，使收益值更加的精確，為；其次提高模擬棋局的次數(shù)，實(shí)現(xiàn)了基于