极大极小值算法、α-β剪枝算法的理解
-
定义:极大极小值算法(摘自百度百科)
Minimax算法 又名极小化极大算法,是一种找出失败的最大可能性中的最小值的算法(即最小化对手的最大得益)。通常以递归形式来实现。=========================
谈一下我的理解:
刚开始看极大极小算法的时候,说实话并不是很理解。其实通俗的意思:既然是博弈,那必然要使自己的利益最大化,也就是想将自己分数得的尽可能的高,而对手是尽可能的去选取最小的,给我留下最不利的局面来选择 -
极大极小算法图解分析:
当然如果觉得我的图太少,可以转向这篇博客
图解比较清晰 -
伪代码:
//伪代码:A表示己方,B表示对方
int MaxMin(int level, int curVal)
{
if (level == 0) return 该局面结点的估价值;
int best;
if(player == A){
best = INT_MIN; //初始化最小值,之后才会更新取到更高分
while(子树不空){
int newval = MaxMin(level-1,best);
if (newval > best)
{
best = newval;
}
}
}
//player == B
else{
best = INT_MAX; //初始化最大值,之后才会更新取到更低的分留给对方
while(子树不空){
int newval = MaxMin(level-1,best);
if (newval < best)
{
best = newval;
}
}
}
return best;
}
但是我们发现最小最大值算法将所有的子树全部扫描,会很浪费时间和空间。
所以就有了α-β剪枝算法的优化。下面谈一下我对α-β剪枝算法的理解,个人很菜,欢迎各位dalao及时指出错误~谢谢!
二、α-β剪枝算法
-
α-β剪枝算法的定义:(摘自百度百科)
AlphaBeta剪枝算法是一个搜索算法旨在减少在其搜索树中,被极大极小算法评估的节点数。这是一个常用人机游戏对抗的搜索算法。它的基本思想是根据上一层已经得到的当前最优结果,决定目前的搜索是否要继续下去。 -
图解:
其中α代表的是下界,β代表的是上界,即在(α,β)的范围内进行搜索
初始值是(α,β)= (-∞,+∞)
所以:
(1)对手也就是player B
负责更新上限,目的是使上限尽可能的小,留给player A
最不利的局面。
(2)己方也就是player A
负责更新下限,目的是使下限尽可能的大,保证最次的情况下也可以提高分数,留给自己最好的局面我的图解:
解释一下:对于level = 2
拥有的第一个方案,己方获利值为3,那么α=3
,然后向下传递,现在选到2的,那么β = 2
,目前存在α>β
,则不需要再对这个节点及其子树进行遍历,因为player A
根本不会在乎此方案会不会比β = 2
小的数,虽然player B
想去这个分支去寻找更小的数,但是player A
压根不会理会,白白浪费空间,SO直接剪枝。
有一张更详细的图解来自此篇博文
- 伪代码:
int AlphaBeta(int level,int CurVal)
{
int alpha = INT_MIN;
int beta = INT_MAX;
if(level == 0) return 该局面结点的估价值;
if(player == A){
while(子树不空){
int newval = AlphaBeta(level-1,alpha);
if (newval > alpha){
alpha = newval;
}
if(alpha > beta)
return alpha;
}
}
return alpha;
else{
while(子树不空){
int newval = AlphaBeta(level-1,beta);
if (newval < beta){
beta = newval;
}
if(alpha > beta)
return beta;
}
}
return beta;
}
参考博客:
https://www.jianshu.com/p/3b464aeba078
https://blog.****.net/u013351484/article/details/50789521#commentBox