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

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