基于点格棋的博弈算法研究与改进

发布时间：2018-03-03 15:40

本文选题：机器博弈　切入点：评估函数　出处：《中国矿业大学》2017年硕士论文　论文类型：学位论文

【摘要】：人工智能是计算机科学的一个分支,目的是使机器能够像人类智能一样感知环境并最大化达到目标的可能。机器博弈是人工智能极具挑战的分支之一,其研究对人工智能的发展具有积极的作用。国外在机器博弈方面的研究较早,并取得了一定的成就;国内的研究相对滞后。以棋类为载体是目前机器博弈的主要研究方法。机器博弈系统可以分为四部分:局面表示、行动集合、评估函数和博弈树搜索,其中前两者相对简单。本文以点格棋为载体,着重对评估函数和博弈树搜索算法进行了研究。在评估函数方面,分析了影响点格棋棋局评价的因素,设计了一个带参数的评估函数。采用遗传算法对参数进行优化。为了加快收敛速度,加入启发式信息指导搜索的进行,引入适应度矩阵、交叉变异率矩阵,对染色体中的每个参数进行分别考虑。为了减少训练时间,提出一种梯度训练方案。最后通过实验对以上方案进行验证分析,实验结果表明,参数优化后的点格棋棋力得到提升,梯度训练方案有效减少了训练时间。在博弈树搜索方面,对经典的博弈树搜索算法进行了研究。对算法的思路及其改进措施进行了分析,通过实验对比统计了不同搜索算法搜索的节点数和时间开销,同时也指出了其不足之处,这些不足往往是其他搜索算法优化的基础。本文还介绍了几个优化策略,分析了其优化思路,通过实验对其优化效果进行了验证。传统博弈树搜索算法进行等深度搜索使得时间资源得不到合理分配从而导致效率低下,为此本文提出离散度的概念,以此作为判断标准对不同的局面进行不同深度的搜索;针对历史启发算法可能出现不准确的情况以及迭代加深算法效率低的问题,本文提出HT-IT算法,综合了历史启发与迭代加深的优点,使搜索效率得到提升;将博弈树搜索算法与并行、分布式相结合,研究了基于PVM的并行博弈树搜索算法,提供了一种新的改进方向。最后通过实验对以上改进策略进行了对比验证,结果表明与其他算法相比变长搜索方案和HT-IT算法减少了搜索节点数,并行博弈树搜索算法则有效缩短了搜索时间。
[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.
【学位授予单位】：中国矿业大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP18

【参考文献】