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