极大极小值算法、α-β剪枝算法的理解
-
定义：极大极小值算法（摘自百度百科）
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 == Belse{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.csdn.net/u013351484/article/details/50789521#commentBox
https://blog.csdn.net/UFv59to8/article/details/79331675
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！