NO.81——极大值极小值α-β剪枝博弈树搜索

引言

• 对于一个与节点MIN，若能估计出其上确界beta，以及MIN的父节点的下确界alpha，如果alpha>=beta，则不必扩展MIN的剩余子节点，这个过程称为alpha剪枝。
• 对于一个或节点MAX，若能估计出其下确界alpha，以及MAX的父节点的上确界beta，如果alpha>=beta，则不必扩展MAX的剩余子节点，这个过程称为beta剪枝。

1. F的第一个节点K=4，那么作为MIN节点F的上确界是beta=4，现在拿出L和M来比较，发现都大于4，此时确定F的上确界beta=4。那么F的父节点，作为MAX节点的C，其下确界alpha=4，将4沿C—G传递给G。
2. G的第一个子节点N=1，那么更新作为MIN的G的上确界beta=1，此时发现，G的父节点C，下确界alpah=4，发现4>1，所以不必扩展G的剩余子节点，通过alpha剪枝剪掉。
3. C的下确界alpah=4，父节点A的上确界beta=4，将4沿A—D---H传递给H，H的第一个节点P=5，那么更新MIN的H的上确界beta=5，此时发现4<5，所以仍需要扩展H的剩余子节点Q，Q=8，所以作为MIN的H的上确界仍然为5。
4. 更新H的MAX父节点D，其下确界alpha=5，此时发现5>4，所以不必扩展D的剩余子节点，通过beta剪枝剪掉。
5. 此时C下确界alpha=4，D下确界alpha=5，那么确定作为MIN的A的上确界beta=4，作为MAX的父节点的S0下确界alpha=4。
6. 将4沿S0—B---E—I传递给I。I的第一个子节点R=0，然后更新作为MIN的父节点I的上确界beta=0，此时发现1>0，所以不必再探索I的剩余子节点，通过alpha剪枝剪掉。
7. 更新作为MAX的E的下确界alpha=0，将0沿E—J传递给J。首先看J的第一个子节点S=-6，更新J的上确界beta=-6，发现0>6，所以不必探索J的剩余子节点，通过alpha剪枝剪掉。
8. I上确界beta=0，J上确界beta=-6，所以更新E的下确界alpha=0。更新E的MIN父节点B的上确界beta=0，发现4>0，所以不必探索B的剩余子节点，通过alpha剪枝剪掉。
9. 最终完成搜索。