一.简介：
有今天这篇博客是因为最近在做一个lua版的象棋游戏（忽略lua效率不高这件事），在做游戏的PVE功能的过程中需要实现一个简单的象棋AI，于是对于象棋AI进行了一番研究，研究的主要资料来源于象棋巫师。下面的内容也主要是对于最大最小算法和AlphaBeta算法理解的一个记录。对于棋类AI，目前没有深入了解的打算，只要能实现我的游戏的基础功能即可，而且我接触棋类AI的实践也才几天，所以这篇博客也主要是记录我自己的理解，难免会有一些理解不到位甚至理解错误的地方，如果您有幸看到了这些内容，您可以在评论区告知我，非常感谢。
我刚开始试图理解算法时是直接看的最大最小算法的部分，说实话，看得是很懵的，直到我看到了评价函数，才将之前看到的算法实现给串联起来。我想我之所以直接看算法很困难，是搞错了顺序，所以我也试图按照我理解的顺序去组织这篇文章。这篇文章主要按照评价函数--博弈树--最小最大算法--AlphaBeta算法的顺序展开。
二.评价函数
首先我们谈到评价函数，因为这是棋类游戏AI的核心部分。我在我前两天的博文中大概梳理了一下中国象棋中的评价函数（中国象棋评估函数建模），您可以作为参考，因为我对这个评价函数做了很多简化。这里我们主要强调评估函数是什么，以及它的作用。
评估函数是评估什么的呢？现在我们可以将自己代入为一个象棋AI，现在该我下棋了，我想知道我该怎么下。作为一个AI，在程序设定的象棋规则内，我现在能够找到很多种不同的着法，那么该选择哪一种着法呢？很容易想到我可以给不同的着法进行评分，使用数学模型去量化这个着法的好坏，这样作为一个AI，我就可以通过比较这个量化的结果来比较不同的着法，找到其中最好的着法。这个量化着法好坏的数学模型在程序中使用一个函数去实现它，这个函数就是我们的评价函数。评价函数应该就是AI程序的核心内容，因为它使得AI可以评判不同决策的优劣，评价着法的数学模型越精确，AI也就表现得越“聪明”。
那么评价函数该评价哪些方面呢？一个显然的事情是，在棋类游戏中我们的一个着法的好坏不是取决于这个着法本身，同样的一步棋因为在不同的局面中导致的结果一定是不一样的，所以我们评判的应该是在下完棋后的整体棋局双方的优势程度，选择各种着法中完成后对AI方最优势的棋盘格局。在象棋中，一般从双方棋子的数量、位置、灵活度、相互牵制等方面去评判当前双方的优劣，利用这些衡量标准去建立我们的数学模型并用程序实现它就有了我们的评价函数。
三.博弈树（搜索树）
刚才在谈到评价函数时，我们说可以让计算机评价每一种着法的优劣，选择其中最有利于AI方的着法，这就可以视作一个深度为1的博弈树模型。下图是一个博弈树（图片来自于象棋巫师的文章）：
这是一个井字棋的博弈树，可以看到博弈树本质就是使用树形结构去描述接下来选择着法的不同棋盘可能性，每一种可能性的棋盘都是一个节点，未落子前的棋盘作为根节点，由其经过一步着法产生的棋盘各种棋盘布局作为其子节点，这一层深度为1，接下来又会衍生出深度为2的各种子节点，以此类推。理论上，随着深度的增加，子节点的数量是指数级增加的。对于博弈树，我们可以总结出以下规则：
1.奇数层的节点是由AI着棋后产生的；2.偶数层的节点是由玩家着棋后产生的；3.如果某个节点是叶子节点（没有子节点），那么这个节点的棋盘布局应该是有一方获胜或是判定为和棋。
四.最小最大算法
我们看到对于棋盘可能的发展，我们使用了博弈树去描述它，而且在实际搜索下一步的着法时，我们不希望AI只是根据一步棋后的棋盘布局就决定（搜索深度为1），因为当下可能一些着法不能立即带来收益，但是在多轮后会带来更大的收益，这种情况在棋类游戏中经常出现，所以我们希望AI能多看几步（加深搜索深度），这时就需要去模拟双方博弈的过程：
如果我们的评价函数的返回值越大代表棋盘局面AI优势越大，返回值越小代表玩家优势越大，那么在博弈树的奇数层（AI着棋），AI就会希望最后的结果越大越好，而在博弈树的偶数层（玩家着棋），我们会假设玩家也是理性的，那么玩家则一定会倾向于评价函数的返回值小的棋局结果，这便是最大最小的名称来源，在搜索时根据深度的不同应该选择最大或者最小的结果作为AI或玩家的着棋预测。下面是一个简单的搜索树，我们使用它来详细分析以下如何进行最大最小搜索：
可以看到A节点是根节点，有3个子节点，这3个子节点又分别有3个子节点，这些子节点的子节点的棋盘布局评价值如图中所示。这个搜索树最下面一层节点并非是叶子节点，还是有子节点的，只是我们没有画。这是一个搜索深度为2的搜索树，这个树中我们没有计算每一个节点的评价值，只是计算了搜索深度节点的评价值。我们可以做出这样的推导，现在AI想要在两步后棋局达到最优，那么显然应该是24，但是玩家会让AI如愿吗？显然不会，因为搜索深度为2的这一层节点是由玩家选择着法形成的，所以这一层玩家应该会选择最小值，也就是说玩家会选择8、6、5这三个节点对应着法中的一种，那么我们就将这3个节点值作为B、C、D节点的评价值（B、C、D的深度值不用计算），显然AI继续评价A节点的着法时应该选择B、C、D节点中的最大值8，也就是B节点，这样AI获得的预期收益最大。相信你也看出来了，对于一个规定了深度的搜索树来说，我们只需要计算最后一层节点或叶子节点的评估值，上层节点的评估值无需计算由最后一层节点依次取得最大值或最小值向上类推确定，取最大还是最小由当前层是玩家决定着法还是AI决定着法来确定，这样我们就合理地预估了在规定步骤（深度）AI想取得预期最大收益双方的着法选择。
五.负值最大函数--最大最小搜索的优化
我们每一次确定上一层的节点的评估值时都需要根据当前节点层数确定取最大值还是最小值，我们可以使用每次将计算出的评估值取相反数的方式来简化逻辑，这样我们就可以每一层节点都取最大值了。
六.Alpha-Beta搜索算法
最大最小算法有一个明显的问题，就是我们的节点产生是指数增长的，相应的运行评估函数的次数也是指数增长。最后一层节点的节点数可以用m的n次方来确定，n是搜索深度，m是当前游戏平均每一步的可能着法数，像国际象棋每一步就平均有35种可能着法，35的n次方增大的速度太快了，搜索深度不可能太深，所以我们需要简化不必要的节点评估值计算，也就是简化搜索树，AlphaBeta算法就可以理解为一种简化后的最大最小搜索。下图是一个部分搜索树示意，我们可以梳理以下是如何简化的：
可以看到，F、G、H、I节点是由玩家确定的着法产生的，而接下来由AI确定着法了，当我们计算完F的各种着法的评价值后我们知道如果走到了F这一步，那么我们应该会选择12这一步的着法（选出最大的），所以F的评价值为12，然后继续搜索G节点，发现G节点的第一种着法的评价值就是15，也就是说G节点的评价值至少是15，但是F、G、H、I这四个节点中玩家大概率会选择最小值，那么玩家就不会选择G节点，既然G节点最终会被抛弃（B节点的评价值不会由G节点产生），那么G节点下其他的着法的评价值也就没有必要计算了。12这个值就可以暂时作为我们的Beta值，也就是F、G、H、I节点中目前找到的玩家可以选择的最坏结果，一旦F、G、H、I中某个子节点的评价值高于12，就舍弃整个节点，而F、G、H、I中一旦某个评价值比Beta值12低，就将Beta值更新（这个Beta值就是最后B节点的评价值）。换言之，当玩家发现选择G节点会让AI获得至少15的评价值时，是不会让AI如愿的。在评估F、G、H、I这四个最大值节点的过程中，Beta值作为AI会获得的上限值存在，如果某个评价值高于Beta，就可以舍弃掉节点下的其他评价值计算，直接返回这个评价值，正所谓在最坏的中选最好的，F已经如此坏（12）了，G可能更坏（至少15）吗？同样地，在最小值节点地评价值计算过程中也应该会有一个评价值的下限（图片来自于：最清晰易懂的MinMax算法和Alpha-Beta剪枝详解）:
如图，圆圈是最小值节点，方块是最大值节点，从左下角开始看，当我们首先遍历得到最小值节点H的值为3时，接下来最大值节点D的值应该至少是3，此时再遍历H节点的兄弟节点I的子节点，当遍历到第一个子节点值为2时，说明I的节点值最多是2（I是最小值节点，其他比2大的子节点值不会取），这时实际上H节点就确定了一个下限3，当I节点的子节点值小于下限3时，就可以直接将这个值（2）作为I节点的值返回，因为I节点反正也会被舍去，所以究竟有多小也就无所谓了。这个下限就是Alpha值。换言之，当AI发现玩家可能取得2这个更小的评价值时，是不会让AI如愿的，所以AI也就舍弃了I节点。
总结：1.Alpha-Beta算法更多被叫做Alpha-Beta剪枝算法，它还是基于最大最小算法的，是对最大最小算法的运算优化，只是去除了其中大量的多余运算。
2.在评估最大值节点下的几个最小值子节点的过程中，可以计算完一个子节点后合理地确定一个上限Beta，当其他兄弟节点的子节点值高于Beta时就直接将子节点值作为兄弟节点值返回，舍去其他兄弟节点的子节点运算，如果低于上限Beta就更新上限Beta；同样地，在评估最小值节点下的几个最大值子节点时，可以计算完一个子节点后确定一个下限Alpha，当其他兄弟节点的子节点值低于Alpha时舍去整个兄弟节点值得计算，当高于Alpha时更新Alpha。
3.因为所有得节点值都会汇总到根节点，所以这个上限值Beta和下限值Alpha是全局通用得，也就是说全局只需要确定一组Alpha值和Beta值即可，最后计算得到得根节点值一定是Alpha值或是Beta值