本文選題：機器博弈　切入點：評估函數(shù)　出處：《中國礦業(yè)大學》2017年碩士論文　論文類型：學位論文

【摘要】：人工智能是計算機科學的一個分支,目的是使機器能夠像人類智能一樣感知環(huán)境并最大化達到目標的可能。機器博弈是人工智能極具挑戰(zhàn)的分支之一,其研究對人工智能的發(fā)展具有積極的作用。國外在機器博弈方面的研究較早,并取得了一定的成就;國內(nèi)的研究相對滯后。以棋類為載體是目前機器博弈的主要研究方法。機器博弈系統(tǒng)可以分為四部分:局面表示、行動集合、評估函數(shù)和博弈樹搜索,其中前兩者相對簡單。本文以點格棋為載體,著重對評估函數(shù)和博弈樹搜索算法進行了研究。在評估函數(shù)方面,分析了影響點格棋棋局評價的因素,設(shè)計了一個帶參數(shù)的評估函數(shù)。采用遺傳算法對參數(shù)進行優(yōu)化。為了加快收斂速度,加入啟發(fā)式信息指導搜索的進行,引入適應(yīng)度矩陣、交叉變異率矩陣,對染色體中的每個參數(shù)進行分別考慮。為了減少訓練時間,提出一種梯度訓練方案。最后通過實驗對以上方案進行驗證分析,實驗結(jié)果表明,參數(shù)優(yōu)化后的點格棋棋力得到提升,梯度訓練方案有效減少了訓練時間。在博弈樹搜索方面,對經(jīng)典的博弈樹搜索算法進行了研究。對算法的思路及其改進措施進行了分析,通過實驗對比統(tǒng)計了不同搜索算法搜索的節(jié)點數(shù)和時間開銷,同時也指出了其不足之處,這些不足往往是其他搜索算法優(yōu)化的基礎(chǔ)。本文還介紹了幾個優(yōu)化策略,分析了其優(yōu)化思路,通過實驗對其優(yōu)化效果進行了驗證。傳統(tǒng)博弈樹搜索算法進行等深度搜索使得時間資源得不到合理分配從而導致效率低下,為此本文提出離散度的概念,以此作為判斷標準對不同的局面進行不同深度的搜索;針對歷史啟發(fā)算法可能出現(xiàn)不準確的情況以及迭代加深算法效率低的問題,本文提出HT-IT算法,綜合了歷史啟發(fā)與迭代加深的優(yōu)點,使搜索效率得到提升;將博弈樹搜索算法與并行、分布式相結(jié)合,研究了基于PVM的并行博弈樹搜索算法,提供了一種新的改進方向。最后通過實驗對以上改進策略進行了對比驗證,結(jié)果表明與其他算法相比變長搜索方案和HT-IT算法減少了搜索節(jié)點數(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.
【學位授予單位】：中國礦業(yè)大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：TP18

【參考文獻】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

，

本文編號：1561647