單回合的回合制戰(zhàn)棋博弈模型搜索算法研究.pdf

1、戰(zhàn)棋博弈（Turn-Based War Chess，TBW）是回合制策略游戲（Turn-Based Strategy，TBS）的重要成分，但目前其人工智能關(guān)注度還不夠。受限于戰(zhàn)棋具有豐富多樣的元素，目前還沒有一個(gè)標(biāo)準(zhǔn)化的數(shù)學(xué)模型，從而導(dǎo)致了戰(zhàn)棋博弈目前的研究還停留在較為簡(jiǎn)單的層次上。隨著移動(dòng)端游戲的井噴式發(fā)展，戰(zhàn)棋博弈類游戲因其觸屏操作、輕量級(jí)、碎片化時(shí)間而擁有更大的發(fā)展?jié)摿?，然而因其人機(jī)博弈部分智能低下，嚴(yán)重影響了用戶體驗(yàn)和產(chǎn)品黏性，

2、成為束縛其游戲性的瓶頸。戰(zhàn)棋博弈本質(zhì)上是由橫向的組合優(yōu)化問題和縱向的博弈樹搜索問題結(jié)合的產(chǎn)物，既可以看作是一個(gè)分階段的多智能體協(xié)同作業(yè)的規(guī)劃問題，也可以看作是一個(gè)分支系數(shù)巨大的樹搜索問題。所以，其背后潛藏著的對(duì)以上傳統(tǒng)問題體系的擴(kuò)充和發(fā)展，其研究意義都超出了對(duì)戰(zhàn)棋游戲本身的研究。如今，基于大數(shù)據(jù)、云計(jì)算和機(jī)器學(xué)習(xí)的新一輪弱人工智能研究正在蓬勃興起，使得運(yùn)用更為有效的技術(shù)讓戰(zhàn)棋博弈的人工智能獲得較大程度的提升成為了可能。
　　本論文

3、較為系統(tǒng)的分析了戰(zhàn)棋博弈的特性，基于特征選擇了從棋類博弈的角度來研究戰(zhàn)棋的機(jī)器博弈。首先建立戰(zhàn)棋游戲的通用博弈模型，提出橫向的組合優(yōu)化和縱向的博弈樹搜索的理論框架，闡明橫向分支系數(shù)巨大的關(guān)鍵難題，其次，針對(duì)橫向問題提出單回合窮舉搜索的按序枚舉法和遞歸枚舉法，并深入分析它們的性能和各自的適用性。隨后就計(jì)算冗余問題提出兩套優(yōu)化策略—單位移動(dòng)范圍的簡(jiǎn)化和搜索空間的簡(jiǎn)化，通過理論實(shí)驗(yàn)證實(shí)了它們?cè)诓桓淖冇行阉骺臻g的前提下能大幅的提高搜索效率。然

4、后就搜索過程中比較耗時(shí)的單位移動(dòng)范圍計(jì)算，引入動(dòng)態(tài)最短路徑樹（DynamicShortest Path Tree，DSPT）的新的研究方法，提出關(guān)于動(dòng)態(tài)刪除節(jié)點(diǎn)的MRDA_SPT（Multi-node Removed Dynamic Algorithm of Shortest Path Tree）改進(jìn)算法，并通過理論分析和實(shí)驗(yàn)驗(yàn)證，該算法的效率均優(yōu)于現(xiàn)有其他方法。最后，基于新算法又提出動(dòng)態(tài)更新單位移動(dòng)范圍的DR_SPT（Dynamic

5、Range Shortest Path Tree）算法，通過實(shí)驗(yàn)表明它能顯著的提高計(jì)算移動(dòng)范圍的效率，從而整體上提升了戰(zhàn)棋博弈單回合搜索速度。
　　本論文的研究成果包括如下：
　　①對(duì)戰(zhàn)棋博弈進(jìn)行建模和研究，并提出縱向和橫向的研究框架。研究結(jié)果表明，本質(zhì)上，戰(zhàn)棋博弈屬于二人（或多人）零和完全信息博弈，因其每回合全部棋子都可移動(dòng)，并且移動(dòng)順序敏感的特點(diǎn)，戰(zhàn)棋博弈構(gòu)成了一個(gè)分支系數(shù)異常龐大的博弈樹。本論文對(duì)該博弈樹的規(guī)模進(jìn)行了理

6、論上的計(jì)算，并與其它主流棋類對(duì)比，發(fā)現(xiàn)戰(zhàn)棋的博弈樹分支系數(shù)會(huì)隨著棋子的數(shù)量和每個(gè)棋子的移動(dòng)范圍的增大而急劇增大。最后，在博弈樹理論的框架下就縱向和橫向的研究路線給予了展望。
　　②提出戰(zhàn)棋博弈的單回合搜索算法并做完備性證明和性能比較。單回合搜索是戰(zhàn)棋博弈樹第一層展開的核心算法，其效率也是整個(gè)戰(zhàn)棋博弈性能的關(guān)鍵指標(biāo)。針對(duì)順序優(yōu)先還是行為優(yōu)先提出了兩種單回合搜索算法：
　　1、按序枚舉法；
　　2、遞歸枚舉法。
　　

7、它們的主要區(qū)別是選擇不同的排列算法：前者采用字典序法，后者采用遞歸法，而它們體現(xiàn)出來了不同的搜索架構(gòu)：前者基于序列，后者基于行動(dòng)。從理論上證明了兩個(gè)算法都是最優(yōu)解的，并從理論和實(shí)驗(yàn)分析了他們效率的差別：棋子在所有位置上的擴(kuò)展操作（ops1）的次數(shù)總和，遞歸枚舉法比按序枚舉法在各種條件下都有不同程度的減少。
　　③就單回合搜索計(jì)算復(fù)雜度高、計(jì)算冗余的問題提出了兩套優(yōu)化策略：
　　1、簡(jiǎn)化單位移動(dòng)范圍的計(jì)算；
　　2、劃分

8、與簡(jiǎn)化搜索空間。通過理論證明和實(shí)驗(yàn)檢驗(yàn)，證實(shí)了這兩種策略可以在不改變有效搜索空間的前提下大幅的提高搜索效率。
　?、芴岢鯩RDA_SPT改進(jìn)算法，提升了動(dòng)態(tài)最短路徑樹（DSPT）關(guān)于節(jié)點(diǎn)動(dòng)態(tài)刪除的效率。首先對(duì)動(dòng)態(tài)最短路徑樹（DSPT）進(jìn)行了較為系統(tǒng)的研究，并針對(duì)前人的工作當(dāng)中DSPT動(dòng)態(tài)節(jié)點(diǎn)刪除算法存在冗余的問題提出了新算法—MRDA_SPT改進(jìn)算法，從理論上分析其復(fù)雜度，通過與目前較快的算法做對(duì)比實(shí)驗(yàn)，表明了MRDA_SPT改進(jìn)