让我们首先看一下在创建简单的国际象棋人工智能时会遇到的一些基本概念：
我们将逐步将这些添加到最终的算法中，并展示它们对算法的影响。
您可以在 Github 上查看最终版本。
翻译者尝试了最终版本，但不小心挂断了……？
第一步：移动棋子并绘制棋盘
这里我们使用chess.js和chessboard.js分别控制棋子的移动和绘制棋盘。 chess.js库实现了所有棋子的移动规则。 以此为基础，我们可以根据棋局状态得到棋子所有可能的走法。
根据输入的棋盘状态生成所有可能的棋子走法
有了上述两个库，我们就可以专注于最有趣的事情——创建一个能够找到最佳走法的人工智能。
接下来，让我们开始创建这样一个 AI。 我们首先创建一个随机选择所有合法动作之一的方法。
var calculateBestMove =function(game) {
//generate all the moves for a given position
var newGameMoves = game.ugly_moves();
return newGameMoves[Math.floor(Math.random() * newGameMoves.length)];
};
虽然这个AI就像一个刚刚了解规则的新手，但我们已经可以和它下棋了，这是一个好的开始。
随机移动，
点击尝试
第 2 步：董事会状态评估
现在，我们尝试计算一下在棋局的某种状态下哪一方具有优势。 最简单的方法是根据下表计算棋局中剩余棋子的重量。
棋子对应重量表
根据这个方法，我们可以让我们的AI在棋局的某种状态下选择权重最高的着法。
var calculateBestMove = function (game) {
var newGameMoves = game.ugly_moves();
var bestMove = null;
//use any negative large number
var bestValue = -9999;
for (var i = 0; i < newGameMoves.length; i++) {
var newGameMove = newGameMoves[i];
game.ugly_move(newGameMove);
//take the negative as AI plays as black
var boardValue = -evaluateBoard(game.board())
game.undo();
if (boardValue > bestValue) {
bestValue = boardValue;
bestMove = newGameMove
}
}
return bestMove;
};
添加计算权重后氛围，我们的AI会尝试尽可能多地吃掉对手的棋子。
能吃多少就吃多少
点击尝试
第三步：使用极小极大算法探索树
接下来，我们使用 Minimax 算法让 AI 从探索树中选择最佳移动。
首先制作棋盘游戏，我们根据给定的深度递归构造一棵包含棋子所有可能走法的树，并使用上一节的方法计算所有子节点的权重
然后，根据移动的颜色，父节点取子节点的最大值或最小值。 如果子节点是白色的，则将子节点的最大值返回给父节点。 否则，返回最小值。
深度为2时的minimax算法图解
var minimax = function (depth, game, isMaximisingPlayer) {
if (depth === 0) {
return -evaluateBoard(game.board());
}
var newGameMoves = game.ugly_moves();
if (isMaximisingPlayer) {
var bestMove = -9999;
for (var i = 0; i < newGameMoves.length; i++) {
game.ugly_move(newGameMoves[i]);
bestMove = Math.max(bestMove, minimax(depth - 1, game, !isMaximisingPlayer));
game.undo();
}
return bestMove;
} else {
var bestMove = 9999;
for (var i = 0; i < newGameMoves.length; i++) {
game.ugly_move(newGameMoves[i]);
bestMove = Math.min(bestMove, minimax(depth - 1, game, !isMaximisingPlayer));
game.undo();
}
return bestMove;
}
};
添加极小极大算法后，我们的AI不再受别人摆布。
添加了Minimax算法，
点击尝试
极小极大算法很大程度上取决于我们探索深度的能力。 下一步就是对其进行优化。
步骤 4：Alpha-beta 剪枝
Alpha-beta 剪枝是极小极大算法的优化，用于减少搜索树中需要探索的节点数量。 这样，在相同的资源条件下，增加了探索树的搜索深度。
当探索路径的结果比之前探索的结果更差时，α-β 剪枝就会停止搜索该子树。 它不影响minimax算法的计算结果，但加快了minimax算法的计算速度。 无论如何，Alpha-beta 剪枝总能优化计算效率，即使我们最初探索的是最优解。
极小极大算法中使用了 Alpha-beta 剪枝
如下图所示，通过alpha-beta剪枝开发学习，我们可以显着减少极小极大算法的计算次数。
当深度为 4 时，有或没有 alpha-beta 剪枝的计算次数
var minimax = function (depth, game, alpha, beta, isMaximisingPlayer) {
positionCount++;
if (depth === 0) {
return -evaluateBoard(game.board());
}
var newGameMoves = game.ugly_moves();
if (isMaximisingPlayer) {
var bestMove = -9999;
for (var i = 0; i < newGameMoves.length; i++) {
game.ugly_move(newGameMoves[i]);
bestMove = Math.max(bestMove, minimax(depth - 1, game, alpha, beta, !isMaximisingPlayer));
game.undo();
alpha = Math.max(alpha, bestMove);
if (beta <= alpha) {
return bestMove;
}
}
return bestMove;
} else {
var bestMove = 9999;
for (var i = 0; i < newGameMoves.length; i++) {
game.ugly_move(newGameMoves[i]);
bestMove = Math.min(bestMove, minimax(depth - 1, game, alpha, beta, !isMaximisingPlayer));
game.undo();
beta = Math.min(beta, bestMove);
if (beta <= alpha) {
return bestMove;
}
}
return bestMove;
}
};第五步：升级权重计算方式
最初计算权重的方法很简单，就是计算棋盘上棋子对应的权重。 仅凭这一点并不能确定棋局。 为了改善这一点，我们需要考虑棋子在棋盘上的位置。 例如，马在棋盘中间的位置比在边缘的位置更好，因为边缘有更多的选择。
这里我们根据chess-programming-wiki提供的表格稍微修改一下，适应我们的程序。
棋子位置对应的权重表
这样看来，我们的AI已经看起来不错了，至少从业余玩家的角度来看是这样。
优化，
点击尝试
结论
总体而言，我们创建的简单人工智能不会犯愚蠢的错误，但它仍然缺乏大局意识。
通过我上面介绍的方法，我们已经可以让我们的AI进行基本的战斗了。 AI部分（不包括移动棋子）的最终代码不到200行，这意味着实现起来非常简单。 您可以在 Github 上查看最终版本。
我们还可以继续优化我们的AI制作棋盘游戏，比如：
如果您对此感兴趣，可以在国际象棋编程 wiki 中找到更多信息。
谢谢阅读。
更多文章请访问译者博客，已升级为PWA，支持离线访问、订阅和添加到桌面。
