基于智能算法的六子棋博弈行为选择的应用研究

论文摘要

行为是生命体外在的表现形式,是生命体内在智能的外部表象,Tyrell认为:“行为选择就是从一组可能的候选集中选择最适合的行为。”因此,行为选择是生命体智能的高级形式。行为选择问题是人工生命研究领域的一个核心问题,人工生命是人工智能的发展,人工生命作为信息科学、生命科学、系统科学等学科的交叉学科,它不是用分析、解剖生命体的方法来理解生命,而是用综合的方法来理解生命,强调系统性和整体性。此外,计算机博弈过程,本质上就是一个对抗性极强的、智能程度高的博弈行为的选择过程,因此,将基于计算机博弈系统的博弈机器人作为人工生命体,并利用人工智能方法来研究智能系统是可行的,也具有重要研究意义。模仿人类的博弈行为选择过程,本文将博弈机器人划分为“大脑”、“视觉”、“记忆”、“控制”等4个部分,文章所依托的科研项目的最终目标是构造一个在物理棋盘上与人类对弈的博弈机器人,本文的主要工作是设计“大脑”。论文主要研究了以下4个方面的问题:第一、设计实现了一套博弈系统,包括棋盘和棋子在计算机中的表示问题,走法生成,搜索技术,估值函数等。第二、针对基于棋形的六子棋博弈系统中,棋形难以判断和统计的问题,提出并规范了“路”的思想,使对局面进行评估前的准备工作大大简化。第三、针对静态估值函数依赖人类棋类知识和评估不够准确的问题,本文在前人研究的基础上,对遗传算法的应用进行了改进,克服了原来遗传算法过早收敛的问题,同时提高了种群的多样性,实验结果证明该方法有效。第四、同样针对静态估值函数依赖人类棋类知识和评估不够准确的问题,提出了采用基于聚焦距离动态调整惯性权重的方法,以改进微粒群算法,以此优化相关参数。实验证明,该算法比遗传算法搜索速度更快,结果更优,是解决评估函数参数优化的有效办法。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 引言
• 1.2 课题的学术意义
• 1.2.1 人工生命体及其行为选择的研究价值
• 1.2.2 机器博弈的研究意义
• 1.2.3 六子棋博弈的研究意义
• 1.3 国内外研究现状
• 1.3.1 人工生命行为选择的研究现状
• 1.3.2 机器博弈的研究现状
• 1.3.3 智能算法的研究现状
• 1.4 本文研究的主要内容
• 2 六子棋机器博弈平台的搭建
• 2.1 背景
• 2.1.1 六子棋的基本规则
• 2.1.2 六子棋的复杂度
• 2.1.3 六子棋的发展展望
• 2.2 人-机界面
• 2.3 棋盘表示与状态分析
• 2.4 走法产生
• 2.4.1 如何产生
• 2.4.2 逐个生成VS 全部生成
• 2.5 博弈搜索引擎
• 2.5.1 博弈树
• 2.5.2 极大极小搜索算法
• 2.5.3 负极大值搜索
• 2.5.4 alpha-beta 裁减
• 2.6 棋局评估函数
• 2.7 六子棋机器博弈策略框架
• 3 基于“路”的六子棋机器博弈策略
• 3.1 完全信息博弈与不完全信息博弈
• 3.1.1 完全信息博弈
• 3.1.2 不完全信息博弈
• 3.2 基于棋形的缺陷
• 3.3 “路”的定义
• 3.4 基于“路”的评估函数
• 3.5 基于“路”的博弈策略
• 4 基于遗传算法评估函数的构造
• 4.1 评估函数参数优化问题
• 4.1.1 评估函数参数设置问题
• 4.1.2 评估函数参数设置的2 种方法
• 4.2 基本遗传算法
• 4.2.1 遗传算法的基本思想
• 4.2.2 遗传算法的基本流程
• 4.2.3 遗传算法的特点
• 4.3 改进的遗传算法
• 4.4 遗传算法应用于评估函数
• 4.4.1 编码
• 4.4.2 适应度函数的计算
• 4.4.3 选择算子
• 4.4.4 交叉算子
• 4.4.5 变异算子
• 4.5 遗传算法优化评估函数的实验结果及分析
• 4.5.1 算法收敛性实验与分析
• 4.5.2 优化效果的实验与分析
• 4.6 小结
• 5 基于微粒群算法评估函数的构造
• 5.1 微粒群算法及其应用改造
• 5.1.1 微粒群算法与人工生命
• 5.1.2 标准微粒群算法
• 5.1.3 微粒群算法的改进
• 5.2 评估函数及其应用改进
• 5.3 微粒群算法的实施
• 5.4 实施结果的评估
• 5.4.1 优化效果的实验与分析
• 5.4.2 PSO 与 GA 对比实验的结果与分析
• 5.5 小结
• 6 结论与展望
• 6.1 研究工作小结
• 6.2 存在的问题与不足
• 致谢
• 参考文献
• 个人简历、在学期间发表的学术论文及取得的研究成果