极小化极大搜索
这一章，我们开始介绍博弈论里一个非常经典的算法，叫极小化极大搜索。
首先同样，无论是用何种AI算法，他的目标就是找到下一步最佳的落子位置。我们可以写一个接口。
然后可以用不同的算法去实现，极小化极大搜索只是其中一种算法。
public interface IAIAlgo {
// 对方落子后，做一些处理
void setPieceCallBack(int y, int x, int player, boolean isAI);
// 找到下一步的最佳落子位置
Position aiFindPos();
// 得到棋盘的AI交互算法
IChessboardAIAlgo getChessboardAlgo();
// 得到每个位置的得分，如这个位置可以构成活四，则给高分
IScoreManager getScoreManager();
// 对手的棋子颜色
int getHumanColor();
}
极小化极大搜索，一方所赢就是另一方所输，对于一棵博弈树，可以被分成max层和min层，所谓max层，在实际应用中就代表博弈时自己的回合，在自己的回合想要将自己的利益最大化，所以会遍历博弈树种孩子孩子结点的权值，并回传权值种最大的值，而对于min层，可以理解为对手回合，对手在自己的回合想要将我们的利益最小化，所以会遍历所有的孩子结点并回传最小值，在算法实现中可以用递归来实现。在这样的原理中，就可以通过遍历博弈树，比较每一种情况的权值，找到当前回合的全局最优解或局部最优解。
protected int negamax(boolean isAI, int depth) {
if (chessboardAlgo.isTerminal(getX(idx), getY(idx)) || depth == 0) {
return scoreManager.evaluation(isAI, humanColor);
}
// 返回下一步所有能走的位置，用 y * 15 + x 来把位置存进int
List<Integer> blankList = generateCandidatePiece(isAI);
int resVal = Integer.MIN_VALUE;
for (int nextStep : blankList) {
int y = getY(nextStep), x = getX(nextStep);
addPiece(y, x, isAI);
int value = -negamax(!isAI, depth - 1);
removePiece(y, x, isAI);
resVal = Math.max(resVal, value);
}
return resVal;
}
我们可以看上面的代码，递归第一层，我们是从第二层的NEGAMAX的值返回上来。第二层返回的是人类棋手认为的最优解；人类棋手认为的最优解，是他下了每一步之后，如果是叶子节点，就是局面得分。如果不是叶子节点，就是AI得分。那么在所有AI得分中，我们要取最小值，因为对人类棋手来说，AI得分越低，对人类优势越大。第一层就是评估每一步AI下完之后，人类用最优策略找到的对AI最小值的分数里面，取最大值。因为AI想最大化收益。这就是negamax 的核心思想。
因为一层判最大，一层判最小。所以比较合理的是，写2个函数，相互递归调用对方。这里用了个代码小技巧，就是通过给每一层返回上来的值取相反数。使得递归只需要判最大，就可以实现一层判最大，一层判最小的效果。
如何计算侯选落子
我们可以看到上述代码我们需要一个函数去产生比较优质的落子位置。一个简单的想法是我们可以枚举所有当前棋子相邻距离为1的棋子，作为候选落子。这样做当然是可以，但是不高效。
因为首先可能随着下的子越来越大，这个候选集会越来越大。其次会漏掉一些比较关键的位置，比如我们需要一个跳一步的冲四来构成杀棋。
所以为了更有针对性的去选择落子。我们需要对每个位置进行评分。这个就是我们为何需要一个分数管理模块。他负责高效的计算和更新棋盘和棋子的分数。
private List<Integer> generateCandidatePiece(boolean isAI) {
return scoreManager.generateCandidatePiece(isAI ? aiColor : humanColor);
}
public interface IScoreManager {
// 对棋局进行评分
int evaluation(boolean isAI, int humanColor);
// 找到优质的落子
List<Integer> generateCandidatePiece(int role);
// 下了(y,x)这步棋后，更新相关的落子分数
void updateScore(int y, int x);
// 根据当前的棋局，重新初始化落子分数
void initScore();
// 获得当前位置，ROLE（黑棋/白棋)下棋的分数
int getScore(int y, int x, int role);
}
设计好了接口，就是考虑如何实现。一种简单粗暴的方法，就是每次重新计算落子分数。比如说算落子分数，我们可以看这个位置如果下了黑棋，那么能构成几个活三，几个活四，几个活二。这样其实不太高效，其实我们可以把这个信息缓存下来。那么实际要用的时候，就可以在O(1)的时间去从缓存里读出来。
基于这种方法可以把上面的NEGAMAX的算法深度从3层优化到7层。可见缓存的提速效果是非常大的。
一个更直观的例子是，大概是快了10000倍；（假设一层平均有10个分叉，那么就是10^（7-3））
我们看下这个类需要哪些字段
public class CachedScoreManager implements IScoreManager {
// 用于缓存棋局评分
protected int[][][][] scoreCache;
// 用于缓存落子评分
protected int[][] blackScore;
protected int[][] whiteScore;
// 实时计算落子评分
protected PointEvaluator pointEvaluator;
protected int size;
// 棋盘接口
protected IChessboardAIAlgo chessBoardAlgo;
public CachedScoreManager(IChessboardAIAlgo chessBoardAIAlgo) {
chessBoardAlgo = chessBoardAIAlgo;
size = chessBoardAlgo.getSize();
scoreCache = new int[3][4][size][size];
blackScore = new int[size][size];
whiteScore = new int[size][size];
// 计算完落子得分后，增量更新棋局评分
pointEvaluator = new PointEvaluator(size, chessBoardAlgo, scoreCache);
initScore();
}
下面讲述了如何给定一个棋局，初始化所有的评分。这个方法实现完后，如果我们不写增量更新，依然可以计算，完成AI走棋，就是速度会慢很多。我们运用了多个数组进行缓存，就是为了将来的增量更新。我们先看下全量更新是怎么做的？
@Override
public void initScore() {
for (int j = 0; j < size; j++) {
for (int i = 0; i < size; i++) {
int val = chessBoardAlgo.getValInBoard(i, j);
if (val == 0) {
// 该位置没有棋子的时候，我们只考虑边上2格有棋子时的空位
if (chessBoardAlgo.hasNeighbor(i, j, 2, 1)) {
blackScore[j][i] = pointEvaluator.scorePoint(j, i, Player.BLACK.getId());
whiteScore[j][i] = pointEvaluator.scorePoint(j, i, Player.WHITE.getId());
}
} else if (val == Player.BLACK.getId()) {
blackScore[j][i] = pointEvaluator.scorePoint(j, i, Player.BLACK.getId());
whiteScore[j][i] = 0;
} else if (val == Player.WHITE.getId()) {
blackScore[j][i] = 0;
whiteScore[j][i] = pointEvaluator.scorePoint(j, i, Player.WHITE.getId());
} else {
throw new IllegalStateException("invalid player error");
}
}
}
}
然后我们说下增量更新怎么做。每当有一个新棋子落下时，他可能会影响4个方向的变化，分别是水平，垂直，正对角线，反对角线。我们依次更新这4个方向的相关分数。
@Override
public void updateScore(int y, int x) {
int radius = 10;
for (Direction dir : Direction.values()) {
for (int i = -radius; i <= radius; i++) {
int ny = y + dir.dy * i;
int nx = x + dir.dx * i;
if (ny < 0 || nx < 0 || ny >= size || nx >= size) continue;
updatePointInDirection(ny, nx, dir);
}
}
}
private void updatePointInDirection(int y, int x, Direction dir) {
int role = chessBoardAlgo.getValInBoard(x, y);
if (role != Player.WHITE.getId()) {
int bs = pointEvaluator.scorePoint(y, x, Player.BLACK.getId(), dir);
blackScore[y][x] = bs;
} else {
blackScore[y][x] = 0;
}
if (role != Player.BLACK.getId()) {
int ws = pointEvaluator.scorePoint(y, x, Player.WHITE.getId(), dir);
whiteScore[y][x] = ws;
} else {
whiteScore[y][x] = 0;
}
}
那么其实最核心的我们可以看到，就是如何计算每个落子的分数。
要计算落子分数，我们就需要枚举各种情况。
第一种情况，落子下去到凑成5子连珠，左边和右边都是空的。
第二种情况，或者一边有BLOCK，BLOCK的意思就是走到边界 或者 有对手颜色的棋子。
第三种情况，2边都BLOCK
如果是空的，我们还要考虑空的之后，还有没有自己的连子。比如下图这种情况, 表面上看是个双边空的活三，其实2边都是冲四了；是必胜局势。
[... X _ X X X _ X ...]
那么我们左右分别需要3个变量，记录
- 左边空在哪
- 左边空了一格后，后面接了几个自己的子
- 左边是不是BLOCK
for (int i = 1; true; i++) {
int ny = y + i * curDir.dy, nx = x + i * curDir.dx;
if (outOfBound(ny, nx)) {
rightBlock = true;
break;
}
int val = chessBoardAlgo.getValInBoard(nx, ny);
if (val == 0) {
// 发现一个空格，看空格后面那格还是不是自己的棋
int nny = ny + curDir.dy, nnx = nx + curDir.dx;
if (rightEmptyPos == -1 && !outOfBound(nny, nnx)
&& chessBoardAlgo.getValInBoard(nnx, nny) == role) {
// 如果是自己的棋，这个rightEmptyPos >= 0, 然后把后面的子也统计进rightCnt
rightEmptyPos = rightCnt;
continue;
} else {
break;
}
} else if (val == role) {
rightCnt++;
continue;
} else {
rightBlock = true;
break;
}
}
左边也同理，有了上述信息后，我们需要枚举4类情况。根据左右分别是不是存在隔着1个棋的连子。
private int countToScore() {
if (leftEmptyPos == -1 && rightEmptyPos == -1) {
int count = leftCnt + rightCnt + 1;
if (count >= 5) return Score.FIVE.value;
if (!leftBlock && !rightBlock) return Score.calculateNonEmpty(count, false);
else if (!leftBlock || !rightBlock) return Score.calculateNonEmpty(count, true);
} else if (leftEmptyPos >= 0 && rightEmptyPos == -1) {
int count = leftCnt + rightCnt + 1;
return Score.calculateSingleEmpty(leftEmptyPos, count, leftBlock, rightBlock);
} else if (leftEmptyPos == -1 && rightEmptyPos >= 0) {
int count = leftCnt + rightCnt + 1;
return Score.calculateSingleEmpty(rightCnt - rightEmptyPos, count, rightBlock, leftBlock);
} else if (leftEmptyPos >= 0 && rightEmptyPos >= 0) {
if (leftEmptyPos > rightCnt - rightEmptyPos)
return Score.calculateDoubleEmpty(rightCnt - rightEmptyPos, rightEmptyPos, rightBlock, leftCnt - leftEmptyPos, leftEmptyPos, leftBlock);
return Score.calculateDoubleEmpty(leftEmptyPos, leftCnt - leftEmptyPos, leftBlock, rightEmptyPos, rightCnt - rightEmptyPos, rightBlock);
} else {
throw new IllegalStateException("!!!");
}
return 0;
}
最简单的是2边都没这种情况，那么只要根据2侧有没有被BLOCK。就可以直接算分。
public static int calculateNonEmpty(int count, boolean blocked) {
assert count >= 1 && count <= 4;
switch (count) {
case 1 : return (blocked ? BLOCKED_ONE : ONE).value;
case 2 : return (blocked ? BLOCKED_TWO : TWO).value;
case 3 : return (blocked ? BLOCKED_THREE : THREE).value;
case 4 : return (blocked ? BLOCKED_FOUR : FOUR).value;
}
throw new IllegalStateException("impossible");
}
后面几种情况，处理起来需要分类讨论的会多一些。可以直接到GITHUB上看分类讨论的代码。花一点时间逐个理解各个局势的分数，很快就能看懂。
https://github.com/yixuaz/GomokuAI/blob/main/src/main/java/scorecalculator/PointEvaluator.java
基于缓存的落子的计算，我们已经很大程度提高了搜索速度。
下面为了进一步加速搜索，我们可以做剪枝。在MINMAX中，alpha-beta 剪枝是一种经典的剪枝优化。
alpha-beta 剪枝优化
Alpha-Beta剪枝用于裁剪搜索树中不需要搜索的树枝，以提高运算速度。它基本的原理是：
- 当一个 Min 节点的 β值≤任何一个父节点的α值时 ，剪掉该节点的所有子节点
- 当一个 Max 节点的 α值≥任何一个父节点的β值时 ，剪掉该节点的所有子节点
下面为只使用 MiniMax 和使用 Alpha-Beta 剪枝的简单对比。
简书贴不了图了今天，想学习的小伙伴可以看这篇博客：
https://oi-wiki.org/search/alpha-beta/
那么运用了alpha beta的剪枝搜索代码如下：
protected int negamax(boolean isAI, int depth, int alpha, int beta, int idx) {
if ((chessboardAlgo.isTerminal(getX(idx), getY(idx))) || depth == 0) {
return scoreManager.evaluation(isAI, humanColor);
}
List<Integer> blankList = generateCandidatePiece(isAI);
int resVal = Integer.MIN_VALUE;
for (int nextStep : blankList) {
int y = getY(nextStep), x = getX(nextStep);
addPiece(y, x, isAI);
int value = -negamax(!isAI, depth - 1, -beta, -alpha, nextStep);
removePiece(y, x, isAI);
resVal = Math.max(resVal, value);
if (value > alpha) {
if (depth == firstDepth) {
nextPoint = nextStep;
// 如果已经必胜，不用继续搜索了
if (resVal >= Score.FIVE.value) return resVal;
}
if (value >= beta) return value;
alpha = value;
}
}
return resVal;
}
总结
综上，我们完成了五子棋最基础AI算法的框架，这2步优化，可以让我们的AI 5秒内枚举7步的棋子，但是七步并不能结束游戏时，我们的AI就需要一个评估局面的函数。然后根据这个函数输出的分数，去分析每一步的好坏。
下一章，我们会去介绍，如果设计一个评估函数，和在当前优化的基础上进一步加速我们的搜索，使得可以在10秒内做到9层的搜索。
要知道这个还是非常难的，因为基本上每加一层，耗时就会是原来的10倍，加2层会是100倍。
这一章我希望，你能够从代码中学习到几个基本算法。
第一个就是了解极小化极大搜索的基本思想。
第二个是alpha-beta 剪枝是如何工作，以及代码该如何实现
第三个就是如何利用对每步棋的分数缓存来加速搜索，同时也为我们下一章的评估函数做一个铺垫。
