博弈论

一些简单的定义与定理

必胜点(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轮流操作,每次从某堆中取走任意张.
没石子可取的玩家失败.

分析

像之前那样用(a,b,c)表示状态.

结论是:

  • 当且仅当a Xor b Xor c=0时,(a,b,c)是必败点.
  • 否则就是必胜点.

结论可以推广:

  • 若有n堆石子,则当且仅当a Xor b Xor c Xor d ⋯ = 0时,此点是必败点.

SG函数

等会

显示 Gitment 评论