例题

来自刷题网站LeetCode “464.我能赢吗”

题目描述：
（1）在 “100 game” 这个游戏中，两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，先使得累计整数和达到或超过100 的玩家，即为胜者。
（2）如果我们将游戏规则改为 “玩家不能重复使用整数” 呢？
（3）例如，两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。
（4）给定两个整数 maxChoosableInteger （整数池中可选择的最大数）和 desiredTotal（累计和），若先出手的玩家是否能稳赢则返回 true ，否则返回 false 。假设两位玩家游戏时都表现最佳。

定理内容均来自 知乎

Sprague-Grundy定理（简称SG）

1. 满足下列条件：

• 双人、回合制；
• 信息完全公开；
• 无随机因素；
• 必然在有限步数内结束；
• 没有平局；
• 双方可采取的行动及胜利目标都相同；
• 这个胜利目标是自己亲手达成终局状态，或者说走最后一步者为胜；

则游戏中的任何一个状态，要么先手有必胜策略（胜态），要么后手有必胜策略（败态）。

2. 必胜策略的构造过程

• 对于终局状态，根据游戏规则可以判定“先手者”（即面对此状态的玩家）的胜负；
• 对于非终局状态A，可以考虑先手玩家走一步之后的所有可能状态（称为A的“次态”）：若A的次态全都是胜态，则A本身就是败态；否则，A为胜态，且必胜策略就是在次态中选择一个败态留给对方。由于游戏会在有限步内结束，这个递归过程必然能够终止。

根据策海格 定理，使用记忆化搜索算法判断一个状态是胜态还是败态：

// 使用哈希表存放状态
unordered_map<int,bool> men;
// 判断状态A是否为胜态
bool win(A){
    if(!men.count(A)){
        if(isFinal(A)){   // 若A为终局
            men[A] = rule(A);  // 根据题目规则判断A的胜负
        }
        else {
            // 并非正确语句，只是为了方便理解
            // 判断A的所有次态是否是败态
            men[A] = (!win(for(auto B : nextStates(A))));
        }
    }
}

根据 Sprague-Grundy 定理满足条件，题目中的每个状态都可以按照下面规则赋予一个非负整数，称为 Sprague-Grundy 数：

• SG（A） = mex {SG（B） | A -> B}
• 式中：A,B表示状态，A->B代表A状态经一步行动可以到达B状态，mex表示一个集合所不包含的最小非负整数；

SG数的性质：

• SG数为0的状态，后手必胜；SG数为正的状态，先手必胜；
• 若一个母状态可以拆分成多个相互独立的子状态，则母状态的SG数等于各个子状态的SG数的异或。

将记忆化搜索程序进行优化：

// 编写语言 python
mem = {}
def SG(A):  // 定义一个函数，求状态A的SG数
    if A not in mem:
        S = sub_states(A)  // sub_states(A)将A尽可能细致地拆分成子状态
        if len(S) > 1:  // A可以拆分，用子状态的异或求其SG数
            mem[A] = reduce(operator.xor, [SG(B) for B in S])
        else:   // A不可拆分，根据定义求其SG数
            // next_states(A)返回A的所有次态<注意这条语句蕴含了“终局态的SG数为0”
            mem[A] = mex(set(SG(B) for B in next_states(A)))
    return mem[A]