α-β 剪枝课件

2
5
3
3
Develop Way
9
Example 2
2 2 ≤
≥2 2
≥7
β剪枝
2
≤1
7
α剪枝
2
8
1
15
7
10
Example 3-1 一字棋剪 枝
α
α ≥1
剪枝
S0
β≤ -1
S3
β≤ -2
S1 S4 S5
S2
order of develop
11
Example 3-2 一字棋剪枝
α
α ≥ -1
剪枝
β
Q: if α ≥β , is it necessary to develop other children of the ‘and node’?
6
α 剪枝
(1)或节点下确界α=3 (2)或节点子节点上确界β =2，即α ≥β
≥3
3
≤2 3
2
3 5
扩展顺序
7
4) β剪枝方法
≤β
对于一个与节点，
S0
1
S3
S1
β≤ -1
β≤ 1
S2
S4
S5
order of develop
12
小结
• • • • 博弈 —— 研究对象 博弈树 —— 表示对象 极大极小 —— 问题求节 α –β 剪枝 —— 求解优化
13
Home work
• 1. 一字棋剪枝 • 扩展顺序 S2,S1,S3, 说明一字棋剪枝过程 • 2.极小极大分析法，计算其倒推值,说明计 算其倒推值过程
4.6α –β 剪枝技术
4.6.1引入原因
极小极大分析法，实际是先生成一棵博弈树，然后再计 算其倒推值，这样做效率较低。

注意，由于示例问 题格局数非常少， 我们可以给出完整 的格局树。这种情
况下我可以找到 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时，表示从此处开始不论最 终结局是哪一个，其上限价值也要低于已知的最优解，也就是 说已经不可能此处向下找到更好的解，所以就会剪枝。

AlphaBeta算法是根据Minimax算法得来的，首先我们必须明白MiniMax算法的思想。

Minimax算法常用于棋类等由两方较量的游戏和程序。

该算法是一个零总和算法，即一方要在可选的选项中选择将其优势最大化的选择，另一方则选择令对手优势最小化的方法。

而开始的时候总和为0。

但是如果实际中使用Minimax算法，由于搜索深度和可能的情况很多，算法的效率很不理想，其实并没有必要每个节点都必须搜索完毕，有些事没有必要的。

AlphaBeta算法正是为了解决这个问题。

1. 对于一个MIN节点，若能估计出其倒推值的上确界Beta，并且这个Beta值不大于MIN 的父节点(MAX节点)的估计倒推值的下确界Alpha，即Alpha≥Beta，则就不必再扩展该MIN 节点的其余子节点了，因为这些节点的估值对MIN父节点的倒推值已无任何影响了，这一过程称为Alpha剪枝。

2. 对于一个MAX节点，若能估计出其倒推值的下确界Alpha，并且这个Alpha值不小于MAX 的父节点(MIN节点)的估计倒推值的上确界Beta，即Alpha≥Beta，则就不必再扩展该MAX 节点的其余子节点了，因为这些节点的估值对MAX父节点的倒推值已无任何影响了。

这一过程称为Beta剪枝。

3. 一个MAX节点的Alpha值等于其后继节点当前最大的最终倒推值，一个MIN节点的Beta 值等于其后继节点当前最小的最终倒推值AlphaBeta剪枝算法AlphaBeta剪枝算法(假设方框表示取极大值的节点，圆圈表示取极小值的节点)B的值是18，D的值为16，而C是取极小值，由此可以判断C《=16,而A取Max（B,C），故没必要考虑C的其他子节点了。

Alphabeta的MiniMax形式，伪代码：alpha-beta(player,board,alpha,beta)if(game over in current board position) return winnerchildren = all legal moves for player from this boardif(max's turn)for each childscore = alpha-beta(other player,child,alpha,beta)(we have found a better best move....)if score > alpha then alpha = score(cut off...)if alpha >= beta then return alphareturn alpha (this is our best move)else (min's turn)for each childscore = alpha-beta(other player,child,alpha,beta)(opponent has found a better worse move.....)if score < beta then beta = score(cut off....)if alpha >= beta then return betareturn beta (this is the opponent's best move)AlphaBeta的递归形式01 int AlphaBeta(int depth, int alpha, int beta)02 {//如果层数为0或者已达最终状态则返回本步棋的估值03 if(depth == 0 || IsGameOver()) return Evaluate();04 for(each possible move){06 MakeMove();08 int val = -AlphaBeta(depth - 1, -beta, -alpha);09 UnMakeMove();11 if(val >= beta){13 return val;14 //注意，这里需要返回val，因为上一层应该知道具体搜索到的值，以配合各种Alpha-Beta算法的变种15 }16 if(val > alpha){18 alpha = val;19 ...20 //当然这里还需要记录这步最佳的走法21 }24 }25 return alpha;//返回最好的值26 }2728 Alpha表示MAX节点的下界值，29AlphaBeta算法的递归形式关键就是理解负号，在每一层节点中都是求最大值（例如CP-OP 的最大值,将A方的最大值返回给B，即最小化B的利益），然后返回给父节点的时候加个负号得到的就是（OP-CP），也就是双方都为对方找最差的走法。

人工智能期中作业一字棋编程姓名：班级：学号：一、程序设计思想：1.通过判断一字棋的棋局是否与之前搜索过的棋局重复来减小搜索的复杂度。

（通过对称属性来判断是否重复）2.主程序采用递归的思想来解决此类复杂问题。

主程序的功能为按照αβ剪枝策略算出当前棋局的分数，依次递归。

int jianzhi(enzo a,int tier)为整个程序的关键函数。

其中enzo 是结构体类型（自定义），int tier 为层数。

递归如下：v[tier]=max(jianzhi(a,tier+1),v[tier]);（其中a每次传递之前都会被更新）。

3.如何判断是否是αβ剪枝是关键。

先用int v[4]数组来存储第0 、1、2、3层的分数。

初始值分别为-100,100，-100,100。

共有3种α剪枝情况和1中β剪枝情况。

详情见Int aorb();子函数。

二、程序源代码：#include <iostream>#include<vector>using namespace std;int jzs=0;int ajz=0,bjz=0;int v[4]= {-100,100,-100,100};class enzo{public:int a[3][3];//棋局enzo()//初始构造函数{for(int i=0; i<3; i++)for(int j=0; j<3; j++)a[i][j]=2;}void pr()//输出棋局{for(int i=0; i<3; i++){for(int j=0; j<3; j++){if(a[i][j]==1) cout<<'X'<<" ";if(a[i][j]==0) cout<<'O'<<" ";if(a[i][j]==2) cout<<". ";}cout<<endl;}}};//计算数组的静态估值int value_1(enzo a,int b){int v=0;for(int i=0; i<3; i++){for(int j=0; j<3; j++)if(a.a[i][j]==2) a.a[i][j]=b;}// a.pr();for(int i=0; i<3; i++)if(a.a[i][0]==b&&a.a[i][1]==b&&a.a[i][2]==b) v++;for(int i=0; i<3; i++)if(a.a[0][i]==b&&a.a[1][i]==b&&a.a[2][i]==b) v++;if(a.a[0][0]==b&&a.a[1][1]==b&&a.a[2][2]==b) v++;if(a.a[0][2]==b&&a.a[1][1]==b&&a.a[2][0]==b) v++;return v;}int value(enzo a){return(value_1(a,1)-value_1(a,0));}bool sym(enzo a,enzo b)//判断是否上下左右斜对称（没有考虑旋转的情况）{if(a.a[0][1]==b.a[0][1]&&a.a[1][1]==b.a[1][1]&&a.a[2][1]==b.a[2][1]) //左右对称if(a.a[0][0]==b.a[0][2]&&a.a[1][0]==b.a[1][2]&&a.a[2][0]==b.a[2][2])if(a.a[0][2]==b.a[0][0]&&a.a[1][2]==b.a[1][0]&&a.a[2][2]==b.a[2][0]) return true;if(a.a[1][0]==b.a[1][0]&&a.a[1][1]==b.a[1][1]&&a.a[1][2]==b.a[1][2]) //上下对称if(a.a[0][0]==b.a[2][0]&&a.a[0][1]==b.a[2][1]&&a.a[0][2]==b.a[2][2])if(a.a[2][0]==b.a[0][0]&&a.a[2][1]==b.a[0][1]&&a.a[2][2]==b.a[0][2]) return true;if(a.a[0][0]==b.a[0][0]&&a.a[1][1]==b.a[1][1]&&a.a[2][2]==b.a[2][2]) //两个斜对称if(a.a[0][1]==b.a[1][0]&&a.a[0][2]==b.a[2][0]&&a.a[1][2]==b.a[2][1])if(a.a[1][0]==b.a[0][1]&&a.a[2][0]==b.a[0][2]&&a.a[2][1]==b.a[1][2]) return true;if(a.a[0][2]==b.a[0][2]&&a.a[1][1]==b.a[1][1]&&a.a[2][0]==b.a[2][0])if(a.a[0][0]==b.a[2][2]&&a.a[0][1]==b.a[1][2]&&a.a[1][0]==b.a[2][1])if(a.a[2][2]==b.a[0][0]&&a.a[1][2]==b.a[0][1]&&a.a[2][1]==b.a[1][0]) return true;return false;}bool nsym(enzo a,enzo b){if(sym(a,b)) return false;else return true;}int aorb()//a - 0 b -1{if(v[0]>=v[1]&&v[0]!=-100&&v[1]!=100){jzs++;cout<<jzs<<": "<<"发生a剪枝"<<endl;ajz++;return 1;}else if(v[0]>=v[3]&&v[0]!=-100&&v[3]!=100){jzs++;cout<<jzs<<": "<<"发生a剪枝"<<endl;ajz++;return 1;}else if(v[2]>=v[3]&&v[2]!=-100&&v[3]!=100){jzs++;cout<<jzs<<": "<<"发生a剪枝"<<endl;ajz++;return 1;}else if(v[1]<=v[2]&&v[1]!=100&&v[2]!=-100){jzs++;cout<<jzs<<": "<<"发生b剪枝"<<endl;bjz++;return 1;}else return 0;}int jianzhi(enzo a,int tier){//a.pr();if(tier==4) return value(a);if(tier%2)//极小层{vector<enzo> hi;for(int i=0; i<3; i++){for(int j=0; j<3; j++){if(a.a[i][j]==2){int u=0;int qq=0;a.a[i][j]=0;for(u=0; u<(int)hi.size(); u++){if(sym(hi[u],a)) break;}if((int)hi.size()==u){hi.push_back(a);v[tier]=min(jianzhi(a,tier+1),v[tier]); if(aorb()) qq=1;}a.a[i][j]=2;if(qq==1){a.pr();cout<<endl;v[tier]=100;return -100;}}}}int hj=v[tier];v[tier]=100;return hj;}Else//极大层{vector<enzo> hi;for(int i=0; i<3; i++){for(int j=0; j<3; j++){if(a.a[i][j]==2){int u=0;int qq=0;a.a[i][j]=1;for(u=0; u<(int)hi.size(); u++){if(sym(hi[u],a)) break;}if((int)hi.size()==u){hi.push_back(a);v[tier]=max(jianzhi(a,tier+1),v[tier]); if(aorb()) qq=1;}a.a[i][j]=2;if(qq==1){a.pr();v[tier]=-100;return 100;}}}}int hj=v[tier];v[tier]=-100;return hj;}}int main(){enzo a0;jianzhi(a0,0);cout<<"一共"<<ajz<<"次a剪枝"<<endl;cout<<"一共"<<bjz<<"次b剪枝"<<endl;}三、αβ剪枝搜索过程（其中’.’表示空）共发生了23次α剪枝，5次β剪枝。

5. Adversarial SearchContents:☐5.1. Games☐5.2. Optimal Decisions in Games☐5.3. Alpha-Beta Pruning☐5.4. Imperfect Real-time Decisions☐5.5. Stochastic Games☐5.6. Monte-Carlo Methods☐The problem with minimax search: 采用minimax搜索的问题：⏹Number of game states is exponential in depth of the tree.博弈状态的量随着树的深度呈现指数式增长。

⏹We can’t eliminate the exponent, but we can effectively cut it in half.我们无法消除这种指数，但实际上我们可以将它剪掉一半。

☐The trick to solve the problem: 解决该问题的技巧⏹Compute correct minimax decision without looking at every node in game tree.计算正确的minimax决策而不考虑博弈树的每个节点。

⏹That is, use“pruning” to eliminate large parts of the tree.就是说，采用“剪枝”方法来消除该树的大部分。

☐What is alpha–beta pruning 什么是alpha–beta剪枝⏹It is a search algorithm that seeks to decrease the number of nodes that areevaluated by the minimax algorithm.是一种搜索算法，旨在削减由minimax算法评价的节点数量。

AlphaBeta剪枝算法关于AlphaBeta剪枝的⽂章太多，这个⽅法是所有其它搜索⽅法的基础，得多花些时间认真地理解。

先把基本概念再回顾⼀遍：节点：在中国象棋中就是⼀个棋盘的当前局⾯Board，当然该轮到谁⾛棋也是确定的。

这⾥的圆形节点表⽰终⽌节点，在中国象棋⾥就是⼀⽅被将死的情况（或者到达了搜索的最⼤深度），后续不会再有着法产⽣，游戏如果⾛到这⾥就会结束。

在引擎⾥通常给红⽅⼀个很⼤的评估值，如+30000，给⿊⽅⼀个很⼩的评估值，如-30000，来⽅便地判断这种结束局⾯。

（胜利局⾯有稍微不同的表⽰法，⽤-30000+层数ply来表⽰）连线：表⽰⼀步着法Move，通过这步着法后，局⾯发⽣变化，先后⼿也要交换。

层：通常的术语是ply，复数形式是plies，也有称为levels，当然与depth也是对应的。

这个术语是为了与⽐赛⾥常说的回合相区分，⼀个回合通常包含2步，这个ply就表⽰某⼀⽅⾛了⼀步。

根节点记为0层，以下的层数递增。

深度depth：要注意是从下到上的，还是从上到下的。

（1）通常的算法书中都是从下到上递增的，即根节点为最⼤搜索深度，⾛到最底部的叶⼦结点为0，这种算法只要记住⼀个depth值就可以了。

（2）⽽另⼀种记法是根部结点为0，越向下depth增加，这时在搜索时就要传递2个参数值，depth和maxDepth，稍微有点啰嗦，应该也会影响⼀点效率。

另外在探查置换表中的结点时，⽤第（1）种记法也⽅便⼀些，因为要知道从当前节点迭代的深度值，否则还要在置换表中保存depth和maxDepth两个值。

AlphaBeta剪枝⽅法是对Minimax⽅法的优化，它们产⽣的结果是完全相同的，只不过运⾏效率不⼀样。

这种⽅法的前提假设与Minimax也是⼀样的：1）双⽅都按⾃⼰认为的最佳着法⾏棋。

2）对给定的盘⾯⽤⼀个分值来评估，这个评估值永远是从⼀⽅（搜索程序）来评价的，红⽅有利时给⼀个正数，⿊⽅有利时给⼀个负数。

高级人工智能
问题求解
王浩
2018/10/8
合肥工业大学人工智能与数据挖掘研究室
1/123
问题表示及求解 用搜索法对问题求解 有信息的搜索 对抗搜索
2018/10/8
合肥工业大学人工智能与数据挖掘研究室
2/123
问题表示及求解

问题表达及其变换
问题的直接求解法
状态空间图搜索算法
2018/10/8


式中，fi表示对其右边的当前状态将进行第i个操作。
对一个智能问题全部状态及其操作关系，给予具体 的赋值，就可构成一个状态空间的相互关系有向图， 使用该图，即可进行具体问题求解。
2018/10/8
合肥工业大学人工智能与数据挖掘研究室
14/123
问题表示及求解
--状态空间图搜索算法

搜索法求解问题的基本思想：
--搜索
（2）部分已知信息环境Ep 当只有部分信息已知，这时其目 标和任务是：充分利用已知信息，把未知的信息不利影响设 法降到最低程度，尽可能按照最佳搜索路径取得理想搜索效 果。或者设法弥补信息损失，发挥已知信息作用，扬长避短， 制定策略来克敌制胜。例如，在海陆空战棋或军棋游戏中， 运用知识和经验猜测对方的军事布局，一方面用手榴弹对付 比我方师长还要厉害的指挥官，另一方面要设法用最小代价 摧毁对方强大火力，以便开辟夺取对方军旗的坦途。
--搜索
搜索（Search），即寻找，设法在庞大状态空间图中找到目标。 也可以把搜索看作是一种推理，它是人工智能问题求解的基 本方法之一。 主要分为两类性质的搜索：即基本搜索和智能搜索。 基本搜索是一种没有任何经验和知识起作用的、由某种规则 所确定的非智能性的搜索； 启发式搜索（Heuristic Search）：其特点在于是一种有准 备的、追求效率而有的放矢的智能搜索，它要求依据某种知 识及信息的指导，通过逐一状态比较而找到符合规定条件的 目标状态解。

人工智能与信息社会
基于决策树和搜索的智能系统：Alpha-Beta剪枝 陈斌 北京大学 gischen@
Alpha-Beta剪枝
〉 Minimax需要展开整个决策树 〉 对于局面复杂的问题，需要很大的空间 〉 有部分结点跟最后的结果无关，无需展开局
面和计算估值 〉 不计算这些结点可节省算法搜索的时间
XO X
V=1 V=4
XOX
V=3
OX X
OXX
V=2 V=1
X O X
V=1
北京大学地球与空间科学学院/陈斌/2018
Max结点更新α值(下限)，Min结点更新β值(上限)
〉 从根结点选择评估值最大的分支，作为行动 策略
北京大学地球与空间科学学院/陈斌/2018
剪枝过程
max结点
min结点
X
V=3
V=3
X: max结点 O: min结点
X
X
XO
max结点 O
OX
X
O
X
X
叶结点 O
V=3
X O X
XO X
V=1 V=4
XOX
V=3
OX X
OXX
V=2 V=1
X O X
V=1
北京大学地球与空间科学学院/陈斌/2018
剪枝过程
max结点
min结点
X
βV==33
V=3
X: max结点 O: min结点
X
V=1
X
max结点 O V=3
XO
V=4
OX
V=2
X
V=1 O
X
X
叶结点 O
V=3
X O X
XO X
V=1 V=4

❖ 初始设置α为负无穷大，β为正无 穷大
对于B(第四层)而已，尽量使得A 获利最小，因此当遇到使得A获利 更小的情况，则需要修改β。这里 3小于正无穷大，所以β修改为3
(第四层)这里17大于3，不用修பைடு நூலகம்β
对于A(第三层)而言，自
己获利越大越好，因此遇 到利益值大于α的时候， 需要α进行修改，这里3大 于负无穷大，所以α修改
选择第二个方案.
A(第一层)使自己利益最大,也就是A(第一层)的第二个方案不能差于第一个方案, 但是A(第三层)的一个 方案会导致利益为2, 小于3, 所以A(第三层)不会选择第一个方案, 因此B(第四层)也不用考虑第二个方
案.
S0 0 5 -3 3 3 -3 0 2 2 -3 0 -2 3 5 4 1 -3 0 6 8 9 -3
α-β 剪枝
Alpha-Beta剪枝用于裁剪搜索树中没有 意义的不需要搜索的树枝，以提高运算 速度
假设α为下界，β为上界，对于α
≤ N ≤ β: 若 α ≤ β 则N有解。 若 α > β 则N无解
❖ 图为整颗搜索树。这里使用极小 极大算法配合Alpha-Beta剪枝算 法，正方形为自己（A），圆为 对手（B）
为3
B(第四层)拥有一个方案使得A获利只有2，α=3, β=2, α > β, 说明A(第三层)只要选择第二个方案, 则B 必然可以使得A的获利少于A(第三层)的第一个方案,这样就不再需要考虑B(第四层)的其他候选方案了
,因为A(第三层)根本不会选取第二个方案,多考虑也是浪费.
B(第二层)要使得A利益最小,则B(第二层)的第二个方案不能使得A的获利大于β, 也就 是3. 但是若B(第二层)选择第二个方案, A(第三层)可以选择第一个方案使得A获利为 15, α=15, β=3, α > β, 故不需要再考虑A(第三层)的第二个方案, 因为B(第二层)不会

组合游戏1：详解Minimax和AlphaBeta剪枝算法本系列，我们来看看在⼀种常见的组合游戏——回合制棋盘类游戏中，如何⽤算法来解决问题。

⾸先，我们会介绍并解决搜索空间较⼩的问题，引⼊经典的博弈算法和相关理论，最终实现在⼤搜索空间中的Deep RL近似算法。

在此基础上可以理解AlphaGo的原理和⼯作⽅式。

本系列的第⼀篇，我们介绍3个Leetcode中的零和回合制游戏，从最初的暴⼒解法，到动态规划最终演变成博弈论⾥的经典算法：minimax 以及 alpha beta 剪枝。

获得最好的阅读体验，请点击最下⽅阅读原⽂，并在电脑上打开第⼀篇 [Leetcode中的Minimax 和 Alpha Beta剪枝]第⼆篇: ⼀些组合游戏的理论第三篇: 连接N个点的OpenAI Gym GUI环境第四篇: 蒙特卡洛树搜索（MCTS）和时间差分学习（TD learning）Leetcode 292 Nim Game (简单)简单题 Leetcode 292 Nim Game。

你和你的朋友，两个⼈⼀起玩 Nim游戏：桌⼦上有⼀堆⽯头，每次你们轮流拿掉 1 - 3 块⽯头。

拿掉最后⼀块⽯头的⼈就是获胜者。

你作为先⼿。

你们是聪明⼈，每⼀步都是最优解。

编写⼀个函数，来判断你是否可以在给定⽯头数量的情况下赢得游戏。

⽰例:输⼊: 4输出: false解释: 如果堆中有 4 块⽯头，那么你永远不会赢得⽐赛；因为⽆论你拿⾛ 1 块、2 块还是 3 块⽯头，最后⼀块⽯头总是会被你的朋友拿⾛。

定义为有个⽯头并采取最优策略的游戏结果，的值只有可能是赢或者输。

考察前⼏个结果：，然后来计算。

因为玩家采取最优策略（只要有⼀种⾛法让对⽅必输，玩家获胜），对于4来说，玩家能⾛的可能是拿掉1块、2块或3块，但是⽆论剩余何种局⾯，对⽅都是必赢，因此，4就是必输。

总的说来，递归关系如下：这个递归式可以直接翻译成Python 3代码# TLE# Time Complexity: O(exponential)class Solution_BruteForce:def canWinNim(self, n: int) -> bool:if n <= 3:return Truefor i in range(1, 4):if not self.canWinNim(n - i):return Truereturn False以上的递归公式和代码很像fibonacci数的递归定义和暴⼒解法，因此对应的时间复杂度也是指数级的，提交代码以后会TLE。

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
M
6
*
0
5
-3
*
3
6
5
4
-3
*
6
8

24 18 24 20 24 18 24 16 14 18 16 18 14 16 12 16 14 12 14 16 12 6 2 2 4 8 8 4 0 6 8 4 0 10 4 2 0 6 8 4 0 8 8 4 0 6 2 2 4
e2( m h )
马窝心和马卧槽大不相同！
东北大学机器博弈研究室
e2 (m, i, j ) e2,m
m x
x 分别为各兵种代码
东北大学机器博弈研究室
红车位置评估值(m=r)
14 16 12 12 12 12 6 4 8 2 14 12 18 16 18 12 14 14 20 18 24 26 24 18 20 16 12 12 18 18 18 12 12 12 18 16 22 22 22 16 18 12 14 12 18 18 18 12 14 12 16 14 20 20 20 14 16 12 10 8 14 14 14 8 10 6 8 6 14 12 14 6 8 4 4 8 16 8 16 8 4 8 10 6 14 12 14 6 10 2
博弈思维过程 展开博弈树
红 方 走 棋
红方先手
蓝 方 走 棋
红 方 走 棋
东北大学机器博弈研究室
如何表示博弈树？
树枝为着法 节点为局面
东北大学机器博弈研究室
计 算 机 博 弈 软 件 的 构 成
东北大学机器博弈研究室
象棋博弈软件的基本构成
• 人机界面
• 棋局表示与数组管理 • 着法生成与博弈树展开
• • • • • • • • 起源于中国 发展在日本（连珠棋） Renju / Go-Moku 棋盘 15×15 已被证明先手胜 禁手 换手 金球制改进球制

⼈⼯智能---最清晰的α-β剪枝算法基本思想：根据倒推值的计算⽅法，或中取⼤，与中取⼩，在扩展和计算过程中，能剪掉不必要的分枝，提⾼效率。

定义：α值：有或后继的节点，取当前⼦节点中的最⼤倒推值为其下界，称为α值。

节点倒推值>=α；β值：有与后继的节点，取当前⼦节点中的最⼩倒推值为其上界，称为β值。

节点倒推值<=β；α-β剪枝：（1）β剪枝：节点x的α值不能降低其⽗节点的β值，x以下的分⽀可停⽌搜索，且x的倒推值为α ；（2）α剪枝：节点x的β值不能升⾼其⽗节点的α值，x以下的分⽀可停⽌搜索，且x的倒推值为β ；再上个例题图，⽅便⼤家理解：先做个说明：有画弧线的是与，取较⼩值，没有的是或，去最⼤值。

第⼀步：2、9、3做⽐较，取最⼩值2，I点确定为2第⼆步：J点的1和I点2⼤⼩进⾏⽐较，如果1是J点的最⼩值，由于J的⽗节点是取较⼤值，1<2，⽆法升⾼D的值，所以J点的-1可以点可停⽌搜索，我们划掉该值。

第三步：I点2接着与K点的左值-1进⾏⽐较，如果-1是最⼩值，由于K的⽗节点取较⼤值，-1<2，⽆法升⾼D的取值，所以K点的右值可以停⽌搜索。

第四步：D的值可以确定为2第五步：L点的作⽤值进⾏⽐较，取较⼩值6，D值与L值相⽐较，由于E去较⼤值，假设L就是最⼤值，E=6，⼆B点取得是D和E的较⼩值，2<6，E的结果值⽆法降低B的取值，所以E的右枝可以截掉。

第六步：B的值可以确定为2第七步：N的左右值进⾏⽐较，取0,N点在和O点的左值-5进⾏⽐较，假设-5是最⼩值，0>-5,O点的取值⽆法升⾼⽗节点F的值，所以可以停⽌搜索O点的右枝。

第⼋步：F确定为0.第九步：F点假设是C的最⼩值，它和B点的值⽐较，2>0,也就是说C点的取值⽆法升⾼A点的取值，所以G和H都停⽌搜索。

第⼗步：A点取2.-----------------------------------------------------------------------------------------------【转】。

α-β过程的剪枝规则描述如下：在进行α-β剪枝时，应注意以下几个问题：（1）比较都是在极小节点和极大节点间进行的，极大节点和极大节点的比较，或者极小节点和极小节点间的比较是无意义的。

（2）在比较时注意是与"先辈层"节点比较，不只是与父辈节点比较。

当然，这里的"先辈层"节点，指的是那些已经有了值的节点。

（3）当只有一个节点的"固定"以后，其值才能够向其父节点传递。

（4）α-β剪枝方法搜索得到的最佳走步与极小极大方法得到的结果是一致的，α-β剪枝并没有因为提高效率，而降低得到最佳走步的可能性。

（5）在实际搜索时，并不是先生成指定深度的搜索图，再在搜索图上进行剪枝。

如果这样，就失去了α-β剪枝方法的意义。

在实际程序实现时，首先规定一个搜索深度，然后按照类似于深度优先搜索的方式，生成节点。

在节点的生成过程中，如果在某一个节点处发生了剪枝，则该节点其余未生成的节点就不再生成了。

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

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

这个MAX节点的最终倒推值就确定为这个α值。

通过对图3.10的搜索，来说明α-β剪枝搜索过程。

在搜索过程中，假定节点的生成次序是从上到下，从左到右进行的。

图中带圈的数字，表示节点的计算次序，在叙述时，为了表达上的方便，该序号也同时表示节点。

当一个节点有两个以上的序号时，不同的序号，表示的是同一个节点在不同次序下计算的结果。

过程如下：首先，从根节点开始，向下生成出到达指定节点深度的节点○1{注释：○1应为，○2...○32也一样表示}，由○1的值为0，可知○2≤0，继续扩展生成节点○3，由于○3的值5大于○2的值0，并且节点○2再也没有其它的子节点了，所以○4（与○2是同一个节点）的值确定为0。

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

有研究表明，在⿊⽩棋的中盘阶段，平均每个局⾯⼤约有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）。

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

1） 2）
MAX节点的α 值为当前子节点的最大倒推值； MIN 节点的β 值为当前子节点的最小倒推值；
对于一个与节点来说，它取当前 子节点中的最小倒推值作为它倒推值 的上界，称该值为β 值。
对于一个或节点来说，它取当前 子节点中的最大倒推值作为它倒推值 的下界，称该值为α 值。
Alpha-Beta剪枝用于裁剪搜索树中没有意义的不需要搜 索的树枝，以提高运算速度
A(第一层)使自己利益最大,也就是A(第一层)的第二个方案不能差于第一个方 案, 但是A(第三层)的一个方案会导致利益为2, 小于3, 所以A(第三层)不会选 择第一个方案, 因此B(第四层)也不用考虑第二个方案.
S0
0
5 -3 3
3 -3 0
2
2 -3 0 -2 3
5
4 1 -3 0
6
8
9
-3
假设α为下界，β为上界，对于α ≤ N ≤ β: 若 α ≤ β 则N有解。 若 α > β 则N无解

图为整颗搜索树。这里使用极小极大算法配合Alpha-Beta剪枝算法，正方形为自 己（A），圆为对手（B） 初始设尽量使得A获利最小，因 此当遇到使得A获利更小的情况，则需要修改β。 这里3小于正无穷大，所以β修改为3
B(第二层)要使得A利益最小,则B(第二层)的第二个方案不能使得 A的获利大于β, 也就是3. 但是若B(第二层)选择第二个方案, A(第三层)可以选择第一个方案使得A获利为 15, α=15, β=3, α > β, 故不需要再考虑A(第三层)的第二个方案, 因为B(第二层)不会选择第二个方案.
(第四层)这里17大于3，不用修改β
对于A(第三层)而言，自己获利越大越好，因此 遇到利益值大于α的时候，需要α进行修改，这 里3大于负无穷大，所以α修改为3