需要算杀吗？

算杀其实是很多AI都带有的功能，简单的说，正常的搜索会搜索所有的可能性，而算杀只计算活三和冲四的节点，由于每一层的分支变得更少，因此算杀可以很容易实现较大的深度，一般都可以搜索到 12层以上。

在第一版教程中我是在叶节点算杀的，用的是 6 + 5 的方式，也就是正常搜索到6层，然后在叶节点进行5层的算杀，把整体深度提升到 11 层。实际测试的时候经常会出现需要计算 60 秒以上的棋。因为每个叶节点都进行算杀还是很慢的，特别是中盘容易碰到一些有很多冲四活三的局面，算杀会变得非常慢。

在新版本中，我直接抛弃了算杀模块，代码依然存在，但是并没有使用。不过其实我更建议另一种做法，算杀模块作为搜索模块的一个补充，而不是混在一起使用，就是在正常搜索完毕，且没有搜索到必胜局面的时候，进行一次较大深度的算杀（或者在之前也行），由于单次算杀的时间很短，几乎不会影响电脑的思考时间，并且能得到棋力的提升。估计在后序我会加上这个额外的算杀。

克服水平线效应

所谓算杀就是计算出杀棋，杀棋就是指一方通过连续的活三和冲四进行进攻，一直到赢的一种走法。我们一般会把算杀分为两种：

  • VCF (victory of continuous four) 连续冲四胜
  • VCT (victory of continuous three) 连续活三胜

一般在算杀的时候，我们优先进行 VCT，没有找到结果的时候再进行 VCF。很显然，同样的深度，算杀要比前面讲的搜索效率高很多。因为算杀的情况下，每个节点只计算活三和冲四的子节点。所以同样是1秒钟的时间，搜索只能进行4层，而算杀很多时候可以进行到12层以上。

为了方便，我们把前面的讲到全面的极大极小值搜索简称为搜索

而且很容易想到，算杀其实也是一种极大极小值搜索，具体的策略是这样的：

  • MAX层，只搜索己方的活三和冲四节点，只要有一个子节点的能赢即可
  • MIN 层，搜索所有的己方和对面的活三和冲四节点（进攻也是防守），只要有一个子节点能保持不败即可。

算杀的实现代码也比较长，这里贴出部分关键代码，完整代码请参阅 https://github.com/lihongxun945/gobang：

vcx.js

  1. //找到所有比目标分数大的位置
  2. //注意，不止要找自己的，还要找对面的，
  3. var findMax = function(role, score) {
  4.   var result = [],
  5.       fives = [];
  6.   for(var i=0;i<board.board.length;i++) {
  7.     for(var j=0;j<board.board[i].length;j++) {
  8.       if(board.board[i][j] == R.empty) {
  9.         var p = [i, j];
  10.         // 省略部分代码
  11.         var s = (role == R.com ? board.comScore[p[0]][p[1]] : board.humScore[p[0]][p[1]]);
  12.         p.score = s;
  13.         if(s >= score) {
  14.           result.push(p);
  15.         }
  16.       }
  17.     }
  18.   }
  19.   // 能连五，则直接返回
  20.   // 但是注意不要碰到连五就返回，而是把所有连五的点都考虑一遍，不然可能出现自己能连却防守别人的问题
  21.   if (fives.length) return fives;
  22.   //注意对结果进行排序
  23.   result.sort(function(a, b) {
  24.     return b.score - a.score;
  25.   });
  26.   return result;
  27. }
  30. // MIN层
  31. //找到所有比目标分数大的位置
  32. //这是MIN层，所以己方分数要变成负数
  33. var findMin = function(role, score) {
  34.   var result = [];
  35.   var fives = [];
  36.   var fours = [];
  37.   var blockedfours = [];
  38.   for(var i=0;i<board.board.length;i++) {
  39.     for(var j=0;j<board.board[i].length;j++) {
  40.       if(board.board[i][j] == R.empty) {
  41.         var p = [i, j];
  43.         var s1 = (role == R.com ? board.comScore[p[0]][p[1]] : board.humScore[p[0]][p[1]]);
  44.         var s2 = (role == R.com ? board.humScore[p[0]][p[1]] : board.comScore[p[0]][p[1]]);
  45.         if(s1 >= S.FIVE) {
  46.           p.score = - s1;
  47.           return [p];
  48.         }
  50.         if(s2 >= S.FIVE) {
  51.           p.score = s2;
  52.           fives.push(p);
  53.           continue;
  54.         }
  56.        // 省略，其他分数的判断
  57.       }
  58.     }
  59.   }
  60.   if(fives.length) return fives;
  62.   // 注意冲四，因为虽然冲四的分比活四低，但是他的防守优先级是和活四一样高的，否则会忽略冲四导致获胜的走法
  63.   if(fours.length) return fours.concat(blockedfours);
  65.   //注意对结果进行排序
  66.   //因为fours可能不存在，这时候不要忽略了 blockedfours
  67.   result = blockedfours.concat(result);
  68.   result.sort(function(a, b) {
  69.     return Math.abs(b.score) - Math.abs(a.score);
  70.   });
  71.   return result;
  72. }
  74. var max = function(role, deep, totalDeep) {
  75.   debugNodeCount ++;
  76.   //board.logSteps();
  77.   if(deep <= 1) return false;
  79.   var points = findMax(role, MAX_SCORE);
  80.   if(points.length && points[0].score >= S.FOUR) return [points[0]]; //为了减少一层搜索，活四就行了。
  81.   if(points.length == 0) return false;
  82.   for(var i=0;i<points.length;i++) {
  83.     var p = points[i];
  84.     board.put(p, role);
  85.     // 如果是防守对面的冲四，那么不用记下来
  86.     if (!p.score <= -S.FIVE) lastMaxPoint = p;
  87.     var m = min(R.reverse(role), deep-1);
  88.     board.remove(p);
  89.     if(m) {
  90.       if(m.length) {
  91.         m.unshift(p); //注意 unshift 方法返回的是新数组长度，而不是新数组本身
  92.         return m;
  93.       } else {
  94.         return [p];
  95.       }
  96.     }
  97.   }
  98.   return false;
  99. }
  102. //只要有一种方式能防守住，就可以了
  103. var min = function(role, deep) {
  104.   debugNodeCount ++;
  105.   var w = board.win();
  106.   //board.logSteps();
  107.   if(w == role) return false;
  108.   if(w == R.reverse(role)) return true;
  109.   if(deep <= 1) return false;
  110.   var points = findMin(role, MIN_SCORE);
  111.   if(points.length == 0) return false;
  112.   if(points.length && -1 * points[0].score  >= S.FOUR) return false; //为了减少一层搜索，活四就行了。
  114.   var cands = [];
  115.   for(var i=0;i<points.length;i++) {
  116.     var p = points[i];
  117.     board.put(p, role);
  118.     lastMinPoint = p;
  119.     var m = max(R.reverse(role), deep-1);
  120.     board.remove(p);
  121.     if(m) {
  122.       m.unshift(p);
  123.       cands.push(m);
  124.       continue;
  125.     } else {
  126.       return false; //只要有一种能防守住
  127.     }
  128.   }
  129.   var result = cands[Math.floor(cands.length*Math.random())];  //无法防守住
  130.   return result;
  131. }
  135. //迭代加深
  136. var deeping = function(role, deep, totalDeep) {
  137.   // 省略迭代加深代码
  138. }
  140. var vcx = function(role, deep, onlyFour) {
  142.   deep = deep === undefined ? config.vcxDeep : deep;
  144.   if(deep <= 0) return false;
  146.   if (onlyFour) {
  147.     //计算冲四赢的
  148.     MAX_SCORE = S.BLOCKED_FOUR;
  149.     MIN_SCORE = S.FIVE;
  151.     var result = deeping(role, deep, deep);
  152.     if(result) {
  153.       result.score = S.FOUR;
  154.       return result;
  155.     }
  156.     return false
  157.   } else {
  158.     //计算通过 活三 赢的；
  159.     MAX_SCORE = S.THREE;
  160.     MIN_SCORE = S.BLOCKED_FOUR;
  161.     result = deeping(role, deep, deep);
  162.     if(result) {
  163.       result.score = S.THREE*2; //连续冲三赢，就等于是双三
  164.     }
  166.     return result;
  167.   }
  169.   return false;
  171. }
  173. // 连续冲四
  174. var vcf = function (role, deep) {
  175.   var c = getCache(true);
  176.   if (c) return c;
  177.   var result = vcx(role, deep, true);
  178.   cache(result, true);
  179.   return result;
  180. }
  182. // 连续活三
  183. var vct = function (role, deep) {
  184.   var c = getCache();
  185.   if (c) return c;
  186.   var result = vcx(role, deep, false);
  187.   cache(result);
  188.   return result;
  189. }
  191. export default {
  192.   vct: vct,
  193.   vcf: vcf
  194. }

这样我们正常进行 8 层搜索，如果没有好的结果则进行约 12层的算杀，能达到一个比较理想的棋力。

下一篇：五子棋AI设计教程第二版九：性能优化