市面上比较常用的五子棋算法是博弈树极大极小值alpha-beta剪枝算法，该算法可以分成四个部分来讲解，它们是环环相扣的：博弈树 - 极大极小值搜索 - 负值极大法 -alpha&beta剪枝 。
博弈树
博弈树（Game Tree）是博弈论中的一个概念，用于表示博弈过程中的各种可能走法和对应的结果。它是树结构，树的每个节点表示游戏的一个状态，每个节点的子节点表示在该状态下可能的下一步行动。
由于是树结构，在代码实现上会使用递归，再细分一下可以说是回溯法traceback。
在博弈树中，根节点表示游戏的初始状态，而叶子节点则表示游戏结束的状态。通过遍历博弈树，可以找到最佳的行动策略或评估游戏的结果。
对于两人对弈的游戏，博弈树的每一层交替表示不同的玩家的行动。在五子棋游戏中，轮到某一方行动时，会生成一层子节点，每个子节点代表下一步的落子位置。对于每个落子位置，继续生成下一层子节点，以此类推，直到游戏结束。
但是通常不可能一直类推到游戏结束，走3步的计算时间就很长很长了。
举个例子，假设有一个2*2的五子棋棋盘，黑子先行，下在左上角，如下图：
那么博弈树就如上图构建的这样。根节点为当前棋局，第1步是白子下棋，还剩下3个空位可以下；第2步又轮到黑子下棋，还剩2个空位；如此循环下去……
我们发现对于2x2的棋盘，博弈树一共有3x2x1种路径。对于一个正常的15x15的棋盘，博弈树会有224层224!种路径。那么如何能确定哪一种路径是最优的呢？这就用到了极大极小值思想。
极大极小值搜索Minimax
极大极小值思想是一种在博弈和人工智能领域中常用的方法。在博弈中，可以使用极大极小值搜索算法（如Minimax算法）来确定最佳的下一步行动。算法通过递归地模拟所有可能的游戏状态和对手的反应，然后选择最有利于自己的行动。
在执行极大极小值搜索算法之前，我们需要给每个状态的棋盘进行打分，然后才能用极大极小值搜索算法来比较哪个状态的棋盘是优的。
为棋盘打分 - 评分标准
首先需要一个评分标准。对于五子棋来说，即如果出现了"空白白空空"这样的棋型我们要算多少分，如果出现了"白黑黑黑黑空"这样的棋型我们要算多少分。项目中设计的评分标准如下，并不区分黑白子，1为有子，0为空子：
# 棋型的评估分数 shape_score = [ (50, (0, 1, 1, 0, 0)), (50, (0, 0, 1, 1, 0)), (200, (1, 1, 0, 1, 0)), (500, (0, 0, 1, 1, 1)), (500, (1, 1, 1, 0, 0)), (5000, (0, 1, 1, 1, 0)), (5000, (0, 1, 0, 1, 1, 0)), (5000, (0, 1, 1, 0, 1, 0)), (5000, (1, 1, 1, 0, 1)), (5000, (1, 1, 0, 1, 1)), (5000, (1, 0, 1, 1, 1)), (5000, (1, 1, 1, 1, 0)), (5000, (0, 1, 1, 1, 1)), (500000, (0, 1, 1, 1, 1, 0)), (99999999, (1, 1, 1, 1, 1)) ]
这个评分标准的设计直接影响算法的效果，非常重要。而且，这里的评分标准也不是最优的，只是效果还不错，建议读者自行增加、修改去试试。
为棋盘打分 - 如何累计分数
累计分数也是一个大学问。
本项目的做法是，对于每一个落白子的点A，去遍历A的横、竖、左斜、右斜的四个方向上是否有白子的形状落入评分标准，有的话就记录下最大分值和对应的形状。如果这个点A在四个方向中的某个方向已经被记录过，那么就不在纳入计算了。最后从记录的数组中找一下有没有相交的点，有的话得分加倍。
黑子也是这样计算。
最终棋盘的分数 = 我方颜色棋子总得分 - 敌方棋子总得分 * 权重。
所以其实白子、黑子都有参与到计算中来。权重体现了电脑的进攻性，可配置。
极大极小值思想
极大极小值思想的目的是为了找到博弈树最优的一条路径。
极大极小值思想考虑的是在对手也采取最优策略的情况下，我们能够保证的最小收益或最大损失。
在上图中，假设最后一层分数为1、2、3、4、5、6，那么它们的上一层是我方，我方取对自己有利的（取max），所以第三层还是1、2、3、4、5、6，第二层是敌方，他会取对我方最不利的分数（取min），所以是1、3、5，第一层是我方，取max=5。
总结一下，当前黑子下完了，白子落子搜索到了第二层节点值为5的那个节点的落子坐标。
因为是回溯，所以树肯定是从下往上看。
负值极大法Negamax
对于敌方而言，取得是最小。但是如果也让敌方取最大，只是最后加一个负号，那么不也相当于取最小吗？？而且这样会简化我们的代码，使得我们的代码变得更少更优雅。于是就产生了负值极大法。
其实是使代码像天书一样抽象难看懂。。。。
负值极大法（Negamax）是一种基于极小化搜索树的博弈算法。它基于一个基本的观察：对于一个玩家而言，最好的策略与对手的最差策略是等价的。因此，通过将对手的收益取负值，问题可以转化为一个极大化搜索问题。
这两种算法本质上是相似的，只是表达方式不同。在Negamax算法中，通过将对手的收益取负值，将问题转化为一个极大化搜索问题；而在Minimax算法中，通过交替最大化和最小化的方式，在博弈树中搜索最佳决策。
AI算法的厉害之处还在于你会往下递归几步，15x15的棋盘可以递归224步，有224!种路径，意味着你要从第224层往第一层回溯，估计只有超算才行了。
通常我们递归3层就224x223x222=1108,9344个叶子节点了。于是，聪明的人对其进行了优化， 这就是alpha-beta剪枝搜索。
alpha-beta剪枝
Alpha-beta剪枝是一种用于优化极大极小搜索（Minimax Search）算法的技术，它可以有效地减少搜索的节点数，从而提高搜索效率。Alpha-beta剪枝算法在Minimax搜索的基础上引入了两个参数：alpha和beta。
在Minimax搜索过程中，每个玩家都追求最大化自己的收益或最小化对手的收益。在搜索的过程中，当某个节点的值超出了alpha到beta的范围时，可以通过剪枝操作来减少对该节点以及其子节点的搜索。
具体来说，当搜索到一个节点时，会先搜索其子节点，并递归地进行下去。在递归返回之后，根据当前玩家是最大化还是最小化玩家，对alpha和beta进行更新。如果alpha的值大于等于beta的值，那么当前节点的搜索可以提前结束，不再搜索其余子节点，因为它们不会影响当前玩家的最佳选择。
通过不断更新alpha和beta的值，可以在搜索的过程中动态地减少搜索的节点数，从而大幅度提高搜索效率。Alpha-beta剪枝算法的关键在于正确地维护alpha和beta的值，并且按照正确的顺序遍历子节点，以确保剪枝操作的正确性。
特别重要 - 剪枝过程
如上图，α为已知的最大值， β为已知的最小值， 因为还没搜索不知道是多少，保险起见，初始化为-∞ 和+∞。
1 => 首先，深度优先遍历，会遍历到第四层第一个节点值为1，它的父节点属于Max层，那么把α置为1，说明这个父节点只接收>=1的值。
2 => 接着回溯到了第二层第一个节点，由于每返回一层它们的α、β值是互换的，所以此时这个节点说它只接收<=1的值。
3 => 接着遍历到第四层第二个节点值为2，它的父节点属于Max层，那么把α置为2，说明这个父节点只接收>=2的值。此时问题来了，第三层第二个节点>=2，第二层第一个节点<=1，产生冲突，把第三层第二个节点为根的子树剪掉，因为第三层第二个节点>=2表示我这个子树肯定是>=2了，但是它的父节点只要<=1的，那还要你干嘛？
4 => 那么回溯到根节点，根节点现在变成>=1的了。
5 => 接着遍历到第四层第三个节点值为3，它的父节点属于Max层，那么把α置为3，说明这个父节点只接收>=3的值。
6 => 此时回溯到了第二层第二个节点，由于每返回一层它们的α、β值是互换的，所以此时这个节点说它只接收<=3的值。
7 => 接着遍历到第四层第四个节点值为2，它的父节点属于Max层，那么把α置为2，说明这个父节点只接收>=2的值。而它的父节点是>=3，所以不剪枝，同时回溯，覆盖父节点的范围，变成<=2。
8 => 那么又回溯到根节点，根节点之前是>=1的，现在被覆盖，变为>=2。
9 => ……其他同理……
因为我图画的简陋，所以看不出来剪枝的妙处。但是可以想象一下上图被剪枝的部分，如果它们节点有很多，那么除了左子树，它们的右子树都不会再需要遍历了。
值得注意的是，Alpha-beta剪枝算法适用于满足最优化原则的博弈问题，即一个玩家的收益等于另一个玩家的损失。它能够在保证找到最优解决方案的前提下，大大减少搜索的节点数，提高搜索效率。然而，如果搜索树的分支因子很高，或者搜索深度很大，仍然可能需要相当大的计算资源来完成搜索。因此，在实际应用中，仍然需要结合启发式评估函数等其他优化技术来进一步提高效率。
