文档介绍：基于极小极大搜索和α(论文范文, JSP,JAVA 毕业设计)
目录
摘要 I
ABSTRACT II
1. 绪论 1
2. 开发语言及工具介绍 3
3. 需求分析 6
4. 工作原理和关键技术 11
5. 系统总体设计 14
6. 系统详细设计 19
7 系统实现 27
32
结束语 36
致谢 37
参考文献 38
附录 39
本毕业设计包含:开题报告+任务书+毕业正文+文献原文及中文翻译+毕业设计源码
摘要
一字棋人机对弈算法的研究主要是对极小极大搜索方法,α-β剪枝搜索方法的研究。
这些算法还需要一个评估函数作为基础来执行。
极大极小算法:当轮到我方走棋时,首先按照一定的搜索深度生成出给定深度 d 以内的
所有状态的生成树,计算所有叶节点的评价函数值。然后从 d-1 层节点开始逆向计算:对于
我方要走的节点(用 MAX 标记,称为极大节点)取其子节点中的最大值为该节点的值(因
为我方总是选择对我方有利的棋)。
对于对方要走的节点(用 MIN 标记,称为极小节点)取其子节点中的最小值为该节点
的值(对方总是选择对我方不利的棋)。一直到计算出根节点的值为止。获得根节点取值的
那一分枝,即为所选择的最佳走步。
α-β剪枝搜索:α剪枝:若任一极小值层节点的β值小于或等于它任一先辈极大值居
节点的α值,即α(先辈层)≥β(后继层),则可中止该极小值层中这个 MIN 节点以下的
搜索过程。这个 MIN 节点最终的倒推值就确定为这个β值。
β剪枝:若任一极大值层节点的α值大于或等于它任一先辈极小值层节点的β值,即α
(后继层)≥β(先辈层),则可以中止该极大值层中这个 MAX 节点以下的搜索过程。这个
MAX 节点的最终倒推值就确定为这个α值。
评估函数——系统根据将所有空白点填上电脑棋子得到能够连成 N 颗棋子一线的条数
与填上玩家棋子得到能够连成 N 颗棋子一线的条数的差。以及获得该点能够达到的权值(由
己方该点最大连子数、对方该点最大连子数、己方该点可拓展最大连子数、对方该点可拓展
最大连子数、己方目前局面最大连子数、对方目前局面最大连子数 6 个因素影响),这两个
方面的和作为评估值。
AI 实现思路:第一步:判断棋盘空置点个数,如果只有一个,直接落子;第二步:判断
是否存在一步获胜的走法,如果有,直接落子;第三步:判断是否存在一步失败的情况,如
果有,直接落子;第四步:判断是否为开局阶段;第五步:判断是否为中盘阶段;第六步:
运行α-β剪枝搜索算法。
关键词:一字棋,极大极小搜索算法,α-β剪枝搜索算法,评估函数,AI
ABSTRACT
Tic-tac-toe man-machine right algorithm of MIN-MAX is mainly to search method, alpha
beta pruned search method of research. These algorithms also need a evaluation function as a
basis to execute.
MIN-MAX algori