博弈树启发式搜索的α-β剪枝技术研究

实验二：利用α-β搜索过程的博弈树搜索算法编写一字棋游戏(3学时)一、实验目的与要求（1）了解极大极小算法的原理和使用方法，并学会用α-β剪枝来提高算法的效率。

（2）使用C语言平台，编写一个智能井字棋游戏。

（3）结合极大极小算法的使用方法和α-β剪枝，让机器与人对弈时不但有智能的特征，而且计算的效率也比较高。

二、实验原理一字棋游戏是一个流传已久的传统游戏。

游戏由两个人轮流来下，分别用“X”和“O”来代替自身的棋子。

棋盘分9个格，双方可以在轮到自己下的时候，可以用棋子占领其中一个空的格子。

如果双方中有一方的棋子可以连成一条直线，则这一方判胜，对方判负。

当所有的格子都被占领，但双方都无法使棋子连成一条直线的话，则判和棋。

这是一个智能型的一字棋游戏，机器可以模拟人与用户对弈。

当轮到机器来下的时候，机器会根据当前棋局的形势，利用极大极小算法算出一个评价值，判断如何下才对自身最有利，同时也是对方来说对不利的，然后下在评价值最高的地方。

另外利用α-β剪枝，使机器在搜索评价值的时候不用扩展不必要的结点，从而提高机器计算的效率。

在用户界面方法，用一个3×3的井字格来显示用户与机器下的结果。

当要求用户输入数据的时候会有提示信息。

用户在下的过程中可以中途按下“0”退出。

当用户与计算机分出了胜负后，机器会显示出比赛的结果，并按任意键退出。

如果用户在下棋的过程中，输入的是非法字符，机器不会做出反应。

三、实验步骤和过程1.α-β搜索过程在极小极大搜索方法中，由于要先生成指定深度以内的所有节点，其节点数将随着搜索深度的增加承指数增长。

这极大地限制了极小极大搜索方法的使用。

能否在搜索深度不变的情况下，利用已有的搜索信息减少生成的节点数呢？设某博弈问题如下图所示，应用极小极大方法进行搜索MINIMAX过程是把搜索树的生成和格局估值这两个过程分开来进行，即先生成全部搜索树，然后再进行端节点静态估值和倒推值计算，这显然会导致低效率。

α-β剪枝算法例题α-β剪枝算法是一种用于优化博弈树搜索的算法，它通过剪去不必要的搜索分支来减少搜索空间，从而提高搜索效率。

下面我将以一个简单的例题来说明α-β剪枝算法的应用。

假设我们有一个简化的棋盘游戏，双方轮流在棋盘上放置棋子，每个棋子的位置可以用一个坐标表示。

游戏的目标是找到双方都无法再放置棋子的最佳位置。

我们可以用一个博弈树来表示游戏的状态和可能的走法。

每个节点表示游戏的一个状态，边表示一次棋子的放置。

叶子节点表示游戏结束的状态，双方都无法再放置棋子。

我们的目标是找到一个最佳的叶子节点。

现在，我们来看一个简化的博弈树：A./ | \。

B C D./|\ / \。

E F G H I.在这个博弈树中，A是根节点，B、C、D是A的子节点，E、F、G是B的子节点，H和I是D的子节点。

每个节点都有一个评估值，表示当前状态的好坏。

我们可以使用α-β剪枝算法来搜索博弈树，找到最佳的叶子节点。

算法的基本思想是，在搜索过程中维护两个值，α和β。

α表示当前玩家的最好选择，β表示对手的最好选择。

在搜索过程中，我们从根节点开始，递归地向下搜索子节点。

对于每个节点，我们根据当前玩家是最大化还是最小化来更新α和β的值。

如果β小于等于α，表示对手已经找到了一个更好的选择，我们可以剪掉当前节点的搜索分支，不再继续搜索。

具体地，我们可以使用以下伪代码表示α-β剪枝算法：function alphabeta(node, depth, α, β,maximizingPlayer):if depth = 0 or node is a terminal node:return the heuristic value of node.if maximizingPlayer:value = -∞。

for each child of node:value = max(value, alphabeta(child, depth 1, α, β, FALSE))。

注意，由于示例问 题格局数非常少， 我们可以给出完整 的格局树。这种情
况下我可以找到 Minimax算法的全 局最优解。而真实 情况中，格局树非 常庞大，即使是计 算机也不可能给出 完整的树，因此我 们往往只搜索一定 深度，这时只能找
到局部最优解。
这些轮到甲 方的节点叫 做max节点， max节点的 值是其子节 点最大值。 Min节点则
Alpha-Beta 剪枝算法
什么是Alpha-Beta 剪枝算法
• Alpha——beta修剪是一种搜索算法，它试图减少在搜索树中由极 小极大算法评估的节点数量。它是一种对抗性的搜索算法，通常用 于两玩家游戏（井字游戏、棋类、围棋等）的机器游戏。当至少有 一种可能性被发现时，它就会停止完全评估一个动作，这证明了这 一举动比之前检查过的动作更糟糕。这些举措不需要进一步评估。 当应用到标准的极小极大树时，它会返回与minimax相同的移动， 但是去掉那些不可能影响最终决策的分支。
相反。 最终完整赋 值的格局树
如下：
在上面的例子 中，根节点的 价值为20，表 示如果对方每 一步都完美决 策，则我方按 照上述算法可 最终拿到20元， 这是我方在 Minimax算法 下最好的决策。 格局转换路径 如下图红色路
径所示：
• 那这跟alpha-beta剪枝算法有什么关系呢？
• 由于Minimax算法有一个很大的问题就是计算复杂性。它所需 搜索的节点数随最大深度呈指数膨胀，而算法的效果往往和深 度相关，因此这极大限制了算法的效果。
• Alpha-beta算法可以看成变种的Minimax，基本方法是从根节点 开始采用深度优先的方式构造格局树，在构造每个节点时，都 会读取此节点的alpha和beta两个值，其中alpha表示搜索到当 前节点时已知的最好选择的下界，而beta表示从这个节点往下 搜索最坏结局的上界。由于我们假设对手会将局势引入最坏结 局之一，因此当beta小于等于alpha时，表示从此处开始不论最 终结局是哪一个，其上限价值也要低于已知的最优解，也就是 说已经不可能此处向下找到更好的解，所以就会剪枝。

局的例子
15
S0
S1 -1
S2 1
S3 -2
S4
S5
6-5=1
6-5=1
4-5=-1
5-4=1
6-4=2
5-6=-1
5-6=-1
4-6=-2
5-5=0
5-5=0
5-5=0
6-6=0
16
图3 一子棋的极大极小搜索
MAX在初始节点时应该怎么走…
b.MIN走步必然选择对自己最有 利的一步,如节点的估计值是-2
3 A
a1
a2
a3
a.MAX走步必然选择对自己最有利的 一步,如A节点的估计值是3 b.MIN走步必然选择对自 己最有利的一步,如D节 点的估计值是2 获得根节点取值的那一 d3分枝，即为所选择的最 佳走步
MIN
3 B
b2 b3 c1
2C
c2 c3 d1
2D
d2
b1
3
12 8
2
4
6
14
5
2
定义一个静态估计函数f,以便对棋局的叶子节点作出优劣估值 1.首先按照一定的搜索深度生成出给定深度d以内的所有状态， 计算所有叶节点的评价函数值。 极大极小搜索方法是一种在有限搜索深度范围进行求解的方法.
一字棋游戏极小极大树
MAX在第二步应该怎么走…
一字棋游戏极小极大树
α -β 剪枝
在极小极大搜索方法中，由于要先生成指定深度以内的所 有节点，其节点数将随着搜索深度的增加呈指数增长。这极 大地限制了极小极大搜索方法的使用。
α-β剪枝的基本思想:
边生成博弈树边计算评估各节点的倒推值，并且根据评估 出的倒推值范围，及时停止扩展那些已无必要再扩展的子节 点，即相当于剪去了博弈树上的一些分枝，从而节约了机器 开销，提高了搜索效率。

题目:智能五子棋游戏一、实验目的理解和掌握博弈树的启发式搜索过程和α-β减枝技术，能够用某种程序语言开发一个五子棋博弈游戏。

二、实验要求（1）设计一个15行15列棋盘，要求自行给出估价函数，按极大极小搜索方法，并采用α-β减枝技术。

（2）采用人机对弈方式，对弈双方设置不用颜色的棋子，一方走完后，等待对方走步，对弈过程的每个棋局都在屏幕上显示出来。

当某一方在横、竖或斜方向上先有5个棋子连成一线时，该方为赢。

（3）提交一篇实验论文，以及完整的软件（包括源程序和可可执行程序）和相关文档。

三、实验原理①估价函数的设计：下子后，求在该点的所有8个方向上4格之内的所有的没有阻隔的白子的和加上没有阻隔的黑子的数目之和，和为估价函数的值。

直观来说就是，如果在该点下子后连成同颜色的棋子越多，该点的估价值越大，同时阻挡另一种颜色的棋子越多，估价值也越大。

②判断是否有一方胜出：设计is_win函数，在每一次下子后检查是否是终局（一方胜出或者棋盘下满和局）。

对于棋盘上每一个已经下了棋子的点，检查其4个方向上是否有连续5颗同颜色的棋子，若有，则有一方胜出。

③寻找候选点，用于建立博弈树：对于棋盘上每一个还没有下子的点，测试其附近8个点是否已经下了棋子，若有，把该点加入候选点。

④搜寻最佳着点：根据候选点建立3层的博弈树，再利用估价函数对节点进行比较，得出最佳着点。

四、代码人主要代码public void refreshMax(int n){switch(n){case 1:{ //更新预测棋盘1最大值及其坐标maxValue1=0;number1=0;for(int i=0;i<size;i++){for(int j=0;j<size;j++){if(preBoard1[i][j]>maxValue1){maxX1.clear();maxY1.clear();maxX1.add(i);maxY1.add(j);number1=1;}else if(preBoard1[i][j]==maxValue1){maxX1.add(i);maxY1.add(j);number1++;}}}break;}case 2:{ //更新预测棋盘2最大值及其坐标maxValue2=0;number2=0;for(int i=0;i<size;i++){for(int j=0;j<size;j++){if(preBoard2[i][j]>maxValue2){maxX2.clear();maxY2.clear();maxX2.add(i);maxY2.add(j);number2=1;}else if(preBoard2[i][j]==maxValue2){maxX2.add(i);maxY2.add(j);number2++;}}}break;}case 3:{ //更新预测棋盘3最大值及其坐标maxValue3=0;number3=0;for(int i=0;i<size;i++){for(int j=0;j<size;j++){if(preBoard3[i][j]>maxValue3){maxX3.clear();maxY3.clear();maxX3.add(i);maxY3.add(j);number3=1;}else if(preBoard3[i][j]==maxValue3){maxX3.add(i);maxY3.add(j);number3++;}}}break;}case 4:{ //更新预测棋盘4最大值及其坐标maxValue4=0;number4=0;for(int i=0;i<size;i++){for(int j=0;j<size;j++){if(preBoard4[i][j]>maxValue4){maxX4.clear();maxY4.clear();maxX4.add(i);maxY4.add(j);number4=1;}else if(preBoard4[i][j]==maxValue4){maxX4.add(i);maxY4.add(j);number4++;}}}break;}case 5:{ //更新预测棋盘5最大值及其坐标maxValue5=0;number5=0;for(int i=0;i<size;i++){for(int j=0;j<size;j++){if(preBoard5[i][j]>maxValue5){maxX5.clear();maxY5.clear();maxX5.add(i);maxY5.add(j);number5=1;}else if(preBoard5[i][j]==maxValue5){maxX5.add(i);maxY5.add(j);number5++;}}}break;}case 6:{ //更新预测棋盘6最大值及其坐标maxValue6=0;number6=0;for(int i=0;i<size;i++){for(int j=0;j<size;j++){if(preBoard6[i][j]>maxValue6){maxX6.clear();maxY6.clear();maxX6.add(i);maxY6.add(j);number6=1;}else if(preBoard6[i][j]==maxValue6){maxX6.add(i);maxY6.add(j);number6++;}}}break;}case 7:{ //更新预测棋盘7最大值及其坐标maxValue7=0;number7=0;for(int i=0;i<size;i++){for(int j=0;j<size;j++){if(preBoard7[i][j]>maxValue7){maxX7.clear();maxY7.clear();maxX7.add(i);maxY7.add(j);number7=1;}else if(preBoard7[i][j]==maxValue7){maxX7.add(i);maxY7.add(j);number7++;}}}break;}}}AI主要代码public void refreshMax(int n){switch(n){maxValue1=0;number1=0;for(int i=0;i<size;i++){for(int j=0;j<size;j++){if(preBoard1[i][j]>maxValue1){maxValue1=preBoard1[i][j];maxX1.clear();maxY1.clear();maxX1.add(i);maxY1.add(j);number1=1;}else if(preBoard1[i][j]==maxValue1){maxX1.add(i);maxY1.add(j);number1++;}}}break;}maxValue2=0;number2=0;for(int i=0;i<size;i++){for(int j=0;j<size;j++){if(preBoard2[i][j]>maxValue2){maxValue2=preBoard2[i][j];maxX2.clear();maxY2.clear();maxX2.add(i);maxY2.add(j);number2=1;}else if(preBoard2[i][j]==maxValue2){maxX2.add(i);maxY2.add(j);number2++;}}}break;}maxValue3=0;number3=0;for(int i=0;i<size;i++){for(int j=0;j<size;j++){if(preBoard3[i][j]>maxValue3){maxValue3=preBoard3[i][j];maxX3.clear();maxY3.clear();maxX3.add(i);maxY3.add(j);number3=1;}else if(preBoard3[i][j]==maxValue3){maxX3.add(i);maxY3.add(j);number3++;}}}break;}maxValue4=0;number4=0;for(int i=0;i<size;i++){for(int j=0;j<size;j++){if(preBoard4[i][j]>maxValue4){maxValue4=preBoard4[i][j];maxX4.clear();maxY4.clear();maxX4.add(i);maxY4.add(j);number4=1;}else if(preBoard4[i][j]==maxValue4){maxX4.add(i);maxY4.add(j);number4++;}}}break;}maxValue5=0;number5=0;for(int i=0;i<size;i++){for(int j=0;j<size;j++){if(preBoard5[i][j]>maxValue5){maxValue5=preBoard5[i][j];maxX5.clear();maxY5.clear();maxX5.add(i);maxY5.add(j);number5=1;}else if(preBoard5[i][j]==maxValue5){maxX5.add(i);maxY5.add(j);number5++;}}}break;}maxValue6=0;number6=0;for(int i=0;i<size;i++){for(int j=0;j<size;j++){if(preBoard6[i][j]>maxValue6){maxValue6=preBoard6[i][j];maxX6.clear();maxY6.clear();maxX6.add(i);maxY6.add(j);number6=1;}else if(preBoard6[i][j]==maxValue6){maxX6.add(i);maxY6.add(j);number6++;}}}break;}maxValue7=0;number7=0;for(int i=0;i<size;i++){for(int j=0;j<size;j++){if(preBoard7[i][j]>maxValue7){maxValue7=preBoard7[i][j];maxX7.clear();maxY7.clear();maxX7.add(i);maxY7.add(j);number7=1;}else if(preBoard7[i][j]==maxValue7){maxX7.add(i);maxY7.add(j);number7++;}}}break;}}}五、感想通过这个试验，我对估价函数，极大极小搜索方法，α-β减枝技术有了更全面的认识，对它们的运用也更加熟练。

博弈原理
• 参加博弈的各方都希望己方取得胜利。因此，当一方 面临多个行动方案选择时，博弈的各方总是要挑选对 自己最为有利而对对方最不利的那个行动方案。 • 假如A方的目标：尽可能使自己达到最大（或最高）的 分数分枝节点，可用“或”关系来描述，称之为MAX方 节点； • 而当轮到B方行动时，B方的目标：尽可能使A方获得最 小（或最低）的分数分枝节点，这对A方来说，这些行 动方案或分数分枝节点之间，可以用“与”关系来描 述，是由MIN方自主进行控制的，故又称之为MIN节点 。
-搜索策略
• 在极大极小值算法基础上增加了剪枝功能, 并 采用深度优先策略进行搜索。
• α值和β值：对于一个极大节点来说，为了剪除某些分 枝，应该取其子节点中的最大倒推值，把它作为当前 下界的参考，称此值为α值；对于一个极小节点来说， 应取其子节点中的最小倒推值，把它作为当前上界的 参考，称此值为β值。
博弈原理
• 博弈树有如下特点：
（1）博弈的初始格局总是要求从初始节点出发，为寻求某个
确定的方向而选取行动方案； （2）在博弈树中，由于双方轮流地扩展节点，“或”节点和
“与”节点逐层交替出现。如果自己一方扩展的节点之间是
“或”关系，则对方扩展的节点之间是“与”关系。 （3）把本方获胜的终局定义为本原问题，相应最优搜索路径 上的节点是可解节点，而所有使对方获胜的终局和属于对方 最优搜索路径上的节点则是不可解节点。此外，所有其它的
判断游戏是否结束效用函数或称目标函数对终止状态给出一个数值如输赢和平局以0表示双方的初始状态和合法招数定义了游戏的博弈树此为博弈搜索最优解是导致取胜的终止状态的一系列招数博弈原理参加博弈的各方都希望己方取得胜利
博弈搜索 1. 极大极小决策
2. –剪枝

4.15
• 设有如图4.35所示的博弈树，其中最下面的 数字是假设的估值，请对该博弈树做如下 工作：
– 计算各节点的倒退值； – 利用α-β剪枝技术剪去不必要的分支。
4.15
S0 A C D E B F
G
H
I
J
K
L
M
N
0
5
-3
3
3
6
-2
3
5
4
-3
0
6
8
9
-3
4.15 解答
S0 A C ≥0 D E B F
G
0
H
≤-3
I
J
K
L
M
N
0
5
-3
3
3
6
-2
3
5
4
-3
0
6
8
9
-3
4.15 解答
S0 A C ≥0 0 ≤0 D ≥3 E B F
G
0
H
≤-3
I
3
J
K
L
M
N
0
5
-3
*
3
6
-2
3
5
4
-3
0
6
8
9
-3
4.15 解答
≥0 S0 A C 0 ≤0 D ≥3 E ≥4 B F
G
0
H
≤-3
I
3
*
K
4
L
-3
M
N
α-β剪枝技术 知识点 剪枝技术-剪枝技术
• α-β剪枝技术 剪枝技术 首先分析极小极大分析法效率，上述的极小极大分析法，实际是先生成一棵博弈树，然后再计 算其倒推值，至使极小极大分析法效率较低。于是在极小极大分析法的基础上提出了α-β剪枝技术 。 α-β剪枝技术的基本思想或算法是，边生成博弈树边计算评估各节点的倒推值，并且根据评估 出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分 枝，从而节约了机器开销，提高了搜索效率。具体的剪枝方法如下： (1) 对于一个与节点MIN，若能估计出其倒推值的上确界β，并且这个β值不大于 MIN的父节点( 一定是或节点)的估计倒推值的下确界α，即α≥β，则就不必再扩展该 MIN节点的其余子节点了(因为 这些节点的估值对MIN父节点的倒推值已无任何影响 了)。这一过程称为α剪枝。 (2) 对于一个或节点MAX，若能估计出其倒推值的下确界α，并且这个α值不小于 MAX的父节点( 一定是与节点)的估计倒推值的上确界β，即α≥β，则就不必再扩展该MAX节点的其余子节点了(因为 这些节点的估值对MAX父节点的倒推值已无任何影响 了)。这一过程称为β剪枝。 从算法中看到： (1) MAX节点(包括起始节点)的α值永不减少； (2) MIN节点(包括起始节点)的β值永不增加。 在搜索期间，α和β值的计算如下： (1) 一个MAX节点的α值等于其后继节点当前最大的最终倒推值。 (2) 一个MIN节点的β值等于其后继节点当前最小的最终倒推值。

alphabeta剪枝算法原理Alpha-Beta剪枝算法原理一、引言Alpha-Beta剪枝算法是一种用于搜索树的算法，用于提高搜索效率。

在博弈树等搜索问题中，搜索空间往往非常庞大，传统的搜索算法需要遍历所有可能的节点，耗费大量时间和计算资源。

而Alpha-Beta剪枝算法通过剪去不必要的节点，大大减少了搜索空间，提高了搜索效率。

二、算法原理Alpha-Beta剪枝算法是基于Minimax算法的改进。

Minimax算法是一种博弈树搜索算法，用于在双方对抗的情况下选择最优的决策。

它通过递归地遍历博弈树，计算每个节点的值，然后根据节点的深度和玩家角色选择最优的决策。

Alpha-Beta剪枝算法在Minimax算法的基础上，引入了Alpha和Beta两个参数，用于剪枝。

具体来说，Alpha表示玩家1（Max玩家）当前的最佳选择值，Beta表示玩家2（Min玩家）当前的最佳选择值。

在搜索过程中，如果某个节点的值超出了Alpha或Beta的范围，就可以剪掉该节点及其子树，因为对当前玩家来说，该节点及其子树的值不会被选择。

三、算法步骤1. 初始化Alpha和Beta为负无穷和正无穷，分别表示玩家1和玩家2的最佳选择值；2. 对于当前节点，递归地遍历其子节点。

如果当前节点是Max节点，遍历所有子节点，并更新Alpha值；如果当前节点是Min节点，遍历所有子节点，并更新Beta值；3. 在遍历子节点的过程中，进行剪枝操作。

如果某个节点的值超出了Alpha或Beta的范围，就可以剪掉该节点及其子树；4. 根据Alpha和Beta的更新情况，判断是否进行剪枝。

如果Beta 小于等于Alpha，说明已找到最佳决策，可以提前终止搜索；5. 递归地返回父节点，并将当前节点的值传递给父节点。

如果当前节点是Max节点，返回最大值；如果是Min节点，返回最小值；6. 重复步骤2-5，直到搜索完成。

四、优势与应用领域Alpha-Beta剪枝算法在搜索空间庞大的问题中具有明显优势。

文章标题：深入探讨Alpha-Beta算法及Zillmer修正方法一、引言在计算机科学领域中，Alpha-Beta算法是一种用于减少博弈树搜索的一种优化技术。

Zillmer修正方法是对Alpha-Beta算法的一种改进，能够更好地提高搜索效率和性能。

本文将从简单到复杂，由浅入深地探讨Alpha-Beta算法及Zillmer修正方法，以便读者能更全面地理解这一主题。

二、Alpha-Beta算法的基本概念1. 什么是Alpha-Beta算法Alpha-Beta算法是一种用于减少博弈树搜索的一种优化技术，它通过剪枝的方式来避免搜索不必要的分支，从而提高搜索效率。

2. Alpha-Beta算法的原理在搜索过程中，Alpha-Beta算法会维护两个变量：Alpha和Beta。

其中，Alpha表示当前最好的选择，Beta表示对手的最好选择。

通过比较Alpha和Beta的值，可以确定是否进行剪枝，从而减少搜索的分支。

3. Alpha-Beta算法的应用及局限性Alpha-Beta算法在博弈树搜索、人工智能等领域得到了广泛的应用，但也存在一些局限性，比如对于某些特定的游戏状态，它可能无法有效地剪枝。

三、Zillmer修正方法的改进1. Zillmer修正方法的提出Zillmer修正方法是对Alpha-Beta算法的一种改进，它通过引入额外的修正值来提高搜索效率和性能。

2. Zillmer修正方法的原理在搜索过程中，Zillmer修正方法会根据当前搜索的情况，动态地计算并更新修正值，从而更加准确地评估当前的搜索情况，提高搜索效率。

3. Zillmer修正方法的应用及改进效果Zillmer修正方法在实际的应用中能够显著提高Alpha-Beta算法的搜索效率和性能，特别是对于一些复杂的游戏状态，它能够更好地优化搜索过程。

四、个人观点及总结个人观点：Alpha-Beta算法及Zillmer修正方法对于优化博弈树搜索具有重要的意义。

摘
要： 博弈是启发 式搜 索的一个重要应用领域 ， 博弈的过程可以用一棵博 弈搜 索树表示 ， 通过对博弈树进行搜 索求取 问题的解 ，
剪枝 过程 中剪掉 更 多 的分 枝 ， 高搜 索效 率 。 提
搜索策 略常采用 剪 枝技术。 入研究 剪枝技术的基础 提出 展未 规定 在深 上， 在扩 达到 深度节点时， 对扩展出 的子节点 按照
ｃ ｉ ｎ ｄ ｓ ｒ ｉｓ ｒ ｄ ｎ ｏ ａ — ｌｙ ｎ — ｒ ｅ ｒｍ ｌｒ ｅ ａｕ ｏ ｅ ｔ ｔ ｎ ｕ ｃ ｏ ｔ ｓ ｌ ｎ ｗｈ ｎ ｈ ｎ ｄ ｏ ｏ ｈｌ ｄ ｏ ｅ ａ ｅ ｎ ｅ ｅ ｉ ｔ ｇ ｍｅ ｐ ａ ｉ ｇ ｔ ｆｏ ｔ ｅ ａ ｇ ｖ ｌ ｅ ｆ ｓｉ ｉ ｆ ｎ ｔ ｎ ｏ ｍａ ｌ ｅ ｍａ ｏ ｉ ｏ ｅ ｔ ｅ ｏ ｅ ｆ ｎ
估 价 函 数 大 小顺 序 插 入 到 搜 索 树 中 ， 而在 从 关键 词 ： 弈 ； 发 式搜 索 ； 剪枝 博 启 ＤＯＩ １． ７／ｉ ｎ１０ — ３ １ ０ ８１ ．１ 文章编 号：０ ２ ８ ３ （０ ８ １－ ０ ４ ０ 文献标识码 ： 中图分类号 ：Ｐ ８ ：０３ ８ｊｓ ． ２ ８ ３ ． ０ ． ０６ ７ ．ｓ ０ ２ ６ １０ — ３ １２ ０ ）６ ０ ５ － ２ Ａ Ｔ ｌ
ｔｅ ． ｐｈ ｒ ｅＡ１ ａ—ｂｅａ ｔ ｐｒ ｎ ｎ ｉ ａ ｗａ ｓ ｕ ｉ ｇ ｓ ｌ ｙ ｕｓ ｄ ｏ ｐｒ ｌｍ ｓ ｌｉ ｇ ｙ ｅ ｒ ｈｉｇ ｈ ｇａ ｅ—ｐ ａ ｉｇ—ｔｅ ．ｎ ｈｓ ｅ ｆｒ ｏｂｅ ｏｖ ｎ ｂ ｓ ａ ｃ ｎ ｔ ｅ ｍ ｌ ｙｎ ｒ ｅＩ ｔ ｉ ｐａ ｅ ，ｈ ｐ ａ ｗｈｉｈ ｐ ｒ ｔｅ ｌ ｎ ｃ
掌握在 曰的手里 ， 任何一个方案都有 可能被 日选 中， Ａ必须防

alphabeta剪枝算法原理Alpha-Beta剪枝算法原理引言：在人工智能领域，博弈树搜索是一种常见的算法，用于解决两个对手之间的决策问题。

而Alpha-Beta剪枝算法则是一种优化博弈树搜索的方法，它通过剪去不必要的搜索分支，大大减少了搜索的时间复杂度，提高了搜索效率。

本文将详细介绍Alpha-Beta剪枝算法的原理及其应用。

一、博弈树搜索博弈树搜索是通过构建一棵树来表示博弈的决策过程。

树的每个节点表示一个决策点，树的边表示决策的选项。

对于每个节点，可以根据某种评估函数来确定它的分值。

通过搜索博弈树，可以找到最优的决策序列。

二、极小极大算法极小极大算法是一种常用的博弈树搜索算法，它在树上进行深度优先搜索，通过对叶子节点进行评估，逐层向上选择最优的决策。

该算法中的每个节点都有一个值，对于极大节点，它的值是其子节点中最大的值；对于极小节点，它的值是其子节点中最小的值。

三、Alpha-Beta剪枝算法的原理Alpha-Beta剪枝算法是对极小极大算法的一种优化方法，它通过剪去不必要的搜索分支，减少了搜索的时间复杂度。

具体来说，Alpha-Beta剪枝算法引入了两个参数：alpha和beta。

其中，alpha表示当前搜索路径中极大节点已经找到的最优值，beta表示当前搜索路径中极小节点已经找到的最优值。

在搜索过程中，当某个极大节点的值大于等于beta时，可以直接剪去该极大节点的所有子节点，因为极小节点不会选择这个极大节点。

同理，当某个极小节点的值小于等于alpha时，可以直接剪去该极小节点的所有子节点，因为极大节点不会选择这个极小节点。

通过递归地进行搜索，并不断更新alpha和beta的值，可以逐渐缩小搜索范围，从而大大减少搜索时间。

四、Alpha-Beta剪枝算法的应用Alpha-Beta剪枝算法广泛应用于博弈领域，特别是各种棋类游戏。

在这些游戏中，博弈树的规模往往非常庞大，而Alpha-Beta剪枝算法能够有效地减少搜索时间，提高计算机对手的决策速度。

第一章将会阐述计算机博弈发展以及对电脑五子棋的介绍、电脑五子棋的状态空间复 杂度以及文章架构。
第二章首先描述了电脑象棋表示的一些基本数据结构。 第三章将重点讲述博弈树的搜索方法，包括博弈树构建、各算法介绍、以及五子棋规 则的实现，最后对整体搜索框架进行总结。 最后，第四章是全文的总结及展望。
2 数据结构
2.1 棋局的表示 我们知道五子棋的走法中有优先和禁手，如连四肯定是没有三四优先，而如果是黑方
出现三三（包括“四、三、三”）、四四（包括“四、四、三”），而黑方只能以四三取胜，如果 黑方走出禁手则是输；五连与禁手同时形成，先五为胜，等等的规矩。但是电脑毕竟不是 人类，可以类人但是却不可以自己思考，那么就需要给电脑一个它可以明白的评判标准。
根节点 S 30 最佳
30
-40
-30
第二层节点
30 40 60 第三层节点
60
-40
图 1：博弈树
50 -30 80 50
根据极小极大化分析法，先计算第3层子结点h(n)值，然后第2层子结点的估计值取他的各
后继子结点的极小值，根结点的估计值取他的各子结点的极大值。这个取得最大估计值的
子结点即为从S出发的计算机方的最佳落子方案。棋盘上某一行、某一列或某一对角线为
一路，这里使用的棋盘为19行19列，因此，行和列方向上共有19+19=38路；从左下到右上
方向的对角线有37路，同样，从左上到右下方向的对角线也有37路。但对于五子棋来说必
须在一条直线上有连续五个棋子才能赢。因此，在对角线上就可以减少8路。所以，整个
棋盘路的总数为：38+(37-8)+(37-8)=96路。
1 绪论
在人类文明发展的初期，人们便开始进行棋类博弈的游戏了。在人工智能领域内，博 弈是很重要的一个研究分支，很多实际问题可以在博弈的研究中得到解决，并且使计算机 智能更加靠近人类智能。电脑博弈是人工智能研究的一个方向，到了近 50 年前，随着电 子计算机的诞生，科学家们开始通过电脑模拟人的智能逐步向人类智能发起挑战，香农 (1950)与图灵(1953)提出了对棋类博弈程序的描述，随着电脑硬件和软件的高速发展，从

用一字棋的例子来说明α-β剪枝方法

为了使生成和估值过程紧密结合，采用有 界深度优先策略进行搜索，这样当生成达到规 定深度的节点时，就立即计算其静态估值函数， 而一旦某个非端节点有条件确定其倒推值时就 立即计算赋值。
一字棋第一阶段α-β剪枝方法


（1）α剪枝：若任一极小值层节点的β值小于 或等于它任一先辈极大值居节点的α值，即α （先辈层）≥β（后继层），则可中止该极小值 层中这个MIN节点以下的搜索过程。这个MIN 节点最终的倒推值就确定为这个β值 （2）β剪枝：若任一极大值层节点的α值大于 或等于它任一先辈极小值层节点的β值，即α （后继层）≥β（先辈层），则可以中止该极大 值层中这个MAX节点以下的搜索过程。这个 MAX节点的最终倒推值就确定为这个α值。

方法：当轮到我方走棋时，首先按照一定的搜 索深度生成出给定深度d以内的所有状态，计 算所有叶节点的评价函数值。然后从d-1层节 点开始逆向计算：对于我方要走的节点（用 MAX标记，称为极大节点）取其子节点中的最 大值为该节点的值（因为我方总是选择对我方 有利的棋）。

对于对方要走的节点（用MIN标记，称为极小 节点）取其子节点中的最小值为该节点的值 （对方总是选择对我方不利的棋）。一直到计 算出根节点的值为止。获得根节点取值的那一 分枝，即为所选择的最佳走步。

（3）对某些博弈的开局阶段和残局阶段， 往往总结有一些固定的对弈模式，因此可以利 用这些知识编好走步表，以便在开局和结局时 使用查表法。只是在进入中盘阶段后，再调用 其他有效的搜索算法，来选择最优的走步。
需要作进一步的研究和探讨的问题



（1）在一个短时期内短兵相接，进攻和防御 的战术变化剧烈，这些情况如何在搜索策略中 加以考虑。 （2）基于极小极大过程的一些方法都设想对 手总是走的最优走步，即我方总应考虑最坏的 情况，实际上再好的选手也会有失误，如何利 用失误加强攻势，也值得考虑。 （3）选手的棋风问题。

第40卷第3期温州大学学报（自 然 科 学 版）2019年8月V ol 40, No 3 Journal of Wenzhou University (Natural Science Edition) Aug, 2019基于极小极大值搜索和Alpha Beta剪枝算法的五子棋智能博弈算法研究与实现郑健磊，匡芳君†(温州商学院信息工程学院，浙江温州325035)摘要：针对五子棋棋型定义不准确、棋型不充足等问题，提出了一套改进的五子棋棋型模型和估值方法．针对利用极小极大值搜索和Alpha Beta剪枝算法对此棋型模型着棋时存在效率低和博弈水平不高的问题，提出了一系列改进的着棋方法，即利用局部搜索、多线程技术、浅层最优算法优化剪枝算法，以提升着棋的速度和准确率．实验结果表明，提出的着棋方案能提升着棋效率和准确性，设计得出的五子棋博弈系统具备远超过多数人类玩家的棋力．关键词：五子棋；估值函数；Alpha-Beta搜索算法；局部搜索；多线程中图分类号：TP301.6 文献标志码：A 文章编号：1674-3563(2019)03-0053-10DOI：10.3875/j.issn.1674-3563.2019.03.008 本文的PDF文件可以从/获得五子棋是一款经典的两人对弈的纯策略型棋类游戏．相对于国际象棋、中国象棋、围棋、日本将棋，五子棋简单易学，但是精通五子棋并非易事．2016年人工智能程序AlphaGo，击败人类围棋冠军李世石[1]，计算机在围棋领域不可能战胜人类的预言破灭．虽然AlphaGo已经宣布退出围棋比赛，但是其留下来的宝贵算法和围棋招数是计算机界的新突破，也给围棋界带来翻天覆地的变化．在五子棋领域，五子棋先后于1994年[2]、2001年[3]被计算机证明原始无禁手、原始有禁手规则下先手必胜，然而相比计算机象棋和围棋，计算机五子棋的发展是缓慢的．很多五子棋专家相信目前的五子棋程序依旧无法超越最强的人类棋手．五子棋博弈研究学者们都有其独到见解，张明亮[4]通过各类棋型估值的研究，优化了五子棋估值函数，解决了部分五子棋程序估值不完善的问题；毛丽民等[5]结合图像采集和分析，研发可以进行实物对弈的五子棋机器人；程宇等[6]通过对Alpha Beta剪枝算法的改进，优化了着棋效率低下的问题；还有学者设计和实现了整套完整的五子棋人机博弈软件[7-8]．但五子棋博弈系统仍然存在棋型定义模糊，说法不一和博弈水平不高等问题．因此，本文针对五子棋棋型的定义不准确、棋型不充足，提出一套改进的五子棋棋型模型和估值方法，对基本棋型和绝杀棋型分别进行估值；针对Alpha Beta剪枝算法存在效率低和博弈水平不高等问题，提出改进智能博弈算法，利用多线程技术和浅层最优算法优化Alpha Beta剪枝算法，以提升着棋速度和准确率，通过局部搜索，加收稿日期：2018-09-08基金项目：国家自然科学基金(61402227)；2018年温州商学院国家创新创业训练计划项目(201813637004)作者简介：郑健磊(1996-)，男，浙江绍兴人，本科生，研究方向：智能算法与软件开发．† 通讯作者，407807096@54温州大学学报（自然科学版）(2019)第40卷第3期 深程序的局部观，使得系统着棋能力得到提升．1 五子棋棋型与估值五子棋棋型存在定义模糊，如对活二、眠三、死四定义的不完整或存在术语使用不当[9]．而在大部分研究中，考虑的棋型较少，如对活三的定义不够完整，对跳活三、跳四这样的重要棋型未进行定义或定义不完整[10]．本文对棋型进行新的定义，特别是对一些特殊绝杀棋型进行了直接定义，以降低搜索深度，即颠覆从前往后的计算方式，直接从后往前推算，可提供接近2层的计算深度，而庞大的搜索树需要提高1层的搜索深度也是非常不容易的．1.1 五子棋的基本棋型在五子棋博弈中，活三和冲四是五子棋着棋过程最重要的棋型，活三两头均可进攻，冲四具有绝对先手，连续的冲四和活三的进攻是五子棋获胜的关键技术．而活三的一些变体棋型，如有一边空一格被对方棋子拦住，如图1的棋型g所示．此外跳活三、跳四，也是十分重要的棋型．跳四和冲四一样，具备绝对先手．图1 五子棋主要棋型与部分绝杀棋型Fig 1 Main Chess Type and Partial Lore Chess Type of Gobang1.2 五子棋的绝杀棋型如果不考虑对手的疏忽，那么活四或者成五一定是由多个棋型连续进攻所形成．本文例举了一方因无法防御而导致另一方必定出现活四或成五的棋型如图1所示，故着此类棋型是获胜的关键所在．通过棋型可以判断，此类棋型是由两个或两个以上的先手棋型组成．因此本文将先手棋型进行计数，如果一方先手棋型的数量超过2个，那么就给予一个相对非常高的分值，这些先手棋型包括：活三、跳活三、冲四、跳四．在着棋过程中发现，绝杀棋型有时也会存在被对手反胜或者化解的情况，一般是因为对方连续着绝对先手棋型（即冲四或跳四）导致的．而绝杀棋型中存在绝对先手的棋型，则不会存在此类情况，相对胜率会更高．1.3 棋型的估值通过对比不同估值的对局胜率，以及对棋型的分析，最终得出表1所示估值方案．郑健磊等：基于极小极大值搜索和Alpha Beta 剪枝算法的五子棋智能博弈算法研究与实现55表1 棋型估值 Table 1 Chess Type Valuation棋型名称 估值 棋型名称 估值 成五 9 999 999 眠三 15 活四 1 000 000活二 20 冲四 200 眠二 5 跳四 120 双活二 40活三 200 绝杀棋型 10 000*（1+冲四个数+跳四个数）跳活三302 五子棋基础算法分析本研究的算法思想基于极小极大值算法和Alpha Beta 剪枝算法①，这两种算法思想在棋类游戏中最为常用．2.1 极小极大值算法效率分析基于本文棋型的估值，使用极小极大值算法对局面进行评估．极小极大值算法能够模拟人的思维，找出局面范围内最优的解．在对弈中，对局面进行评估，估值越大表明对当前棋手越有利，估分越小则表明越不利．对所有节点进行计算局面评估，其所得最高分，即所达深度所能走出的最佳棋面，记录第1手着棋位置，即是当前局面最佳着棋点．如果不对极大极小值加以优化，这样的全盘遍历的方法会搜索大量毫无意义的点，对代码测试可以得出，在可以接受的时间内，只能进行两层搜索，即黑白各一手棋，而专业棋手能对未来十几步棋进行预测．2.2 Alpha Beta 剪枝算法效率分析AlphaBeta 剪枝算法在棋类博弈的应用也不乏优秀研究[6]．人类棋手在着棋的过程中不会去考虑对己方明显不利的点和对对方明显有利的点．AlphaBeta 剪枝算法就是不对那些双方都不会考虑的点进行剪枝，不进行下一步的考虑，以此将搜索树加以修剪．1975年，Knuth 等[11]证明在搜索节点排列为理想的情况下，将节点分支数记为b ，深度记为d ，搜索的节点数n 为：当d 为偶数，221d n b=-；当d 为奇数，(1)2(1)21d d n b b +-=+-．表2 AlphaBeta 剪枝算法效率分析Table 2 Efficiency Analysis of AlphaBeta Pruning Algorithm搜索产生节点数 / 个深度 d 不使用剪枝算法 节点数d b最理想排列情况221d b -本文所编写程序 取10次平均值本文程序比不使用剪枝 算法效率减少率 / %0 1 1 1.0 0 2 50 625 449 17 338.5 65.8 4 2 562 890 625 101 249 186 767 951.392.7 6129 746 337 890 62522 781 249① Sato N, Ikeda K. Three types of forward pruning techniques to apply the alpha beta algorithm to turn-based strategy games [C]. 2016 IEEE Conference on Computational Intelligence and Games, Santorini, Greece, 2016: 20-23.温州大学学报（自然科学版）(2019)第40卷第3期56Alpha Beta 剪枝算法高度依赖于节点的排列顺序，如果每次总是找到最差的节点，那么相当于剪枝永远不会发生，其效果相当于没有使用剪枝算法，即dn b =．Alpha Beta 剪枝算法效率分析如表2所示．从表2可知，虽然使用Alphabeta 剪枝对着棋能力有较大提升，但是其效率与理想排列状态相差甚远．3 五子棋博弈算法研究与效率改进通过对五子棋基础算法的分析，算法所存在的问题已然暴露．在极小极大值算法暴力搜索的基础上，使用AlphaBeta 剪枝算法进行改进，但其效率依旧低下，且只能对第四层进行非常缓慢的搜索，因此，结合局部搜索、多线程技术和浅层最优算法提出效率改进方案． 3.1 局部搜索在五子棋博弈过程中，没有哪个人类棋手会对整个棋盘进行计算，其思考过程往往是从中心向四周发散，并且五子棋着棋往往不会超出原有棋子两格的位置，而未经优化的搜索算法会将任何一个空白的节点作为可能的落子点．经过文献资料[6,8-9]和实战分析，一般对于搜索区域限制的算法往往是计算具有最大横坐标的棋子(max x )，具有最小横坐标的棋子(min x )，具有最大纵坐标的棋子(max y )，具有最小纵坐标的棋子(min y )，得出一个区域为(max x - min x + n )*(max y - min y + n )，其中n 表示偏移量，即可能的着棋点和原有棋子的最大距离[6]，但是这种计算方式并不高效．如果棋型呈现斜向狭长走势，或者棋子距离较远且中间有大量空白的情况，依旧会存在大量的无效搜索．前者的情况并不少见，在五子棋博弈过程中，与任何已有棋子成不了直线的点也往往是不会成为落子区域，这样就会出现如图2所示的区域化限制着棋点潜在的缺陷．对此，本文提出一种新思路，计算所需搜索节点的坐标，即可精确确定搜索范围．这样记录节点坐标的计算方式虽然比记录搜索范围计算方式更加复杂，但其减少的时间依旧比其增加的时间更可观．图2 区域化限制着棋点潜在的缺陷Fig 2 Potential Defects of the Chess Sub-point Restricted by Regionalization本文局部搜索使用偏移量为2，其伪代码如下： for (遍历整个棋盘) { if 当前节点存在棋子郑健磊等：基于极小极大值搜索和Alpha Beta剪枝算法的五子棋智能博弈算法研究与实现 57for对当前偏移量为1的范围内进行搜索{if当前节点没有棋子，且当前节点未被记录then记录当前节点坐标，并将当前节点记为已记录endif}endifif当前节点存在棋子for对当前偏移量为2的范围内进行搜索{if当前节点没有棋子，且当前节点未被记录，且横纵偏移量相等then记录当前节点坐标，并将当前节点记为已记录endif}endif}使用局部搜索前后的节点量对比如表3所示，局部搜索效果非常有效，第二层和第四层节点分别减少了96.59%和99.94%，且原本无法计算的第六层使用较长时间也可被成功计算．表3 使用局部搜索前后的节点量对比Table 3 Comparison of Grid Point V ariable before and after the Application of Local Search搜索产生节点数（着棋10次平均值）/ 个节点减少率/ % 深度d不使用局部搜索使用局部搜索2 17 338.5 592.1 96.594 186 767 951.3（取4次平均值）114 741.6 99.946 47 581 577.43.2 多线程技术使用局部搜索后，搜索速度有了质的飞跃．但博弈过程中又出现了新问题，即在4层和6层搜索过程中CPU的平均占用率只有35%左右．研究发现，这是因为整个搜索的过程是单线程串行的，而现在的CPU普遍采用了多核多线程设计，实验所用的笔记本电脑使用的是Intel i7 8550U 处理器，使用了4核8线程的设计．多线程技术避免了因阻塞带来的等待问题，能够有效提高处理器的工作效率和资源利用率[12]．本文采取了多线程技术来优化CPU的使用率，目前市面上多数消费级CPU采用的是2核4线程，4核4线程，或者4核8线程的设计．因此，选择了4线程对搜索进行优化．本文通过给每个线程分配不同的搜索区域，达到4线程搜索，其伪代码如下：length = 搜索数组的长度;range 1[开始] = 1; range 1[结束] = length / 4;range 2[开始] = range 1[结束] + 1; range 2[结束] = length / 2;range 3[开始] = range 2[结束] + 1; range 3[结束] = (range 2[结束] + 1 + length) / 2;range 4[开始] = range 3[结束] + 1; range 4[结束] = length;通过将局部搜索时保存的节点数组4等分，然后使用4个线程分别对4个节点数组分别进行温州大学学报（自然科学版）(2019)第40卷第3期 58搜索．改进后CPU占用率从35%左右提升到了95%左右，而剩下的5%也已经被其他任务占据，因此CPU的使用率已经达到了100%．3.2.1 效率分析CPU效率得到明显提升，本应该计算速度也明显提升．但是实验结果却是令人意外的，使用多线程搜索之后，节点数几乎是使用单线程的2 -3倍．单位时间内对节点的搜索速度提高到了原来的2倍左右，如表4所示，反而需要比单线程更长的时间．而且多线程的博弈过程发现，当前局面存在冲四棋型时，个别线程的节点明显增多．表4 使用多线程技术前后的节点量与时间（取前10次平均值）对比Table 4 Comparison of Grid Point V ariable and Time before and after the Application of Multi-threadingTechnology (Take the First 10 Average Values)单线程搜索4线程搜索深度d 节点数/ 个耗时/ ms 节点数/ 个耗时/ ms 节点减少率/ %时间减少率/ %2 592.1 15.3 1 207.1 17.1 -104 -124 114 741.6 1 185.5 310 164.9 1 420.8 -170 -206 47 581 577.4 458 916.5 98 051 448.1 487 238.2 -106 -63.2.2 多线程效率低下的原因分析经过多次博弈发现，多线程效率低下是因为四个线程彼此独立，个别线程所找到着棋点有时候往往是非常不好的，导致个别线程剪枝不易发生．最为显著的是出现浅层绝杀的棋面，如对方着棋形成了冲四，那么只有一个线程可以找到拦截冲四继续形成成五的点，而其他线程因为这个点不在它的搜索范围内，导致得到的永远是一个极差的局面分．如果使用单线程，那么单棵的搜索树将被分成4棵彼此独立的搜索树，虽然4线程的每棵小树的节点比单线程的大树要更少，但是4棵树的总和却要更多．而多线程并不能带来4倍的速度提升，因为CPU负载升高后其每个线程所获得的算力明显低于单线程．3.3 浅层最优算法Alpha Beta剪枝算法严重依赖于节点的排列．如果程序总是先去搜索最坏的节点，那么Alpha Beta截断就不会发生，该算法最终会遍历整个搜索树．在搜索的过程中，节点的排列顺序是完全无规律的，甚至没有优化的搜索往往是从边缘往中心推进，这样得到的节点往往比随机排列还要更差．显然找到最优排列是不可能的，因为这势必要算出所有节点．但是可以通过着棋的特点，算法的特性，提前找到较为优秀的解．浅层搜索虽然不能找到深层的最优解，但是其找到的解往往是较优解．而且对于某些棋型，浅层的搜索结果和深层的结果是完全一样的．比如下一着如果可以形成活四，那么不管搜索深度是多少，着活四棋型永远都是最优解．通过这一特点，在原来的Alpha Beta剪枝算法的搜索范围的基础上，先使用两层搜索找到一个当前局面的最优解，再将这个解的节点替换为深层搜索的每一个线程的起始节点，那么深层搜索将从一个较为优秀的节点开始搜索．浅层最优搜索算法的伪代码如下：(x, y) = 获取深度为2的最佳着棋点;线程1计算范围[0][0] = x; 线程1计算范围[0][1] = y;线程2计算范围[0][0] = x; 线程2计算范围[0][1] = y;郑健磊等：基于极小极大值搜索和Alpha Beta剪枝算法的五子棋智能博弈算法研究与实现 59线程3计算范围[0][0] = x; 线程3计算范围[0][1] = y;线程4计算范围[0][0] = x; 线程4计算范围[0][1] = y;这样算法将四个线程都能联系，尤其是在浅层绝杀的棋面下，让四个线程都有机会找到绝杀点，大大提高了搜索效率，如表5所示，使用了浅层最优算法后的多线程搜索效率显著提高．浅层最优算法不仅解决某些线程因找不到拦截浅层绝杀的点而导致搜索速度极慢，还使得节点排列顺序有一定提升，如表6所示，单线程也比不使用浅层最优算法的效率高．表5 使用浅层最优算法前后多线程的节点量与时间（取前10次平均值）对比Table 5 Comparison of the Amount of Nodes and Time of a Multiple Thread before and after the Applicationof Shallow Optimal Algorithm (Take the First 10 Average Values)4线程搜索不使用浅层最优算法使用浅层最优算法深度d节点数/ 个耗时/ ms 节点数/ 个耗时/ ms 节点减少率/ %时间减少率/ %2 1 207.1 17.1 2 904.8 32.2 -141 -88 4 310 164.9 1 420.8 111 672.5 561.0 64 61 6 98 051 448.1 487 238.2 38 399 549.0 183 329.6 61 62表6 使用浅层最优算法前后单线程的节点量与时间（取前10次平均值）对比Table 6 Comparison of the Amount of Nodes and Time of a Single Thread before and after the Application of Shallow Optimal Algorithm (Take the First 10 Average Values)单线程搜索不使用浅层最优算法使用浅层最优算法深度d节点数/ 个耗时/ ms 节点数/ 个耗时/ ms 节点减少率/ %时间减少率/ %2 592.1 15.3 979.5 18.7 -65 -224 114 741.6 1 185.5 70 245.9 720.9 39 396 47 581 577.4 458 916.5 32 797 238.2 311 161.2 31 32使用了浅层最优算法之后，无论单线程与多线程都有了效率的提升，使用浅层最优算法后单线程与多线程的节点量与时间对比如表7所示．表7 使用浅层最优算法后单线程与多线程的节点量与时间对比Table 7 Comparison of Node Quantity and Time between Single Thread and Multithread afterthe Application of Shallow Optimal Algorithm单线程4线程深度d步数节点数/ 个耗时/ ms 节点数/ 个耗时/ ms 4线程节点减少率/%4线程时间减少率/%1 13 077 125 24 489 222 -87 -782 20 058 188 26 907 159 -34 153 30 146 321 60 340 317 -100 14 64 510 611 82 742 421 -28 315 72 862 701 110 208 660 -51 646 65 111 710 154 394 740 -137 -4（接下表）60温州大学学报（自然科学版）(2019)第40卷第3期（接上表）7 229 329 2 331 316 264 1 436 -38 388 55 889 593 77 904 424 -39 2849 51 523 574 88 536 410 -72 2910 99 954 1 055 174 941 821 -75 22平均值70 245.9 720.9 111 672.5 561.0 -59 221 1 491 025 14 4602 111 350 11 012 -42 242 1 946 012 17 6643 549 182 18 797 -82 -63 787 581 7 271 1 603 237 6 791 -104 74 2 777 389 26 342 3 842 868 15 197 -38 425 7 529 166 74 4407 529 166 37 646 0 4966 93 603 148 840 879 98 675 655 432 788 -5 497 76 446 115 692 205 91 676 698 503 718 -20 278 32 996 289 319 549 44 678 231 210 746 -35 349 51 264 007 516 822 63 563 678 288 926 -24 4410 59 131 650 601 980 66 765 425 307 675 -13 49平均值32 797 238.2 311 161.2 38 399 549.0 183 329.6 -17 41 由表7可知，在节点多的时候，多线程表现出的效率要优于单线程，而在节点较少的时候，单线程效率更优．由于深度为2的时候，无论基于什么算法，都是瞬间完成的，因此不在考虑之内．对于深度4和深度6而言，多线程的综合速度要明显优于单线程，随着棋面复杂度的增加，搜索深度加深，多线程的优势将更加明显，因此多线程的表现是值得肯定的．4 实验结果与分析全文实验方式均采用了15×15的标准五子棋棋盘，以前10步着棋为实验数据，并保持相同深度的着棋棋型一致，对所使用的各项技术进行分析．通过使用五子棋基本棋型和绝杀棋型的两种估值方式，对棋力带来了明显改善，尤其是对于浅层绝杀方面．对于极小极大值算法和Alpha Beta剪枝算法效率不足的问题，提出了以下改进方案：（1）局部搜索意在优化减少对理论上不会落子的区域进行优化，本文打破常见的计算着棋区域的方法，转而使用了直接计算落子坐标的方法，优化了前者所存在的不足，其效率提升也十分明显，带来约99%的综合效率提升，并使得6层搜索成为了可能．（2）对CPU使用率过低的问题，采取了4线程并行计算，但是其结果并不理想，因为Alpha Beta剪枝算法的特点，其效率反而有所下降．（3）为了解决多线程计算存在的问题，提出了浅层最优算法，此算法不仅提高了多线程效率，也提高了单线程效率，使用了浅层最优算法之后，效率较低的多线程搜索有了较大的改善，相对于未使用此算法提升了约60%的综合效率．如图3是系统程序对局测试的结果，玩家持黑，电脑持白，电脑从第13手进行了连续的先手进攻，最终于第27手取胜．5 结语本文针对五子棋棋型的定义不准确，棋型不充足等问题，提出了一套改进的五子棋棋型模型郑健磊等：基于极小极大值搜索和Alpha Beta剪枝算法的五子棋智能博弈算法研究与实现 61图3 电脑持白对弈过程Fig 3 The Process to Play Chess by Computer Holding White Chess和估值方法．针对利用极小极大值搜索和Alpha Beta剪枝算法对此棋型模型着棋时存在效率低和博弈水平不高的问题，提出改进智能博弈算法，在可接受的时间内，将搜索深度做到了6层，实验结果表明，程序性能和效率相对较高，通过使用五子棋基本棋型和绝杀棋型的两种估值方式，对棋力也有明显改善，尤其是浅层绝杀方面有着很大优势．下一步工作将使用机器学习算法保存已下棋局，以使同样错误的着棋不再出现，同时在着棋时考虑对手存在计算漏洞，使程序具备更激进棋风．参考文献[1] 张洁．人机大战的跨时空解读[J]．围棋天地，2016（13）：110．[2] Allis L V. Searching for solutions in games and artificial intelligence [D]. Netherlands: Maastricht University, 1994:164-165.[3] Wágner J, Virág I. Solving renju [J]. Icga J, 2001, 24(1): 30-34.[4] 张明亮，吴俊，李凡长．五子棋机器博弈系统评估函数的设计[J]．计算机应用，2012，32（7）：1969-1972．[5] 毛丽民，朱培逸，卢振利，等．基于LabVIEW的五子棋博弈算法[J]．计算机应用，2016，36（6）：1630-1633．[6] 程宇，雷小锋．五子棋中Alpha-Beta搜索算法的研究与改进[J]．计算机工程，2012，38（17）：186-188．[7] 张效见．五子棋计算机博弈系统的研究与设计[D]．合肥：安徽大学，2017：62-67．[8] 王杨．基于计算机博弈的五子棋算法研究[D]．沈阳：沈阳理工大学，2016：56-63．[9] 王长飞，蔡强，李海生．智能五子棋算法的设计实现[J]．系统仿真学报，2009，21（4）：1051-1054．[10] 徐建．五子棋的一种价值的估算[J]．智能计算机与应用，2016，6（5）：90-92．[11] Knuth D E, Moore R W. An analysis of Alpha-Beta pruning [J]. Artif Intell, 1975, 6(4): 293-326.[12] 周佳佳，李涛，黄小康．多核同时多线程处理器的线程调度器设计[J]．电子技术应用，2016，42（1）：19-21．62温州大学学报（自然科学版）(2019)第40卷第3期 The Research and Implementation of Gobang Intelligent Game Playing Algorithm Based on Mini-max Value Searchand Alpha Beta Pruning AlgorithmZHENG Jianlei, KUANG Fangjun(School of Information Engineering, Wenzhou Business College, Wenzhou, China 325035)Abstract: A set of improved Gobang chess patterns and valuation methods is raised in this paper, which aimsat the problems like inaccurate definition chess patterns and inadequate chess patterns of Gobang. Then, aseries of modified game methods are proposed for the problems of lower efficiency and lower game levelwhen the minimax search algorithm and Alpha Beta pruning algorithm in this game model game. Tgesemethodsare involved in the local search, multithreading technology, the shallow optimal pruning algorithm inorder to optimize the speed and accuracy of the game. The experimental results show that the proposed gamescheme tends to improve the efficiency and accuracy of the game. The designed Gobang game system is farmore powerful than a majority of human players.Key words: Gobang; Evaluation Function; Alpha-Beta Search Algorithm; Local Search; Multithreading(编辑：封毅)。

ab剪枝算法摘要：一、算法背景- 介绍ab剪枝算法的起源二、算法原理- 详细阐述ab剪枝算法的核心思想三、算法步骤- 分析ab剪枝算法的具体操作流程四、算法应用- 说明ab剪枝算法在实际问题中的运用五、优缺点分析- 总结ab剪枝算法的优点与不足六、总结- 对ab剪枝算法进行总结，展望未来发展正文：ab剪枝算法是一种在决策树算法中进行剪枝的优化方法，它起源于20世纪90年代，由Tom M.Mitchell等学者提出。

该算法的主要目的是解决决策树过拟合的问题，通过在构建决策树的过程中进行剪枝，从而得到一个泛化性能更好的模型。

ab剪枝算法的核心思想是通过比较两个子节点的信息增益来决定是否进行剪枝。

在构建决策树的过程中，每个节点都会生成两个子节点，其中一个子节点为当前节点的一个属性A，另一个子节点为A的补集。

ab剪枝算法会比较这两个子节点的信息增益，选择信息增益较大的子节点进行分裂。

当两个子节点的信息增益相差较大时，算法将剪去信息增益较小的子节点，避免过拟合现象的发生。

ab剪枝算法的具体步骤如下：1.对于每个节点，生成两个子节点，一个基于属性A，另一个基于A的补集。

2.计算两个子节点的信息增益。

3.比较两个子节点的信息增益，选择信息增益较大的子节点进行分裂。

4.当两个子节点的信息增益相差较大时，剪去信息增益较小的子节点。

5.重复步骤1-4，直到满足停止条件（如最大深度限制）。

ab剪枝算法在许多实际问题中都有广泛应用，如文本分类、信用评估、生物信息学等。

通过剪枝，ab剪枝算法能够有效地降低过拟合风险，提高模型的泛化性能。

然而，ab剪枝算法也存在一定的局限性，例如在处理连续属性时，可能会遇到计算困难。

此外，当特征数量较大时，算法的计算复杂度较高，可能会影响其性能。

总之，ab剪枝算法作为一种决策树剪枝方法，在解决过拟合问题方面具有一定的优势，已在许多实际问题中得到应用。

析
由于 Ｂ＊ 算法对估值的依赖性很强，实验所用的估值效
与 实
果实现算法速度很快（时间小于一秒），但走法只有搜索深
现
度为三层α － β剪枝的水准，实用时有待进一步提高。
３ 结束语
以上讨论了博弈树搜索算法的两类算法，其中α － β剪
枝算法比较成熟，是当前最常用的算法，在融合各种策略后
具有很高的剪枝效率。如果能进一步改进数据结构和进行代
节点结果（包括搜索深度，估值类型： 准确还是上下边界） 记录下来，在后继的搜索过程中，查看表中记录。如果搜索 的节点已经有记录（子树的深度大于或者等于当前的新节点 要求的搜索深度），它的信息就可以直接运用了，这样我们 可以避免重复搜索很多子树。置换表是一种内存增强技术， 以空间换时间。
１．３ 历史启发（Ｈｉｓｔｏｒｙ Ｈｅｕｒｉｓｔｉｃ） 历史启发是为了迎合α － β剪枝搜索对节点排列顺序敏 感的特点来提高剪枝效率的，即根据历史走法对当前搜索的 节点集进行排序，从而优先搜索好的走法。 １．４ 迭代深化（Ｉｔｅｒａｔｉｖｅ Ｄｅｅｐｅｎｉｎｇ） 迭代深化是一个不断求精的过程，对博弈树进行多次遍 历，并不断加深其深度，用于控制搜索的时间。 在实用中迭代深化和前面提到的算法结合使用具有很好 的效果，如 ＰＶＳ 算法，上几层迭代得到的最佳走法可以帮助 下一层提高剪枝效率； 迭代过程中把前面局面的历史得分存 入置换表，最佳走法存入历史启发表可以提高剪枝效率。 １．５ 实验数据分析 各种增强策略都能提高α － β剪枝的效率，其中空窗口
｝
｝
博
２．用的策略为 Ｂｅｒｌｉｎｅｒ 原则： 用一组候选分枝与
搜
最佳分枝做比较，如果各候选分枝实行信息反馈的深度是
索
算
ｔｉ，最佳分枝实行信息反馈的深度是ｔ，比较∑ｔｉ２和ｔ２，若前

α-β剪枝算法α-β剪枝算法 前⾯介绍的基本搜索算法，在实际应⽤是是⼗分费时的，因为它需要考虑所有可能的棋步。

有研究表明，在⿊⽩棋的中盘阶段，平均每个局⾯⼤约有10步棋可供选择[1]。

如果程序前瞻10步（搜索深度为10），就需要考虑⼤约100亿个局⾯。

假设计算机以每秒1000万个局⾯的速度进⾏运算，每下⼀步棋⼤约需要运算⼗⼏分钟。

因此，在有限的时间内，程序⽆法进⾏很深的搜索，这就⼤⼤制约了程序的棋⼒。

有没有更⾼效的搜索⽅法呢？Edwards、Timothy（1961年）[2]、Brudno（1963年）[3]等⼈相继在研究中发现，程序搜索过程中有很多局⾯是完全可以忽略的，并提出了α-β剪枝算法（Alpha-beta Pruning）。

我们就仍以图1所⽰的局⾯为例，简要说明剪枝算法的原理。

图1 ⽩先，当前最佳估值为0 假设⽩棋已经搜索了D6的后续变化，得出这步棋的估值为0。

接着开始搜索F4这步棋，⽩棋下F4后形成图2所⽰的局⾯。

图2 ⿊先，当前最佳估值为 6 在这⼀局⾯中，⿊棋相继搜索了C3、D3、E3三步棋，当前最佳估值是E3的 6。

作为⿊棋⽅，他是很乐意看到有E3这样的好棋，他也很希望尚未进⾏搜索的F3和G3能有更好的表现。

但问题是，⿊棋能遇上E3这样好棋的前提是⽩棋要先下出F4，下F4的决定权在于⽩棋⽅。

⽽对于⽩棋⽽⾔，⿊棋的这步E3回应显然对他太不利了。

在他看来，F4这步棋的估值最多只有-6，甚⾄有可能更差。

当⽩棋知道⿊棋将有⼀步好棋E3在等着他时，他是绝对不会去下F4的，因为他完全可以选择下D6，或者等待后续搜索中可能出现的更好棋步。

换句话说，⿊棋根本没有机会⾯对图2所⽰的局⾯，F3和G3这两步棋的结果已经⽆关紧要了，⿊棋没有必要再继续搜索下去。

我们将这种现象称为剪枝（Pruning）。

这看上去是个相当诡异的现象，⿊棋从⾃⼰的利益出发，努⼒寻找尽可能好的棋步，但是⼀旦他的棋步好过头了，对于当前局⾯的搜索⼯作就瞬间变成是多余的。