本文選題：機(jī)器博弈　切入點(diǎn)：評(píng)估函數(shù)　出處：《中國(guó)礦業(yè)大學(xué)》2017年碩士論文　論文類型：學(xué)位論文

【摘要】：人工智能是計(jì)算機(jī)科學(xué)的一個(gè)分支,目的是使機(jī)器能夠像人類智能一樣感知環(huán)境并最大化達(dá)到目標(biāo)的可能。機(jī)器博弈是人工智能極具挑戰(zhàn)的分支之一,其研究對(duì)人工智能的發(fā)展具有積極的作用。國(guó)外在機(jī)器博弈方面的研究較早,并取得了一定的成就;國(guó)內(nèi)的研究相對(duì)滯后。以棋類為載體是目前機(jī)器博弈的主要研究方法。機(jī)器博弈系統(tǒng)可以分為四部分:局面表示、行動(dòng)集合、評(píng)估函數(shù)和博弈樹(shù)搜索,其中前兩者相對(duì)簡(jiǎn)單。本文以點(diǎn)格棋為載體,著重對(duì)評(píng)估函數(shù)和博弈樹(shù)搜索算法進(jìn)行了研究。在評(píng)估函數(shù)方面,分析了影響點(diǎn)格棋棋局評(píng)價(jià)的因素,設(shè)計(jì)了一個(gè)帶參數(shù)的評(píng)估函數(shù)。采用遺傳算法對(duì)參數(shù)進(jìn)行優(yōu)化。為了加快收斂速度,加入啟發(fā)式信息指導(dǎo)搜索的進(jìn)行,引入適應(yīng)度矩陣、交叉變異率矩陣,對(duì)染色體中的每個(gè)參數(shù)進(jìn)行分別考慮。為了減少訓(xùn)練時(shí)間,提出一種梯度訓(xùn)練方案。最后通過(guò)實(shí)驗(yàn)對(duì)以上方案進(jìn)行驗(yàn)證分析,實(shí)驗(yàn)結(jié)果表明,參數(shù)優(yōu)化后的點(diǎn)格棋棋力得到提升,梯度訓(xùn)練方案有效減少了訓(xùn)練時(shí)間。在博弈樹(shù)搜索方面,對(duì)經(jīng)典的博弈樹(shù)搜索算法進(jìn)行了研究。對(duì)算法的思路及其改進(jìn)措施進(jìn)行了分析,通過(guò)實(shí)驗(yàn)對(duì)比統(tǒng)計(jì)了不同搜索算法搜索的節(jié)點(diǎn)數(shù)和時(shí)間開(kāi)銷,同時(shí)也指出了其不足之處,這些不足往往是其他搜索算法優(yōu)化的基礎(chǔ)。本文還介紹了幾個(gè)優(yōu)化策略,分析了其優(yōu)化思路,通過(guò)實(shí)驗(yàn)對(duì)其優(yōu)化效果進(jìn)行了驗(yàn)證。傳統(tǒng)博弈樹(shù)搜索算法進(jìn)行等深度搜索使得時(shí)間資源得不到合理分配從而導(dǎo)致效率低下,為此本文提出離散度的概念,以此作為判斷標(biāo)準(zhǔn)對(duì)不同的局面進(jìn)行不同深度的搜索;針對(duì)歷史啟發(fā)算法可能出現(xiàn)不準(zhǔn)確的情況以及迭代加深算法效率低的問(wèn)題,本文提出HT-IT算法,綜合了歷史啟發(fā)與迭代加深的優(yōu)點(diǎn),使搜索效率得到提升;將博弈樹(shù)搜索算法與并行、分布式相結(jié)合,研究了基于PVM的并行博弈樹(shù)搜索算法,提供了一種新的改進(jìn)方向。最后通過(guò)實(shí)驗(yàn)對(duì)以上改進(jìn)策略進(jìn)行了對(duì)比驗(yàn)證,結(jié)果表明與其他算法相比變長(zhǎng)搜索方案和HT-IT算法減少了搜索節(jié)點(diǎn)數(shù),并行博弈樹(shù)搜索算法則有效縮短了搜索時(shí)間。
[Abstract]:Artificial intelligence is a branch of computer science designed to enable machines to perceive the environment as human intelligence and maximize the possibility of achieving its goals. Machine game is one of the most challenging branches of artificial intelligence. Its research has positive effect on the development of artificial intelligence. At present, the machine game system can be divided into four parts: situation representation, action set, evaluation function and game tree search. The first two are relatively simple. In this paper, the evaluation function and the game tree search algorithm are studied. In the evaluation function, the factors that affect the evaluation of the game are analyzed. An evaluation function with parameters is designed. Genetic algorithm is used to optimize the parameters. In order to speed up the convergence, heuristic information is added to guide the search. The fitness matrix and the cross-mutation rate matrix are introduced. In order to reduce the training time, a gradient training scheme is proposed. Finally, the experimental results show that, After the optimization of parameters, the strength of grid chess is improved, and the training time is effectively reduced by the gradient training scheme. In the aspect of game tree search, the classical game tree search algorithm is studied. The train of thought of the algorithm and its improvement measures are analyzed. The number of nodes and the time cost of different search algorithms are compared through experiments. At the same time, the shortcomings are pointed out, which are often the basis of the optimization of other search algorithms. Several optimization strategies are also introduced in this paper. The optimization idea is analyzed, and its optimization effect is verified by experiments. The traditional game tree search algorithm for equal depth search results in inefficiency due to the lack of reasonable allocation of time resources. In this paper, the concept of discreteness is proposed in this paper. In order to solve the problem of inaccuracy of historical heuristic algorithm and low efficiency of iterative deepening algorithm, HT-IT algorithm is proposed in this paper. The search efficiency is improved by synthesizing the advantages of historical inspiration and iterative deepening, and the parallel game tree search algorithm based on PVM is studied by combining game tree search algorithm with parallel and distributed search algorithm. A new direction of improvement is provided. Finally, the experimental results show that the variable length search scheme and the HT-IT algorithm reduce the number of search nodes compared with other algorithms. The parallel game tree search algorithm effectively shortens the search time.
【學(xué)位授予單位】：中國(guó)礦業(yè)大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：TP18

【參考文獻(xiàn)】

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

1 陶九陽(yáng);吳琳;胡曉峰;;AlphaGo技術(shù)原理分析及人工智能軍事應(yīng)用展望[J];指揮與控制學(xué)報(bào);2016年02期

2 盧俊;張保明;郭海濤;陳小衛(wèi);;利用并查集的多視匹配點(diǎn)提取算法[J];計(jì)算機(jī)應(yīng)用;2016年06期

3 賀倩;;人工智能技術(shù)發(fā)展研究[J];現(xiàn)代電信科技;2016年02期

4 劉明;王瑞;;基于自適應(yīng)遺傳算法的改進(jìn)PID參數(shù)優(yōu)化[J];計(jì)算機(jī)測(cè)量與控制;2015年03期

5 蔡自興;;人工智能在冶金自動(dòng)化中的應(yīng)用[J];冶金自動(dòng)化;2015年01期

6 王弈;李傳富;;人工智能方法在醫(yī)學(xué)圖像處理中的研究新進(jìn)展[J];中國(guó)醫(yī)學(xué)物理學(xué)雜志;2013年03期

7 程宇;雷小鋒;;五子棋中Alpha-Beta搜索算法的研究與改進(jìn)[J];計(jì)算機(jī)工程;2012年17期

8 張明亮;吳俊;李凡長(zhǎng);;五子棋機(jī)器博弈系統(tǒng)評(píng)估函數(shù)的設(shè)計(jì)[J];計(jì)算機(jī)應(yīng)用;2012年07期

9 鄒蕾;張先鋒;;人工智能及其發(fā)展應(yīng)用[J];信息網(wǎng)絡(luò)安全;2012年02期

10 焦尚彬;劉丁;;博弈樹(shù)置換表啟發(fā)式算法研究[J];計(jì)算機(jī)工程與應(yīng)用;2010年06期

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

1 夏小云;隨機(jī)啟發(fā)式搜索算法的性能分析[D];華南理工大學(xué);2015年

2 宮良偉;基于AutoCAD Map 3D的通風(fēng)仿真系統(tǒng)的研究[D];中國(guó)礦業(yè)大學(xué);2012年

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

1 劉洋;點(diǎn)格棋博弈中UCT算法的研究與實(shí)現(xiàn)[D];安徽大學(xué);2016年

2 唐霜霜;點(diǎn)格棋機(jī)器博弈系統(tǒng)的研究與實(shí)現(xiàn)[D];安徽大學(xué);2015年

3 黃春;改進(jìn)遺傳算法的函數(shù)優(yōu)化及應(yīng)用[D];廣西大學(xué);2015年

4 褚秋雯;從哲學(xué)的角度看人工智能[D];武漢理工大學(xué);2014年

5 宋興亮;中國(guó)象棋博弈樹(shù)搜索算法研究與實(shí)現(xiàn)[D];沈陽(yáng)工業(yè)大學(xué);2012年

6 楊旭;基于動(dòng)態(tài)博弈的入侵響應(yīng)決策模型[D];吉林大學(xué);2011年

7 連蓮;基于Moore自動(dòng)機(jī)的機(jī)器博弈系統(tǒng)建模與研究[D];東北大學(xué);2009年

8 張明亮;一種新的博弈樹(shù)搜索算法及其應(yīng)用研究[D];蘇州大學(xué);2007年

9 高強(qiáng);一種混合博弈樹(shù)算法在中國(guó)象棋人機(jī)博弈中的應(yīng)用研究[D];大連交通大學(xué);2007年

10 張雪瓊;基于博弈論的入侵檢測(cè)系統(tǒng)[D];華中科技大學(xué);2006年

，

本文編號(hào)：1561647