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

发布时间：2017-04-29 05:06

  本文关键词：基于搜索算法的人工智能在五子棋博弈中的应用研究，由笔耕文化传播整理发布。

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

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

【参考文献】

中国期刊全文数据库 前2条

1 肖齐英,王正志;博弈树搜索与静态估值函数[J];计算机应用研究;1997年04期

2 王鲁明,戴汝为;在计算机围棋中形象思维的研究[J];自动化学报;1997年04期

  本文关键词：基于搜索算法的人工智能在五子棋博弈中的应用研究，，由笔耕文化传播整理发布。

本文编号：334237