0x00 前言
很早之前学习flutter时曾写过一个五子棋游戏，但是当时只是基于棋子估值算法实现了一个简单的AI，总感觉不够智能，由于算法一直是我的劣势，且还一直固执的认为一切脱离业务谈算法皆为虚妄，所以就萌生了使用一种人工智能算法去重写五子棋AI机器，也算是将其应用到了实际业务中，毕竟能解决实际问题的算法才是好算法。
0x01 已有的AI实现原理
虽然本文说的是基于alpha-beta剪枝算法AI，但是在此之前还需要先补一些五子棋AI的基础知识，才好继续探讨下去。
那么，试想这么一个场景，当你落完一子之后，此时轮到AI落子，但是棋盘上有那么多空位，究竟应该落子到哪里？这就引出了第一个问题：
如何评估一个位置的好坏？
这句话虽然看起来像是个判断句（一个位置不是好就是坏？）但它绝不是判断句，棋盘上的空位置很多，如果我们能对棋盘上每一个空位置都进行打分，然后以分数高低排序，即每个位置都对应一个分值，其中分值最大的就是当前可落子的最好位置了。
那么接下来的问题就很具体了
设计一个可以给每个空位置打分的方法
首先，如果棋盘是空的，那么你落子在棋盘的边上和落子在棋盘的中间显然效果是不同的，这说明棋子有一个位置得分，且越靠近中心位置越高，就像是一个圆锥，中心区域是最高的，那么就很容易可以想到计算这个位置得分的函数其实就是圆锥方程的变种
棋子位置评分表达式：(x-7.5)^2+ (y-7.5)^2 - z = 0
(注：这个图可以在 https://www.geogebra.org/calculator 生成)
其次，当一个位置相邻的位置也存在自己的棋子时候，可以组成不同的形式，比如：当有两个棋子时，可以构成以下几种形式，具体有如下：
当有三子时，可以构成如下形式：
当有四子时，可以构成如下形式：
当有五子连珠时，已经不需要考虑其他，因为已经获胜，游戏结束了，所以，所有的中间态棋型也就上述几种了，哦，对了，上面只是拿竖直方向举例，实际情况还需要加上水平、左斜、右斜三个方向，但是形势是一样的。
有了上述的几种基本组合形态，我们就可以给一个棋子的组合打分了，只需要检测其周围，看它能构成那种形势，然后加上这个形势的分值既可。经过多次的实验与调整，我得出一套打分标注，基于这个打分标准做出的AI智能程度还不错，可以参考一下：
static const int WIN = 10000;
static const int DEEP_DEATH2 = 2;
static const int LOWER_DEATH2 = 4;
static const int DEEP_DEATH3 = 3;
static const int LOWER_DEATH3 = 6;
static const int DEEP_DEATH4 = 4;
static const int LOWER_DEATH4 = 32;
static const int ALIVE2 = 10;
static const int JUMP_ALIVE2 = 2;
static const int ALIVE3 = 100;
static const int JUMP_ALIVE3 = 10;
static const int ALIVE4 = 5000;
static const int JUMP_ALIVE4 = 90;
写到这儿，我们第一版的AI就已经呼之欲出了，只需要遍历当前棋盘上的空位置，然后逐个计算该空位的得分(位置分+组合分)，然后取分数最高的点落子。
嗯，如果你按照这个思路去写一个AI的话，那么你就可以得到一个人工智障AI，它只会自顾自的落子，压根就不会管对手的落子，为啥呢，因为我们只计算了自己的最优位置，没有考虑对手的位置，所以它只会进攻，不会防守。
为了能让它提升点智商，我们还需要计算对手的最优位置，原理同上，然后再决定是防守还是进攻，这样就不会出现自顾自的落子的问题了，经过我的多次测试经验，发现当 对手的最优位置得分 / 我方最优位置得分 > 1.2 时适合防守，反之适合进攻，代码如下：
Offset bestPosition(BufferMap<Offset> ourPositions , BufferMap<Offset> enemyPositions){
Offset position;
double maxScore = 0 ;
///魔法值 1.2 , 0.7
if(enemyPositions.maxKey() / ourPositions.maxKey() > 1.2){
for (int key in enemyPositions.keySet){
int attackScore = chessmanGrade(enemyPositions[key]);
double score = key * 1.0 + attackScore * 0.7;
if(score >= maxScore){
maxScore = score ;
position = enemyPositions[key];
}
}
}else{
for (int key in ourPositions.keySet){
int defenseScore = chessmanGrade(ourPositions[key]);
double score = key * 1.0 + defenseScore * 0.7;
if(score >= maxScore){
maxScore = score ;
position = ourPositions[key];
}
}
}
return position;
}
到这儿，一个简单的AI就已经完成了，它可以在你无聊的时候陪你玩几局了。不过要是你棋艺高超，它可能就很难赢你了，毕竟它只会看一步棋，也就是永远只会选择下一步最优的位置，对于能一次预测后面几步的你，它就显得很稚嫩了。那么如何能让它也能够一次看多步棋呢，这就终于说到正题了，使用alpha-beta剪枝算法可以让它快速搜索以预测到后几步，从而在当前选择最优的落子位置。
0x02 Max-Min算法搜索博弈树
我们在前面的时候已经得到一个可以按照分值排序的可落子位置列表，那么我们可以尝试把这个列表的每一个位置都落子一次试试，然后我们假设对手的落子总是会取我们得分中最低的一种情况，然后又是我们落子，我们落子的时候肯定会选择使我们得分最大的一种情况，以此往复，就可以得到一颗博弈树了，最终我们选择那个使我们得分最大的情况去落子就可以实现我们在几步之后得分最大的目标，有点难以理解，画个图说吧。
在这颗博弈树中，假设我们当前有两种走法，分别是：B、C；
而如果我们走了B走法，则对方会有E、D两种走法；
当对方走法为E时，我们又有J、K两种走法；
而J走法对应的对方又有U、V、W、X、Y 等5种走法；
假设此时游戏已经分出了胜负或者我们就此打住，不再继续往下推演，我们就到达了这颗博弈树的叶子节点，此时我们可以就当前棋局形式进行打分，如图所示，假设我们最后打分为：
U：24分、V：2分、W：10分、X：10分、Y：7分
由于它的父节点是对手的回合，因此对手肯定会选择我们这些得分中最小的那个，即V节点2分，同理可得K节点为6分；
继续往回推演：由于J、K节点的父节点E为我方回合，因此我们选择这两个中最大的值，即E节点值为6；
以此类推，则可以得出最终得分为2，最优路径为图中红线路径。
理论梳理完毕，转化为算法则是：
1、节点遍历的顺序是从下往上、从左往右
2、如果当前节点为叶子节点，则评估棋局形势
3、若当前节点为对手回合（MIN节点），则其值取子节点中值最小的
4、若当前节点为我方回合（MAX节点），则其值取子节点中值最大的
/// 极大值极小值算法
num maxMinSearch(ChessNode root){
if(root.childrenNode.isEmpty){
return root.value;
}
List<ChessNode> children = root.childrenNode;
if(root.type == ChildType.MIN){
for(ChessNode node in children){
if(maxMinSearch(node) < root.maxValue){
//当前节点的父节点为MIN节点，也就是取所有子节点值中最小的值，
//换句话说：这个父节点产生的最大值不会高于所有子节点中的最小值，因此更新父节点的maxValue
root.maxValue = node.value;
root.value = node.value;
root.checked = node.current;
}else{
// 当前节点的值大于了父节点的最大值，由于父节点是MIN节点，因此不会取该值
// 换句话说：当前为对手回合，对手已经有了一个可以让我方收益更低的选择，因此对手不会考虑一个比让我们当前收益更高的选择
continue;
}
}
}else{//beta
for(ChessNode node in children){
if(maxMinSearch(node) > root.minValue){
// 当前节点的父节点为MAX节点，也就是取所有子节点中最大的值
// 换句话说：这个父节点所产生的最小值不会低于所有子节点中的最大值，因此更新父节点的minValue
root.minValue = node.value;
root.value = node.value;
root.checked = node.current;
}else{
// 当前节点的值小于父节点的最小值，由于父节点值MAX节点，因此不会取该值
// 换句话说：当前为自己回合，已经有了一个可以使我方收益更高的选择，那么就不会再考虑比这个收益更低的选择了
continue;
}
}
}
return root.value;
}
通过这个算法，我们就可以计算出下一步落子何处在接下来的几步中都是对我们最有利的解法。
但是有一个问题，这种算法会遍历每一个节点，随着博弈树的层数增加，要搜索的节点成指数式增长；要解决这个问题，我们就需要引入一个可以提升搜索效率的算法
0x03 Alpha-Beta剪枝算法搜索博弈树
我们在回过头来看上图，在执行到 J->V 的搜素后，我们发现J的最大值不会超过2（J为对手回合，对手会选择我方得分最小的路径），但是J的父节点E为我方回合，我方会选择最大的值，通过 E->K 的搜索可知：E最小不会低于6。既然已经有了一个不低于6的选择，那我们压根儿就没必要再去看一个不高于2的选择中到底还有些什么选择了，因为我们要使游戏更利于己方，所以不会选择J节点这条路径，那么 W、X、Y节点就没有再遍历的必要了（beta剪枝）
相似的，我们再看 G -> M 节点：
当我们计算完M节点的值，发现M节点值为9，而M节点G的父节点是我方回合，我方会选择最大的值，故这个值不会低于9，但是G的父节点C为对手回合，此时它已经有一个1的值，它会选择最小值，1 < 9 ,因此它不会选择9这个值，也就是C节点不会选择G节点，那么G节点就被废弃了，它下的所有节点都没有再遍历的必要了（alpha剪枝）
这样就可以大大缩减所要搜索的节点数量，转换为算法则是：
/// alpha-beta 剪枝算法
num alphaBetaSearch(ChessNode current){
count++;
if(current.childrenNode.isEmpty){
return current.value;
}
//该枝已被剪掉
if(current.parentNode!=null && !current.parentNode.childrenNode.contains(current)){
ChessNode parent = current.parentNode;
return parent.type == ChildType.MAX ? parent.minValue : parent.maxValue;
}
List<ChessNode> children = current.childrenNode;
if(current.type == ChildType.MIN){
num parentMin = current.parentNode?.minValue ?? double.negativeInfinity;
int index = 0;
for (ChessNode node in children) {
index ++;
//当前节点node的父节点(current)为MIN节点，也就是取所有子节点值中最小的值，
//换句话说：这个节点(node)产生的最大值不会高于所有子节点中的最小值，因此取两者间的最小值
num newCurrentMax = math.min(current.maxValue, alphaBetaSearch(node));//K
//current节点的值不能比current.parentNode的最小值还小，
//若不符合这个条件则current节点没有继续搜索下去的必要
//alpha剪枝
if (newCurrentMax <= parentMin) { //V->J
current.childrenNode = current.childrenNode.sublist(0, index);
return parentMin;
}
//因为当前节点为MIN节点，如果发现一个比当前最大值还小的值，则更新当前节点的最大值为这个新值
if (newCurrentMax < current.maxValue) {//A1->K
current.maxValue = newCurrentMax;
current.value = node.value;
current.checked = node.current;
}
}
//当遍历完成当前节点后，如果发现父节点的最小值小于当前节点的最大值，则更新父节点的最小值
if(current.maxValue > parentMin){//K->E
current.parentNode?.minValue = current.maxValue;
current.parentNode?.value = current.value;
current.parentNode?.checked = current.current;
}
return current.maxValue;
}else{//beta(MAX节点)
num parentMax = current.parentNode?.maxValue ?? double.infinity;
int index = 0;
for(ChessNode node in children) {
index ++;
//当前节点(node)的父节点(current)为MAX节点，也就是取所有子节点中最大的值
//换句话说：这个父节点(current)所产生的最小值不会低于所有子节点中的最大值，因此取两者间的最大值
num newCurrentMin = math.max(current.minValue, alphaBetaSearch(node));
//current节点的父节点为MIN节点，如果current节点值的下界(current.minValue)比父节点(current.parentNode)的值的上界还大的话，
//则父节点(current.parentNode)不会取当前节点current路径，故无需在搜索
//beta剪枝
if(parentMax < newCurrentMin){//M->G
current.childrenNode = current.childrenNode.sublist(0,index);
return parentMax;
}
//因为当前节点为MAX节点，如果发现一个比当前最小值还大的新值，则更新当前节点的最小值为这个新值
if(newCurrentMin > current.minValue){
current.minValue = newCurrentMin;
current.value = node.value;
current.checked = node.current;
}
}
//当遍历完成当前节点后，如果发现当前节点的最小值比父节点的最大值还小的话，则更新父节点的最大值
if(current.minValue < parentMax){//D->B
current.parentNode?.maxValue = current.minValue;
current.parentNode?.value = current.value;
current.parentNode?.checked = current.current;
}
return current.minValue;
}
}
0x04 成果体验
最后附上截图、git库地址和apk包(iOS包由于签名问题可以自行clone代码后打包)
-
游戏截图
黑子为普通AI，白子为智能AI APK体验：
app下载1（GitHub）
app下载2（码云，备用下载地址 ）
