博弈论

一些简单的定义：

必胜点（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$那一堆石子。则后手得到$(1,2k-1)$必胜。因此不会这样选。 2. 先手取走$1$那一堆石子。则后手得到$(0,2k)$局面必败。先手胜。 3. 两堆石子都取。则后手得到$(0,2k-1)$必胜，因此不会这样选。

因此我们得到结论：$(1,\ast )$是必胜点。

由于$(1,\ast )$必胜，且$(2,2)$只能走到$(1,\ast )$，所以$(2,2)$必败。
故$(2,3)$和$(3,3)$是必胜点。由于$(2,4)$是必败点，所以$(3,4)$是必胜点。

稍微推理一番就得知：

(偶数,偶数)是必败点。
(奇数,偶数)是必胜点。
(偶数,奇数)是必胜点。
(奇数,奇数)是必胜点。

历经艰险，总算把事情推完了。博弈论真是迷人……

Nim游戏

Alice和Bob正在玩一个游戏，Alice先手。

他们面前有三堆石子。Alice和Bob轮流操作，每次从某堆中取走任意张。
没石子可取的玩家失败。

那么这个博弈如何做？

抱歉，我也不会证，只知道结论，如果要证，请找Link神。

像之前那样以$(a,b,c)$表示状态。结论是($\oplus$表示异或)：
1. 当且仅当$a\oplus b\oplus c=0$时，$(a,b,c)$是必败点。 2. 否则就是必胜点。

结论可以推广：
若有$n$堆石子，则当且仅当$a\oplus b\oplus c\oplus d\cdots =0$时，此点是必败点。

SG函数

留坑待补