用原生JS实现Web版黑白棋 AI

有同学对这个游戏感兴趣，问我怎么实现这样的人机对战游戏，所以在这里我把这个游戏开发过程中的要点拿出来说一说，看看从中间能学到什么知识。

---

首先是UI，这块的布局比较简单，我们可以采用grid布局，容器就用单个标签：

<div id="board" data-turn="white"></div>

CSS样式如下：

#board {
  width: 482px;
  height: 482px;
  box-sizing: border-box;
  background-image: linear-gradient(90deg, rgba(0, 0, 0, 0.5) 2.5%, transparent 2.5%), linear-gradient( rgba(0, 0, 0, 0.95) 2.5%, transparent 2.5%);
  background-size: 60px 60px;
  background-repeat: repeat;
  background-color: wheat;
  display: grid;
  grid-template-columns: repeat(8, 60px);
  grid-template-rows: repeat(8, 60px);
}

我们用linear-gradient来绘制格子线，用display:grid来设置网格，这都是常规操作了。

注意一个细节，我们用data-turn="white"表示当前是白棋回合，这个属性是为了标记后续落子的时候能给出对应的可落子提示信息：

我们对应添加CSS样式细节：

#board > div {
  border-radius: 50%;
  margin: 3px;
}

#board > .black {
  background-color: #022;
}

#board > .white {
  background-color: #EEE;
}

#board[data-turn="black"] > div.empty:hover[data-allow="yes"] {
  background-color: #022;
  opacity: 0.7;
}

#board[data-turn="white"] > div.empty:hover[data-allow="yes"] {
  background-color: #EEE;
  opacity: 0.7;
}

其中.black、.white、.empty分别表示对应的黑子、白子和空点。我们用#board[data-turn="black"] > div.empty:hover[data-allow="yes"]来显示可落子提示。

这样我们就完成了HTML和CSS部分。

接下来，我们实现JS的部分；首先是关于规则的。

我们用一个长度为64的数组表示棋盘状态就可以了，其中0表示对应位置的空格，1表示黑棋，2表示白棋。

我们可以初始化一下棋盘：

function init(data = new Array(64)) {
  data.fill(0);
  data[27] = 2;
  data[28] = 1;
  data[35] = 1;
  data[36] = 2;
  return data;
}

接着我们把初始棋盘数据绘制到HTML容器中，就可以将棋盘呈现出来。

function initBoard(data) {
  init(data);
  const allowPut = getAllAllowPut(data, 1);
  updateBoard(data, 1, allowPut);
}

function updateBoard(data, turn, allowPut = []) {
  board.innerHTML = '';
  for(let i = 0; i < 64; i++) {
    const cell = document.createElement('div');
    const x = i % 8;
    const y = Math.floor(i / 8);
    cell.dataset.x = x;
    cell.dataset.y = y;
    cell.dataset.idx = i;
    if(data[i] === 1) {
      cell.className = 'black';
    } else if (data[i] === 2) {
      cell.className = 'white';
    } else {
      cell.className = 'empty';
    }
    if(allowPut.includes(i)) {
      cell.dataset.allow = 'yes';
    } else {
      cell.dataset.allow = 'no';
    }
    board.appendChild(cell);
  }
  board.dataset.turn = turn === 1 ? 'black': 'white';
}

这里updateBoard用来根据data来初始化棋盘，注意到这里有个turn表示是黑棋还是白棋的回合，allowPut表示所有允许落子的点，因为根据黑白棋的规则，只有能反转棋子的点才可以落子，我们可以通过以下算法来判定：

// 获得棋盘上所有允许放置的位置
function getAllAllowPut(data, turn) {
  const allowPut = [];
  for(let i = 0; i < 64; i++) {
    const x = i % 8;
    const y = Math.floor(i / 8);
    const aw = checkStone(data, turn, x, y);
    if(aw && aw.length) {
      allowPut.push(i);
    }
  }
  return allowPut;
}

// 尝试放置棋子
function checkStone(data, turn, x, y) {
  const stone = getStone(data, x, y);
  if(stone) return false; // 已经有棋子

  const aw = []; // 总共能影响的子
  const w = [];

  function check(x, y) {
    const ns = getStone(data, x, y);
    if(ns === 0) { // 空位
      return false;
    }
    if((ns ^ turn) === 3) { // 反子
      w.push(x + 8 * y);
    }
    if(ns === turn) { // 同色子
      aw.push(...w);
      return false;
    }
  }

  for(let i = x - 1; i >= 0; i--) { // 左边
    if(check(i, y) === false) break;
  }

  w.length = 0;
  for(let i = x + 1; i < 8; i++) { // 右边
    if(check(i, y) === false) break;
  }

  w.length = 0;
  for(let i = y - 1; i >= 0; i--) { // 上边
    if(check(x, i) === false) break;
  }

  w.length = 0;
  for(let i = y + 1; i < 8; i++) { // 下边
    if(check(x, i) === false) break;
  }

  w.length = 0;  // 左上
  for(let i = x - 1, j = y - 1; i >= 0 && j >= 0; i--, j--) {
    if(check(i, j) === false) break;
  }

  w.length = 0;  // 右上
  for(let i = x + 1, j = y - 1; i < 8 && j >= 0; i++, j--) {
    if(check(i, j) === false) break;
  }

  w.length = 0;  // 右下
  for(let i = x + 1, j = y + 1; i < 8 && j < 8; i++, j++) {
    if(check(i, j) === false) break;
  }

  w.length = 0;  // 左下
  for(let i = x - 1, j = y + 1; i >= 0 && j < 8; i--, j++) {
    if(check(i, j) === false) break;
  }

  return aw;
}

这样我们其实就可以实现双人对战了：

async function waitPutStone(data, turn) {
  return new Promise((resolve) => {
    const handler = ({target}) => {
      if(target.dataset.allow === 'yes') {
        const x = Number(target.dataset.x);
        const y = Number(target.dataset.y);
        const idx = Number(target.dataset.idx);
        const aw = checkStone(data, turn, x, y);
        if(aw && aw.length) {
          data[idx] = turn;
          for(let i = 0; i < aw.length; i++) {
            data[aw[i]] = turn;
          }
          turn = turn === 1 ? 2 : 1;
          const poss = getAllAllowPut(data, turn);
          updateBoard(data, turn, poss);
          board.removeEventListener('click', handler);
          resolve(poss);
        }
      }
    }
    board.addEventListener('click', handler);
  });
}

function sleep(ms = 500) {
  return new Promise((resolve) => {
    setTimeout(resolve, ms);
  });
}


(async () => {
  // 棋盘数据
  const boardData = (new Array(64)).fill(0);
  initBoard(boardData);

  let turn = 1;

  while(1) {
    let poss = await waitPutStone(boardData, turn);

    if(poss.length > 0) { // 如果可以交替走子
      turn = turn === 1 ? 2 : 1;
    } else {
      // 尝试连续走子
      nextPoss = getAllAllowPut(boardData, turn);
      if(nextPoss.length <= 0) {
        console.log('游戏结束！');
        const res = boardData.filter(d => d === 1);
        if(res.length > 32) {
          result.innerHTML = '黑方胜！';
        } else if(res.length === 32) {
          result.innerHTML = '平局！';
        } else {
          result.innerHTML = '白方胜！';
        }
      }
    }
  }
})();

这里我们用异步waitPutStone来监听异步事件，因为游戏的很多操作是异步等待用户交互，用这样的模型配合async/await能写出可读性比较高的流程控制代码来。

这里有个小细节，一般情况下黑白棋是黑白交替落子，但是如果一方无子可落，那么另一方连续落子，如果另一方也无子可落，则结束该局游戏。

这样我们就实现了双人对战的版本，一共100多行JS代码，非常简单。

接下来，我们要实现AI部分。黑白棋的变化不算太复杂，使用比较传统的深度优先搜索策略就可以。不过首先要解决的是，得建立黑白棋的盘面评估模型。一般来说评估黑白棋优劣势，常使用行动力和稳定子模型。

所谓行动力，简单来说指的就是一方落子的可选点数量。一方可落子选点数越多，行动力就越强，优势也就越大。所以在对弈时，尽可能提升己方行动力，减少对方行动力。

稳定子，则是指棋盘上不会被反转的棋子，最简单的比如四个角的棋子，以及占满一整条边之后，边上的棋子，这些都是不能被再反转的棋子，属于稳定子。在对弈时，尽可能增加己方稳定子，减少对方稳定子。

在这里，我们采用一个简单的行动力+稳定子模型来进行盘面估值：

// 评估盘面价值
function evaluate(data) {
  const p1 = getAllAllowPut(data, 1);
  const p2 = getAllAllowPut(data, 2);
  if(p1.length === 0 && p2.length === 0) {
    // 终局
    return (data.filter(d => d === 1).length
      - data.filter(d => d === 2).length) * 10000;
  }
  else {
    // 行动力，让自己的行动力尽可能大
    const mobi = p1.length - p2.length;

    // 稳定子，让自己尽可能获得更多的稳定子
    let stable = countStable(data, 1) - countStable(data, 2);
    stable += countStable2(data, 1) - countStable2(data, 2);

    // corner 角加成
    const corAddOn = countCorner(data, 1) - countCorner(data, 2);
    const corAddOn2 = countNearCorner(data, 2) - countNearCorner(data, 1);

    return mobi * 10 + corAddOn * 30 + corAddOn2 * 20 + stable * 10;
  }
}

这里有几个估值，第一个是行动力，我们直接用 getAllAllowPut 返回的数组长度，也就是可选落子点来算就可以了。

第二个是稳定子，这里只是简单计算四个角和整条边，不算特别合理，但是建议AI也足够了。

第三个是再对角加强估值，对占据四个角的位置加权，对空角时占据四个角相邻位置减权（因为此时占据相邻位置，则角很容易被对方占据）。

最终的实现如下：

// 计算稳定子：连通四个角的同色子
function countStable(data, turn) {
  let stable = 0;
  if(getStone(data, 0, 0) === turn) {
    for(let i = 0; i < 8; i++) {
      if(getStone(data, 0, i) === turn) stable++;
      else break;
      if(i === 7) stable -= 8; // 避免重复
    }
    for(let i = 0; i < 8; i++) {
      if(getStone(data, i, 0) === turn) stable++;
      else break;
      if(i === 7) stable -= 8;
    }
  }
  if(getStone(data, 0, 7) === turn) {
    for(let i = 7; i >= 0; i--) {
      if(getStone(data, 0, i) === turn) stable++;
      else break;
    }
    for(let i = 0; i < 8; i++) {
      if(getStone(data, i, 7) === turn) stable++;
      else break;
      if(i === 7) stable -= 8;
    }
  }
  if(getStone(data, 7, 7) === turn) {
    for(let i = 7; i >= 0; i--) {
      if(getStone(data, 7, i) === turn) stable++;
      else break;
    }
    for(let i = 7; i >= 0; i--) {
      if(getStone(data, i, 7) === turn) stable++;
      else break;
    }
  }
  if(getStone(data, 7, 0) === turn) {
    for(let i = 0; i < 8; i++) {
      if(getStone(data, 7, i) === turn) stable++;
      else break;
      if(i === 7) stable -= 8;
    }
    for(let i = 7; i >= 0; i--) {
      if(getStone(data, i, 0) === turn) stable++;
      else break;
    }
  }

  return stable;
}

// 计算稳定子：占满一条边之后的所有棋子都是稳定子
function countStable2(data, turn) {
  let v = 0;
  let stable = 0;
  for(let i = 0; i < 8; i++) {
    if(getStone(data, 0, i) === turn) v++;
    if(getStone(data, 0, i) === 0) {
      v = 0;
      break;
    }
  }
  stable += v;
  v = 0;
  for(let i = 0; i < 8; i++) {
    if(getStone(data, i, 0) === turn) v++;
    if(getStone(data, i, 0) === 0) {
      v = 0;
      break;
    }
  }
  stable += v;
  v = 0;
  for(let i = 0; i < 8; i++) {
    if(getStone(data, i, 7) === turn) v++;
    if(getStone(data, i, 7) === 0) {
      v = 0;
      break;
    }
  }
  stable += v;
  v = 0;
  for(let i = 0; i < 8; i++) {
    if(getStone(data, 7, i) === turn) v++;
    if(getStone(data, 7, i) === 0) {
      v = 0;
      break;
    }
  }
  stable += v;
  return stable;
}

// 计算角子数，一般情况下己方尽量占据较为有利
function countCorner(data, turn) {
  let corAddOn = 0;
  if(getStone(data, 0, 0) === turn) corAddOn++;
  if(getStone(data, 7, 0) === turn) corAddOn++;
  if(getStone(data, 7, 7) === turn) corAddOn++;
  if(getStone(data, 0, 7) === turn) corAddOn++;

  return corAddOn;
}

// 计算临近角子数，在空角情况下尽量让对方占据较为有利
function countNearCorner(data, turn) {
  let corAddOn2 = 0;
  if(getStone(data, 0, 0) === 0 && getStone(data, 1, 0) === turn) {
    corAddOn2++;
  }
  if(getStone(data, 0, 0) === 0 && getStone(data, 0, 1) === turn) {
    corAddOn2++;
  }
  if(getStone(data, 0, 0) === 0 && getStone(data, 1, 1) === turn) {
    corAddOn2+=3;
  }
  if(getStone(data, 7, 0) === 0 && getStone(data, 6, 0) === turn) {
    corAddOn2++;
  }
  if(getStone(data, 7, 0) === 0 && getStone(data, 7, 1) === turn) {
    corAddOn2++;
  }
  if(getStone(data, 7, 0) === 0 && getStone(data, 6, 1) === turn) {
    corAddOn2+=3;
  }
  if(getStone(data, 0, 7) === 0 && getStone(data, 0, 6) === turn) {
    corAddOn2++;
  }
  if(getStone(data, 0, 7) === 0 && getStone(data, 1, 7) === turn) {
    corAddOn2++;
  }
  if(getStone(data, 0, 7) === 0 && getStone(data, 1, 6) === turn) {
    corAddOn2+=3;
  }
  if(getStone(data, 7, 7) === 0 && getStone(data, 7, 6) === turn) {
    corAddOn2++;
  }
  if(getStone(data, 7, 7) === 0 && getStone(data, 6, 7) === turn) {
    corAddOn2++;
  }
  if(getStone(data, 7, 7) === 0 && getStone(data, 6, 6) === turn) {
    corAddOn2+=3;
  }

  return corAddOn2;
}

要说明一下，这个估值其实严格来说并不是非常非常合理，但它有可取的地方，在Web上，浏览器JS运行效率不算特别高，搜索深度不会很深，所以快速判定角的位置，有助于在搜索深度不足时快速估值。

有了估值函数，最后我们再实现深度优先搜索方法就可以了：

let branches = 0;
function search(data, turn = 2, depth = 0, maxDepth = 6, ab = null) {
  // 深度优先搜索，返回 idx, value
  branches++;
  const poss = getAllAllowPut(data, turn); // 先获取所有可能的落子点
  const isSearchMax = !!(depth % 2); // 奇数层找最大值
  let v = isSearchMax ? -Infinity : Infinity;

  const opTurn = turn === 1 ? 2 : 1;

  if(poss.length <= 0) { // 如果一方没有落子点
    if(getAllAllowPut(data, opTurn).length <= 0) {
      // 终局情况
      return evaluate(data);
    } else { // 跳过
      return search(data, opTurn, depth + 1, maxDepth, ab);
    }
  }
  if(depth > maxDepth) {
    // 最后一层
    return evaluate(data);
  }

  let pidx = -1;

  for(let i = 0; i < poss.length; i++) {
    const idx = poss[i];
    const x = idx % 8;
    const y = Math.floor(idx / 8);
    // 试走
    const aw = checkStone(data, turn, x, y);
    if(aw && aw.length) {
      data[idx] = turn;
      for(let i = 0; i < aw.length; i++) {
        data[aw[i]] = turn;
      }
      const vv = search(data, opTurn, depth + 1, maxDepth, v);
      // recover
      data[idx] = 0;
      for(let i = 0; i < aw.length; i++) {
        data[aw[i]] = opTurn;
      }

      if(ab != null && isSearchMax && vv >= ab) { // 取最大值的层
      // 最大值已经比上一层的最小值大，不用再搜索了，剪枝
        return vv;
      }
      if(ab != null && !isSearchMax && vv <= ab) { // 取最小值的层
        // 如果最小值已经比上一层的最大值小，也不用再搜索了，剪枝
        return vv;
      }

      if(isSearchMax) {
        // console.log(v, vv, '---', depth);
        v = Math.max(v, vv);
        // console.log('>>>', v, depth);
      } else {
        // if(depth === 0) console.log(depth, i, v, vv);
        if(depth === 0 && vv < v) {
          pidx = idx;
        }
        v = Math.min(v, vv);
      }
    }
  }
  // console.log(v, pidx);
  if(depth === 0) {
    // console.log(v, pidx, '***');
    return pidx;
  }
  return v;
}

上面代码就是一个经典的Minimax深度优先算法，做了alhpa-beta剪枝

最后，我们把具体对弈执行过程实现：

(async () => {
  let round = 0;
  let maxDepth = 0;
  let step = 0;

  // 棋盘数据

  const boardData = (new Array(64)).fill(0);
  initBoard(boardData);

  while(round++ < 100) {
    let poss = await waitPutStone(boardData, 1); // 玩家先行
    let nextPoss;
    step++;
    while(poss.length) { // 如果AI可以走子
      result.innerHTML = '计算中...';
      await sleep(100); // 停0.5秒
      // const idx = poss[0]; // 通过AI搜索
      branches = 0;
      if(step < 40) {
        maxDepth = 4;
      } else if(step < 48) {
        maxDepth = 6;
      } else if(step < 52) {
        maxDepth = 10;
      } else {
        maxDepth = 6;
      }
      const idx = search([...boardData], 2, 0, maxDepth);
      result.innerHTML = '';
      console.log(round, maxDepth, idx, branches);
      
      const x = idx % 8;
      const y = Math.floor(idx / 8);
      const aw = checkStone(boardData, 2, x, y);
      if(aw && aw.length) {
        boardData[idx] = 2;
        for(let i = 0; i < aw.length; i++) {
          boardData[aw[i]] = 2;
        }
        nextPoss = getAllAllowPut(boardData, 1);
      }
      step++;
      if(nextPoss && nextPoss.length) break; // 交还给玩家
      updateBoard(boardData, 2, []);
      poss = getAllAllowPut(boardData, 2); // 电脑连续走
    }
    poss = nextPoss || getAllAllowPut(boardData, 1);
    updateBoard(boardData, 1, poss);
    
    if(!poss.length) {
      console.log('游戏结束！');
      const res = boardData.filter(d => d === 1);
      if(res.length > 32) {
        result.innerHTML = '你赢了！';
      } else if(res.length === 32) {
        result.innerHTML = '平局！';
      } else {
        result.innerHTML = '你输了！';
      }
    }
  }
})();

这里面，考虑一个细节，在黑白棋早期，我们的搜索深度不用太深，这里用了四层，到中后期，我们把搜索深度加到六层、十层，因为那时候黑白方行动力都不会太高，搜索分支不会很大，深度增加了，提高了棋力。

目前的AI，如果不是对黑白棋有比较专业的研究的同学，应该是很难取胜的。

整个黑白棋游戏实现就介绍到这里，你学会了吗？有问题欢迎留言讨论。