文章目录
写在前面
听说CSDN给米就来了，不过作为一个品质优良的程序员来说，无私奉献是我应该做的，所以博主写的文章基本上不花钱，都是为了以后某天忘记了，自己能看懂才写的。so，我会写的很啰嗦，直到保证忘记的我能够看懂。
对于读者嘛，能看就看吧，我就不管了。
咱们一步一步来。
公平游戏
这里直接给出公平游戏的特征：
- 两个玩家博弈
- 对于当前状态来讲，之后先手操作，而与当前操作人是谁无关
- 游戏一定可以进行完
- 游戏的结果是有限个
三个概念
先手必胜态：即谁是先手，在保证后续都聪明的情况下（是考点），此局必胜。
先手必败态： 同理，先手必败（在都保证聪明的情况下）
后继状态： 当前状态的下一个状态就是后继状态~~（一开始我就没明白后继状态，以为是后面所有的状态）~~
然后我们来看几个显然的性质：
- 如果是必胜态当且仅当至少一个后继状态是必败态
- 没有后继状态的一定是毕生态
- 如果是必败态(特意空着)
- 一个状态的后继状态都是必胜态，则当前为必败态。
这个《特意空着》 是我在写性质的时候突然有了疑问？
显然：一个状态的后继状态都是必胜态，则当前为必败态。
这句话一定是正确的，但是反过来来呢？即：如果当前是必败态，那么后续状态都是必胜态？
oiwiki 的定理三：一个状态是必败状态当且仅当它的所有后继状态均为必胜状态。
我们来思考一下，这是对的吗？
举个例子，两堆石子，各 4 4 4 个，问在都是最优策略的情况下谁会赢？
很显然，有个先手必败的策略就是，无论先手选什么，后手跟着选另一堆相同的数，这样必败，那么这就是先手必败喽
我们再来看定义，如果定理三是正确的，那么对于后继状态来讲，必须都是必胜态，可事实如此吗？
当先手选 2 2 2 的时候时候，后者可以有多种选择，而其中选 2 2 2 是一定会胜利的，但是！其他状态可以保证他毕胜吗，显然不行，手玩就可发现不行。
我们发现：后续状态并不全是必胜状态呀？
那应该如何解释？
其实，无论是先手必胜还是先手必败态，我们都是在双方绝对聪明的情况下考虑的，也就是说：上述的状态之中，只有选 2 2 2 才是后继状态，其他是不可能存在的，因为题目条件是：双方都会采取当前最优策略。
所以，通过这个疑问，我们学到了：必胜和必败成立的前提是，双方采取最优策略，否则不成立。
看到这里，不免会抱怨，为什么讨论这个问题，感觉是对的不就行了吗？
因为这个定理三在和后面的异或和联系起来的时候，定理三的等价语言就是:
“当 S G 1 ⊕ S G 2 ⊕ . . . . = 0 SG_1 \oplus SG_2 \oplus....=0 SG1⊕SG2⊕....=0 时，改变其中一个 S G SG SG值，不存在 S G 1 SG^1 SG1 满足 S G 1 1 ⊕ S G 2 ⊕ . . . . = 0 SG^1_1 \oplus SG_2 \oplus....=0 SG11⊕SG2⊕....=0 再次成立”
很显然，单单从异或和方面来讲，这是正确的，但是如果你搞不懂定理三，就不明白为什么可以用异或和表示必胜或者必败态。
标签：状态,浅谈,必败,....,后继,必胜,SG,函数 From： https://blog.csdn.net/zxsure/article/details/142799073