中国象棋机器博弈数据结构设计与搜索算法研究

论文摘要

人工智能（AI）是计算机知识、心理学和哲学等知识的综合体现。中国象棋的计算机博弈属于人工智能的研究范畴。目前黑白棋、五子棋、国际象棋等棋类的计算机博弈已经取得了成功,而博弈树更为庞大的中国象棋计算机博弈尚处于萌芽阶段。本课题结合在中国象棋机器博弈方面的实践经验,对中国象棋计算机博弈做了详细的分析和研究,主要做了以下工作:首先,设计了中国象棋计算机博弈软件的数据结构,对马和象的着法生成采用模版匹配法,并且根据路向行向比特向量对车、炮等棋子的着法生成采用预置表法。由于采用模版匹配法和预置表法省去了棋子边界的判断,并且利用查询代替搜索,提高了着法生成的速度,进而提高了整个博弈树的搜索效率,该部分的工作是整个程序的基础。另外,研究了博弈树的搜索算法。在alpha-beta搜索算法的基础上,采用极小窗口（PvS）、置换表启发、历史表启发、静态启发等启发算法,有效的提高了搜索的效率;采用静态搜索、选择性延伸等手段,避免了在叶子节点由于棋子交换、将军等因素导致的估值剧烈波动而带来的评估风险;采用空着前向裁剪（NULLMOVE）使得搜索深度在原来基础上增加了2～3层,并且完善了空着前向裁剪的条件判断,使得采用该方法更稳定。最后,简要描述了棋局的评估要点。对各种算法编程实现,实践结果表明了算法可行性,并表现出了良好的性能。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 研究背景
• 1.2 关键技术简介
• 1.3 本文内容安排
• 2 数据结构设计
• 2.1 棋盘棋子编码
• 2.1.1 棋盘坐标编码
• 2.1.2 棋子种类编码
• 2.1.3 棋子个体编码
• 2.2 棋盘信息编码
• 2.2.1 棋盘索引数组
• 2.2.2 棋子索引数组
• 2.2.3 映射数组
• 2.2.4 路向行向比特向量
• 2.3 着法生成
• 2.3.1 模板匹配法
• 2.3.2 预置表法
• 3 搜索算法研究
• 3.1 传统搜索算法介绍
• 3.1.1 极大极小搜索
• 3.1.2 Alpha-Beta搜索
• 3.2 极小窗口搜索（PVS）
• 3.2.1 PVS的原理及实现
• 3.2.2 PVS与alpha-beta算法比较
• 3.3 迭代加深
• 3.3.1 迭代深化描述
• 3.3.2 迭代深化效率分析
• 3.4 置换表
• 3.4.1 置换表的概念
• 3.4.2 哈希概念
• 3.4.3 Zobrist哈希技术
• 3.4.4 置换表搜索
• 3.4.5 置换表启发
• 3.5 启发算法
• 3.5.1 概述
• 3.5.2 历史启发
• 3.5.3 杀手启发
• 3.5.4 静态启发
• 3.5.5 启发式算法的走法排序
• 3.6 静态搜索
• 3.6.1 基本概念
• 3.6.2 静态搜索实现
• 3.7 前向空着裁剪（NullMove）
• 3.8 搜索主体结构
• 4 评估函数
• 4.1 评估函数基本概念
• 4.2 估值函数内容
• 4.2.1 棋子固定价值评估
• 4.2.2 棋子的灵活性评估
• 4.2.3 棋子位置评估
• 4.2.4 棋子关系评估
• 4.2.5 其他评估
• 4.3 估值函数优化
• 4.3.1 基本模型
• 4.3.2 静态估值
• 4.3.3 估值优化
• 5 系统实现
• 6 总结与展望
• 致谢
• 参考文献
• 发表的论文