愛(ài)恩斯坦棋計(jì)算機(jī)博弈系統(tǒng)的研究與實(shí)現(xiàn)
本文關(guān)鍵詞：愛(ài)恩斯坦棋計(jì)算機(jī)博弈系統(tǒng)的研究與實(shí)現(xiàn)，由筆耕文化傳播整理發(fā)布。
【摘要】：計(jì)算機(jī)博弈,也稱機(jī)器博弈,是一個(gè)極具挑戰(zhàn)與發(fā)展前景的計(jì)算機(jī)研究領(lǐng)域,其作為人工智能領(lǐng)域一個(gè)極其重要的課題,素有人工智能領(lǐng)域“果蠅”之稱。而對(duì)于棋類游戲的研究又是計(jì)算機(jī)博弈研究過(guò)程中的一個(gè)標(biāo)準(zhǔn)且極為重要的問(wèn)題�，F(xiàn)有的很多重要理論和技術(shù)方法諸如各類搜索算法及智能方法,最初的提出都是為了解決存在于棋類博弈中的某些問(wèn)題。對(duì)于計(jì)算機(jī)博弈的研究最早可以追溯到半個(gè)世紀(jì)之前,在過(guò)去的五六十年里,人工智能的學(xué)者們嘔心瀝血的研究了計(jì)算機(jī)博弈中的包括奧賽羅、國(guó)際象棋、跳棋、五子棋、圍棋等等,取得了大量傲人的成果。97年IBM的“深藍(lán)”戰(zhàn)勝棋王卡斯帕羅夫更是引起了世人的矚目與震動(dòng),讓世人第一次意識(shí)到冰冷的機(jī)器在棋類博弈上的智能超越了人類；而在不久之前,人機(jī)圍棋大戰(zhàn)巔峰對(duì)決——谷歌圍棋人工智能AlphaGo VS人類頂尖棋手李世石剛剛落幕,AlphaGo以4：1擊敗李世石,從某種層面上來(lái)說(shuō)機(jī)器的智能已經(jīng)遠(yuǎn)遠(yuǎn)超過(guò)了人類。相比于國(guó)外,國(guó)內(nèi)對(duì)于此方面的研究起步較晚,但是隨著這幾年的國(guó)內(nèi)各種博弈比賽的開(kāi)展,吸引了越來(lái)越多的學(xué)生與學(xué)者參與博弈的研究,國(guó)內(nèi)的計(jì)算機(jī)博弈研究迎來(lái)了黃金期,極大的促進(jìn)了國(guó)內(nèi)計(jì)算機(jī)博弈研究的發(fā)展。傳統(tǒng)的機(jī)器博弈模型多是完全信息博弈,即在對(duì)弈過(guò)程中完全了解其他對(duì)手的狀態(tài)特征、策略和得益方式,現(xiàn)有的機(jī)器博弈研究大多以此類為研究載體,如五子棋、象棋等等。此種棋類的數(shù)據(jù)結(jié)構(gòu)和局面狀態(tài)描述設(shè)計(jì)依賴于準(zhǔn)確的狀態(tài)策略信息,搜索引擎也有現(xiàn)成的模板可供參考。本文的研究對(duì)象愛(ài)恩斯坦棋博弈屬于不完全信息博弈,對(duì)博弈過(guò)程中的信息了解不完全,在進(jìn)行數(shù)據(jù)結(jié)構(gòu)和局面狀態(tài)描述設(shè)計(jì)之前,需要先對(duì)其他對(duì)手的狀態(tài)特征等信息進(jìn)行一個(gè)估計(jì),讓博弈信息“偽完全化”,然后再進(jìn)行相關(guān)設(shè)計(jì),同樣,需要對(duì)傳統(tǒng)的博弈搜索算法進(jìn)行修改,使其適應(yīng)于不完全信息博弈。本文以愛(ài)恩斯坦棋博弈平臺(tái)為研究載體,研究了計(jì)算機(jī)博弈關(guān)鍵技術(shù),包括基本概念、研究對(duì)象分析和搜索引擎,設(shè)計(jì)了愛(ài)恩斯坦棋機(jī)器博弈系統(tǒng)。在棋盤(pán)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)過(guò)程中,對(duì)對(duì)手的狀態(tài)信息等進(jìn)行了預(yù)判和估計(jì)量化,使其信息完全化,從攻擊和防守兩個(gè)方向同時(shí)評(píng)估,得到了攻防兼?zhèn)涞墓乐岛瘮?shù)；同時(shí),還研究了估值函數(shù)的參數(shù)優(yōu)化方法,保證估值函數(shù)設(shè)計(jì)的準(zhǔn)確性和合理性；在搜索算法方面,基于傳統(tǒng)的完全信息博弈算法——極大極小算法,參考期望搜索算法,在極大層與極小層之間人為加入一層骰子層,并將上述估值函數(shù)應(yīng)用到算法中同時(shí)加入置換表優(yōu)化技術(shù),設(shè)計(jì)了適應(yīng)于愛(ài)恩斯坦棋的攻防兼?zhèn)涞钠谕惴?解決了使用傳統(tǒng)博弈算法無(wú)法構(gòu)建博弈樹(shù)的問(wèn)題,提高博弈水平。從搜索效率和博弈水平兩個(gè)角度攻防兼?zhèn)涞钠谕惴?雖然在搜索效率有所下降,但是在博弈水平方面卻有較好的突破,博弈水平明顯提高證明了應(yīng)用了攻防兼?zhèn)涞墓乐岛瘮?shù)的期望算法在一定深度范圍內(nèi)博弈水平和博弈效率取得了較好的平衡,既具有較高的博弈水平,又充分利用了博弈時(shí)間。同時(shí),加入置換表優(yōu)化方法之后,搜索效率與博弈水平都有一定的提升,本文的創(chuàng)新點(diǎn)如下：(1)研究并設(shè)計(jì)了適用愛(ài)恩斯坦棋的不完全信息博弈的數(shù)據(jù)結(jié)構(gòu),深入研究估值函數(shù)的構(gòu)成,針對(duì)傳統(tǒng)的估值函數(shù)存在的估值片面不準(zhǔn)確的問(wèn)題,從攻擊防守兩個(gè)方向同時(shí)考慮并結(jié)合愛(ài)恩斯坦棋的兩種贏棋方式,設(shè)計(jì)了準(zhǔn)確且效率較好的攻防兼?zhèn)涞墓乐岛瘮?shù)；同時(shí)分析研究了一些應(yīng)用于估值參數(shù)優(yōu)化的方法和策略。在設(shè)計(jì)估值函數(shù)時(shí),使用了攻擊因子和威脅度因子來(lái)調(diào)整著法路徑,有效的提高了博弈水平。(2)具體上采用爬山法結(jié)合手工調(diào)整對(duì)攻防兼?zhèn)涞墓乐颠M(jìn)行參數(shù)優(yōu)化,將優(yōu)化之后的估值應(yīng)用到算法中去,極大的提高了博弈水平。(3)基于傳統(tǒng)的極大極小博弈算法,參考期望搜索算法,改進(jìn)并設(shè)計(jì)了適用于愛(ài)恩斯坦棋的攻防兼?zhèn)涞钠谕惴?在原有的極大極小層中加入一層骰子層,來(lái)模擬投骰子的過(guò)程,解決了博弈過(guò)程中信息不完全的問(wèn)題,并將(1)中的估值函數(shù)應(yīng)用到算法中,加入置換表來(lái)優(yōu)化算法,降低搜索過(guò)程中的節(jié)點(diǎn)數(shù)量,提高了搜索算法的效率。上述方法均在愛(ài)恩斯坦棋博弈系統(tǒng)“行云流水”與“流刃若火”程序中成功應(yīng)用,其中“行云流水”在2014年“成理杯”全國(guó)大學(xué)生計(jì)算機(jī)博弈大賽愛(ài)恩斯坦棋項(xiàng)目榮獲季軍(一等獎(jiǎng)),實(shí)踐上證明本文提出的估值方法及搜索算法具有可操作性與實(shí)際應(yīng)用價(jià)值。
【關(guān)鍵詞】：計(jì)算機(jī)博弈 愛(ài)恩斯坦棋 估值函數(shù) 攻防兼?zhèn)?/strong> 期望算法
【學(xué)位授予單位】：安徽大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：TP18
【目錄】：
- 摘要3-5
- Abstract5-11
- 第一章 緒論11-18
- 1.1 研究背景11-13
- 1.1.1 人工智能11-12
- 1.1.2 計(jì)算機(jī)博弈12-13
- 1.2 研究現(xiàn)狀13-15
- 1.3 研究意義15-16
- 1.4 本文研究工作16-18
- 1.4.1 具體研究?jī)?nèi)容16
- 1.4.2 本文組織結(jié)構(gòu)16-18
- 第二章 計(jì)算機(jī)博弈相關(guān)技術(shù)18-28
- 2.1 基本概念及技術(shù)19-24
- 2.1.1 博弈樹(shù)19-20
- 2.1.2 搜索樹(shù)20-22
- 2.1.3 復(fù)雜度22-23
- 2.1.4 遞歸23-24
- 2.1.5 回溯24
- 2.2 研究對(duì)象及分析24-26
- 2.2.1 研究對(duì)象分類24-26
- 2.2.2 本文研究對(duì)象分析26
- 2.3 本章小結(jié)26-28
- 第三章 愛(ài)恩斯坦棋計(jì)算機(jī)博弈建模28-39
- 3.1 愛(ài)恩斯坦棋概述28-32
- 3.1.1 規(guī)則28-30
- 3.1.2 基本概念30-32
- 3.2 特征要素32-36
- 3.3 數(shù)學(xué)建模36-38
- 3.4 本章小結(jié)38-39
- 第四章 攻防兼?zhèn)涞墓乐岛瘮?shù)39-55
- 4.1 數(shù)據(jù)結(jié)構(gòu)40-41
- 4.2 攻防兼?zhèn)涞墓乐岛瘮?shù)41-47
- 4.2.1 進(jìn)攻值42-43
- 4.2.2 阻擊值43-44
- 4.2.3 威脅值44-45
- 4.2.4 總體估值函數(shù)45-46
- 4.2.5 估值方法計(jì)算舉例46-47
- 4.3 參數(shù)優(yōu)化47-53
- 4.3.1 相關(guān)優(yōu)化方法47-49
- 4.3.2 參數(shù)優(yōu)化策略49-51
- 4.3.3 估值實(shí)驗(yàn)51-53
- 4.4 本章小結(jié)53-55
- 第五章 攻防兼?zhèn)涞钠谕阉魉惴?/span>55-65
- 5.1 經(jīng)典搜索算法簡(jiǎn)介56-59
- 5.1.1 極大極小算法56-58
- 5.1.2. 期望搜索算法58-59
- 5.2 攻防兼?zhèn)涞钠谕阉魉惴?/span>59-61
- 5.3 實(shí)驗(yàn)分析61-64
- 5.3.1 實(shí)驗(yàn)環(huán)境設(shè)置61-62
- 5.3.2 搜索效率實(shí)驗(yàn)62-63
- 5.3.3 博弈水平實(shí)驗(yàn)63-64
- 5.4 本章小結(jié)64-65
- 第六章 愛(ài)恩斯坦棋計(jì)算機(jī)博弈系統(tǒng)65-70
- 6.1 系統(tǒng)設(shè)計(jì)65-67
- 6.1.1 系統(tǒng)總體結(jié)構(gòu)設(shè)計(jì)65-66
- 6.1.2 系統(tǒng)流程圖66-67
- 6.2 系統(tǒng)實(shí)現(xiàn)67-69
- 6.2.1 實(shí)現(xiàn)技術(shù)67-68
- 6.2.2 系統(tǒng)界面68-69
- 6.3 本章小結(jié)69-70
- 第七章 總結(jié)與展望70-73
- 7.1 本文的主要貢獻(xiàn)與結(jié)論70-71
- 7.2 未來(lái)工作與展望71-73
- 參考文獻(xiàn)73-77
- 致謝77-78
- 攻讀碩士期間的學(xué)術(shù)與科研成果78
【參考文獻(xiàn)】
中國(guó)期刊全文數(shù)據(jù)庫(kù) 前10條
1 李占宇;李淑琴;顧磊;史玉峰;周文敏;;愛(ài)恩斯坦棋算法設(shè)計(jì)與分析[J];信息技術(shù)與信息化;2014年01期
2 周文敏;李淑琴;;愛(ài)恩斯坦棋靜態(tài)攻防策略的研究[J];電腦知識(shí)與技術(shù);2014年05期
3 聶華;;基于四皇后問(wèn)題的回溯法求解及算法實(shí)現(xiàn)[J];電子測(cè)試;2013年18期
4 眭俊華;劉慧娜;王建鑫;秦慶旺;;多核多線程技術(shù)綜述[J];計(jì)算機(jī)應(yīng)用;2013年S1期
5 宋金平;;遞歸程序編寫(xiě)方法探討[J];科技通報(bào);2013年04期
6 張明亮;吳俊;李凡長(zhǎng);;五子棋機(jī)器博弈系統(tǒng)評(píng)估函數(shù)的設(shè)計(jì)[J];計(jì)算機(jī)應(yīng)用;2012年07期
7 呂艷輝;宮瑞敏;;計(jì)算機(jī)博弈中估值算法與博弈訓(xùn)練的研究[J];計(jì)算機(jī)工程;2012年11期
8 王驕;徐心和;;計(jì)算機(jī)博弈:人工智能的前沿領(lǐng)域——全國(guó)大學(xué)生計(jì)算機(jī)博弈大賽[J];計(jì)算機(jī)教育;2012年07期
9 徐長(zhǎng)明;馬宗民;徐心和;李新星;;面向機(jī)器博弈的即時(shí)差分學(xué)習(xí)研究[J];計(jì)算機(jī)科學(xué);2010年08期
10 徐心和;;從計(jì)算機(jī)博弈到機(jī)器人足球——人工智能長(zhǎng)期而持續(xù)的挑戰(zhàn)[J];機(jī)器人技術(shù)與應(yīng)用;2010年01期
中國(guó)重要會(huì)議論文全文數(shù)據(jù)庫(kù) 前1條
1 徐心和;王浩;孔凡禹;;事件對(duì)策理論及在棋類游戲中的應(yīng)用[A];2007年中國(guó)智能自動(dòng)化會(huì)議論文集[C];2007年
中國(guó)博士學(xué)位論文全文數(shù)據(jù)庫(kù) 前1條
1 徐長(zhǎng)明;基于連珠模式的六子棋機(jī)器博弈關(guān)鍵技術(shù)研究[D];東北大學(xué);2010年
中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫(kù) 前10條
1 唐霜霜;點(diǎn)格棋機(jī)器博弈系統(tǒng)的研究與實(shí)現(xiàn)[D];安徽大學(xué);2015年
2 李景棚;非完備信息博弈估值算法的研究[D];哈爾濱工業(yè)大學(xué);2014年
3 王小龍;連珠模式棋類博弈的搜索優(yōu)化[D];安徽大學(xué);2014年
4 劉雅靖;基于Alpha-Beta搜索算法的計(jì)算機(jī)博弈的研究與實(shí)現(xiàn)[D];大連交通大學(xué);2012年
5 張柳;基于極大極小搜索算法的亞馬遜棋博弈系統(tǒng)的研究[D];東北大學(xué);2010年
6 閔文杰;六子棋計(jì)算機(jī)博弈關(guān)鍵技術(shù)研究[D];重慶交通大學(xué);2010年
7 郭秀麗;中國(guó)象棋計(jì)算機(jī)博弈中搜索算法的研究與改進(jìn)[D];河北大學(xué);2010年
8 賈春艷;中國(guó)象棋計(jì)算機(jī)博弈評(píng)估函數(shù)與開(kāi)局庫(kù)研究[D];西安理工大學(xué);2009年
9 張穎;六子棋計(jì)算機(jī)博弈及其系統(tǒng)的研究與優(yōu)化[D];重慶大學(xué);2008年
10 謝艷茹;中國(guó)象棋計(jì)算機(jī)博弈數(shù)據(jù)結(jié)構(gòu)與評(píng)估函數(shù)的研究和實(shí)現(xiàn)[D];西安理工大學(xué);2008年
本文關(guān)鍵詞：愛(ài)恩斯坦棋計(jì)算機(jī)博弈系統(tǒng)的研究與實(shí)現(xiàn)，，由筆耕文化傳播整理發(fā)布。
本文編號(hào)：455127
本文鏈接：http://www.sikaile.net/kejilunwen/zidonghuakongzhilunwen/455127.html
