proc alpha-beta(n: node)
begin
L ←[n];
while {n ≠car(L) ∨<nに値が対応付けられていない>} do
begin
x ←car(L);
if <xに値vx が対応付けられている>;
then begin
p ←<xの親>;
;;;pとその子孫が木から刈り取れるか否かを決め
る
case <ノードpのタイプ> of
最小化ノード:
begin
α←<現在pとpの祖先の兄弟の最小化ノードに割り当てられている値の最大値．
そのような値が無ければ-∞とする>
if vx ≦α then <pとその全ての子孫をLから取り除く>;
end
最大化ノード:
begin
β←<現在pとpの祖先の兄弟の最大化ノードに割り当てられている値の最小値．
そのような値が無ければ+∞とする>;
if vx ≧β then <pとその全ての子孫をLから取り除く>;
end
end
if <pが刈り取れない>
then begin vp ← <現在pに対応付けられている値>;
case <ノードpのタイプ> of
最小化ノード: vp ← min(vp,vx);
最大化ノード: vp ← max(vp,vx);
end
<xをLから取り除く>
end
end
else if <xが終端ノードである>∨<深さ限界に達した>
else
begin
case <xのタイプ> of
最大化ノード: vx ← -∞;
最小化ノード: vx ← +∞;
end
<xの子供をLの先頭に追加する>;
end
end
end
|