五子棋AI的思路
隔了一年才把AI思路给写了。。。
需求分析与设计方案：http://www.cnblogs.com/songdechiu/p/4951634.html
如需整个工程，移步http://download.csdn.net/detail/sdzuiaidanpianji/9452789
如没有积分，可在百度网盘下载：
链接:https://pan.baidu.com/s/1UXzhEDWXfsb6EbFOzRVuqg提取码:ezm6
注：全文，都默认以黑方为己方。
一、五子棋基本棋型参考资料：http://game.onegreen.net/wzq/HTML/142336.html
最常见的基本棋型大体有以下几种：连五，活四，冲四，活三，眠三，活二，眠二。
①连五：顾名思义，五颗同色棋子连在一起，不需要多讲。图2-1
②活四：有两个连五点（即有两个点可以形成五），图中白点即为连五点。稍微思考一下就能发现活四出现的时候，如果对方单纯过来防守的话，是已经无法阻止自己连五了。图2-2
③冲四：有一个连五点，如下面三图，均为冲四棋型。图中白点为连五点。相对比活四来说，冲四的威胁性就小了很多，因为这个时候，对方只要跟着防守在那个唯一的连五点上，冲四就没法形成连五。图2-3 图2-4 图2-5
④活三：可以形成活四的三，如下图，代表两种最基本的活三棋型。图中白点为活四点。活三棋型是我们进攻中最常见的一种，因为活三之后，如果对方不以理会，将可以下一手将活三变成活四，而我们知道活四是已经无法单纯防守住了。所以，当我们面对活三的时候，需要非常谨慎对待。在自己没有更好的进攻手段的情况下，需要对其进行防守，以防止其形成可怕的活四棋型。图2-6 图2-7
其中图2-7中间跳着一格的活三，也可以叫做跳活三。
⑤眠三：只能够形成冲四的三，如下各图，分别代表最基础的六种眠三形状。图中白点代表冲四点。眠三的棋型与活三的棋型相比，危险系数下降不少，因为眠三棋型即使不去防守，下一手它也只能形成冲四，而对于单纯的冲四棋型，我们知道，是可以防守住的。图2-8 图2-9 图2-10
2-11 图2-12 图2-13
如上所示，眠三的形状是很丰富的。对于初学者，在下棋过程中，很容易忽略不常见的眠三形状，例如图2-13所示的眠三。
有新手学了活三眠三后，会提出疑问，说活三也可以形成冲四啊，那岂不是也可以叫眠三？会提出这个问题，说明对眠三定义看得不够仔细：眠三的的定义是，只能够形成冲四的三。而活三可以形成眠三，但也能够形成活四。
此外，在五子棋中，活四棋型比冲四棋型具有更大的优势，所以，我们在既能够形成活四又能够形成冲四时，会选择形成活四。
温馨提示：学会判断一个三到底是活三还是眠三是非常重要的。所以，需要好好体会。后边禁手判断的时候也会有所应用。
⑥活二：能够形成活三的二，如下图，是三种基本的活二棋型。图中白点为活三点。活二棋型看起来似乎很无害，因为他下一手棋才能形成活三，等形成活三，我们再防守也不迟。但其实活二棋型是非常重要的，尤其是在开局阶段，我们形成较多的活二棋型的话，当我们将活二变成活三时，才能够令自己的活三绵绵不绝微风里，让对手防不胜防。图2-14 图2-15 图2-16
⑦眠二：能够形成眠三的二。图中四个为最基本的眠二棋型，细心且喜欢思考的同学会根据眠三介绍中的图2-13找到与下列四个基本眠二棋型都不一样的眠二。图中白点为眠三点。图2-17 图2-18 图2-19 图2-20
二、打分机制1、打分思路（1）先对整个棋盘形势进行打分，存在两个矩阵（二维数组）上
（2）一个为我方的形势分数，一个为敌方的形势分数
（3）找出我方形势分数的最大值mymaxscore及其对应的位置，找出敌方形势的最大值hismaxscore及其对应的位置
（4）判断是进攻还是防守：
如果mymaxscore>=hismaxscore，则进攻，下我方形势最大值mymaxscore对应的位置；如果有多个mymaxscore相等，则下这几个对应位置上hismaxscore最大的位置。
否则，防守，下敌方形势最大值hismaxscore对应的位置。如果有多个hismaxscore相等，则下这几个对应位置上mymaxscore最大的位置。
2、打分方法（1）在棋盘空位置上预添加要判断放的棋子
（2）取出以空位置为中心的4个方向（上，下，左，右），每个方向以该位置为中心两边各取4个格子信息。如下所示：
注：中心位置都是预放置，当前判断的时候位置还是空的
（3）四个方向都判断其棋型，是否连五，活四，冲四，活三，眠三，活二，眠二等中的一种
（4）最后综合四个方向的棋型，对该位置进行打分。
3、打分规定注：机器方即为本方，人方即为敌方
综合四个方向后：
判断是否能成5,如果是机器方的话给予100000分，如果是人方的话给予100000分；
判断是否能成活4或者是双死4或者是死4活3，如果是机器方的话给予10000分，如果是人方的话给予10000分；
判断是否已成双活3，如果是机器方的话给予5000分，如果是人方的话给予5000分；
判断是否成死3活3（高级），如果是机器方的话给予1000分，如果是人方的话给予1000分；
判断是否能成死4，如果是机器方的话给予500分，如果是人方的话给予500分；
判断是否能成低级死4，如果是机器方的话给予400分，如果是人方的话给予400分；
判断是否能成单活3，如果是机器方的话给予100分，如果是人方的话给予100分；
判断是否能成跳活3，如果是机器方的话给予90分，如果是人方的话给予90分；
判断是否能成双活2，如果是机器方的话给予50分，如果是人方的话给予50分；
判断是否能成活2，如果是机器方的话给予10分，如果是人方的话给予10分；
判断是否能成低级活2，如果是机器方的话给予9分，如果是人方的话给予9分；
判断是否能成死3，如果是机器方的话给予5分，如果是人方的话给予5分；
判断是否能成死2，如果是机器方的话给予2分，如果是人方的话给予2分。
判断是否其他情况（nothing），如果是机器方的话给予1分，如果是人方的话给予1分。
有棋子，则直接0分。
4、棋型判断方法（1）在空位置上添加要判断色的棋子
（2）取出以空位置为中心的，要判断单个方向（上，下，左，右中的一种）上的，两边各4个位置信息，形成
（3）先找出与中心点相连而成的连续子有多少个
（4）再进行下一步判断
注：以下说明都以黑方为例子
中心点相连而成的连续子有5个：不管哪种情况，都可以直接判断为成5：中心点相连而成的连续子有4个：两边均空，活41、2均非空，则nothing1、2只有一个为空，则死4中心点相连而成的连续子有3个：2,3均空时：1,4均为白子，则为死31,4只要有一个空，则为活31,4只要有一个黑，则为死4
以此类推，根据第一部分中的五子棋棋型去判断棋型类型。
具体可直接查看源码部分。
单个方向的棋型判断：
if(count>=5)//中心线5连returnWIN5;//5连珠if(count==4)//中心线4连{if(colorleft==NOTHINGFLAG&&colorright==NOTHINGFLAG)//两边断开位置均空returnALIVE4;//活四elseif(colorleft==hiscolor&&colorright==hiscolor)//两边断开位置均非空returnNOTHREAT;//没有威胁elseif(colorleft==NOTHINGFLAG||colorright==NOTHINGFLAG)//两边断开位置只有一个空returnDIE4;//死四}if(count==3){//中心线3连intcolorleft1=chess[left-1];intcolorright1=chess[right+1];if(colorleft==NOTHINGFLAG&&colorright==NOTHINGFLAG)//两边断开位置均空{if(colorleft1==hiscolor&&colorright1==hiscolor)//均为对手棋子returnDIE3;elseif(colorleft1==mycolor||colorright1==mycolor)//只要一个为自己的棋子returnLOWDIE4;elseif(colorleft1==NOTHINGFLAG||colorright1==NOTHINGFLAG)//只要有一个空returnALIVE3;}elseif(colorleft==hiscolor&&colorright==hiscolor)//两边断开位置均非空{returnNOTHREAT;//没有威胁}elseif(colorleft==NOTHINGFLAG||colorright==NOTHINGFLAG)//两边断开位置只有一个空{if(colorleft==hiscolor){//左边被对方堵住if(colorright1==hiscolor)//右边也被对方堵住returnNOTHREAT;if(colorright1==NOTHINGFLAG)//右边均空returnDIE3;if(colorright1==mycolor)returnLOWDIE4;}if(colorright==hiscolor){//右边被对方堵住if(colorleft1==hiscolor)//左边也被对方堵住returnNOTHREAT;if(colorleft1==NOTHINGFLAG)//左边均空returnDIE3;if(colorleft1==mycolor)//左边还有自己的棋子returnLOWDIE4;}}}if(count==2){//中心线2连intcolorleft1=chess[left-1];intcolorright1=chess[right+1];intcolorleft2=chess[left-2];intcolorright2=chess[right+2];if(colorleft==NOTHINGFLAG&&colorright==NOTHINGFLAG)//两边断开位置均空{if((colorright1==NOTHINGFLAG&&colorright2==mycolor)||(colorleft1==NOTHINGFLAG&&colorleft2==mycolor))returnDIE3;//死3elseif(colorleft1==NOTHINGFLAG&&colorright1==NOTHINGFLAG)returnALIVE2;//活2if((colorright1==mycolor&&colorright2==hiscolor)||(colorleft1==mycolor&&colorleft2==hiscolor))returnDIE3;//死3if((colorright1==mycolor&&colorright2==mycolor)||(colorleft1==mycolor&&colorleft2==mycolor))returnLOWDIE4;//死4if((colorright1==mycolor&&colorright2==NOTHINGFLAG)||(colorleft1==mycolor&&colorleft2==NOTHINGFLAG))returnTIAO3;//跳活3//其他情况在下边返回NOTHREAT}elseif(colorleft==hiscolor&&colorright==hiscolor)//两边断开位置均非空{returnNOTHREAT;}elseif(colorleft==NOTHINGFLAG||colorright==NOTHINGFLAG)//两边断开位置只有一个空{if(colorleft==hiscolor){//左边被对方堵住if(colorright1==hiscolor||colorright2==hiscolor){//只要有对方的一个棋子returnNOTHREAT;//没有威胁}elseif(colorright1==NOTHINGFLAG&&colorright2==NOTHINGFLAG){//均空returnDIE2;//死2}elseif(colorright1==mycolor&&colorright2==mycolor){//均为自己的棋子returnLOWDIE4;//死4}elseif(colorright1==mycolor||colorright2==mycolor){//只有一个自己的棋子returnDIE3;//死3}}if(colorright==hiscolor){//右边被对方堵住if(colorleft1==hiscolor||colorleft2==hiscolor){//只要有对方的一个棋子returnNOTHREAT;//没有威胁}elseif(colorleft1==NOTHINGFLAG&&colorleft2==NOTHINGFLAG){//均空returnDIE2;//死2}elseif(colorleft1==mycolor&&colorleft2==mycolor){//均为自己的棋子returnLOWDIE4;//死4}elseif(colorleft1==mycolor||colorleft2==mycolor){//只有一个自己的棋子returnDIE3;//死3}}}}if(count==1){//中心线1连intcolorleft1=chess[left-1];intcolorright1=chess[right+1];intcolorleft2=chess[left-2];intcolorright2=chess[right+2];intcolorleft3=chess[left-3];intcolorright3=chess[right+3];if(colorleft==NOTHINGFLAG&&colorleft1==mycolor&&colorleft2==mycolor&&colorleft3==mycolor)returnLOWDIE4;if(colorright==NOTHINGFLAG&&colorright1==mycolor&&colorright2==mycolor&&colorright3==mycolor)returnLOWDIE4;if(colorleft==NOTHINGFLAG&&colorleft1==mycolor&&colorleft2==mycolor&&colorleft3==NOTHINGFLAG&&colorright==NOTHINGFLAG)returnTIAO3;if(colorright==NOTHINGFLAG&&colorright1==mycolor&&colorright2==mycolor&&colorright3==NOTHINGFLAG&&colorleft==NOTHINGFLAG)returnTIAO3;if(colorleft==NOTHINGFLAG&&colorleft1==mycolor&&colorleft2==mycolor&&colorleft3==hiscolor&&colorright==NOTHINGFLAG)returnDIE3;if(colorright==NOTHINGFLAG&&colorright1==mycolor&&colorright2==mycolor&&colorright3==hiscolor&&colorleft==NOTHINGFLAG)returnDIE3;if(colorleft==NOTHINGFLAG&&colorleft1==NOTHINGFLAG&&colorleft2==mycolor&&colorleft3==mycolor)returnDIE3;if(colorright==NOTHINGFLAG&&colorright1==NOTHINGFLAG&&colorright2==mycolor&&colorright3==mycolor)returnDIE3;if(colorleft==NOTHINGFLAG&&colorleft1==mycolor&&colorleft2==NOTHINGFLAG&&colorleft3==mycolor)returnDIE3;if(colorright==NOTHINGFLAG&&colorright1==mycolor&&colorright2==NOTHINGFLAG&&colorright3==mycolor)returnDIE3;if(colorleft==NOTHINGFLAG&&colorleft1==mycolor&&colorleft2==NOTHINGFLAG&&colorleft3==NOTHINGFLAG&&colorright==NOTHINGFLAG)returnLOWALIVE2;if(colorright==NOTHINGFLAG&&colorright1==mycolor&&colorright2==NOTHINGFLAG&&colorright3==NOTHINGFLAG&&colorleft==NOTHINGFLAG)returnLOWALIVE2;if(colorleft==NOTHINGFLAG&&colorleft1==NOTHINGFLAG&&colorleft2==mycolor&&colorleft3==NOTHINGFLAG&&colorright==NOTHINGFLAG)returnLOWALIVE2;if(colorright==NOTHINGFLAG&&colorright1==NOTHINGFLAG&&colorright2==mycolor&&colorright3==NOTHINGFLAG&&colorleft==NOTHINGFLAG)returnLOWALIVE2;//其余在下边返回没有威胁}returnNOTHREAT;//返回没有威胁
综合四个方向评分：
if(situation.win5>=1)returnLevelOne;//赢5if(situation.alive4>=1||die4>=2||(die4>=1&&alive3>=1))returnLeveltwo;//活4双死4死4活3if(alive3>=2)returnLevelthree;//双活3if(situation.die3>=1&&situation.alive3>=1)returnLevelfour;//死3高级活3if(situation.die4>=1)returnLevelfive;//高级死4if(situation.lowdie4>=1)returnLevelsix;//低级死4if(situation.alive3>=1)returnLevelseven;//单活3if(situation.tiao3>=1)returnLevelEight;//跳活3if(alive2>=2)returnLevelNight;//双活2if(situation.alive2>=1)returnLevelTen;//活2if(situation.lowalive2>=1)returnLevelEleven;//低级活2if(situation.die3>=1)returnLevelTwelve;//死3if(situation.die2>=1)returnLevelThirteen;//死2returnLevelFourteen;//没有威胁
五子棋AI算法的实现
五子棋五子棋五子棋是比较流行的棋类游戏了，玩法简单，基本上人人会玩，在此就不介绍游戏规则了。下面使用swift实现五子棋这个游戏，主要实现AI算法，包括极大值极小值算法，深度搜索算法，估值函数，AlphaBeta剪枝算法等等。
//横向五子连珠（除去四边线的五子连珠）staticfuncisFiveChess(_point:SWSPoint,_chessArray:[[FlagType]])->Bool{lettype=chessArray[point.x][point.y]letpointLeft=SWSPoint()letpointRight=SWSPoint()letpointTop=SWSPoint()letpointBottom=SWSPoint()letpointLeft45=SWSPoint()letpointRight45=SWSPoint()letpointTop135=SWSPoint()letpointBottom135=SWSPoint()//东西方向vari=0whilepoint.x-i>=0&&chessArray[point.x-i][point.y]==type{pointLeft.x=point.x-ii+=1}i=0whilepoint.x+i=0&&chessArray[point.x][point.y-i]==type{pointTop.y=point.y-ii+=1}i=0whilepoint.y+i=0&&point.y+i=0&&point.y-i>=0&&chessArray[point.x-i][point.y-i]==type{pointTop135.x=point.x-ipointTop135.y=point.y-ii+=1}i=0whilepoint.x+ialpha){alpha=val;}}returnalpha;}实际在代码中的运用，代码比较复杂请结合项目理解。项目地址
staticfuncgetAIPoint(chessArray:inout[[FlagType]],role:FlagType,AIScore:inout[[Int]],humanScore:inout[[Int]],deep:Int)->(Int,Int,Int)?{letmaxScore=10*live_FiveletminScore=-1*maxScoreletcheckmateDeep=self.checkmateDeepvartotal=0,//总节点数steps=0,//总步数count=0,//每次思考的节点数ABcut=0//AB剪枝次数funchumMax(deep:Int)->(Int,Int,Int)?{letpoints=self.getFiveChessType(chessArray:chessArray,AIScore:&AIScore,humanScore:&humanScore)varbestPoint:[(Int,Int)]=[]varbest=minScorecount=0ABcut=0foriin0..11||p.y11{score=score/2}ifTJFTool.equal(a:Float(score),b:Float(best)){bestPoint.append((p.x,p.y))}ifTJFTool.greatThan(a:Float(score),b:Float(best)){best=scorebestPoint.removeAll()bestPoint.append((p.x,p.y))}chessArray[p.x][p.y]=.freeChessself.updateOneEffectScore(chessArray:chessArray,point:(p.x,p.y),AIScore:&AIScore,humanScore:&humanScore)}steps+=1total+=countifbestPoint.count>0{letnum=arc4random()%UInt32(bestPoint.count)return(bestPoint[Int(num)].0,bestPoint[Int(num)].1,best)}returnnil}funcaiMaxS(deep:Int,alpha:Int,beta:Int,role:FlagType)->Int{varscore=0varaiMax=0varhumMax=0varbest=minScoreforiin0..=2*live_Three{doubleThrees.insert((i,j),at:0)}elseifhumScore>=2*live_Three{doubleThrees.append((i,j))}elseifaiScore>=live_Three{threes.insert((i,j),at:0)}elseifhumScore>=live_Three{threes.append((i,j))}elseifaiScore>=live_Two{twos.insert((i,j),at:0)}elseifhumScore>=live_Two{twos.append((i,j))}else{oters.append((i,j))}}}}iffives.count>0{return[fives[0]]}iffours.count>0{returnfours}ifsleepFours.count>0{return[sleepFours[0]]}ifdoubleThrees.count>0{returndoubleThrees+threes}letresult=threes+twos+otersvarrealy:[(Int,Int)]=[]ifresult.count>limitNum{realy+=result.prefix(limitNum)returnrealy}returnresult}五子棋是一种进攻优势的棋，依靠连续不断地活三或者冲四进攻，最后很容易会形成必杀棋，所以在进行深度搜索时，我们另开一种连续进攻的搜索，如果，电脑可以依靠连续进攻获得胜利，我们可以直接走这条路劲。这条路劲，其实也是极大值极小值搜索算法的一种，只不过是只考虑活三冲四这两种棋型，指数的底数较小，搜索的节点比较少，因此是效率很高的算法。代码如下：
//有限考虑ai成五staticfuncfindMaxScore(chessArray:[[FlagType]],role:FlagType,aiScore:[[Int]],humanScore:[[Int]],score:Int)->[(Int,Int,Int)]{varresult:[(Int,Int,Int)]=[]foriin0..=score{result.append((i,j,score1))}}}}}returnresult.sorted{(a,b)->Boolinreturnb.2>a.2}}//考虑活三，冲四staticfuncfindEnemyMaxScore(chessArray:[[FlagType]],role:FlagType,aiScore:[[Int]],humanScore:[[Int]],score:Int)->[(Int,Int,Int)]{varresult:[(Int,Int,Int)]=[]varfours:[(Int,Int,Int)]=[]varfives:[(Int,Int,Int)]=[]foriin0..=live_Four{fours.insert((i,j,-score1),at:0)continue}ifscore2>=live_Five{fives.append((i,j,score2))continue}ifscore2>=live_Four{fours.append((i,j,score2))continue}ifscore1>score||score2>score{result.append((i,j,score1))}}}}}iffives.count>0{return[fives[0]]}iffours.count>0{return[fours[0]]}returnresult.sorted{(a,b)->Boolinreturnabs(b.2)>abs(a.2)}}小结本次编写的AI还是比较强的，我胜利的机会很少，但还是存在赢的时候，因此AI算法还存在漏洞，主要表现在评分标准不准确和搜索深度不够问题上，如何优化评分标准和搜索算法，是实现AI无敌的关键工作。另外，在增加搜索深度的同时，遍历的节点指数增长，计算时间增长，可以结合哈希算法，保存每次的棋盘评分，一定程度上提高计算时间，这也只是治标不治本的做法。
最后代码具体实现地址代码中具体实现了两个棋类游戏（有时间会持续添加游戏种类），包括在线对战，人机对战（算法不错哦），蓝牙对战。代码编写不易，喜欢的请点赞，谢谢！
五子棋AI进阶：极大极小值搜索
前言上篇文章，介绍了一下五子棋AI的入门实现，学完之后能用，就是AI还太年轻，只能思考一步棋。
本文将介绍一种提高AI思考能力的算法：极大极小值算法。
Minimax算法又名极小化极大算法，是一种找出失败的最大可能性中的最小值的算法（即最小化对手的最大得益）。通常以递归形式来实现。Minimax算法常用于棋类等由两方较量的游戏和程序。该算法是一个零总和算法，即一方要在可选的选项中选择将其优势最大化的选择，另一方则选择令对手优势最小化的一个，其输赢的总和为0（有点像能量守恒，就像本身两个玩家都有1点，最后输家要将他的1点给赢家，但整体上还是总共有2点）。——百度百科
极大极小值搜索算法算法实现原理对于五子棋游戏来说，如果AI执黑子先下，那么第一步AI共有225种落子方式，AI落子到一个点后，表示AI回合结束，换到对手（白子）落子，这时对手共有224种落子方式。我们可以将AI和对手交替落子形成的所有情况穷举出来，这样就形成了一棵树，叫做博弈树。
但是，穷举出所有情况太不现实了，这颗博弈树最后一层节点数就有225!，这个数字是特别庞大的，数字10后边要加432个0！！！这程序运行起来，电脑还要不要了？
所以，我们只考虑2步棋或4步棋的情况。
如图所示，我只列举出了走4步棋所形成的部分情况。A0是起点，AI将在这个点中选择出最佳的落子点位。A0下面有两个分支（实际有225个分支，这里放不下，就只演示2个）A1和A2，这两个分支表示的就是AI第一步落子的两种情况。
A1如果落子到(0,0)，则当前局面就如下图所示
A2如果落子到(0,1)，则当前局面就如下图所示
AI落子完后，就轮到对方落子了。在A1分支中，对方有B1和B2两种落子情况（实际有224种）
B1情况如图所示
B2情况如图所示
一直到第4步落子完时，B5的局面就会像下图这样
要知道，这颗博弈树是以AI的角度建立的，AI为了赢，它需要从A1和A2分支中，选择一个对自己最有利的落子点，而A1和A2分支的好坏需要它们下面的B1、B2和B3、B4决定，所以说，下层分支的局面会影响上层分支的选择。
要确定A1和A2分支哪个好，我们必须从这个分支的最深层看起。
B5~B12节点的局面是由对方造成的，我们就假设对方很聪明，他一定能选择一个最有利于他自己的落子点。怎么知道哪个落子点好？还是和之前一样，用评估函数评估一下，分高的就好呗，但有一点不同的是，之前评估的是一个点，现在需要评估一个局面，怎么评估本文后面会提到。
假设B5~B12中各个节点的得分如下图最底部所示
则A3节点得分为0，A4节点得分为1，A5节点得分为3，A6节点得分为2。这就很奇怪了，不是说让选得分最大的吗？这怎么都选的最小的得分？？？
这其实还是要从评估函数说起，因为我们现在的评估函数都是从AI角度出发的，评估的得分越高，只会对AI有利，对对方来说是不利的。所以，当是对方的分支的时候，我们要选得分最低的节点，因为AI要站在对方的角度去做选择，换位思考。这里如果还是没有搞懂的话，我们可以这么理解：
假如张三遇到了抢劫犯，他认为他身上值钱的东西有：《Java从入门到入土》、1000元现金、某厂月薪3.5K包吃包住的Offer。现在抢劫犯要抢劫他身上的一样东西，如果站在张三的角度思考的话，那肯定是让抢《Java从入门到入土》这本破书了，但是站在抢劫犯的角度思考，1000元现金比什么都强！
这就是思考角度的问题，对方如果很聪明，那他肯定是选择让AI利益最低的一个节点，现在我们就认为对方是一个绝顶聪明的人，所以在对方选择的分支里都选择了分值最低的，好让AI的利益受损。
再接下去就是AI选择分支了，不用说，AI肯定选分高的。AI要从对方给的那些低分分支里选择分最高的，也就是差的里面选好的。所以B1得分为1，B2得分为3。
后面也是一样的流程，又轮到对方选择了，对方肯定选择B1分支，B1分支是得分最低的节点，所以到最后，A1分支的最终得分为1。
我们对A2分支也做如上操作：AI选高分，对方选低分。最后可以得出如下图所示的结果
现在我们知道A1最终得分为1，A2最终得分为2，因为AI会选择最大得分的分支A2，所以最终A0得分为2，也就是说，AI下一步的最佳落子点为(0,1)。
AI选择的分支一定是选最高分值的叫做Max分支，对方选择的分支一定是选最低分值的叫做Min分支，然后由低到高，倒推着求出起点的得分，这就是极大极小值搜索的实现原理。
代码实现我们接着上次的代码来，在ZhiZhangAIService类中定义一个全局变量bestPoint用于存放AI当前最佳下棋点位，再定义一个全局变量attack用于设置AI的进攻能力。
/***AI最佳下棋点位*/privatePointbestPoint;/***进攻系数*/privateintattack;复制代码新增minimax方法，编写极大极小值搜索算法的实现代码。这里是使用递归的方式，深度优先遍历博弈树，生成树和选择节点是同时进行的。type表示当前走棋方，刚开始时，因为要从根节点开始生成树，所以要传入0，并且AI最后选择高分节点的时候也是在根节点进行的。depth表示搜索的深度，也就是AI思考的步数，我这边传入的是2，也就是只思考两步棋，思考4步或6步都行，只要你电脑吃得消（计算量很大的哦）。
/***极大极小值搜索**@paramtype当前走棋方0.根节点表示AI走棋1.AI2.玩家*@paramdepth搜索深度*@returnprivateintminimax(inttype,int{//是否是根节点booleanisRoot=type==0;if(isRoot){//根节点是AI走棋type=this.ai;}//当前是否是AI走棋booleanisAI=type==this.ai;//当前分值，intscore;if(isAI){//AI因为要选择最高分，所以初始化一个难以到达的低分score=-INFINITY;}else{//对手要选择最低分，所以初始化一个难以到达的高分score=INFINITY;}
//到达叶子结点if(depth==0){/***评估每棵博弈树的叶子结点的局势*比如：depth=2时，表示从AI开始走两步棋之后的局势评估，AI(走第一步)->玩家(走第二步)，然后对局势进行评估*注意：局势评估是以AI角度进行的，分值越大对AI越有利，对玩家越不利*/returnevaluateAll();}
for(inti=0;iscore){//最高值被刷新score=curScore;if(isRoot){//根节点处更新AI最好的棋位this.bestPoint=p;}}}else{//对手要选对AI最不利的节点（分最低的）if(curScore