JS实现的围棋吃子算法

由于前段时间自己开发一个围棋相关的微信小程序，需要实现围棋吃子的功能。网上找了一圈没有找到满足需求的实现，于是决定自己动手，丰衣足食。
首先先分析一下具体规则，拆解一下需求：
（1）与棋子直接紧邻的空点称之为“气”，直接紧邻的同色棋子视为一个整体，它们的“气”应一起计算；
（2）没有气的棋子则为死子，应从棋盘上提掉；
（3）当下棋造成双方棋子都没有气时，只有对方棋子被吃掉；
（4）当下棋只造成自己棋子没气，这是不合法的（不允许自杀）；

开始写代码：

先用一个19*19的二维数组表示棋盘，-1代表空交叉点，0代表白子，1代表黑子，这就不谈了；
当然这里19可以定义成常量，这样就方便实现9路、13路小棋盘等；

数气：

DFS，用一个与棋盘一样大的数组记录是否遍历过，依次遍历4个方向；

countLiberty: function (x, y, checked) {
  let q = 0;    // 气
  let checked_pos = checked || this.getEmptyStones();
  let color = stones[x][y];

  if (checked_pos[x][y] != -1) return 0;    // 已经遍历过
  checked_pos[x][y] = 1;

  const left_x = x - 1;
  const right_x = x + 1;
  const up_y = y - 1;
  const down_y = y + 1;

  if (left_x >= 0) {
    if (stones[left_x][y] == -1) { // 空位
      ++q;
    } else if (stones[left_x][y] == color) { // 己方棋子
      q += this.countLiberty(left_x, y, checked_pos);
    }
  }

  ......

获取一片棋子：

当确认了死子之后，需要将相连的棋子一起从棋盘中提掉；
将所有死子的信息放入deads数组，反馈给UI处理；同样是DFS：

removeBlock: function (x, y, deads, checked) {
  let checked_pos = checked != undefined ? checked : this.getEmptyStones();
  const color = stones[x][y];
  const left_x = x - 1;
  const right_x = x + 1;
  const up_y = y - 1;
  const down_y = y + 1;
  if (checked_pos[x][y] != -1) return;

  if (stones[x][y] != -1) {
    //console.log('remove block push x:', x, ' y:', y);
    deads.push({ "x": x, "y": y, "color":color });
    stones[x][y] = -1;
  }
  checked_pos[x][y] = 1;

  if (left_x >= 0 && stones[left_x][y] == color) {
    this.removeBlock(left_x, y, deads, checked_pos);
  }
  if (right_x <= LINE_COUNT - 1 && stones[right_x][y] == color) {
    this.removeBlock(right_x, y, deads, checked_pos);
  }
  if (up_y >= 0 && stones[x][up_y] == color) {
    this.removeBlock(x, up_y, deads, checked_pos);
  }
  if (down_y <= LINE_COUNT - 1 && stones[x][down_y] == color) {
    this.removeBlock(x, down_y, deads, checked_pos);
  }
},

落子逻辑：

（1）首先判断是不是空位；
（2）判断能不能提掉对方棋子；
（3）判断是不是禁入点（不允许自杀）；
接口这里设计的是返回吃掉的对方棋子数组，如果落子不符合规则则返回false

addStone: function (x, y, color) {
  if (x < 0 || x > LINE_COUNT - 1) return false;
  if (y < 0 || y > LINE_COUNT - 1) return false;
  if (stones[x][y] != -1) return false; // 已经有棋子
  stones[x][y] = color;

  // 判断是否使对方棋子没气
  const left_x = x - 1;
  const right_x = x + 1;
  const up_y = y - 1;
  const down_y = y + 1;

  let left_dead = false, right_dead = false, up_dead = false, down_dead = false;
  if (left_x >= 0 && stones[left_x][y] != -1 && stones[left_x][y] != color) {
    //console.log('left liberty ', this.countLiberty(left_x, y));
    left_dead = (this.countLiberty(left_x, y) == 0);
  }
  ......

  if (!(left_dead || right_dead || up_dead || down_dead)) { // 没有吃掉对方棋子
    // 判断自己是否没气
    //console.log('this liberty ', this.countLiberty(x, y));
    if (this.countLiberty(x, y) == 0) {
      stones[x][y] = -1;
      return false;
    } else return [];
  }

  let deads = [];
  if (left_dead && stones[left_x][y] != color) {
    this.removeBlock(left_x, y, deads);
  }
  ......
  return deads;
},

最后简单放几个测试用例吧：
吃子：

image.png

同时吃多片棋子：

image.png
自杀：
image.png
棋盘边角情况：
image.png