五子棋计算机博弈系统的研究与设计

摘要

计算机博弈是人工智能领域最具挑战的研究分支之一。它是研究人脑思维的载体，是计算机技术与博弈论相结合的产物，是人工智能领域的“试验田”，被誉为人工智能的“果蝇”。因此，有关计算机博弈的理论与实践研究，将可以促进人工智能的发展。在计算机博弈中，棋类博弈是其研究热点之一，因为人们相信存在于棋类博弈中的智能信息或许可以应用到人类智能活动中。
　　五子棋博弈是棋类博弈中至关重要的组成部分，其普及程度仅次于国际象棋。它具有聚集博弈典型意义、容易深入研究、博弈结果直观反应机器智能程度等优点。因此可以把五子棋博弈作为计算机博弈的典型代表之一，对其进行深入研究，从而促使计算机博弈理论和实践研究的发展，进而推动人工智能事业不断地前进。
　　本文以五子棋为载体对计算机博弈相关理论与技术进行了分析与研究。针对传统Alpha-Beta剪枝算法搜索效率较低以及博弈水平不高的问题，提出了一种基于连续冲四搜索的Alpha-Beta剪枝算法以及基于搜索限定的Alpha-Beta剪枝算法;针对传统基于棋型估值函数的参数主要由经验获得并通过手工进行调整，存在人为不确定性的问题，提出了一种新的自适应惯性权重混沌粒子群算法(CPSO-NAIW)，并把它首次应用到五子棋估值函数参数优化问题中。实验结果表明，本文提出的改进Alpha-Beta剪枝算法有效地提高了搜索效率和博弈水平;采用本文提出的CPSO-NAIW算法优化后参数的五子棋博弈系统的博弈水平得到了很大提升。
　　本文首先介绍了计算机博弈相关概念与技术，然后分析了五子棋博弈组成要素并利用事件对策论对其进行数学建模，研究了五子棋博弈中的搜索算法以及估值函数，最后对系统进行了设计与实现。
　　本文核心技术与创新点如下:
　　(1)提出了一种基于连续冲四搜索的Alpha-Beta剪枝算法。根据五子棋博弈的特点，在Alpha-Beta剪枝算法中引入连续冲四搜索这种强有力的进攻手段，并采用搜索范围限定以及对连续冲四成功进行保存，当下次遇到相同局面时，优先对存储的连续冲四着法进行搜索的连续冲四启发方法，以减少无用和重复搜索。该算法提高了搜索效率和博弈水平。
　　(2)提出了一种基于搜索限定的Alpha-Beta剪枝算法。根据五子棋落子比较集中和脱离战场思想，对棋盘搜索区域进行划分，并根据不同搜索区域落子对局面的影响程度采用不同的搜索深度，以减少无用搜索。该算法在不影响博弈水平的情况下，提高了搜索效率。
　　(3)提出了一种新的自适应惯性权重混沌粒子群算法(CPSO-NAIW)。该算法从惯性权重的调整以及如何摆脱局部极值两个方面入手来改善粒子群算法(Particle Swarm Optimization，PSO)的性能。首先采用粒子相对于群体极值位置的距离对权重进行动态调整，把权重的变化与粒子的位置状态信息关联起来的方法，减少了算法陷入局部极值的概率，然后在算法陷入局部极值时，对群体极值位置进行混沌优化，以使粒子搜索局部极值外的新邻域和新路径，增强了算法跳出局部极值的可能，最后把CPSO-NAIW算法首次应用到五子棋估值函数的参数优化问题中，以解决传统估值参数仅通过手工调整，存在人为不确定的问题。采用该算法优化后参数的五子棋博弈系统的博弈水平有显著提升。
　　本文以五子棋为载体对计算机博弈中至关重要的搜索算法以及估值函数进行了相关研究与改进。在搜索算法方面，提出了一种基于连续冲四搜索的Alpha-Beta剪枝算法以及基于搜索限定的Alpha-Beta剪枝算法。在估值函数方面，提出了一种CPSO-NAIW算法，并把它首次应用到估值函数的参数优化问题中。实验结果表明，两种改进的Alpha-Beta剪枝算法有效地提高了搜索效率和博弈水平，应用CPSO-NAIW算法优化后参数的五子棋博弈系统的博弈水平具有明显优势。

目录

声明

摘要

第一章 绪论

1．1 研究背景

1．2 研究现状

1．3 研究意义

1．4 本文工作

1．4．1 研究内容

1．4．2 论文组织结构

第二章 计算机博弈基本概念与技术

2．1 基本概念与技术

2．1．1 博弈树

2．1．2 复杂度

2．1．3 递归

2．1．4 回溯

2．2 研究对象及分析

2．2．1 对象分类

2．2．2 本文研究对象

2．3 本章小结

第三章 五子棋计算机博弈建模

3．1 五子棋术语

3．2 五子棋规则

3．3 五子棋博弈系统组成要素

3．3．1 知识表示

3．3．2 着法生成

3．3．3 搜索算法

3．3．4 估值函数

3．4 五子棋博弈过程建模

3．5 本章小结

第四章 Alpha-Beta剪枝算法搜索优化

4．1 基本搜索算法介绍

4．1．1 盲目搜索算法

4．1．2 极大极小算法

4．1．3 Alpha-Beta剪枝算法

4．1．4 Alpha-Beta剪枝算法效率

4．2 基于连续冲四搜索的Alpha-Beta剪枝算法

4．2．1 连续冲四与相关优化

4．2．2 算法描述

4．2．3 实验设计与分析

4．3 基于搜索限定的Alpha-Beta剪枝算法

4．3．1 搜索限定

4．3．2 算法描述

4．3．3 实验设计与分析

4．4 本章小结

第五章 基于CPSO-NAIW算法的估值函数参数优化

5．1 估值函数

5．2 CPSO-NAIW算法

5．2．1 粒子群算法

5．2．2 自适应惯性权重

5．2．3 基于混沌优化摆脱局部极值的方法

5．3 基于CPSO-NAIW算法的估值函数参数优化算法

5．3．1 个体编码和种群初始化

5．3．2 适应度函数的计算方法-锦标赛法

5．3．3 算法描述

5．4 实验设计与分析

5．5 本章小结

第六章 五子棋博弈系统设计与实现

6．1 系统设计

6．1．1 系统总体结构

6．1．2 系统流程图

6．2 系统实现

6．2．1 运行环境与实现技术

6．2．2 系统界面

6．3 本章小结

第七章 总结与展望

7．1 本文的主要贡献与结论

7．2 未来工作与展望

参考文献

附录

致谢

攻读硕士期间发表的论文、科研项目及获奖情况