上篇文章，介绍了一下五子棋 AI 的入门实现，学完之后能用，就是 AI 还太年老，只能思考一步棋。
本文将介绍一种进步 AI 思考能力的算法：极大极小值算法。
Minimax 算法 又名极小化极大算法，是一种找出失败的最大可能性中的最小值的算法（即最小化对手的最大得益）。通常以递归模式来实现。
Minimax 算法罕用于棋类等由两方较量的游戏和程序。该算法是一个零总和算法，即一方要在可选的选项中抉择将其劣势最大化的抉择，另一方则抉择令对手劣势最小化的一个，其输赢的总和为 0（有点像能量守恒，就像自身两个玩家都有 1 点，最初输家要将他的 1 点给赢家，但整体上还是总共有 2 点）。—— 百度百科
极大极小值搜索算法
算法实现原理
对于五子棋游戏来说，如果 AI 执黑子先下，那么第一步 AI 共有 225 种落子形式，AI 落子到一个点后，示意 AI 回合完结，换到对手（白子）落子，这时对手共有 224 种落子形式。咱们能够将 AI 和对手交替落子造成的所有状况穷举进去，这样就造成了一棵树，叫做 博弈树。
然而，穷举出所有状况太不事实了，这颗 博弈树 最初一层节点数就有 225!，这个数字是特地宏大的，数字 10 后边要加 432 个 0！！！这程序运行起来，电脑还要不要了？
所以，咱们只思考 2 步棋或 4 步棋的状况。
如图所示，我只列举出了走 4 步棋所造成的局部状况。A0 是终点，AI 将在这个点中抉择出最佳的落子点位。A0 上面有两个分支（理论有 225 个分支，这里放不下，就只演示 2 个）A1 和 A2，这两个分支示意的就是 AI 第一步落子的两种状况。
A1 如果落子到 (0,0)，则以后场面就如下图所示
A2 如果落子到 (0,1)，则以后场面就如下图所示
AI 落子完后，就轮到对方落子了。在 A1 分支中，对方有 B1 和 B2 两种落子状况（理论有 224 种）
B1 状况如图所示
B2 状况如图所示
始终到第 4 步落子完时，B5 的场面就会像下图这样
要晓得，这颗 博弈树 是以 AI 的角度建设的，AI 为了赢，它须要从 A1 和 A2 分支中，抉择一个对本人最无利的落子点，而 A1 和 A2 分支的好坏须要它们上面的 B1、B2 和 B3、B4 决定，所以说，上层分支的场面会影响下层分支的抉择。
要确定 A1 和 A2 分支哪个好，咱们必须从这个分支的最深层看起。
B5 ~ B12 节点的场面是由对方造成的，咱们就假如对方很聪慧，他肯定能抉择一个最有利于他本人的落子点。怎么晓得哪个落子点好？还是和之前一样，用评估函数评估一下，分高的就好呗，但有一点不同的是，之前评估的是一个点，当初须要评估一个场面，怎么评估本文前面会提到。
假如 B5 ~ B12 中 各个节点的得分如下图最底部所示
则 A3 节点得分为 0，A4 节点得分为 1，A5 节点得分为 3，A6 节点得分为 2。这就很奇怪了，不是说让选得分最大的吗？这怎么都选的最小的得分？？？
这其实还是要从评估函数说起，因为咱们当初的评估函数都是从 AI 角度登程的，评估的得分越高，只会对 AI 无利，对对方来说是不利的。所以，当是对方的分支的时候，咱们要选得分最低的节点，因为 AI 要站在对方的角度去做抉择，换位思考。这里如果还是没有搞懂的话，咱们能够这么了解：
如果张三遇到了抢劫犯，他认为他身上值钱的货色有：《Java 从入门到入土》、1000 元现金、某厂月薪 3.5K 包吃包住的 Offer。当初抢劫犯要抢劫他身上的一样货色，如果站在张三的角度思考的话，那必定是让抢《Java 从入门到入土》这本破书了，然而站在抢劫犯的角度思考，1000 元现金比什么都强！
这就是思考角度的问题，对方如果很聪慧，那他必定是抉择让 AI 利益最低的一个节点，当初咱们就认为对方是一个绝顶聪明的人，所以在对方抉择的分支里都抉择了分值最低的，好让 AI 的利益受损。
再接下去就是 AI 抉择分支了，不用说，AI 必定选分高的。AI 要从对方给的那些低分分支里抉择分最高的，也就是差的外面选好的。所以 B1 得分为 1，B2 得分为 3。
前面也是一样的流程，又轮到对方抉择了，对方必定抉择 B1 分支，B1 分支是得分最低的节点，所以到最初，A1 分支的最终得分为 1。
咱们对 A2 分支也做如上操作：AI 选高分，对方选低分。最初能够得出如下图所示的后果
当初咱们晓得 A1 最终得分为 1，A2 最终得分为 2，因为 AI 会抉择最大得分的分支 A2，所以最终 A0 得分为 2，也就是说，AI 下一步的最佳落子点为 (0,1)。
AI 抉择的分支肯定是选最高分值的叫做 Max 分支，对方抉择的分支肯定是选最低分值的叫做 Min 分支，而后由低到高，倒推着求出终点的得分，这就是 极大极小值搜寻 的实现原理。
代码实现
咱们接着上次的代码来，在 ZhiZhangAIService 类中定义一个全局变量 bestPoint 用于寄存 AI 以后最佳下棋点位，再定义一个全局变量 attack 用于设置 AI 的防御能力。
/**
* AI 最佳下棋点位
*/
private Point bestPoint;
/**
* 防御系数
*/
private int attack;新增 minimax 办法，编写 极大极小值搜寻 算法的实现代码。这里是应用递归的形式，深度优先遍历 博弈树，生成树和抉择节点是同时进行的。type 示意以后走棋方，刚开始时，因为要从根节点开始生成树，所以要传入 0，并且 AI 最初抉择高分节点的时候也是在根节点进行的。depth 示意搜寻的深度，也就是 AI 思考的步数
，我这边传入的是 2，也就是只思考两步棋，思考 4 步或 6 步都行，只有你电脑吃得消（计算量很大的哦）。
/**
* 极大极小值搜寻
*
* @param type 以后走棋方 0. 根节点示意 AI 走棋 1.AI 2. 玩家
* @param depth 搜寻深度
* @return
*/
private int minimax(int type, int depth) {
// 是否是根节点
boolean isRoot = type == 0;
if (isRoot) {
// 根节点是 AI 走棋
type = this.ai;
}
// 以后是否是 AI 走棋
boolean isAI = type == this.ai;
// 以后分值，int score;
if (isAI) {
// AI 因为要抉择最高分，所以初始化一个难以达到的低分
score = -INFINITY;
} else {
// 对手要抉择最低分，所以初始化一个难以达到的高分
score = INFINITY;
}
// 达到叶子结点
if (depth == 0) {
/**
* 评估每棵博弈树的叶子结点的局势
* 比方：depth= 2 时，示意从 AI 开始走两步棋之后的局势评估，AI(走第一步) -> 玩家(走第二步)，而后对局势进行评估
* 留神：局势评估是以 AI 角度进行的，分值越大对 AI 越无利，对玩家越不利
*/
return evaluateAll();}
for (int i = 0; i < this.cols; i++) {for (int j = 0; j < this.rows; j++) {if (this.chessData[i][j] != 0) {
// 该处已有棋子，跳过
continue;
}
/* 模仿 AI -> 玩家 交替落子 */
Point p = new Point(i, j, type);
// 落子
putChess(p);
// 递归生成博弈树，并评估叶子结点的局势获取分值
int curScore = minimax(3 - type, depth - 1);
// 撤销落子
revokeChess(p);
if (isAI) {
// AI 要选对本人最无利的节点（分最高的）if (curScore > score) {
// 最高值被刷新
score = curScore;
if (isRoot) {
// 根节点处更新 AI 最好的棋位
this.bestPoint = p;
}
}
} else {
// 对手要选对 AI 最不利的节点（分最低的）if (curScore < score) {
// 最低值被刷新
score = curScore;
}
}
}
}
return score;
}
新增模仿落子 putChess 和撤销落子 revokeChess 等办法。
/**
* 下棋子
*
* @param point 棋子
*/
private void putChess(Point point) {this.chessData[point.x][point.y] = point.type;
}
/**
* 撤销下的棋子
*
* @param point 棋子
*/
private void revokeChess(Point point) {this.chessData[point.x][point.y] = 0;
}
新增一个评估函数 evaluateAll，用于评估一个场面。这个评估函数实现原理为：搜寻棋盘上当初所有的已落子的点位，而后调用之前的评估函数 evaluate 对这个点进行评分，如果这个地位上是 AI 的棋子，则加上评估的分值，是对方的棋子就减去评估的分值。留神这里有个防御系数 attack，这个值我当初设定的是 2，如果这个值太低或太高都会影响 AI 的判断，我这边通过测试，感觉设置为 2 会比拟好点。最初就是将 AI 所有棋子的总得分乘以防御系数，再减去对手所有棋子的总得分，作为本场面的得分。
/**
* 以 AI 角度对以后局势进行评估，分数越大对 AI 越无利
*
* @return
*/
private int evaluateAll() {
// AI 得分
int aiScore = 0;
// 对手得分
int foeScore = 0;
for (int i = 0; i < this.cols; i++) {for (int j = 0; j < this.rows; j++) {int type = this.chessData[i][j];
if (type == 0) {
// 该点没有棋子，跳过
continue;
}
// 评估该棋位分值
int val = evaluate(new Point(i, j, type));
if (type == this.ai) {
// 累积 AI 得分
aiScore += val;
} else {
// 累积对手得分
foeScore += val;
}
}
}
// 该局 AI 最终得分 = AI 得分 * 防御系数 - 对手得分
return aiScore * this.attack - foeScore;
}
调整 AI 入口办法 getPoint，当初应用 minimax 办法获取 AI 的最佳落子点位。
@Override
public Point getPoint(int[][] chessData, Point point, boolean started) {initChessData(chessData);
this.ai = 3 - point.type;
this.bestPoint = null;
this.attack = 2;
if (started) {
// AI 先下，首子天元
int centerX = this.cols / 2;
int centerY = this.rows / 2;
return new Point(centerX, centerY, this.ai);
}
// 基于极大极小值搜寻获取最佳棋位
minimax(0, 2);
return this.bestPoint;
}测试一下，因为当初的 AI 能够思考两步棋了，所以比之前厉害了许多。
然而，又因为要搜寻很多个节点，所以响应耗时也变长了很多，思考两步的状况下，均匀响应工夫在 3s 左右。
再去和大佬的 AI 下一把（gobang.light7.cn/#/），思考两步棋的 AI 执黑子先下，曾经能够很轻松的战胜大佬的一般级别的 AI 了。
AI 执白后下的话，连萌新级别的都打不赢，这个应该是评估模型的问题，后续须要对评估模型做进一步的优化。
当初写的搜索算法，如果要让 AI 思考 4 步棋的话，我这一般电脑还是吃不消的，后续对搜索算法还有更多的优化空间。
源码：github.com/anlingyi/xe…