博弈论中玩家的选择均为对自己最有利の理论最优解.
文中提到的必胜状态和必败状态来自要求的游戏起始状态, 但不由其推得.
这句话可能有些抽象，我也不太会表达(重度社恐),所以举个例子:
\(nim\)游戏,3堆石子,分别为1,2,3.
最暴力的解法,我们枚举所有可能的状态,
然后把他们构成一个有向无环图——这也是博弈论中的一种最简单的思路
.在构图的过程中,针对这个{1,2,3}, 一定会有一种{1,2,2}.
但这个{1,2,2}是必胜还是必败与{1,2,3}无关.相反,{1,2,2}的状态可以决定 {1,2,3}的状态.
\(nim\)游戏
首先，有个很经典的问题——\(nim\)游戏:有\(n\)堆石子，两名玩家轮流选一堆取走若干个(不能不取).拿走最后一枚石子的玩家获胜,没有石子可取的玩家失败.
这个问题的求解方式很抽象:求所有石子的异或和.若为0,先手必败，否则先手必胜.
这是因为, 一个必败状态要么直接寄，要么只能转化成必胜状态.一个必胜状态一定能转化成必败状态.
由此可见，我们可以从状态的角度理解博弈论.我们可以把所有状态构成一个有向无环图.
每个状态要么先手必胜,要么先手必败.
如果一个状态只能转移到必胜，则其为必败;如果它能转移到必败,则其为必胜.
但如果不是有向无环图呢?状态转移中出现环怎么办?
可以利用递推,先推出尽可能多的状态.
如果一个已知的状态为必败，则所有指向它的状态均为必胜;
如果一个状态只指向已知的必胜,则其为必败.
直到不能推出更多状态为止.可以使用拓扑排序.
可以验证未被递推的状态即为平局.