計(jì)算機(jī)博弈是人工智能領(lǐng)域的重要研究方向之一,被譽(yù)為人工智能學(xué)科的“果蠅”。愛恩斯坦棋屬于完備信息博弈棋種,是一種棋局信息完全透明的博弈類型,即博弈雙方在任何時(shí)候都能完全掌握當(dāng)前的棋局信息。然而,它不同于其它的完備信息博弈棋種,在雙方行棋過程中需通過投擲骰子來確定可走的棋子,具有隨機(jī)性,這使博弈系統(tǒng)對(duì)棋盤局勢(shì)的分析和決策帶來一定的挑戰(zhàn)。自2012年愛恩斯坦棋被列為中國大學(xué)生計(jì)算機(jī)博弈大賽項(xiàng)目之后,國內(nèi)越來越多的人專注于研究針對(duì)愛恩斯坦棋的博弈技術(shù)�，F(xiàn)有估值函數(shù)的研究往往是從進(jìn)攻、防守和概率三個(gè)因素分析局勢(shì)的優(yōu)劣,將這些因素以不同權(quán)重線性相加來組成估值函數(shù)。通過這種方式構(gòu)造的估值函數(shù)一般會(huì)受到設(shè)計(jì)者自身博弈水平的限制,而且很難得到一個(gè)最優(yōu)的權(quán)重。此外,搜索算法的研究大多是針對(duì)Alpha-Beta搜索算法和期望極大極小搜索算法的改進(jìn),但是這些搜索算法過于依賴估值函數(shù),估值函數(shù)的好壞決定了整個(gè)博弈系統(tǒng)的水平。本文以愛恩斯坦棋為研究對(duì)象,研究愛恩斯坦棋計(jì)算機(jī)博弈的關(guān)鍵技術(shù)。在搜索算法方面,本文引入蒙特卡洛樹搜索（Monte-Carlo tree search,MCTS）算法,提出了概率啟發(fā)的并行... 

【文章來源】：安徽大學(xué)安徽省 211工程院校

【文章頁數(shù)】：76 頁

【學(xué)位級(jí)別】：碩士

【部分圖文】：

圖１．１論文框架??Ｆｉｇｕｒｅ?１．１?Ｆｒａｍｅｗｏｒｋ?ｏｆ?Ｔｈｅｓｉｓ??第二章愛恩斯坦棋計(jì)算機(jī)博弈技術(shù)

?第二章愛恩斯坦棋計(jì)算機(jī)博弈相關(guān)技術(shù)??的價(jià)值只可能來源于節(jié)點(diǎn)ｂ，便無需再訪問子樹ｈ和子樹ｉ。同樣地，在圖２．５（ｂ）??中，由于節(jié)點(diǎn)ｃ是最大值節(jié)點(diǎn)，它的第一個(gè)子節(jié)點(diǎn)ｇ的值為６，因此節(jié)點(diǎn)ｃ的值??總是大于等于６。然而，因?yàn)楣?jié)點(diǎn)ａ是最小值節(jié)點(diǎn)，所以它的價(jià)值只可能來源于??節(jié)點(diǎn)ｂ，無需再訪問子樹ｈ和子樹ｉ。??２．４．２期望極大極小搜索算法??期望極大極�。ǎ牛穑澹悖簦椋恚椋睿椋恚幔┧惴ㄊ菢O大極小算法的一個(gè)變種，用于解??決棋類博弈中出現(xiàn)的隨機(jī)性問題，在愛恩斯坦棋中有成功的運(yùn)用。該算法在博弈??樹的Ｍａｘ層和Ｍｉｎ層中插入一層用于表不隨機(jī)事件的Ｃｈａｎｃｅ層，用來模擬隨機(jī)??事件的發(fā)生，評(píng)估隨機(jī)性對(duì)節(jié)點(diǎn)價(jià)值計(jì)算帶來的影響。?????Ｍａｘ?層???／?Ｎ—???Ｃｈａｎｃｅ?層???＾?Ｊ?／Ｖ?（ｙ?Ｍｉｎ?層??￣?Ｃｂａｎｃｅｍ??－?—???一?一????—???—?－?Ｍａｘ?層??圖２．６期望極大極小搜索算法??Ｆｉｇｕｒｅ?２．６?Ｅｘｐｅｃｔｉｍｉｎｉｍａｘ?Ａｌｇｏｒｉｔｈｍ??在圖２．６所示的博弈樹中

ｉｅ?｛１，２，３，４，５，６１。概率節(jié)點(diǎn)的父節(jié)點(diǎn)表示此時(shí)的棋盤狀態(tài)，子節(jié)點(diǎn)表示隨??機(jī)事件發(fā)生后的結(jié)果，即一組新的棋盤狀態(tài)。為更好地描述博弈樹，本文將最大??值節(jié)點(diǎn)和最小值節(jié)點(diǎn)統(tǒng)稱為最值節(jié)點(diǎn)（Ｍｉｎ－Ｍａｘ?Ｎｏｄｅ，?ＭＮｏｄｅ）。以圖３．１（ａ）所示??的棋盤為例，引入概率節(jié)點(diǎn)的博弈樹結(jié)構(gòu)如圖３．３所示。圖中以菱形表示概率節(jié)??點(diǎn)，最值節(jié)點(diǎn)Ｓ有６個(gè)子概率節(jié)點(diǎn)，對(duì)應(yīng)６個(gè)投骰子事件；概率節(jié)點(diǎn)有１個(gè)或多??個(gè)子最值節(jié)點(diǎn)，對(duì)應(yīng)每個(gè)合法走法。??Ｑ?？?Ｇ）?Ｇ）??圖３．３引入概率節(jié)點(diǎn)的博弈樹??Ｆｉｇｕｒｅ?３．３?Ｇａｍｅ?Ｔｒｅｅ?ｗｉｔｈ?Ｐｒｏｂａｂｉｌｉｔｙ?Ｎｏｄｅ??從圖３．１（ａ）的棋盤中可看出，當(dāng)骰子投擲到的點(diǎn)數(shù)為１、２、３時(shí)，可以走動(dòng)??２號(hào)棋子，所以最值節(jié)點(diǎn)Ａ、Ｂ和Ｃ與概率節(jié)點(diǎn)１、２和３建立連接；當(dāng)骰子投??擲到的點(diǎn)數(shù)為３、４、５、６時(shí)，可以走動(dòng)４號(hào)棋子，所以最值節(jié)點(diǎn)Ｄ與概率節(jié)點(diǎn)??３、４、５和６建立連接。概率節(jié)點(diǎn)與最值節(jié)點(diǎn)之間不再是一對(duì)多的樹狀結(jié)構(gòu)，而??是多對(duì)多的網(wǎng)狀結(jié)構(gòu)。因此

【參考文獻(xiàn)】：
期刊論文
[1]動(dòng)態(tài)規(guī)劃求解中國象棋狀態(tài)總數(shù)[J]. 魏印福,李舟軍.  智能系統(tǒng)學(xué)報(bào). 2019(01)
[2]改進(jìn)UCT算法在愛恩斯坦棋中的應(yīng)用[J]. 張小川,李琴,南海,彭麗蓉.  計(jì)算機(jī)科學(xué). 2018(12)
[3]中國象棋博弈系統(tǒng)實(shí)現(xiàn)的關(guān)鍵技術(shù)探索[J]. 肖秀春,劉澤偉,陳柏桃.  電子技術(shù)與軟件工程. 2018(15)
[4]愛恩斯坦棋計(jì)算機(jī)博弈算法研究與改進(jìn)[J]. 楊昌杰,陳柯成,劉躍元,王京.  無線互聯(lián)科技. 2018(15)
[5]愛恩斯坦棋評(píng)估策略的研究[J]. 范博奇,丁濛,張芳梓.  智能計(jì)算機(jī)與應(yīng)用. 2018(01)
[6]基于愛恩斯坦棋削減隨機(jī)性影響的博弈算法研究[J]. 黃恩一,丁濛.  智能計(jì)算機(jī)與應(yīng)用. 2017(01)
[7]深度強(qiáng)化學(xué)習(xí)綜述[J]. 劉全,翟建偉,章宗長,鐘珊,周倩,章鵬,徐進(jìn).  計(jì)算機(jī)學(xué)報(bào). 2018(01)
[8]計(jì)算機(jī)博弈的研究與發(fā)展[J]. 王亞杰,邱虹坤,吳燕燕,李飛,楊周鳳.  智能系統(tǒng)學(xué)報(bào). 2016(06)
[9]AlphaGo技術(shù)原理分析及人工智能軍事應(yīng)用展望[J]. 陶九陽,吳琳,胡曉峰.  指揮與控制學(xué)報(bào). 2016(02)
[10]六子棋中基于局部“路”掃描方式的博弈樹生成算法[J]. 李學(xué)俊,王小龍,吳蕾,劉慧婷.  智能系統(tǒng)學(xué)報(bào). 2015(02)

博士論文
[1]計(jì)算機(jī)博弈問題的復(fù)雜性、理論解及相關(guān)搜索算法研究[D]. 高強(qiáng).東北大學(xué) 2016

碩士論文
[1]愛恩斯坦棋計(jì)算機(jī)博弈算法的研究與實(shí)施[D]. 李琴.重慶理工大學(xué) 2018
[2]五子棋計(jì)算機(jī)博弈系統(tǒng)的研究與設(shè)計(jì)[D]. 張效見.安徽大學(xué) 2017
[3]點(diǎn)格棋博弈中UCT算法的研究與實(shí)現(xiàn)[D]. 劉洋.安徽大學(xué) 2016
[4]愛恩斯坦棋計(jì)算機(jī)博弈系統(tǒng)的研究與實(shí)現(xiàn)[D]. 光洋.安徽大學(xué) 2016
[5]點(diǎn)格棋機(jī)器博弈系統(tǒng)的研究與實(shí)現(xiàn)[D]. 唐霜霜.安徽大學(xué) 2015
[6]并行計(jì)算在計(jì)算機(jī)博弈中的研究與應(yīng)用[D]. 侯鑫磊.重慶理工大學(xué) 2015
[7]基于專家系統(tǒng)和蒙特卡羅方法的計(jì)算機(jī)圍棋博弈的研究[D]. 周明明.南京航空航天大學(xué) 2012
[8]基于極大極小搜索算法的亞馬遜棋博弈系統(tǒng)的研究[D]. 張柳.東北大學(xué) 2010
[9]六子棋中基于BP-TD學(xué)習(xí)的局面估值方法研究[D]. 李新星.東北大學(xué) 2009



本文編號(hào)：2897248