博弈论

一些简单的定义:

必胜点(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,*)$是必胜点。

由于$(1,*)$必胜,且$(2,2)$只能走到$(1,*)$,所以$(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函数

留坑待补


CC0协议 @ ruanxingzhi 2017. CC0是啥玩意?
Home apps close