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

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

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

【學位級別】：碩士

【部分圖文】：

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

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

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

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

博士論文
[1]計算機博弈問題的復雜性、理論解及相關搜索算法研究[D]. 高強.東北大學 2016

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



本文編號：2897248