如何使用 chess.js 节点模块实现 minimax

How do I implement minimax with the chess.js node module

我目前正在使用 chess.js、chessboard.js 和 minimax 算法创建国际象棋引擎。我最终想实现 alpha-beta,但现在,我只想让 minimax 起作用。看起来计算机在思考,但它通常只是执行 Nc6。如果我将兵移动到 d4,它通常会与骑士一起移动,但有时它只会在骑士打开的位置来回移动车。如果骑士没有什么可以拿走的,计算机就会移动车或其他一些无意义的移动。我最好的猜测是所有的动作都返回相同的估值,所以它只是在一系列可能的动作中迈出第一步,因此左上角的车是主要目标。我应该注意到,我的部分困惑是关于递归函数的工作方式,我在网上找到的关于递归函数的大部分内容让我比刚开始时更困惑。

我将 Express.js 与 public/javascripts 中的 chessboard.js 配置一起用作包含在 index.ejs 文件夹中的 boardInit.js,当用户移动,一个 Post 请求被发送到 /moveVsComp。它将它发送到服务器,其中 /moveVsComp 的 app.post 函数告诉 chess.js 执行玩家的移动。

玩家走棋记录后,电脑调用computerMoveBlack函数。

post 请求中的函数调用:

  let compMove = computerMoveBlack(3);
  game.load(currentFen)
  game.move(compMove)
  res.status(200).send({snapback: false, fen: game.fen()})

computerMoveBlack 函数:

function computerMoveBlack(depth) {
  let bestMove = ['', 105];
  for (let move of game.moves()) {
    game.move(move)
    let value = minimax(move, depth-1, false)
    if (value < bestMove[1]) {
      bestMove = [move, value]
    }
    game.undo()
  }
  console.log(bestMove[0])
  return bestMove[0]
}

此函数循环遍历所有移动,我之所以使用它,是因为它似乎是保持最佳移动的最佳方式,而不是仅仅返回当前位置的估值。

极小极大函数:

function minimax(node, depth, maximizingPlayer) {
  let value = maximizingPlayer ? -105 : 105
  if (depth === 0 || game.game_over()) return getValuation()
  if (maximizingPlayer) {
    for (let move of game.moves()) {
      game.move(move)
      value = Math.max(value, minimax(move, depth-1, false))
      game.undo()
    }
    return value
  } else {
    for (let move of game.moves()) {
      game.move(move)
      value = Math.min(value, minimax(move, depth-1, true))
      game.undo()
    }
    return value
  }
}

getValuation 函数:

function getValuation() {
  let evalString = game.fen().split(' ')[0];
  let score = 0;
  score += (evalString.split('r').length -1) * -5 || 0;
  score += (evalString.split('b').length -1) * -3 || 0;
  score += (evalString.split('n').length -1) * -3 || 0;
  score += (evalString.split('q').length -1) * -9 || 0;
  score += (evalString.split('p').length -1) * -1 || 0;
  score += (evalString.split('R').length -1) * 5 || 0;
  score += (evalString.split('N').length -1) * 3 || 0;
  score += (evalString.split('B').length -1) * 3 || 0;
  score += (evalString.split('Q').length -1) * 9 || 0;
  score += (evalString.split('P').length -1) || 0;
  return score;
}

我应该指出,我知道在这个用例中使用 FEN 估值非常慢,但我不确定更好的选择是什么。

就像对问题的回顾一样,我试图弄清楚为什么它每次都只是在数组中移动第一步,我的函数格式有什么问题,还有什么更好的方法获得头寸估值与 FEN 的字符串操作相反。

我会在下面指出一些建议,以帮助您入门。首先,我只想说你可能是对的,所有的动作都得到相同的分数,因此它选择了第一个可能的动作。尝试将一些 Piece Square Tables (PST) 添加到您的评估函数中,看看它是否将棋子放在适当的正方形上。

  1. 我会实现 Negamax 函数而不是 Minimax。调试起来更容易,以后进行更多优化时,您不必重复大量代码。 Negamax 是标准国际象棋算法之一。
  2. 看来您自己不会生成合法着法,您知道棋盘在您使用的库中是如何表示的吗?您不想使用 FEN 进行评估,而是希望使用板(或位板)能够进行更高级的评估(更多内容在下方)。
  3. -105/105 的 min/max 值不是一个好方法。改用 -inf 和 inf 以免以后遇到麻烦。

关于评估,您通常使用棋盘表示法来弄清楚棋子是如何放置的以及它们是如何协同工作的。 Chessprogramming.org 是阅读 different evaluation concepts 的重要资源。

对于简单的开始评估,您可以从计算游戏开始时的所有 material 分数开始。然后你在捕获一块时减去相应的块值,因为这是分数发生变化的唯一情况。现在你要一遍又一遍地重新计算很多东西,这会很慢。

如果您想将 PST 添加到评估中,那么您还想根据新旧方块添加移动棋子的棋子价值变化。尝试总结一下评价:

  1. 在游戏开始时总结所有棋子的价值(如果你使用它们,还有 PST 分数)并将其保存为例如whiteScore 和 blackScore
  2. 在你的评估中,如果你吃到一块,你就会从对手那里减去这块价值。否则你保持分数不变,return 照常。
  3. 如果使用 PST,您会根据移动棋子的新位置更改自己的分数。

我希望它有意义,如果您需要任何进一步的帮助,请告诉我。