人工智能-五子棋算法研究

1五子棋算法研究摘要：人工智能是一门正在迅速发展的新兴的综合性很强的边缘科学。博弈是人工智能的主要研究领域之一，他涉及人工智能中的推理技术、搜索方法和决策规划。本文将这些技术用于五子棋中。设计了一个智能五子棋系统，实现人和计算机两方进行博弈。关键词：五子棋，人工智能，搜索GobangalgorithmtoresearchCAIJieInformationandComputationalScience,Grade2003DirectedbyWANGJian(AssociateProfessor)Abstract:Artificialintelligenceisanewly-developedandhighlycomprehensivefrontierscienceofrapiddevelopment.Gamblingandchessisoneofthemajorartificialintelligenceresearchareas.Itinvolvesreasoning，decision—makingandplanning.Thesetechniquesareappliedtothegobang.Anintelligentgobangsystemisdesignedandrealizedinthegamebetweenhumanandcomputer.Keywords:Gobang,Artificialintelligence,Search1绪论在人类文明发展的初期，人们便开始进行棋类博弈的游戏了。在人工智能领域内，博弈是很重要的一个研究分支，很多实际问题可以在博弈的研究中得到解决，并且使计算机智能更加靠近人类智能。电脑博弈是人工智能研究的一个方向，到了近50年前，随着电子计算机的诞生，科学家们开始通过电脑模拟人的智能逐步向人类智能发起挑战，香农(1950)与图灵(1953)提出了对棋类博弈程序的描述，随着电脑硬件和软件的高速发展，从1980开始，电脑博弈便开始逐渐大规模地向人的智能发起了挑战，到了1997年，IBM超2级电脑DeeperBlue击败了当时国际象棋世界冠军卡斯帕罗夫，成为了人工智能挑战人类智能发展的一个重要旅程碑。1.1电脑五子棋简介五子棋是起源于中国古代的传统黑白棋种之一。现代五子棋日文称之为“连珠”，英译为“Ren-ju”，英文称之为“Gobang”或“FIR”(FiveinaRow的缩写)，亦有“连五子”、“五子连”、“串珠”、“五目”、“五目碰”、“五格”等多种称谓。五子棋不仅能增强思维能力，提高智力，而且变化多端，非常富有趣味性5和消遣性，因此为人民群众所喜闻乐见。本文在研究博弈机器人系统过程中，对五子棋博弈算法进行了一些有效的研究，设计和实现一个人机对弈的五子棋程序。五子棋属于黑白棋的一种，它的博弈树复杂度为1070，状态空间复杂度为10105。因此盘面预测的计算量是非常大的，比如对于五子棋的中盘走法中，如果要预测四步的局面数的话可以达到一百万。1.2设计思路总介绍本文是对五子棋算法的设计原理和实现方法进行探讨和研究，主要包括数据结构、搜索算法和优劣评价函数组成，主要的特点包括快速的数据结构设计实现、以及高效率的搜索算法和尽可能的模拟人类的智能。1.3本文架构第一章将会阐述计算机博弈发展以及对电脑五子棋的介绍、电脑五子棋的状态空间复杂度以及文章架构。第二章首先描述了电脑象棋表示的一些基本数据结构。第三章将重点讲述博弈树的搜索方法，包括博弈树构建、各算法介绍、以及五子棋规则的实现，最后对整体搜索框架进行总结。最后，第四章是全文的总结及展望。2数据结构2.1棋局的表示我们知道五子棋的走法中有优先和禁手，如连四肯定是没有三四优先，而如果是黑方出现三三（包括“四、三、三”）、四四（包括“四、四、三”），而黑方只能以四三取胜，如果黑方走出禁手则是输；五连与禁手同时形成，先五为胜，等等的规矩。但是电脑毕竟不是人类，可以类人但是却不可以自己思考，那么就需要给电脑一个它可以明白的评判标准。首先介绍一个五子棋中的常用术语：3阳线：棋盘上可见的横纵直线。阴线：棋盘上无实线连接的隐形斜线。活3：由于一方走一着在无子交叉点上形成一个“活三”的局面，也就是在放一子就可行成4连了。活4：在棋盘某一条阳线或阴线上有同色4子不间隔地紧紧相连，且在此4子两端延长线上各有一个无子的交叉点与此4子紧密相连。冲四：除活四外的，再下一着棋便可形成五连，并且存在五连的可能性的局面。由于篇幅有限不能将所有的规则讲完，只是提出了对讲算法有用的几点加以叙述。如何让电脑知道该落子在哪一点呢，在这方面。电脑要做得和人一样，判断棋盘上每一点的重要度。比如冲四比冲强，冲三比造二强，遇到四三如果是对方的，堵死，如果是自己的，优先落子。遇到双三，如果是黑棋，黑方输，如果是白棋，优先等级仅次于四三。我们看到电脑在运算的时候，同种棋型在敌我双方的优先等级并不相同，由于禁手的缘故黑棋和白棋的处理也不相同。同样是四三，如果是玩家的，则电脑不会冲自己的，而是先堵玩家的。禁手的处理比较复杂，我们稍候讨论。下面，我列出基本的棋型优先顺序：造一个二……造四个二冲三……冲两个二和一个三冲双三冲四冲四三。之所以这么设置是由于五子棋的下法所致，只要构成5颗一线就赢了，所以说一条线上构成的越多那么就有优势，当然就是棋数越多，分越多。那么为了让电脑明确的知道是不是应该落子，就给它一个标准：分值。用程序语言表示：enumValue{FAILED=-99999，SKIP=20，LENG=10，TWO=100，THREE=1000，IF0UR=10000，FOUR=50000，SF0UR=70000，WIN=100000}；如果某一点导致失败，则分值为FAILED，由于它足够小，所以无论任何棋型与它的组合都小于0，SKIP之所以给它20分，是为了避免电脑出现无棋可下的情况，LENG是有可能发生长连的点，这有可能导致禁手，TWO、THREE、FOUR、WIN观名知意，TFOUR和SFOUR分别是弱四和强四。强四的点比普通的冲四重要的多，比如一个活四，意味着即将判出胜负。弱四是为了提供更大的灵活。也许有某种冲四并不一定比冲三重要，我在这里并没有使用，以后可以扩充。3涉及算法3.1五子棋搜索树种的极大极小搜索在五子棋乃至所有博弈类游戏的研究中[1-4]，最理想的方法是让电脑不论在对手走那种4棋路的时候都可以根据对手的走法来预测下一步，以至于使电脑立于不败之地，但是五子棋博弈树的复杂度为1070，状态空间的复杂度为10105，因此即使电脑的运算速度已经很快了，又有强有力的启发式搜索技术，但是要完成如此复杂的搜索也是不可取的。这种情况下搜索深度可根据实际情况进行调整，从局部搜索树中选取一步最好的走步，等对方走步后再寻找下一步好棋，通过结果来判断以后的走法。我们可以通过极大极小搜索方法来实现这种搜索策略。为了使谈论更有条理性[5]，将博弈的双方分别命名为MAX和MIN。而搜索的任务是为MAX找最佳的移动。假设MAX先移动(此时暂时不考虑五子棋的禁手等规则)，然后2个博弈者轮流移动。因此，深度为偶数的节点，对应于MAX下一步移动的位置，称为MAX节点；深度为奇数的节点对应于MIN下一步移动的位置，称为MIN节点(博弈树的顶节点深度为0)。k层包括深度为2k和2k+1的节点。通常用层数表示博弈树的搜索深度。他可以表示出向前预测的MAX和MIN交替运动的回合数。对于复杂的博弈，博弈者必须认识到由于博弈树的复杂程度所以搜索到终点是不可能的(除了在博弈快结束时)。所以，常采用在有限范围搜索方法，这里使用启发式搜索。在启发式搜索的过程中，关键的一步是如何确定下一个要考察的节点，在确定节点时只要能充分利用与问题有关的信息，估计出节点的重要性，就能在搜索时选择重要性较高的节点，以利于博弈者以较快的速度求出最佳的棋步。在这里我采用静态评估函数[6-13]，用评估函数h(i)衡量每一个叶节点位置的“值”。一个最佳首步可以由一个最小最大化过程产生。假设轮到MAX从搜索树的叶节点中选取，他肯定选择拥有最大值的节点。因此，MIN叶节点的一个MAX节点双亲的倒推值就等于叶节点的静态评估值中的最大值。另一方面，MIN从叶节点中选取时，必然选取最小的节点(即最负的值)。既然如此，MAX叶节点的MIN双亲节点被分配一个倒推值，他等于叶节点静态评估值的最小值。在所有叶节点的父节点被赋予倒推值后，开始倒推另一层，假定MAX将选择有最大倒推值的MIN的后继节点，而MIN会选择有最小倒推值的MAX后继节点。继续逐层对节点评估，直到最后开始节点的后继者被赋予倒推值。MAX将选择有最大倒推值的节点作为他的首步。整个过程的有效性基于这样的假设。用整个棋盘估值的函数h(n)为静态估值函数。设想当前棋局S为轮到计算机方下棋(用方框表示)，任选一空点作为计算机方的下棋位置(可有若干种选择)，接着考虑在此情况下游戏者一方下棋的棋局(用圆圈表示)；从某一个圆圈棋局出发，任选一空点作为游戏者一方的落子处(又有若干种选择)。再次形成计算机方下棋的方框棋局；依此类推，这样可形成一棵以S为根结5点的博弈树，该树以圆圈棋局为第2层子结点，以方框棋局为第3层子结点等等。如果继续向前搜索，可形成多层子结点，现在以向前搜索3层子结点为例来说明极大极小值的过程。对第3层子结点的某一棋局n，求出其估计值h(n)，假设有一博弈树已形成，如图1所示[2]，h(n)的值由各结点旁的数值给出。根据极小极大化分析法，先计算第3层子结点h(n)值，然后第2层子结点的估计值取他的各后继子结点的极小值，根结点的估计值取他的各子结点的极大值。这个取得最大估计值的子结点即为从S出发的计算机方的最佳落子方案。棋盘上某一行、某一列或某一对角线为一路，这里使用的棋盘为19行19列，因此，行和列方向上共有19+19=38路；从左下到右上方向的对角线有37路，同样，从左上到右下方向的对角线也有37路。但对于五子棋来说必须在一条直线上有连续五个棋子才能赢。因此，在对角线上就可以减少8路。所以，整个棋盘路的总数为：38+(37-8)+(37-8)=96路。对某一棋局n[14-15]，第i路得分：h(i)=ht(i)-hm(i)[1]。其中：ht(i)为计算机方在第i路估计值得分，hm(i)为玩家一方在第i路得分。对的得分规则作如下说明。规则中+代表一空点；O代表对方棋子；*代表有计算机方棋子；++表示连续2点为空点；+++*++表示连续3个空点接一个计算机方棋子，再接两空点。为了使电脑可以对棋局进行判断，那就需要告诉电脑什么时候的局势好过什么时候的局势，我们可以通过给不同局势时不同分值的办法来让电脑明白。我给出的局势评估如下：+++*++：ht(i)=10;++**++：ht(i)=100;+***++：ht(i)=1000;根节点S30-40-30最佳第二层节点第三层节点3040603060-4050-308050图1：博弈树6O****+：ht(i)=10000;+****+：ht(i)=50000;*****的时候落子方都已经是胜利了：ht(i)=100000（之所以给分200是为了以后其他棋局的时候好判断）。之所以要给出如此大的分值差距，主要是考虑以后的全局判断的时候不会因为分数的累加使得电脑判断错误。而电脑在判断双方的分值的时候，就是在落子时对自己的落子点涉及分值和对方的分值进行对比来进行之后落子的判断。3.2α-β剪枝我们不用把每个节点都搜索一遍也可获得和极大极小搜索同样结果的走步，不搜索分支节点而舍弃该分支的过程叫剪枝。常用的剪枝方法是α-β剪枝算法。在极大极小搜索的过程中，存在着一定程度的数据冗余。如下图2所示左半部的一棵极大极小树的片断，节点下面为该节点的值，设A为极大值节点，节点B的值为18，节点D的值为16，由此可以判断节点C的值将小于等于16(取极小值)；而节点A的值为节点Max(B，C)，是18，也就是说不再需要估节点C的其他子节点如E、F的值就可以得出父