五子棋人工智能的分析与实现

五子棋人工智能的分析与实现摘要：机器博弈是人工智能的一个重要研究分支，本文通过设计一个五子棋智能博奕程序，采用传统的博弈树算法，利用剪枝和极大极小树搜索最佳位置，从而实现人机智能博弈。并对现有算法存在的问题进行探究改进，最后给出程序实例，结果表明效果比较理想。关键词：五子棋；人工智能；博弈；1主要传统算法1.1博弈树传统的算法是采用博弈树法来设计程序。以甲乙两人下棋为例，甲有很多种落子方式，乙也有多种应对走法，如果把所有的走法列出来，自然就构成了一棵树，即为搜索树，也称博弈树。树的根结点为先手的第一步走法，下面的走法构成了树的子结点，直至棋局结束。显然，如果棋盘足够大，子结点数会以几何级数上升，而我们的任务是从这些子结点中寻找一个对己方最有利的结点，从而得到棋局的最佳走法。这必然是一个指数复杂度的过程，费时低效，无法搜索到最终结果（除了棋局结束），通常只能达到一个有限的深度，在有限的范围内来判断走法的好坏，得到一个局部最优解。[2-3]因此，有必要做一些调整改进，以提高算法的效率和质量。1.2极大极小算法极大极小搜索算法就是在博弈树在寻找最优解的一个过程，这主要是一个对各个子结点进行比较取舍的过程，定义一个估值函数F(n)来分别计算各个终结点的分值，通过双方的分值来对棋局形势进行分析判断。还是以甲乙两人下棋为例，甲为max，乙为min。当甲走棋时，自然在博弈树中寻找最大点的走法，轮到乙时，则寻找最小点的走法，如此反复，这就是一个极大极小搜索过程，以此来寻找对机器的最佳走法。其中估值函数通常是为了评价棋型的状态，根据实现定义的一个棋局估值表，对双方的棋局形态进行计算，根据得到的估值来判断应该采用的走法。棋局估值表是根据当前的棋局形势，定义一个分值来反映其优势程度，来对整个棋局形势进行评价。本程序采用的估值表如下：状态眠二假活三眠三活二冲四假活三活三活四连五分值245812154090200一般来说，我们采用的是15×15的棋盘，棋盘的每一条线称为一路，包括行、列和斜线，4个方向，其中行列有30路，两条对角线共有58路，整个棋盘的路数为88路。考虑到五子棋必须要五子相连才可以获胜，这样对于斜线，可以减少8路，即有效的棋盘路数为72路。对于每一路来说，第i路的估分为E(i)=Ec(i)-Ep(i)，其中Ec(i)为计算机的i路估分，Ep(i)为玩家的i路估分。棋局整个形势的估值情况通过对各路估分的累加进行判断，即估值函数：1.3αβ剪枝αβ剪枝算法简单来说，就是在搜索过程中减少一定的冗余现象，如已经找到极大值，执行该走法就可以获胜，则无须再往下进行搜索比较，此过程即为剪枝。对于极大的MAX结点，称为α剪枝；反之为β剪枝。具体规则可以简单描述如下：α剪枝：对于极大值层结点的α值如果不小于它的任一祖先极小值层结点的β值，即α(后续层)≥β(祖先层)，则可中止该极大值层中这个MAX节点以下的搜索过程，这个MAX节点最终的倒推值就确定为这个α值。β剪枝：对于极小值结点层的β值如果不大于它任一祖先极大值层结点的α值，即α(祖先层)≥β(后续层)，则可中止对该极小值层中这个MIN节点以下结点的搜索，这个MIN节点最终的倒推值就确定为这个β值。[2]αβ剪枝可以进一步进行改进，在走棋过程中，在中心先下的一方往往有一定的优势，双方的搏斗纠缠都是在争夺最佳位置，可以考虑从中心往外螺旋进行扩展搜索；另外由于防守的需要，落子的位置通常也是在彼此下子的附近，因此可以优先考虑在这些位置进行搜索，也就是对落子位置进行排序预先搜索，更进一步的缩减冗余现象，进而提高搜索效率和行棋质量。[5]2改进传统算法传统算法最大的一个缺点还是在于它的指数复杂度问题，虽然通过剪枝、优化搜索位置等方法减少了冗余，提高了一定的搜索效率，但都无法解决搜索深度增加带来的呈几何级数增加的巨大计算量问题。[4]在进一步的实验中发现，搜索超过7层以后，程序响应速度明显变慢，到9层会出现1-2s的间隔期。因此，通过研究五子棋的规律和特点，结合实际经验，可以对程序作一些预定的调整措施，从而提高算法的执行效率和对弈能力。2.1缩减搜索范围对于15x15的棋盘，每一种走法都有上百种可能，如果对每种走法都进行计算估值，则无疑大大增加了计算量，降低了算法的效率和质量。根据规则和实际经验，我们知道只要考虑以棋子为中心的邻近区域皆可，比如不大于4的距离通常为该子的有效范围，同理我们还可以在对方的落子范围进行判断估值。这样可以缩减搜索范围，同时提高算法的效率和走法的实用性。2.2置换表搜索前面我们讨论了利用αβ剪枝来处理冗余结点，对于已经搜索过的结点，我们可以通过设置一张Hash表记录该结点，这样在后续的搜索过程中，可以对这些点的记录进行查询如先前有过记录则直接调用，免于重新搜索，从而避免出现重复操作，加快搜索速度。该方法通常称为置换表（TranspositionTable）。2.3建立棋谱库该方法广泛应用在象棋程序设计中，五子棋远比象棋简单，该方法也更为有效实用。通过在数据库中存储一些开局“定式”手法和经典棋局，开局阶段，程序使用开局库，一旦发现相同棋局，则直接调用该走法，无须再次搜索，同时建立数据库来存储失败案例不断进行调整对策。该方法可以极大的提高程序的智能化，只是增加了额外的系统开销。另外对于棋谱的匹配和存储也是关键问题。[4]但是由于时间和选择语言的限制，建立棋谱库没有在程序中得到实现。2.4合理设置搜索深度理论上来说，为了寻找最优解，最好是对完整博弈树进行完全搜索，但实际中是不可行的，无论是从时间上还是从系统资源上。在后面实际程序设计中，默认为5层，当然也可以根据不同机器配置加以调整，以达到最大效率。3实例分析在Windows7操作系统下，利用上述算法思想，采用ActionScript编程实现一个实现人机对战的五子棋程序。通过实验分析比较，程序的智能化和质量效果较为理想。当计算机执黑时，基本上每次都能获胜，且步骤、时间较短；当玩家执黑先行，计算机获胜比率也较高，具有很好的智能性。4结束语本文介绍了一个智能五子棋的主要算法思想和实现技术，利用剪枝和极大极小树搜索博弈树，作出了一些改进措施，寻求最佳下棋位置，从而提高了智能博弈的质量。进行优化以后，五子棋程序的智能水平和搜索效率有了明显的提升。本文所讨论的算法思想和设计过程也为其他棋类游戏(如象棋和围棋等)提供了一定的参考价值。此外，五子棋的国际规则较为复杂，加入了禁手判负、三手交换等规则限制黑手先行优势，可以在进一步的工作中考虑实现。参考文献：[1]蔡自兴.人工智能及其应用[M].北京：清华大学出版社,1999:2-12.[2]朱全民,陈松乔.五子棋算法的研究与思考[J].计算技术与自动化,2006(02):75-78.[3]董红安,蒋秀英.智能五子棋博弈程序的核心算法[J].枣庄学院学报,2005(2):61-65.[4]蒋加伏,陈蔼祥,唐贤英.基于知识推理的博弈树搜索算法[J].计算机工程与应用,2004(1):74-76.[5]张海峰,白振兴,张登福.五子棋中的博弈智能设计[J].现代电子技术,2004,27(7):25-27.附录：1.程序截图游戏运行中玩家先手胜利玩家先手失败电脑先手胜利电脑先手失败2.主要代码packageClasses{importflash.display.*;importflash.events.*;importflash.geom.*;importflash.text.TextField;/**五子棋*/publicclassGobangDocextendsMovieClip{//棋盘格宽度privateconstgridsize:Number=20;//棋盘格数privateconstgridnum:Number=15;//没有棋子为0,黑子为1，白子为2privateconstNOTHING:uint=0;privateconstBLACK:uint=1;privateconstWHITE:uint=2;//现在轮到哪一方出子privatevarcrtSide:uint=WHITE;//玩家的棋子privatevarmySide:uint=WHITE;//对手的棋子privatevarotherSide:uint;//是否可以进行游戏privatevarcanPlay:Boolean=false;//记录盘面状态的数组privatevaraGridState:Array=[];//记录盘面上的棋子的数组privatevaraChessmen:Array=[];//棋子的几种状态publicconstSTWO:int=2;//眠二publicconstFTWO:int=4;//假活二publicconstSTHREE:int=5;//眠三publicconstTWO:int=8;//活二publicconstSFOUR:int=12;//冲四publicconstFTHREE:int=15;//假活三publicconstTHREE:int=40;//活三publicconstFOUR:int=90;//活四publicconstFIVE:int=200;//五连//玩家的棋形表privatevaraPlayer:Array=[];//对手的棋形表privatevaraOpponent:Array=[];//八个方向，从左上角开始顺时针privatevardir:Array=[[-1,-1],[0,-1],[1,-1],[1,0],[1,1],[0,1],[-1,1],[-1,0]];publicfunctionGobangDoc(){mcGameState.visible=false;otherSide=WHITE+BLACK-mySide;//初始化盘面数组for(vari:uint=0;igridnum;i++){aGridState[i]=[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0];}mcChessboard.addEventListener(MouseEvent.MOUSE_DOWN,AddMyChessman);btnStart.addEventListener(MouseEvent.CLICK,btnStart_Handler);btnReplay.addEventListener(MouseEvent.CLICK,btnReplay_Handler);mcSelectChessman.addEventListener(MouseEvent.MOUSE_DOWN,selectChessman);}//初始化棋盘privatefunctioninit():void{btnStart.visible=false;for(vari:int=0;iaChessmen.length;i++){mcChessboard.removeChild(aChessmen[i]);}for(varj:uint=0;jgridnum;j++){aGridState[j]=[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0];}aChessmen=[];canPlay=true;}//玩家添加棋子publicfunctionAddMyChessman(e:MouseEvent):void{//不能添加棋子的状态（棋局未开始、对方走、棋子没有落在棋盘里）if(!canPlay||crtSide!=mySide||e.target.name!=mcChessboard)return;if(mySide==crtSide){//计算鼠标落在哪一格varcrtx:uint=Math.floor(e.localX/gridsize);varcrty:uint=Math.floor(e.localY/gridsize);//如果这一格已经有棋子就返回if(aGridState[crty][crtx])return;//创建棋子varchessman:Chessman;if(mySid