搜索一个短的对抗回合树时,不能每一层都挑对自己最大的分数。轮到对手时,模型应假定对方会选让自己分数最低的分支,再把结果传回上一层。
树深三层,每个节点有两个动作,根层取最大、下一层取最小、再下一层取最大。八个叶子分数都从根玩家角度评价,同分选左边;没有随机事件。
叶子零至七评分[-1, -11, 19, 9, 15, 0, -9, 18]
最下层动作组0的叶子[-1, -11],轮到根玩家取最大,回传-1。
最下层动作组1的叶子[19, 9],轮到根玩家取最大,回传19。
最下层动作组2的叶子[15, 0],轮到根玩家取最大,回传15。
最下层动作组3的叶子[-9, 18],轮到根玩家取最大,回传18。
对手分支0收到[-1, 19],取最小后回传-1。
对手分支1收到[15, 18],取最小后回传15。
根节点比较[-1, 15],选择分支1,分数15;按同分优先左侧得到最终叶子4,其分数15。
按左到右界限搜索实际查看叶子[0, 1, 2, 4, 5, 6, 7],记录剪枝[区间左,区间右,下界,上界,跳过叶子][[2, 4, 19, -1, [3]]],根结果15。
剪掉的分支表示它不会改变当前上层选择,并不意味着那个分支本身没有值。发生剪枝的内部返回量可能只是足够使用的界限,不能把它当成已完整展开的节点评分。
先把叶子两两取最大,再把相邻两组取最小,最后在两大分支中取最大。还可用界限剪枝跳过已不可能改变上层选择的部分,但根结果必须与完整展开一致。
建议先按原始数据自己算一遍,保留中间状态后再与本例对照。发生分歧时,先寻找最早不同的步骤,检查边界是否包含、编号与坐标方向是否一致,以及状态是在事件之前还是之后更新。最终结果相同并不能替代对过程规则的理解,修改输入后也需要重新核算。
叶子评分是自定估计,不是实际胜负概率。有限深度、评价误差和随机机制都会影响决策。本例的对手会按最低根玩家分数选择,不适用于目标不同或合作的角色。