赞
踩
参考:https://blog.csdn.net/weixin_42192933/article/details/105873866
这里以流程图来表述
图中红 线 \textcolor{Red}{红线}红线代表被剪枝的部分,蓝 线 \textcolor{Blue}{蓝线}蓝线代表流程,正方形代表maximum,圆形代表minimum
剪枝算法内部旨在求α \alphaα的下界极大值,β \betaβ的上界极小值
讨 论 \textcolor{Red}{讨论}讨论:
\qquad流程5与流程10的差别:
\qquad在流程5, 经 过 i f α ≥ β t h e n 经过\ if\ \ α ≥ β\ then经过 if α≥β then 的判断,可以知道数字6直接导致超出区间范围,立刻剪枝,另一分支不再被访问
\qquad在流程10,区间范围是[4,inf],由于2 ≤ 4 2\leq 42≤4,所以α \alphaα不发生改变, ∴ 4 ≤ i n f \therefore\textcolor{Red}{4\leq inf}∴4≤inf,符合范围,v的值被传递出去,传递出去之后,剪枝
伪代码:
- function alphabeta(node, depth, α, β, maximizingPlayer) is
- if depth = 0 or node is a terminal node then
- return the heuristic value of node
- if maximizingPlayer then
- value := −∞
- for each child of node do
- value := max(value, alphabeta(child, depth − 1, α, β, FALSE))
- α := max(α, value)
- if α ≥ β then
- break (* β cut-off *)
- return value
- else
- value := +∞
- for each child of node do
- value := min(value, alphabeta(child, depth − 1, α, β, TRUE))
- β := min(β, value)
- if α ≥ β then
- break (* α cut-off *)
- return value
α代表下界,β代表上界,α初始定义为-inf,β初始定义为inf
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。