α-β剪枝技术解题过程

《α-β剪枝技术解题过程》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、α-β剪枝技术--知识点α-β剪枝技术首先分析极小极大分析法效率，上述的极小极大分析法，实际是先生成一棵博弈树，然后再计算其倒推值，至使极小极大分析法效率较低。于是在极小极大分析法的基础上提出了α-β剪枝技术。α-β剪枝技术的基本思想或算法是，边生成博弈树边计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率。具体的剪枝方法如下：(1)对于一个与节点MIN，若能估计出其倒推值的上确界β，并且这个β值不大于MIN的父节点(一定是或节点)的估计倒推值

2、的下确界α，即α≥β，则就不必再扩展该MIN节点的其余子节点了(因为这些节点的估值对MIN父节点的倒推值已无任何影响了)。这一过程称为α剪枝。(2)对于一个或节点MAX，若能估计出其倒推值的下确界α，并且这个α值不小于MAX的父节点(一定是与节点)的估计倒推值的上确界β，即α≥β，则就不必再扩展该MAX节点的其余子节点了(因为这些节点的估值对MAX父节点的倒推值已无任何影响了)。这一过程称为β剪枝。　　从算法中看到：(1)MAX节点(包括起始节点)的α值永不减少；(2)MIN节点(包括起始节点)的β值永不增加。　　在搜索期间，α和β值的计算如下：(

3、1)一个MAX节点的α值等于其后继节点当前最大的最终倒推值。(2)一个MIN节点的β值等于其后继节点当前最小的最终倒推值。4.15设有如图4.35所示的博弈树，其中最下面的数字是假设的估值，请对该博弈树做如下工作：计算各节点的倒退值；利用α-β剪枝技术剪去不必要的分支。4.15S0ACGHIJDBEKLMNF05-3336-2354-30689-34.15解答S0ACGHIJDBEKLMNF05-3336-2354-30689-30≥0≤-34.15解答S0ACGHIJDBEKLMNF05-3*36-2354-30689-30≥0≤-30≤03≥34.

4、15解答S0ACGHIDBEKLMNF05-3*3654-30689-30≤-30≤03≥3*0≥04≥4-34.15解答S0ACGHIDBEKLMNF05-3*3654-3689-30≤-303≥3*0≥04≥4-3*4≤46≥64.15解答S0ACGHIDBEKLMF05-3*3654-3680≤-303≥3*0≥04-3*4≤46≥64*4