资源描述：
《智能五子棋博弈算法探究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、智能五子棋博弈算法探究摘要：人工智能是一门正在迅速发展的新兴的综合性很强的边缘科学。博弈是人工智能的主要研究领域之一，他涉及人工智能中的推理技术、搜索方法和决策规划。本文将这些技术用于五子棋中。设计了一个智能五子棋系统，实现人和计算机两方进行博弈。关键词：五子棋人工智能搜索人工智能是一门综合性很强的边缘科学，它研究如何使计算机去做那些过去只能靠人的智力才能做的工作。而博弈是人工智能研究的一个重要分支，它不仅存在于游戏、下棋之中，也存在于政治、经济、军事和生物竞争中。五子棋是起源于中国古代的传统黑白棋种之一。现代五子棋日文称之为“连
2、珠”，英译为“Ren-ju”，英文称之为“Gobang"或"FIR"（FiveinaRow的缩写），亦有“连五子”、"五子连"、“串珠"、"五目"、"五目碰"、“五格”等多种称谓。与其他棋类相比，五子棋每一层搜索节点数量庞大，因此盘面预测的计算量是非常大的，比如对于五子棋的中盘走法中，如果要预测四步的局面数的话可以达到一百万。本文是对五子棋算法的设计原理和实现方法进行探讨和研究，主要包括数据结构、搜索算法和优劣评价函数组成,主要的特点包括快速的数据结构设计实现、以及高效率的搜索算法和尽可能的模拟人类的智能。1、棋局的数据结构表示我
3、们知道五子棋的走法中有优先和禁手，如连四肯定是没有三四优先，而如果是黑方出现三三（包括“四、三、三”）、四四（包括“四、四、三”），而黑方只能以四三取胜，如果黑方走出禁手则是输；五连与禁手同时形成，先五为胜，等等的规矩。但是电脑毕竟不是人类，可以类人但是却不可以自己思考，那么就需要给电脑一个它可以明白的评判标准。下面，我列出基本的棋型优先顺序：造一个二〈……〈造四个二〈冲三〈……〈冲两个二和一个三〈冲双三〈冲四〈冲四三。之所以这么设置是由于五子棋的下法所致，只要构成5颗一线就赢了，所以说一条线上构成的越多那么就有优势，当然就是棋数
4、越多，分越多。那么为了让电脑明确的知道是不是应该落子，就给它一个标准：分值。用程序语言表示：enumValue{FAILED—99999,SKIP=20,LENG=10,TWO=100,THREE=1000,IFOUR=10000,FOUR=50000,SF0UR=70000,WIN=100000}；如果某一点导致失败，则分值为FAILED,由于它足够小,所以无论任何棋型与它的组合都小于0,SKIP之所以给它20分，是为了避免电脑出现无棋可下的情况，LENG是有可能发生长连的点，这有可能导致禁手，TWO、THREE.FOUR.WI
5、N观名知意，TFOUR和SFOUR分别是弱四和强四。强四的点比普通的冲四重要的多，比如一个活四，意味着即将判出胜负。弱四是为了提供更大的灵活。也许有某种冲四并不一定比冲三重要，我在这里并没有使用，以后可以扩充。2、五子棋算法介绍及初步实现2.1五子棋博弈树中的极大极小搜索和a-B剪枝为了使谈论更有条理性[5],将博弈的双方分别命名为MAX和MIN。而搜索的任务是为MAX找最佳的移动。假设MAX先移动（此时暂时不考虑五子棋的禁手等规则），然后2个博弈者轮流移动。因此，深度为偶数的节点，对应于MAXy一步移动的位置，称为MAX节点；深
6、度为奇数的节点对应于MIN下一步移动的位置，称为MIN节点（博弈树的顶节点深度为0）。k层包括深度为2k和2k+l的节点。通常用层数表示博弈树的搜索深度。他可以表示出向前预测的MAX和MIN交替运动的回合数。用整个棋盘估值的函数h（n）为静态估值函数。设想当前棋局S为轮到计算机方下棋（用方框表示），任选一空点作为计算机方的下棋位置（可有若干种选择），接着考虑在此情况下游戏者一方下棋的棋局（用圆圈表示）；从某一个圆圈棋局出发，任选一空点作为游戏者一方的落子处(又有若干种选择)。再次形成计算机方下棋的方框棋局；依此类推，这样可形成一棵
7、以S为根结点的博弈树，该树以圆圈棋局为第2层子结点，以方框棋局为第3层子结点等等。如果继续向前搜索，可形成多层子结点，现在以向前搜索3层子结点为例来说明极大极小值的过程。对第3层子结点的某一棋局n,求出其估计值h(n),假设有一博弈树已形成，如图1所示[2],h(n)的值由各结点旁的数值给出。根据极小极大化分析法，先计算第3层子结点h(n)值,然后第2层子结点的估计值取他的各后继子结点的极小值，根结点的估计值取他的各子结点的极大值。这个取得最大估计值的子结点即为从S出发的计算机方的最佳落子方案。棋「上某一行、某一列或某一对角线为一
8、路，这里使用的棋盘为19行19列，因此，行和列方向上共有19+19=38路；从左下到右上方向的对角线有37路，同样，从左上到右下方向的对角线也有37路。但对于五子棋来说必须在一条直线上有连续五个棋子才能赢。因此，在对角线上就可以减少8路。所以，整个
