设为首页 - 加入收藏
广告 1000x90
您的当前位置:二四六天天好彩308K文字资料 > 博弈树搜索 > 正文

alpha-beta剪枝搜索

来源:未知 编辑:admin 时间:2019-07-12

  一种基于剪枝( -cut-off)的深度优先搜索(depth-first search)。

  将走棋方定为MAX方,因为它选择着法时总是对其子节点的评估值取极大值,即选择对自己最为有利的着法;

  将应对方定为MIN方,因为它走棋时需要对其子节点的评估值取极小值,即选择对走棋方最为不利的、最有钳制作用的着法。

  在对博弈树采取深度优先的搜索策略时,从左路分枝的叶节点倒推得到某一层MAX节点的值,可表示到此为止得以“落实”的着法最佳值,记为。

  在搜索此MAX节点的其它子节点,即探讨另一着法时,如果发现一个回合(2步棋)之后评估值变差,即孙节点评估值低于下界值,则便可以剪掉此枝(以该子节点为根的子树),即不再考虑此“软着”的延伸。

  同理,由左路分枝的叶节点倒推得到某一层MIN节点的值,可表示到此为止对方着法的钳制值,记为。

  显然此值可作为MAX方无法实现着法指标的上界。

  在搜索该MIN节点的其它子节点,即探讨另外着法时,如果发现一个回合之后钳制局面减弱,即孙节点评估值高于上界值,则便可以剪掉此枝,即不再考虑此“软着”的延伸。

  -剪枝是根据极大-极小搜索规则的进行的,虽然它没有遍历某些子树的大量节点,但它仍不失为穷尽搜索的本性。

本文链接:http://mzi-ads.com/boyishusousuo/639.html

相关推荐:

网友评论:

栏目分类

现金彩票 联系QQ:24498872301 邮箱:24498872301@qq.com

Copyright © 2002-2011 DEDECMS. 现金彩票 版权所有 Power by DedeCms

Top