原文链接 Minimax for Gomoku (Connect Five) -- 作者 Ofek Gila
回顾
不知道你是否还记得上一篇文章，我们使用深度优先搜索算法来解决井字棋游戏，递归所有可能的分支，然后找到最佳的游戏结果。因为我们是自底向上搜索，我们能够判断每一步棋是赢、输或者平局，为每位玩家下出最佳的一步棋。这使得解决方案非常简单，原因如下：
- 我们不需要存储或者创建任何类型的游戏树
- 我们只需要检测输赢（这在学习其它算法后会更清晰）
然而，它的主要缺陷让它无法用于稍微复杂的游戏 -- 它的复杂度随着分支因素和深度呈几何级别数地递增，这使得在普通电脑上运行四目游戏（Connect Four）需要数年时间。
极大极小值搜索算法
这个问题最基本的解决方法其实就是深度优先算法的另一种形式，这次我们只是搜索到树一定的深度，而不是一直搜索到游戏的结束（即树的底部）。这给 minimax 带来了额外的复杂性，因为需要一个评估函数 Evaluation Function 来评估这个位置的好坏。你可能需要根据自己编写的启发式评估函数的输出返回 0.8, -0.25 或者 0.001，而不是根据游戏输赢或者平局来返回 1，-1 或者 0。
我要表达的是什么？
用下面的井字棋游戏作为例子：
不管现在轮到谁，X 将会赢下该局。分析函数 analysis function 应该为 X 返回一个正值。但是，玩家的回合在分析功能中仍然起着很重要的角色。比如：
如果不看玩家的回合，局面看起来完全平局，但知道下一步是 X 开始，很明显 X 可以获胜。我们的评估函数应该反映这一点，并为 X 提供非常高的正积分，类似于第一个位置的分数。
你应该对如何为五子棋的位置得分有了某种形式的想法。它应该考虑以下因素：
- 你在一行中控制了多少组连续的方块
- 每组有多长
- 轮到谁
- 每组包含多少个开口端（例如：如果你控制了两个连续的位置，但是没有开放端，这两个位置就不可能连成五子，因此不应该获得任何分数）
要注意的是，你应该计算所有方向（垂直/水平/对角线）的组合，以便为不同的组合计算一些方块。
我知道这很难形象化，所以我们再次使用井字棋来类比：
你应该为 X 计算下面集合：
- 水平
- 一个
X，且只有一个开端 - 两个
X，但是没有开端 - 垂直
- 两个
X，且只有一个开端 - 一个
X，且只有一个开端 - 对角线（左上角到右下角）
- 两个
X，但是没有开端 - 一个
X，且有两个开端 - 对角线（右上角到左下角）
- 一个
X，但是没有开端 - 一个
X，且只有一个开端 - 一个
X，且只有一个开端
对于五子棋来说，我们可以使用类似的方法实现：
代码语言：javascript复制function gomokuShapeScore(consecutive, openEnds, currentTurn) {
if (openEnds == 0 && consecutive < 5)
return 0;
switch (consecutive) {
case 4:
switch (openEnds) {
case 1:
if (currentTurn)
return 100000000;
return 50;
case 2:
if (currentTurn)
return 100000000;
return 500000;
}
case 3:
switch (openEnds) {
case 1:
if (currentTurn)
return 7;
return 5;
case 2:
if (currentTurn)
return 10000;
return 50;
}
case 2:
switch (openEnds) {
case 1:
return 2;
case 2:
return 5;
}
case 1:
switch (openEnds) {
case 1:
return 0.5;
case 2:
return 1;
}
default:
return 200000000;
}
}正如你所看到的，这个函数考虑到了连续数 consecutive，开端数 openEnds 还有轮到谁下棋 currentTurn。轮到你的时候，给到 4 子开端的分数值比对手的高很多。还要注意的是，要为没有开端口的情况设置 0 分。这样的权重分其实是根据实战经验选择的。
这里还有一个重要的环节错过了 -- 找到所有的集合并将它们传递给集合评分函数。如下面所示，我们考虑应用在水平集合中：
代码语言：javascript复制function analyzeHorizontalSetsForBlack(current_turn) {
var score = 0;
var countConsecutive = 0;
var openEnds = 0;
for (var i = 0; i < board.length; i ) {
for (var a = 0; a < board[i].length; a ) {
if (board[i][a] == 'B')
countConsecutive ;
else if (board[i][a] == ' ' && countConsecutive > 0) {
openEnds ;
score = gomokuShapeScore(countConsecutive, openEnds, current_turn == 'black');
countConsecutive = 0;
openEnds = 1;
}
else if (board[i][a] == ' ')
openEnds = 1;
else if (countConsecutive > 0) {
score = gomokuShapeScore(countConsecutive, openEnds, current_turn == 'black');
countConsecutive = 0;
openEnds = 0;
}
else openEnds = 0;
}
if (countConsecutive > 0)
score = gomokuShapeScore(countConsecutive, openEnds, current_turn == 'black');
countConsecutive = 0;
openEnds = 0;
}
return score;
}当然，这是其中一种可能的实现方式，绝不是最快的一种。另外，它只是分析了黑子和水平的方向 -- 真正情况下应该考虑黑白子和所有的方向。你可以将一个玩家的点数减去或者除以另一个玩家的点数。然而，这个方法仍然需要你汇总所有集合所需的函数类型。
现在，我们可以构建我们的分析函数了，我们仍需要使用 minmax 算法去实现它。正如回顾那样，这个方法类似深度优先搜索，因为我们尝试逐个分支让玩家最大化它们的结果，然而，这里我们只是遍历到一定的深度，而不是遍历到游戏结束，我们使用分析函数来判断位置的优劣。
深度 1 的时候，你要简单考虑所有你可能下子的棋盘位置，然后选择一个最适合你的位置下子。
给定上面相同的位置作为例子：
要分析的下一步应该是：
需要注意，在你分析过程中 ，你要假设是对手回合，而不是你的回合！这将使得第三种情况最有利，因为在其它的情况中，X 有一个连续的两子和一端空位（因为这也轮不到它们，虽然你的分析函数可以给出很高的分数）。在这个情况下，你已经成功阻止了它们的胜利。
改善这点很容易，我们目前寻找的是深度 1 或者 1 层 ply(https://en.wikipedia.org/wiki/Ply_(game_theory))（层通常用来表示深度 -- 五层表示深度五）。我们可以通过查看两层，使得我们的人工智能更强大，这就包括你的移动和机器的回应。这就要解释 Minimax 这个名字，当你尝试最大化你的分数时，你的对手正在尝试最小化你的分数 -- 在对手所有最小的回应中，你选择最大值，也就是最适合你的一个位置，然后下该位置的子。你尝试从对手的最小值中获得最大值。当然，增加两层以上是微不足道的，因为你需要做更多相同的事情。
下面是用 javascript 编写的一个很基本的例子：
function bestGomokuMove(bturn, depth) {
var color = bturn ? 'B':'W';
var xBest = -1, yBest = -1;
var bestScore = bturn ? -1000000000:1000000000;
var analysis, response;
var analTurn = depth % 2 === 0 ? bturn:!bturn;
var moves = get_moves();
for (var i = moves.length-1; i > moves.length - aiMoveCheck - 1 && i >= 0; i--) {
board[moves[i][1]][moves[i][2]] = color;
if (depth == 1)
analysis = analyzeGomoku(analTurn);
else {
response = bestGomokuMove(!bturn, depth - 1);
analysis = response[2];
}
board[moves[i][1]][moves[i][2]] = ' ';
if ((analysis > bestScore && bturn) || (analysis < bestScore && !bturn)) {
bestScore = analysis;
xBest = moves[i][1];
yBest = moves[i][2];
}
}
return [xBest, yBest, bestScore];
}正如你所看到的，在每一层中，玩家都尝试最大化它们的收益，然后最小化对手的收益。你会注意到此算法和上一篇文章中的深度优先算法很类似。
你可以使用这种极大极小值算法来构建一个相当合理的 AI，但是还有很多需要改进的地方。我们在后面的文章再讲。你可以尝试玩下我自己的 Gomoku AI。
本文正在参加「金石计划 . 瓜分6万现金大奖」
