技能 | 只要五步，教你撸一个缩减版国际象棋AI

AI科技大本营

发布于 2018-04-27 13:37:52

1.6K0

发布于 2018-04-27 13:37:52

文章被收录于专栏：AI科技大本营的专栏

从国际象棋到中国围棋，人类与“机器”已经较上了劲。

看过那么多场对战，你是不是也想上手体验一把？

来来来，简单五步，手把手教你撸一个缩减版的国际象棋AI。

首先，我们来看一些基础概念：

移动生成
棋面评估
Minimax算法
alpha beta剪枝

在每个步骤中，我们将通过一个国际象棋程序技术来改进算法。我将演示每个步骤是如何影响算法的。

你可以在GitHub上查看AI算法的最终版本。

https://github.com/lhartikk/simple-chess-ai

我无法打败自己写的象棋程序，是我太差劲还是算法太强大？

步骤1：移动生成和棋面可视化

在该步骤中，我们使用chess.js 库进行移动生成，使用chessboard.js库可视化棋面。chess.js 库基本上包含国际规则象棋的所有规则。在此基础上，我们可以对给定棋面中所有可行的移动方法进行计算。

https://github.com/jhlywa/chess.js https://github.com/oakmac/chessboardjs/

移动生成功能的可视化。起始位置被用作输入，而从该位置开始的所有可行性移动都是输出。

使用这两个库有助于我们专注于最有趣的任务：创建算法并找到最佳走法。

我们首先构建一个函数，使它可以基于所有可行走法返回一个随机的棋局走法：

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)]; };

这个算法不是一个很强的对手，但是个不错的陪练。

黑子的移动是随机的

体验地址：https://jsfiddle.net/lhartikk/m14epfwb/4

步骤2：棋面评估

我们需要研究在某个特定位置，对战双方哪一方更有优势。想要达到这个目的，最简单的办法是用下方的表格来计算棋盘上每个棋子的相对强度。

通过评估函数，我们可以创建一个算法，该算法能选择评分最高的走法：

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; };

对于我们来说，一个切实的提升——我们的算法可以尽可能地吃掉每个棋子。

通过简单的评估函数，上图黑子已经能进行对弈了，体验地址：

https://jsfiddle.net/lhartikk/m5q6fgtb/1/

步骤3：使用 Minimax 搜索树

通过Minimax算法我们创建了一个简单的搜索树，算法可以从中选择最佳移动方法。在该算法中，可将递归树的所有可能移动探索到特定的深度，并在递归树的子节点处对位置进行评估。

https://en.wikipedia.org/wiki/Minimax

在此之后，我们向父节点返回子节点的最小或者最大值，这取决于黑子移动还是白子移动。（也就是说，我们试图最大化或者最小化每一级的结果）

从“我方”的角度可视化极大极小算法。对于白子来说，最佳移动位置是b2-c3，因为我们确定可以达到评估为-50 的位置

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; } };

通过适当的极大极小算法，我们的算法已经开始理解国际象棋的一些基础策略。

体验地址：https://jsfiddle.net/k96eoq0q/1

步骤四: Alpha-beta 剪枝

Apha-beta剪枝是Minimax算法的优化，允许我们减去搜索树中的一些分支。在相同的资源下，这种方法有助于我们加深Minimax搜对索树的评估。如果发现某个走法会导致更糟糕的局势，那么Alpha-beta 剪枝就会停止评估该分支。这个方法不会影响Minimax算法，相反会提升算法速度。如果一开始就能发现最佳走法，

那么Alpha-beta算法就会更有效。