五子棋 - JavaScript 实现 -人机交互

theme: fancy

上一篇文章五子棋 - JavaScript 实现 - 两人对战我们介绍了人与人之间下棋，还挖了个坑：讲人机交互下棋。不知不觉中，把自己打包给卖了，本文就是来补坑的。

我们一步步来讲解，详细的代码，请跳转到文末。

基本术语

我们先来了解一下五子棋的基本术语。因为之前是介绍人和人玩，只要形成五子相连就行了，可以对概念不理解。但是这是人机娱乐，总得让机器知道五子棋的规则，不然机器乱下就没意思了。

1 代表黑子，-1 代表白子，0 代表空格。以黑子为主要说明，白子同理

连五：五个同色的棋子连成一条线，则有 [1, 1, 1, 1, 1]
活四：有两个可以形成的五子连珠的点，并且连续的四子，则有 [0, 1, 1, 1, 1, 0]
冲四：有且只有一个点可以形成连五的四，则有跳冲 [-1, 1, 0, 1, 1, 1]，[-1, 1, 1, 0, 1, 1]，[-1, 1, 1, 1, 0, 1]，[1, 0, 1, 1, 1, -1]，[1, 1, 0, 1, 1, -1]，[1, 1, 1, 0, 1, -1]，和连冲 [-1, 1, 1, 1, 1, 0]，[0, 1, 1, 1, 1, -1]
活三：能够形成活四的三个点，则有连活三 [0, 1, 1, 1, 0, 0]，[0, 0, 1, 1, 1, 0]，和跳活三 [0, 1, 0, 1, 1, 0]，[0, 1, 1, 0, 1, 0]
眠三：能够形成冲四而不能形成活四的三，类似冲四，则有 [-1, 1, 1, 1, 0, 0]，[-1, 1, 1, 0, 1, 0]， [-1, 1, 0, 1, 1, 0]，[0, 0, 1, 1, 1, -1]，[0, 1, 0, 1, 1, -1]， [0, 1, 1, 0, 1, -1]，[-1, 1, 0, 1, 0, 1, -1]，[-1, 0, 1, 1, 1, 0, -1]，[-1, 1, 1, 0, 0, 1, -1]， [-1, 1, 0, 0, 1, 1, -1]
活二：能够形成活三的二子，类似活三，则有 [0, 0, 1, 1, 0, 0]， [0, 1, 0, 1, 0, 0]，[0, 0, 1, 0, 1, 0]，[0, 1, 1, 0, 0, 0]，[0, 0, 0, 1, 1, 0]，[0, 1, 0, 0, 1, 0]。
眠二：能够形成眠三而不能形成活三的二子，意义不大，不做计算。当然，读者可以添加
活一：同理，能形成活二的一子
眠一：同理，能形成眠二而不能形成活二的一子
天元：指棋盘中间的点。这里人机交互，默认是机器执黑子先落子。棋盘预设是 15 * 15，所以，天元的位置是 [7, 7] 的坐标。

这里的代码有点长，不贴代码。可进入文末的项目查看。好了，机器知道了必要的棋局（这里计算了关键的连五、活四、活三、活二、冲四、眠三）。

关键得分

棋局知道了，那么，我们得知道对应棋局的分值，来计算玩家和机器的目前得分情况，以便机器明确自己要进攻还是防守。赋分如下：

代码语言：javascript复制

/*
* 预设不同的组合对应的得分
* @param { number } w 连五
* @param { number } u2 活二
* @param { number } u3 活三
* @param { number } u4 活四
* @param { number } c3 眠三
* @param { number } c4 眠四
* @return { number } 当前棋局的得分情况
*/
function valueCombo(w, u2, u3, u4, c3, c4) {
  // ...
  return 0;
}

棋局的评分是针对四个方向进行统计，也就是对横线，竖线，正斜线（角度45^。）和反斜线（角度135^。）四条线上的数据统计。

代码语言：javascript复制

/*
* 获取当前的组合
* @param { array[][] } node 棋盘节点情况
* @param EnumRoles.BLACK | EnumRoles.WHITE curPlayer 当前玩家
* @param { number } i 棋盘横轴遍历
* @param { number } y 棋盘横轴遍历
* @param { number } dx 棋盘横轴偏移位置
* @param { number } dy 棋盘纵轴偏移位置
* @return { array[] } combo 返回当前方向的当前玩家的节点情况，比如 [0, 0, 0, 0, -1, 0, 0, 0, 0]。combo.length 最长为 9 = 2 * gameSize - 1
*/
function getCombo(node, curPlayer, i, j, dx, dy) {
  let combo = [curPlayer];
  // ...
  return combo
}

当然，我们也可以使用这种方法来判断输赢。

代码语言：javascript复制

/*
* 检查输赢，针对四个方向进行判断
*/
function checkWin() {
  for (let i = 0; i < cellsCount; i  ) {
    for (let j = 0; j < cellsCount; j  ) {
      if (curState[i][j] == 0) continue;
      let playerVal = combinations.valuePosition(
    // 水平方向
        getCombo(curState, curState[i][j], i, j, 1, 0),
    // 竖直方向
        getCombo(curState, curState[i][j], i, j, 0, 1),
    // 正斜线方向
        getCombo(curState, curState[i][j], i, j, 1, 1),
    // 反斜线方向
        getCombo(curState, curState[i][j], i, j, 1, -1)
      );
      if (playerVal === combinations.winValue) {
        win = true;
      }
    }
  }
};

或者读者可以使用五子棋 - JavaScript 实现 - 两人对战中判断输赢的方法

机器落子

人机模式下棋，初始化机器先落子于天元的位置。

代码语言：javascript复制

// 实例化
let gobangMachine2Person = new GobangMachine2Person({
    role: EnumRoles.WHITE,
    gobangStyle: {
        count: cellsCount,
        borderColor: '#bfbfbf'
    }
})
// 落子于天元的位置
gobangMachine2Person.drawChessman({ x: 7, y: 7 }, true);
// 设置当前角色
gobangMachine2Person.setCurrentRole();
// 设置提示信息
gobangMachine2Person.setResultMsgHint();

然后监听人落子后，基于其落子位置，机器思考最优落子位置：

代码语言：javascript复制

listenDownChessman() {
  this.checkerboardDom.onclick = event => {
    // ...
    // 基于白子的落子位置，算出机器的落子位置
    let answer = login.makeAnswer(x, y);
    // 绘制黑子
    this.drawChessman({
      x: answer[0],
      y: answer[1]
    }, true);
  }
}

那么，机器的最优子落子位置 login.makeAnswer(x, y) 是如何算出来的呢？

这里的最优，是相对而言；并不是整个棋盘最合适的那个落子位置，是绝对而言。最合适这个位置需要遍历整个棋盘，会很耗电脑，得不偿失，具体可以参考文章深度优先搜索实现 AI 井字游戏

我们通过极大极小值算法，算出最最优位置。我们先对极大极小值算法有个概念：

Minmax 算法又名极小化极大算法，是一种找出失败的最大可能性中的最小值的算法（即最小化对手的最大得益）。通常以递归的形式来实现。

先挖个坑，后面有文章详细讲解这个搜索算法。还有 Alpha-beta 剪枝这个搜索算法。不知不觉又挖了两个坑...本文，读者有个概念就行了~ 最主要捋清楚人机的整个流程...

代码语言：javascript复制

/*
* 获取最优的落子
* param { number } x 白子落点 x 轴
* param { number } y 白子落点 y 轴
* return { array[] } 返回最优落子位置
*/
getLogic.makeAnswer = function(x, y) {
  let answ = [-1, -1]; // 预设的最佳位置，在棋盘外，这个随便
  // 获取候选值
  let c = getChilds(curState, maxPlayer);
  let maxChild = -1;
  let maxValue = Number.MIN_VALUE; // 最小的正值
  for (let k = 0; k < c.length; k  ) {
    // 计算当前的得分值
    let curValue = miniMax(c[k], 0, -maxPlayer, curState);
    if (maxValue < curValue) {
      maxValue = curValue;
      maxChild = k; // 获取最大值的索引
    }
  }
  // ...
  
  return answ;
}

完整项目

代码片段

项目可以进行人机，双人娱乐。当然，读者可以根据实际情况，添加诸如 悔棋，复盘 等辅助功能。

参考文章

极大极小值算法
对抗搜索
五子棋基本棋形及特点
五子棋AI进阶：极大极小值搜索
五子棋算法设计

本文正在参加「金石计划 . 瓜分6万现金大奖」

编程算法腾讯云开发者社区 javascript

0 人点赞