我在最近撰写五子棋AI程序设计报告时，翻阅了很多的资料博客，但却发现大佬们的博客，没有一篇是能让我只看它就能理解全部的AI算法。在看了众多博客后，我终于对博弈树、极大极小搜索、αβ剪枝恍然大悟，其实这些看似高大上的算法，其背后的想法都十分直白朴素。人们都说刚刚学会一项技能的人，是这个技能最好的老师，所以我便试着写了我这人生中的第一篇博客～
由于这是一篇算法原理博客，旨在让读者理解，里面就不包含代码了。以下关于算法原理的图片，是我从其他博客借鉴的，但是算法的举例分析完全是由刚刚理解的自己撰写，所以只要你一个字一个字地看，保证能明白！！！
废话少叙，上干货——
一、博弈树
（1）博弈的初始格局是初始节点
（2）在博弈树中，双方轮流扩展节点，假设有两方博弈，若A先走则成处于奇数深度的节点都应由A走，所有偶数级都应该由B走。
说白了博弈树就是对于棋盘状况的一种穷举！
以五子棋为例子：
树中长方形结点为己方决策节点，圆圈结点为对方决策节点。每一个节点对应一种局面，有相应的评估函数算出来的分值（针对己方）。其中，每层的节点孩子的数目等于当前决策者所拥有的选择数量，所以博弈树每层节点的孩子数目逐层递减。（图中第一层三个孩子节点，由于我方已经进行决策，对方剩下的的选择数便只有两个，故第二层结点的孩子只有两个。）
二、极大极小搜索
在五子棋中，双方每一次落子，都会创造出一种新的局面。我们设计好计算局势得分的函数（针对A），来计算每一个局面对于A的得分，轮到A拓展结点（选择落子位置，即创造新局面）时，A会选择得分最大的，而B会选择得分最小的（A越糟糕B越开心）。
在决策树中，轮到我方决策层时，我们总希望做出得分最高的决策（得分以我方标准来算）；而在敌方决策层时，我们假定敌方总能够做出得分最小的决策（我方得分最小便是相应敌方得分最高）。所以在博弈树中，每一层所要追求的结果，在极大分数和极小分数中不断交替，故称之为极大极小搜索。
注意啦！！！
由于一些同学提出我原先的MIN、MAX节点定义说的不太清楚，所以为了把知识掰碎了喂给大家，在此给出针对本文内容的确切定义，以下定义只在本文中生效：
1、方块节点：方块节点所在层称作MIN决策层，也就是敌方决策层，敌方会在所有方块节点中选择得分最小的一个
2、圆圈节点：圆圈节点所在层称作MAX决策层，也就是我方决策层，我方会在所有圆圈节点中选择得分最大的一个
示例图片如下：
（请忽略上图中的MAX和MIN（反了），只看图感受就好，个人感觉我的定义更好理解）
我方要做出局势得分最大的决策，故称我方决策层为极大层；敌方要做出局势得分最小的决策，故称敌方决策层为极小层。
MINMAX的基本思想：f(p)指局势分数
- 当轮到敌方走步时，AI应该考虑最坏的情况（即f(p)取极小值）
- 当轮到我方走步时，AI应该考虑最好的情况（即f(p)取极大值）
- 相应于两位棋手的对抗策略，交替使用（1）和（2）两种方法传递倒推值
三、α,β剪枝
在极大极小搜索过程中，我们很明显地注意到，随着AI思考层数的上升，时间复杂度程指数级增长。当思考层数高时AI反应明显变慢，为了解决这个问题，我们采用α,β剪枝算法。
α,β剪枝算法是一种基于深度优先搜索的剪枝算法，示例如下图所示：
假设博弈树的搜索结果如图，正方形为MIN决策层，圆圈为MAX决策层。搜索结果D、E的评分分别为5和4，根据MAX决策准则，如果极小决策者选择C，那么对手势必会选择D，所以C方案所带给极小决策者的得分是5（记为α）。在搜索F方案的过程中，我们发现下一步极大决策者存在得分为6的方案G，所以F方案带给极小决策者的得分必然大于等于6，这个得分大于已经搜索完毕的方案C，所以对于极小决策者来说F方案已经不可能优于C方案，故不再需要计算F的其他子节点情况，剪去F分枝。
上述过程被称之为α剪枝，触发条件是MIN层方案的子结点出现大于α的得分，则剪去该条分枝。
β剪枝同理，触发条件时MAX层方案的子结点出现小于β的得分，则剪去该条分枝。
设游戏的时间复杂度为m^n，n为思考层数，理论上来说，经过排序的剪枝算法可以剪掉一半的n，使得思考层数可以翻倍。
欢迎关注笔者公众号~哥玛萌的小树洞
