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