博弈论
一些简单的定义：
必胜点（N点）：走到必胜点的玩家一定胜利。
必败点（P点）：走到必败点的玩家一定失败。
定理1.所有游戏终结的点都是必败点。
定理2.所有一步能走到必败点的就是必胜点。因为对手将面临必败点。
定理3.通过一步操作只能到必胜点的就是必败点。因为对手将获得必胜点。
取石子游戏
有两堆石子和两个玩家。
每回合，玩家可以选择从某一堆取走一个石子，或者从两堆中都取走一个石子。
最后无法操作的玩家失败。
分析
以**(A,B)表示当前的状态：第一堆有A个石子，第二堆有B个石子。
由于这个游戏没有和局，所以某个状态不是必败点就是必胜点**。
首先考虑终结点：两堆石子都空了，面对这个状态的玩家必败。
于是有了第一个必败点：**(0,0)**。
定理2.所有一步能走到必败点的就是必胜点。因为对手将面临必败点。
由于**(0,1)和(1,0)能走到(0,0)**，因此它们是必胜点。
定理3.通过一步操作只能到必胜点的就是必败点。因为对手将获得必胜点。
考虑**(0,1)，显然(0,2)只能走到(0,1)，所以(0,2)是必败点。由于(0,3)能走到(0,2)让对手必败，所以(0,3)是必胜点。
以此类推，我们得到结论：(0,2k)是必败点，(0,2k+1)**是必胜点。
如何让对手面临**(0,2k)呢？显然，当目前局面是(1,2k+1)时，可以两堆各取一个石子，所以(1,2k+1)是必胜点。
类似地，(1,2k)**是必胜点，因为：
- 先手不取1那一堆石子。则后手得到**(1,2k-1)**必胜。因此不会这样选。
- 先手取走1那一堆石子。则后手得到**(0,2k)**局面必败。先手胜。
- 两堆石子都取。则后手得到**(0,2k-1)**必胜，因此不会这样选。
因此我们得到结论：**(1,*)**是必胜点。
由于**(1,)必胜，且(2,2)只能走到(1,)，所以(2,2)必败。
故(2,3)和(3,3)是必胜点。由于(2,4)是必败点，所以(3,4)**是必胜点。
稍微推理一番就得知：
(偶数,偶数)是必败点。(奇数,偶数)是必胜点。(偶数,奇数)是必胜点。(奇数,奇数)是必胜点。
历经艰险，总算把事情推完了。博弈论真是迷人……
Nim游戏
Alice和Bob正在玩一个游戏，Alice先手。
他们面前有三堆石子。Alice和Bob轮流操作，每次从某堆中取走任意张。
没石子可取的玩家失败。
那么这个博弈如何做？
抱歉，我也不会证，只知道结论，如果要证，请找Link神。
像之前那样以(a,b,c)表示状态。结论是(⊕表示异或)：
- 当且仅当a ⊕ b ⊕ c = 0时，(a,b,c)是必败点。
- 否则就是必胜点。
结论可以推广：
若有n堆石子，则当且仅当a ⊕ b ⊕ c ⊕ d… = 0**时，此点是必败点。
SG函数
留坑待补
-------------本文结束感谢您的阅读-------------
本文作者： jfy
本文链接： http://example.com/2019/10/17/%E5%8D%9A%E5%BC%88%E8%AE%BA/
版权声明： 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处！
