基于搜索算法的人工智能在五子棋博弈中的应用研究

论文摘要

本文以计算机五子棋博弈系统作为研究课题,在对大量的相关文献进行分析研究的基础上,按照人工智能和计算机博弈的一般原理设计了一个五子棋博弈系统的基本模型,并作了简单的实现和验证,所做的工作包括三个方面:第一研究了五子棋在计算机中的表示问题,讨论了计算机中存贮棋局和识别下棋次序,局势状态变化及局势特征、走法产生等方法。第二研究了博弈树的极小极大搜索技术及在此基础上的Alpha-Beta剪枝过程和剪枝优化问题。实现将候选的后继节点按位置邻近顺序排序,使剪枝过程得到优化。第三根据五子棋的特点,提取棋局局势的若干特征,对这些特征赋加权分,并对整个棋局进行特征统计,采用线性函数求得棋局的总估计分值,从而提高了五子棋程序对弈的水平和能力。在上述工作的基础上,本文的创新性研究主要包括以下两个方面:第一对五子棋博弈的专业知识进行了认真的整理,针对五子棋博弈规则简单、局势判断清楚的特点,对五子棋常见的开局、定式及其后的对局做了细致的统计分析,阐明了五子棋对弈中黑白双方优劣势并非均衡的规律,这一规律作为一个指导原则在设计五子棋博弈系统时起到重要作用。第二通过线性函数获得的总估计值,实现了算法的优化和加强,主要有以下两个方面:在执行常规的Alpha-Beta搜索和NegaScout算法之前,使用置换表搜索避免相同局面的节点的搜索。通过使用威胁空间搜索,让计算机对某一局面找出全部的致胜威胁次序,避免了对静态估值函数的调用,只有计算机对当前局面无法找到致胜威胁次序时,才执行对静态估值函数的调用,由于五子棋博弈中,黑方先行者占有很强的优势,大多数局面往往都能找到致胜威胁次序,所以采用威胁空间搜索,结果表明,可以极大的提高程序的表现和对弈水平。

论文目录

• 中文摘要
• 英文摘要
• 第1章 绪论
• 1.1 课题来源
• 1.2 博弈简史
• 1.3 研究计算机博弈的意义
• 1.4 计算机博弈过程
• 1.5 计算机五子棋基本知识介绍
• 1.6 本文解决的问题
• 第2章 状态空间表示与走法产生
• 2.1 棋盘局势状态表示
• 2.2 棋盘中下棋的顺序表示
• 2.3 状态的变化
• 2.4 特征的表示
• 2.5 走法产生
• 2.6 小结
• 第3章 博弈树的搜索技术
• 3.1 极小极大树搜索算法
• 3.2 Alpha-Beta 剪枝过程
• 3.3 Alpha-Beta 剪枝存在的问题及优化
• 3.4 NegaScout 搜索
• 3.5 小结
• 第4章 静态估值函数
• 4.1 棋盘局势特征
• 4.2 估值
• 4.3 静态估值函数的不足及实践结果
• 4.4 小结
• 第5章 搜索算法的优化与增强
• 5.1 置换表（Transposition Table）的搜索
• 5.1.1 哈希表（Hash Table）
• 5.1.2 应用置换表的其它问题
• 5.1.3 Zobrist 哈希技术
• 5.2 威胁空间搜索（Threat Space Search）
• 5.2.1 专业术语和“威胁次序”
• 5.2.2 人类专业棋手的分析
• 5.2.3 计算机程序的策略
• 5.2.4 人与计算机
• 5.2.5 威胁空间搜索
• 5.2.6 算法优化后效果的检验
• 5.2.7 威胁空间搜索的不足
• 5.3 小结
• 第6章 结论
• 参考文献
• 致谢
• 个人简历及在学期间的研究成果