博弈论中的必胜态与必胜态

信息竞赛新手对博弈论接触的并不多，在打一场牛客竞赛时暴露了问题。比赛之后回看题解，也有很多地方想不通。在终于搞懂之后，把自己当时的疑惑以及过程中的思考贴上来。

1.首先最大的疑惑就是为什么有只有必胜态或者必败态。凭什么就凭一个状态，就能断定不是输就是赢呢？这是当时最百思不得其解的一点，这和我们很多常识相反。例如象棋，围棋，如果存在必胜或必败策略，那么竞赛还有什么意义呢？我们平时的竞技类游戏存在必胜策略，实在是有冲击性。想不通这点，博弈相关始终是糊糊涂涂的。

比赛时，我始终在想，如何确定这个游戏是存在必胜或必败的呢？如何确定这个游戏不是像象棋或围棋一样不存在先手必胜呢？既然不能确定，又怎么能以必胜和必败为前提解题呢？后来在知乎的一篇文章中本人终于得到了解答，得以保住了岌岌可危的小世界观：

（https://zhuanlan.zhihu.com/p/20611132） 策梅洛定理（Zermelo’s theorem）指出，若一个游戏满足如下条件： 1.双人、回合制； 2.信息完全公开（perfect information）； 3.无随机因素（deterministic）； 4.必然在有限步内结束； 5.没有平局； 则游戏中的任何一个状态，要么先手有必胜策略，要么后手有必胜策略（下文把这两种状态分别称为“胜态”、“败态”）。 常见的牌类游戏大多不满足条件2、3；常见的棋类游戏（如井字棋、五子棋、围棋、象棋、跳棋）大多满足条件2、3，在正式竞技中也会通过禁止循环的方式保证条件4，但不一定满足条件5。而第一节中提出的三种游戏，满足全部5个条件。

（查证：象棋截止目前只有证明了存在先手必和的策略；围棋尚未找到先手必胜策略） 如上，象棋和围棋都不能同时符合上述全部条件，所以是否存在先手必胜，还有待后人商榷。至于平时遇到的竞赛题目大多符合5个条件，可以放心保证非必胜即必败。既然这是严谨的定理证明，那么终于可以放心解题了。

2.https://ac.nowcoder.com/acm/contest/11166/A，第二个疑惑是为什么打表时可以确定打完一步之后，可以保证下一步第一个遇到的a[i][j]=0是必败态呢。可以以0,0为必败，0,0可以走到的部分即为必胜，这很容易想。当时的疑惑是怎么说明下一个遇到的a[i][j]==0是必败。

解答如下：其实遍历是从小到大的，某一步能走到某个位置，前面都已经穷举考虑干净了，既然情况全了而且走不到必败，就只能走到必胜。比如5,7，是从5,6/5,4/5,1等等等等走过来的。只有能走到必败态的才是必胜态，目前的必败态是0,0/2,3，而这些必败态能走到的部分，都已经处理完毕了，变成1了，而5,7呢，不是1，也就是一步走不到必败态。一步走不到必败态，而穷举了所有的情况，剩下的一步能走到的情况所有的都是必胜态，也就是保证了5,7只能走到必胜态了。

3.SG函数，这个前人之述备矣。讲的很详细。 https://blog.csdn.net/strangedbly/article/details/51137432