本文選題：戰(zhàn)棋 + 機器博弈��； 參考：《重慶大學(xué)》2016年博士論文

【摘要】：戰(zhàn)棋博弈(Turn-Based War Chess,TBW)是回合制策略游戲(Turn-Based Strategy,TBS)的重要成分,但目前其人工智能關(guān)注度還不夠。受限于戰(zhàn)棋具有豐富多樣的元素,目前還沒有一個標(biāo)準(zhǔn)化的數(shù)學(xué)模型,從而導(dǎo)致了戰(zhàn)棋博弈目前的研究還停留在較為簡單的層次上。隨著移動端游戲的井噴式發(fā)展,戰(zhàn)棋博弈類游戲因其觸屏操作、輕量級、碎片化時間而擁有更大的發(fā)展?jié)摿?然而因其人機博弈部分智能低下,嚴(yán)重影響了用戶體驗和產(chǎn)品黏性,成為束縛其游戲性的瓶頸。戰(zhàn)棋博弈本質(zhì)上是由橫向的組合優(yōu)化問題和縱向的博弈樹搜索問題結(jié)合的產(chǎn)物,既可以看作是一個分階段的多智能體協(xié)同作業(yè)的規(guī)劃問題,也可以看作是一個分支系數(shù)巨大的樹搜索問題。所以,其背后潛藏著的對以上傳統(tǒng)問題體系的擴(kuò)充和發(fā)展,其研究意義都超出了對戰(zhàn)棋游戲本身的研究。如今,基于大數(shù)據(jù)、云計算和機器學(xué)習(xí)的新一輪弱人工智能研究正在蓬勃興起,使得運用更為有效的技術(shù)讓戰(zhàn)棋博弈的人工智能獲得較大程度的提升成為了可能。本論文較為系統(tǒng)的分析了戰(zhàn)棋博弈的特性,基于特征選擇了從棋類博弈的角度來研究戰(zhàn)棋的機器博弈。首先建立戰(zhàn)棋游戲的通用博弈模型,提出橫向的組合優(yōu)化和縱向的博弈樹搜索的理論框架,闡明橫向分支系數(shù)巨大的關(guān)鍵難題,其次,針對橫向問題提出單回合窮舉搜索的按序枚舉法和遞歸枚舉法,并深入分析它們的性能和各自的適用性。隨后就計算冗余問題提出兩套優(yōu)化策略——單位移動范圍的簡化和搜索空間的簡化,通過理論實驗證實了它們在不改變有效搜索空間的前提下能大幅的提高搜索效率。然后就搜索過程中比較耗時的單位移動范圍計算,引入動態(tài)最短路徑樹(Dynamic Shortest Path Tree,DSPT)的新的研究方法,提出關(guān)于動態(tài)刪除節(jié)點的MRDA_SPT(Multi-node Removed Dynamic Algorithm of Shortest Path Tree)改進(jìn)算法,并通過理論分析和實驗驗證,該算法的效率均優(yōu)于現(xiàn)有其他方法。最后,基于新算法又提出動態(tài)更新單位移動范圍的DR_SPT(Dynamic Range Shortest Path Tree)算法,通過實驗表明它能顯著的提高計算移動范圍的效率,從而整體上提升了戰(zhàn)棋博弈單回合搜索速度。本論文的研究成果包括如下:(1)對戰(zhàn)棋博弈進(jìn)行建模和研究,并提出縱向和橫向的研究框架。研究結(jié)果表明,本質(zhì)上,戰(zhàn)棋博弈屬于二人(或多人)零和完全信息博弈,因其每回合全部棋子都可移動,并且移動順序敏感的特點,戰(zhàn)棋博弈構(gòu)成了一個分支系數(shù)異常龐大的博弈樹。本論文對該博弈樹的規(guī)模進(jìn)行了理論上的計算,并與其它主流棋類對比,發(fā)現(xiàn)戰(zhàn)棋的博弈樹分支系數(shù)會隨著棋子的數(shù)量和每個棋子的移動范圍的增大而急劇增大。最后,在博弈樹理論的框架下就縱向和橫向的研究路線給予了展望。(2)提出戰(zhàn)棋博弈的單回合搜索算法并做完備性證明和性能比較。單回合搜索是戰(zhàn)棋博弈樹第一層展開的核心算法,其效率也是整個戰(zhàn)棋博弈性能的關(guān)鍵指標(biāo)。針對順序優(yōu)先還是行為優(yōu)先提出了兩種單回合搜索算法:1、按序枚舉法;2、遞歸枚舉法。它們的主要區(qū)別是選擇不同的排列算法:前者采用字典序法,后者采用遞歸法,而它們體現(xiàn)出來了不同的搜索架構(gòu):前者基于序列,后者基于行動。從理論上證明了兩個算法都是最優(yōu)解的,并從理論和實驗分析了他們效率的差別:棋子在所有位置上的擴(kuò)展操作(ops1)的次數(shù)總和,遞歸枚舉法比按序枚舉法在各種條件下都有不同程度的減少。(3)就單回合搜索計算復(fù)雜度高、計算冗余的問題提出了兩套優(yōu)化策略——1、簡化單位移動范圍的計算;2、劃分與簡化搜索空間。通過理論證明和實驗檢驗,證實了這兩種策略可以在不改變有效搜索空間的前提下大幅的提高搜索效率。(4)提出MRDA_SPT改進(jìn)算法,提升了動態(tài)最短路徑樹(DSPT)關(guān)于節(jié)點動態(tài)刪除的效率。首先對動態(tài)最短路徑樹(DSPT)進(jìn)行了較為系統(tǒng)的研究,并針對前人的工作當(dāng)中DSPT動態(tài)節(jié)點刪除算法存在冗余的問題提出了新算法——MRDA_SPT改進(jìn)算法,從理論上分析其復(fù)雜度,通過與目前較快的算法做對比實驗,表明了MRDA_SPT改進(jìn)算法具有更高的效率和更快的運行速度。(5)提出高效率動態(tài)計算單位移動范圍的DR_SPT算法并通過實驗驗證其高效性。實驗分析出戰(zhàn)棋博弈搜索的一個重要的耗時計算是對棋子移動范圍的計算,根據(jù)移動范圍在搜索算法中會動態(tài)改變這一特點,提出基于動態(tài)最短路徑樹和MRDA_SPT改進(jìn)算法的DR_SPT算法,該算法對棋子移動范圍做增量計算,從而大大提高了搜索中棋子移動范圍計算的速度,并從整體上提高戰(zhàn)棋博弈搜索的效率。
[Abstract]:This paper analyzes the characteristics of chess game , and then puts forward a new research method for the game of chess game based on the combination of horizontal combination optimization and vertical game tree search . Based on the new algorithm , a DR _ SPT ( Dynamic Range Finding Path Tree ) algorithm based on dynamic update unit moving range is proposed . The results of this paper are as follows : ( 1 ) The game of chess game is modeled and studied . The results of this paper are as follows : ( 1 ) The game of chess game belongs to two ( or many ) zero and complete information games . ( 4 ) The improved algorithm of MRDA _ SPT is proposed to improve the efficiency of dynamic deletion of nodes in dynamic shortest path tree ( DSPT ) .
【學(xué)位授予單位】：重慶大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2016
【分類號】：TP18

【參考文獻(xiàn)】

相關(guān)期刊論文 前7條

1 劉代波;侯孟書;武澤旭;屈鴻;;一種高效的最短路徑樹動態(tài)更新算法[J];計算機科學(xué);2011年07期

2 韓志軍;柳少軍;唐宇波;景民;;計算機兵棋推演系統(tǒng)研究[J];計算機仿真;2011年04期

3 梁德恒;姚國祥;官全龍;;基于路由最短路徑樹的動態(tài)多節(jié)點刪除算法[J];計算機工程;2011年05期

4 李晶;王世英;;求二部圖的最大匹配圖的一種算法[J];電子學(xué)報;2010年01期

5 孫知信;高艷娟;王文鼐;;更新最短路徑樹的完全動態(tài)算法[J];吉林大學(xué)學(xué)報(工學(xué)版);2007年04期

6 徐心和;王驕;;中國象棋計算機博弈關(guān)鍵技術(shù)分析[J];小型微型計算機系統(tǒng);2006年06期

7 游貴榮;;游戲搜索算法中估價函數(shù)的構(gòu)造策略[J];福建商業(yè)高等�？茖W(xué)校學(xué)報;2005年06期

相關(guān)碩士學(xué)位論文 前3條

1 鄧超;計算機圍棋中的搜索算法研究[D];昆明理工大學(xué);2013年

2 劉雅靖;基于Alpha-Beta搜索算法的計算機博弈的研究與實現(xiàn)[D];大連交通大學(xué);2012年

3 李秀;最短路徑樹動態(tài)算法的研究[D];電子科技大學(xué);2011年

，

本文編號：1908510