一种博弈树静态估值算法——ΔFeature状态估值

在考虑下棋操作对棋盘影响的局部性后,提出了棋博弈的Δfeature状态估值算法,通过计算博弈树中相邻结点的特征变化来避免在叶结点上扫描整个棋盘,有效地减少了静态估值的时间开销。若棋子影响的局部范围足够小,还可以考虑将局部范围的所有情况列成表,以查表代替棋形匹配。ΔFeature状态估值算法也可以与其它优化博弈树搜索的方法一同使用,达到更好的效果。

棋子问题的算法分析——2003年第11期题解

由于是求必胜状态，因此在搜索过程中，先假设甲方(x)在第k步已经处于必胜状态，那么，乙方(o)的第k步无论下在哪儿，甲方下第k+1步的时候，至少能够找到一个位置保持这个状态，即要么甲方已经赢了，要么继续保持这个必胜状态。因为甲方一直都能够保持这个必胜状态，所以甲方最后一定能够赢棋，因此甲方的第k步就是本题的解。