一、什么是算杀？为什么要算杀？
算杀就是只算杀棋。
我用五子棋ai跟别人下了一阵子之后发现，用博弈树看6层深度(模拟ai走4步，模拟人走3步)其实根本不够，因为真正的高手看到的远比6层要多。高手进行谋划以后，一开始走看似“不那么重要”的位置，然后就可以形成双活3或者活4的必杀棋型打败ai。我实现的ai其实还非常短视，也就是只能看到6层以内的利益，而看不到更大的、全局的利益。
这里我参考了这位大佬的文章，写的非常好，无奈我不是很能看懂，也只能凭自己的理解写算杀了：五子棋AI算法第五篇-算杀。
怎么样让电脑也能这样进行“谋划”？一个简单的思路就是算杀。算杀是只算杀棋，很容易想到，算杀也是一个极大极小搜索，只不过不用考虑10个节点(之前实现的)，只需要考虑白棋(ai)的杀棋节点(形成新的连5、活4、冲4、活3)，黑棋只考虑最好的那个节点，那么分支数b极大减少，搜索深度可以达到16层以上(很多搜不到16层，因为没有那么多的杀棋节点)，达到搜索深度之前，只要有一个节点白棋获胜了，算杀就成功了。这就是我简单实现的算杀模块。
我实现的算杀功能比较简单，但也进一步提升了棋力。
二、具体实现
首先进行算杀，如果算杀成功就用算杀的点，如果不成功就用原来6层极大极小搜索找到的点。
首先是找白棋的杀棋点。
QList<QPoint> chessAi::seek_kill_points(int (*board)[15]){//找白棋的连5,活4,冲4,活3的杀棋位置QList<QPoint> pointList;POINTS P=seekPoints(board);//一般来说,能冲4或者活3的必在评分前20的点内int sameBoard[15][15];copyBoard(board,sameBoard);for(int i=0;i<20;++i){sameBoard[P.pos[i].x()][P.pos[i].y()]=C_WHITE;//模拟落子if(evaluate(sameBoard).STAT[WIN]>0){//产生连5pointList.append(P.pos[i]);}else if(evaluate(sameBoard).STAT[FLEX4]>evaluate(board).STAT[FLEX4]){//产生新活4pointList.append(P.pos[i]);}else if(evaluate(sameBoard).STAT[BLOCK4]>evaluate(board).STAT[BLOCK4]){//产生新冲4pointList.append(P.pos[i]);}else if(evaluate(sameBoard).STAT[FLEX3]>evaluate(board).STAT[FLEX3]){//产生新活3pointList.append(P.pos[i]);}sameBoard[P.pos[i].x()][P.pos[i].y()]=C_NONE;//还原落子}return pointList;}
简单算杀模块：
struct EVALUATION{int score;gameResult result;int STAT[8];//储存部分棋形的个数,下标WIN=1为白连5,LOSE=2为黑连5,FLEX4=3为白活4,BLOCK4=5为白冲4,FLEX3=7为白活3};struct POINTS{//最佳落子位置,[0]分数最高,[19]分数最低QPoint pos[20];int score[20];//此处落子的局势分数};struct DECISION{QPoint pos;//位置int eval;//对分数的评估};DECISION decision;bool chessAi::analyse_kill(int (*board)[15], int depth){EVALUATION EVAL=evaluate(board);if(depth==0||EVAL.result!=R_DRAW){if(depth==0){//若抵达最深层,走一步对白棋的最好位置,若白棋还没赢则返回falsePOINTS P;P=seekPoints(board); board[P.pos[0].x()][P.pos[0].y()]=C_WHITE;gameResult result=evaluate(board).result;if(result==R_WHITE)return true;else return false;}else if(EVAL.result==R_WHITE)return true;//找到白棋杀棋else return false;//白棋输}else if(depth%2==0){//max层,我方(白)决策QList<QPoint> pointList=seek_kill_points(board);//产生杀棋点if(pointList.length()==0)return false;//没有杀棋点for(auto i:pointList){int sameBoard[15][15];copyBoard(board,sameBoard);sameBoard[i.x()][i.y()]=C_WHITE;//模拟己方落子if(analyse_kill(sameBoard,depth-1)){if(depth==16){//开始层,需决定落子,结果存于decision中decision.pos.setX(i.x());decision.pos.setY(i.y());decision.eval=INT_MAX;//杀棋评分没有作用}return true;}}return false;}else{//min层,敌方(黑)决策,只下对自己最好的棋int rBoard[15][15];reverseBoard(board,rBoard);POINTS P=seekPoints(rBoard);//找对于黑子的最佳位置,需要将棋盘不同颜色反转,因为seekPoint是求白色方的最佳位置int sameBoard[15][15];copyBoard(board,sameBoard);sameBoard[P.pos[0].x()][P.pos[0].y()]=C_BLACK;//模拟敌方落子:只走最好的一步//无需剪枝return analyse_kill(sameBoard,depth-1);}}//调用if(!ai.analyse_kill(ai.chesses,16)){qDebug()<<"没找到杀棋";ai.analyse(ai.chesses,6,-INT_MAX,INT_MAX);}else{qDebug()<<"找到了杀棋";}
结束
简单写了一个算杀模块，还是提升了部分棋力。
棋类博弈知识还是很值得去研究的，在知网上找资料的时候我竟然发现可以用五子棋ai作为硕士毕业论文，看了以后感觉。。国内论文审查的确比较水。真正的高手都在GitHub上啊！
