1. 算法原理
1.1 博弈树
博弈树针对的是二人零和博弈的问题，二人轮流行动，行动时令自己的优势最大。二人零和博弈有如下特点：
- 确定性：二人的行动有多种选择，但最终的行动是确定的
- 信息完备性：博弈双方知道当前局势（即空间状态）的全部信息
- 零和性：一方的损失等于另一方的收益，二者得分相加恒为零
由以上特点，我们可以构造博弈树。因为信息完备性和确定性，可以用博弈树的每个节点表示一个确定的状态，在动作后得到的新状态作为子节点。对于每个状态都有同一个评价函数来评估双方的得分。因为零和性，一方通过决策使得自身的评价函数尽可能的大，另一方让队手的评价函数尽可能的小。因为二者是轮流行动的，在树的每一层让一方的评价函数取最大和最小交替进行。
由上述的特性，博弈树的搜索过程又被称为minimax搜索。博弈双方行动逐层交替，将评价函数值看做一方的分数，在那一方行动时要让分数尽可能的大，这样的节点被称为Max节点；在另一方行动时要让分数尽可能的小，这样的节点被称为Min节点。
要让一方的下一步采取最优的策略，需要进行树的搜索。在实际问题中，树往往非常大，因此只考虑一定的深度，而不是整个遍历。进行深入搜索时，轮流考虑Max节点和Min节点，每次都采取最优策略，最终得到本步的最优策略。
1.2 Alpha-beta剪枝
通过Alpha-beta剪枝可以对minimax搜索进行剪枝。在博弈树的每个节点保存两个值： α \alpha α表示在该节点能达到的分数的下界，初始化为 − ∞ -\infin −∞， β \beta β表示该节点能达到的分数的上界，初始化为 ∞ \infin ∞。
1.2.1 Max节点的剪枝
Max节点的 β \beta β值初始化时应该为父节点的 β \beta β值。因为Max节点的父节点是Min节点，如果Max节点的 β \beta β值大于父节点的 β \beta β值，Max节点最终得到的估值必然会大于父节点的 β \beta β值，从而表示的状态被不会被父节点选择。
之后，Max节点依次生成子节点。每生成完一个子节点就将子节点的 α \alpha α值传递回来。因为子节点为Min节点，会取到分数的最小值，因此必然会取到它的下界 α \alpha α，也就是说，Min节点最终的的 α \alpha α值就是它的估值。而Max会取子节点中估值最大的，因此，要通过子节点的 α \alpha α值来提高自身评分的下界，也就是说，如果子节点的 α \alpha α值大于自身的 α \alpha α值，则将自身的 α \alpha α值更新为更大的那一个。www.biyezuopin.vip
当 α > β \alpha>\beta α>β时，该节点的估值一定会大于父节点的估值上界，而父节点是Min节点，是必然不会选择当前节点的。因此所有的子节点可以停止拓展，从而实现了剪枝。
12.2 Min节点的剪枝
Min节点的 α \alpha α值初始化时应该为父节点的 α \alpha α值。因为Min节点的父节点是Max节点，如果Min节点的 α \alpha α值小于父节点的 α \alpha α值，Min节点最终得到的估值必然会小于父节点的 α \alpha α值，从而表示的状态不会被父节点选择。
之后，Min节点依次生成子节点。每生成完一个子节点就将子节点的 β \beta β值传递回来。因为子节点为Max节点，会取到分数的最大值，因此必然会取到它的上界 β \beta β，也就是说，Max节点最终的 β \beta β值就是它的估值。而Min节点会取子节点中估值最小的，因此要通过子节点的 β \beta β值来提高自身评分的上界，也就是说，如果子节点的 β \beta β值小于自身的 β \beta β值，则将自身的 β \beta β值更新为更小的那一个。
当 α > β \alpha>\beta α>β时，该节点的估值一定会小于父节点的估值下界，而父节点是Max节点，是必然不会选择当前节点的。因此所有的子节点可以停止拓展，从而实现了剪枝。
2. 流程图和伪代码
2.1 Minimax搜索的实现
本次实现的是人机交互的五子棋，其中五子棋的AI是通过Minimax搜索决定下棋的位置的。
棋盘为11*11大小，棋子使用列表chesses存储，每个元素为一个元组(x, y, color)，表示棋子的位置坐标和颜色。
生成Max节点的过程如下：
生成Min节点的过程如下：
容易看出，二者具有相当的对称性。Min节点和Max节点的生成和剪枝可以用同一个函数通过递归实现。
input:type, state, depth, last_a, last_b
/* 输入：节点类型、 当前状态、深度(越大则越浅)、父节点的α和β值 */
output: act, a, b
/* 输出：当前节点取到极值的动作、当前节点的α和β值 */
def NodeSummon(type, state, depth, last_a, last_b):/* 生成叶子节点则直接打分 */if depth == 0 then return Null, getScore(state),getScore(state)/* 依据节点类型初始化α和β值 */a = -infinb = infinif type == Max then b = last_belse a = last_a/* 遍历每个可行的动作 */for eachAct that possiblenewState = changeState(state, eachAct) /* 依据动作改变当前状态 */_, next_a, next_b = NodeSummon(type, chesses, depth-1, a, b) /* 递归生成子节点 *//* 依据节点类型更新α或β值，保存取极值的状态 */if type == Max && a<next_a thenact = eachActa = next_aif type == Min && b>next_b thenact = eachActb = next_b/* 剪枝判断 */if a>b then return act, a, bendreturn act, a, b
需要注意的是，根节点没有父节点，故父节点的α和β值分别设置为负无穷和正无穷。叶子节点不需要向下拓展，而是直接进行打分。打分同时作为该叶子节点的 α \alpha α和 β \beta β值即可将叶子节点也视作中间节点，方便统一处理。
2.2 分数标准（评价函数的设计）
那么如何给五子棋的棋局打分呢？考虑针对每种颜色进行打分，某一方的分数为：自身颜色的得分减去对手颜色的得分。这样一来就实现了博弈的“零和”条件。五子棋通常是场上连续的相同颜色的子的优势更大，更容易连成五个子，而有时棋手也会有“飞棋”的策略，也就是说，将两部分连续的棋子中间断开一格，当下到这一格将两边连起来时，优势会大幅增加。因此考虑的范围必须必简单的五子棋的“五子”更大。因此这里我每次取六个格子进行评分依据。
对一个棋盘的某种颜色进行打分时，策略如下：依次遍历所有横向、竖向、斜向的连续的六个位置。判断这六个位置的布局，每种布局对应一个分数。以AI为黑色棋子为例，分数具体标准分为如下几个标准：
2.2.1 第一标准：下一步获胜
当AI能够下一步直接制胜时，不要考虑其他任何局势，直接取胜即可。这样一来，取胜的分数就要设置得非常高。同时，要考虑到多层迭代下去，有可能使得连续的子不止五个，应该也给予相当高的分数。
| 棋子状态（下划线表示为空，不列出对称状况） | ●●●●●● | ○●●●●● | _●●●●● |
|---|---|---|---|
| 给分 | 10000 | 10000 | 10000 |
2.2.2 第二标准：防止敌方下一步获胜
当敌方下一步要获胜且自己不能一步制胜时，需要优先拦截对方的棋，而不是自己造棋势。要注意直接相连的棋和飞棋（隔空的棋）。
| 棋子状态 | ●○○○○● | ○○●○○_ | ○○●○○○ | ○○○○●_ | ○○○●○_ | _○○○●○ | ○○○○●○ | ○○○●○○ |
|---|---|---|---|---|---|---|---|---|
| 给分 | 8000 | 8000 | 8000 | 8000 | 8000 | 8000 | 8000 | 8000 |
总的来说，就是对方再下一个子，就能形成五连或者六连，需要将对方封住。
2.2.3 第三标准：下一步造出必胜棋
如果自己和地方都下一步不能制胜，那么考虑下一步造出必胜棋，即下了之后没有获胜，但可以预期之后就能获胜的棋。也就是两端为空四连。在不同的方向进行联动可以造出其他必胜棋的棋型，这里不进行考虑，只考虑单行/列/斜角的一个方向。
| 棋子状态 | _●●●●_ |
|---|---|
| 给分 | 6000 |
2.2.4 第四标准：破坏对方造必胜棋的条件
如果自己造不出必胜棋，且对方已经出现了活三或者2+1的飞棋形式，两端又为空，则需要防止对方造出活四的必胜棋。
| 棋子状态 | _●○○○_ | _○○●○_ | _○○_○● | ●○○_○_ |
|---|---|---|---|---|
| 给分 | 4000 | 4000 | 2000 | 2000 |
2.2.5 第五标准：连棋和堵棋
当自己和对手都不能造出必胜棋和一棋制胜，则尽量连自己更多的子、堵对方的连起来的子。标准较杂，不一一列举。
2.2.6 第六标准：其他
若不符合上述所有标准，则直接打分为0。
3. 代码展示
为了实现用户图形界面，我使用pygame库来展示。
首先定义一些基本的游戏参数：trace为列表，按时间顺序依次记录落棋的位置。chesses为所有的棋子，每个元素的格式为(第几行，第几列，颜色)，其中颜色为0（纯黑）或255（纯白），初始化为-1，即没有棋。cross_num表示棋盘交叉点的个数，即棋盘大小。depth为minimax树的大小。
# 游戏参数
trace = [] # 记录下棋的位置
chesses = {} # 记录所有的落子
cross_num = 11 # 交叉点的个数
depth = 2#int(input())
for x in range(cross_num):for y in range(cross_num):chesses[(x,y)] = -1
4. 实验结果及分析
依据实验题目要求，棋盘落子情况初始化为下：
下面尝试玩家执黑棋先行。一回合之后结果如下：
我尝试做了一个活三（三个连续的黑子，两端为空），AI下了右下的白子。这看上去的确是合理的。AI落子的位置一方面堵住了玩家的活三，同时AI下的位置上两格有一个白子，便于它之后连接成活三。
第二回合结果如下：
我连成一个一端有空的四个连起来的黑子，如此一来，如果AI不拦截的话我下一步就能直接胜利。可以看到，AI的确拦截了。
第三回合：
AI优先做了一个活三。
第四回合：
第五回合：
可以看到，在第五回合我落子后，如果在中点的左上角再下一子，连成两个活三，就必胜了，因此AI必须提前拦住我。它选择了我落子的下方进行落子，这样一来即破坏了我的两个连续的活三，又能制造一个自己的活三。
这五回合AI的得分分别为：
第一回合我有一个活三，因此拉低了AI的得分。而AI通过堵我的活三得到了一些分。第二回合我做出了连续的四个子，AI要马上拦截连续的四个子防止我获胜，于是按照设定，拦截可以拿到很高的分。在第二回合通过拦截，AI的分数急剧提高了。之后的几回合没有出现“马上要获胜”的情况，因此分数没有急剧上升。而被堵住的连续的四个黑子一直都在场上，会重复计算分数，因此分数会一直在较高的水平。
下面尝试让AI先手，并让AI取得胜利。
第一步AI下棋：
第二回合：
我造出了三个活二，因此AI选择进行拦截。
第三回合：
我造了一个2+1的飞棋，AI在拦截飞棋的同时又去拦截上方的活二。
第四回合：
我造了2+2的飞棋，AI必须进行拦截，否则我将胜利。AI的确拦截了。
第五回合：
AI有个活三，我故意不去拦截让AI造出了活四。
第六回合：
我造了个活三，AI优先取得胜利而不是来拦截我的活三。
这五步AI的得分为：
我造了2+2的飞棋，AI必须进行拦截，否则我将胜利。AI的确拦截了。
第五回合：
AI有个活三，我故意不去拦截让AI造出了活四。
第六回合：
我造了个活三，AI优先取得胜利而不是来拦截我的活三。
第二步我一次性造了三个活二，而在评价函数中活二可以出现在多个六个相邻位置的排列中，因此AI的分数骤降。第三个回合我造了2+1的飞棋，如果AI不拦截则会输，所以拦截的分数很高。AI拦截了，分数也提高了很多。之后我连成了四个子，AI不拦截则会输。拦截后AI又提高了很多分。第五回合AI造了活四，得了很高的分，最后一步取得胜利，直接取得胜利的得分比拦截活三高得多，因此AI选择直接取胜而不是拦截我的活三。
