六子棋计算机博弈及其系统的研究与优化

论文摘要

计算机博弈是人工智能领域一个极其重要且最具挑战性的研究方向之一,它的研究为人工智能带来了很多重要的方法和理论,产生了广泛的社会影响和学术影响以及大量的研究成果。计算机博弈是人工智能的一个果蝇,然而棋类游戏又是计算机博弈的一个标准性问题,各种搜索算法、模式识别及智能方法在计算机博弈中都可以得到广泛的应用。因此在过去的半个世纪里,世界各地的学者花费了大量的心血对于计算机博弈包括奥赛罗、checker、国际象棋、中国象棋、五子棋、围棋进行研究。涌现出大量令人震惊的成果,1997年“深蓝”战胜卡斯帕罗夫的比赛就在全世界范围内引发了震动。其他很多棋类的计算机水平都已达到了世界冠军的水平。目前,对于像五子棋、中国象棋等棋类游戏的计算机博弈算法研究已相对成熟,六子棋作为一个刚刚兴起不久的棋类游戏,其计算机博弈算法的研究还相对较少。即使目前已经出现六子棋的论坛以及比赛的平台,真正对于六子棋计算机博弈算法以及系统的研究还不多。六子棋的发明者台湾吴毅成教授给出了六子棋的公平性问题以及基于迫著（Threats-based）的胜利策略,但是对于其计算机博弈问题没有给出更加深刻的阐述,同时也没有全面解决六子棋计算机博弈问题。本文正是对六子棋计算机博弈技术的进一步探索。本文主要对本课题组前期实现的系统四个主要部分（搜索引擎、走法生成、评估函数和开局库）进行了完善和进一步的优化,同时对功能进行了扩展。走法生成模块中利用棋类的战场策略进行了搜索限制和棋型特征码的提取;搜索引擎模块加入策略启发式信息进行优化,使其更“智能”;评估函数模块中,由于特征码的引入使得采用遗传算法进行优化具有实际可行性;开局库存储了大量的专家棋谱,可以避免在开局时由于搜索深度的不足而带来战略上的失误,同时大大提高了对战的效率。最后本文对六子棋计算机博弈系统进行了测试与评价,包括评估函数的准确度、搜索算法的效率以及系统的整体性能确实得到了显著的提升。

论文目录

• 摘要
• ABSTRACT
• 1 绪论
• 1.1 引言
• 1.2 六子棋计算机博弈的研究意义
• 1.3 六子棋计算机博弈在国内外的研究现状
• 1.3.1 计算机博弈研究简史
• 1.3.2 六子棋计算机博弈的研究现状
• 1.4 六子棋计算机博弈的核心问题
• 1.4.1 搜索算法
• 1.4.2 评估函数
• 1.5 六子棋计算机博弈系统的评价方法
• 1.6 课题的提出和研究意义
• 1.6.1 课题的提出
• 1.6.2 研究的意义
• 1.7 本文的主要研究内容
• 2 六子棋平台介绍
• 2.1 背景
• 2.2 规则
• 2.3 公平性问题
• 2.3.1 五子棋的公平性问题
• 2.3.2 公平的定义
• 2.3.3 脱离战场
• 2.3.4 六子棋的公平性问题
• 2.4 复杂度
• 2.5 六子棋定石和诘棋
• 2.6 六子棋发展动向
• 2.6.1 台湾六子棋协会
• 2.6.2 六子棋学术活动
• 2.7 本章小结
• 3 棋类设计的通用方法和思想—计算机博弈
• 3.1 计算机博弈的要点
• 3.2 计算机博弈程序的组成
• 3.2.1 人机界面
• 3.2.2 棋盘和棋局表示－数据结构
• 3.2.3 着法生成
• 3.2.4 机器博弈、搜索技术
• 3.2.5 评估函数
• 3.3 本章小结
• 4 六子棋计算机博弈系统的优化
• 4.1 引言
• 4.2 六子棋系统的实现结构模型
• 4.3 棋局信息的数据表示
• 4.3.1 棋盘状态表示
• 4.3.2 棋子状态数组描述
• 4.3.3 六子棋棋型及其数字化描述
• 4.3.4 前期棋型数组表示的错误
• 4.3.5 改进的棋型表示方法－特征码表示
• 4.4 六子棋计算机博弈问题描述－博弈树
• 4.5 优化的搜索算法－基于启发式信息的搜索
• 4.5.1 α-β剪枝搜索算法的实现
• 4.5.2 优化的α-β剪枝搜索算法－启发式搜索
• 4.6 本章小结
• 5 评估函数优化及遗传算法优化评估值
• 5.1 引言
• 5.2 局面评估方法
• 5.3 评估值和评估函数的改进
• 5.4 遗传算法的实际操作
• 5.4.1 奠定应用遗传算法的基础
• 5.4.2 遗传算法优化棋型评估值的操作过程和方法
• 5.4.3 改进的遗传算法
• 5.5 实际操作结果对比分析
• 5.6 本章小结
• 6 系统功能的完善
• 6.1 引言
• 6.2 程序的完善
• 6.2.1 悔棋的实现
• 6.2.2 棋谱保存
• 6.2.3 其他优化
• 6.3 本章小结
• 7 结论与展望
• 7.1 结论、比赛结果及系统评价
• 7.2 本系统目前存在的问题和不足
• 7.3 后续工作
• 7.4 结语
• 致谢
• 参考文献
• 附录
• A 作者在攻读硕士学位期间发表论文目录