《α-β 剪枝.ppt》由会员分享，可在线阅读，更多相关《α-β 剪枝.ppt（19页珍藏版）》请在三一文库上搜索。
1、1） MAX节点的值为当前子节点的最大倒推值；2） MIN 节点的值为当前子节点的最小倒推值；,对于一个与节点来说，它取当前子节点中的最小倒推值作为它倒推值的上界，称该值为值。 对于一个或节点来说，它取当前子节点中的最大倒推值作为它倒推值的下界，称该值为 值。,Alpha-Beta剪枝用于裁剪搜索树中没有意义的不需要搜索的树枝，以提高运算速度,假设为下界，为上界，对于 N : 若 则N有解。 若 则N无解,图为整颗搜索树。这里使用极小极大算法配合Alpha-Beta剪枝算法，正方形为自己（A），圆为对手（B） 初始设置为负无穷大，为正无穷大,对于B(第四层)而已，尽量使得A获利最小，因此当遇到
2、使得A获利更小的情况，则需要修改。这里3小于正无穷大，所以修改为3,(第四层)这里17大于3，不用修改,对于A(第三层)而言，自己获利越大越好，因此遇到利益值大于的时候，需要进行修改，这里3大于负无穷大，所以修改为3,B(第四层)拥有一个方案使得A获利只有2，=3, =2, 说明A(第三层)只要选择第二个方案, 则B必然可以使得A的获利少于A(第三层)的第一个方案,这样就不再需要考虑B(第四层)的其他候选方案了,因为A(第三层)根本不会选取第二个方案,多考虑也是浪费.,B(第二层)要使得A利益最小,则B(第二层)的第二个方案不能使得A的获利大于, 也就是3. 但是若B(第二层)选择第二个方案, A(第三层)可以选择第一个方案使得A获利为15,=15, =3, 故不需要再考虑A(第三层)的第二个方案, 因为B(第二层)不会选择第二个方案.,A(第一层)使自己利益最大,也就是A(第一层)的第二个方案不能差于第一个方案, 但是A(第三层)的一个方案会导致利益为2, 小于3, 所以A(第三层)不会选择第一个方案, 因此B(第四层)也不用考虑第二个方案.,