[数学记录] 博弈论()

Part 0. 问题

只有公平博弈，不能操作者输。

Part 1. 基础理论

  • Bool SG ：必败态：后继全是必胜态；必胜态：后继存在必败态。
  • 必败态 SG 值 = 0
  • 当个游戏 SG 值为后继状态 SG 值的 mex。
  • 多个游戏 SG 值为当个游戏的 xor 值。

Part 2. 经典模型

Nim

若干堆石子，每次操作

若干堆石子，每次操作

SG 本身就是对应一堆石子。异或和 = 0 / \(\ne = 0\) 意味着先手必败 / 先手必胜。

Joker Nim

还是若干堆石子，但是两个玩家自己也有一堆石子。可以把自己的拿给中间的，也可以把中间的拿给自己的。

还是若干堆石子，但是两个玩家自己也有一堆石子。可以把自己的拿给中间的，也可以把中间的拿给自己的。

还是 Nim。因为一方如果把自己的给中间的，另一方就拿回来，这样另一方只增不减。

Lasker’s nim

还是取石子，但是可以分成把一堆变成两份。

还是取石子，但是可以分成把一堆变成两份。

一堆：\(f[i] = mex\{f[1], \dots, f[i – 1], f[a] ^ f[i – a]}\)。

找规律可以做到 O(1)。

Staircase Nim

每次可以往左边给若干石子。

每次可以往左边给若干石子。

结论：偶数格子的异或值。

左移奇数格，下一方可以再移动一次。所以奇数格的移动是没有意义的。
而偶数格左移一格到了奇数格相当于丢弃。

Anti-SG

无法操作者 win.

无法操作者 win.

结论：

  • 当所有单个游戏 SG = 0，且所有 SG 异或和 = 0
  • 当所有单个游戏 SG > 0，且存在 SG 异或和 > 0
————————

Part 0. 问题

只有公平博弈，不能操作者输。

Part 1. 基础理论

  • Bool SG ：必败态：后继全是必胜态；必胜态：后继存在必败态。
  • 必败态 SG 值 = 0
  • 当个游戏 SG 值为后继状态 SG 值的 mex。
  • 多个游戏 SG 值为当个游戏的 xor 值。

Part 2. 经典模型

Nim

若干堆石子，每次操作

若干堆石子，每次操作

SG 本身就是对应一堆石子。异或和 = 0 / \(\ne = 0\) 意味着先手必败 / 先手必胜。

Joker Nim

还是若干堆石子，但是两个玩家自己也有一堆石子。可以把自己的拿给中间的，也可以把中间的拿给自己的。

还是若干堆石子，但是两个玩家自己也有一堆石子。可以把自己的拿给中间的，也可以把中间的拿给自己的。

还是 Nim。因为一方如果把自己的给中间的，另一方就拿回来，这样另一方只增不减。

Lasker’s nim

还是取石子，但是可以分成把一堆变成两份。

还是取石子，但是可以分成把一堆变成两份。

一堆：\(f[i] = mex\{f[1], \dots, f[i – 1], f[a] ^ f[i – a]}\)。

找规律可以做到 O(1)。

Staircase Nim

每次可以往左边给若干石子。

每次可以往左边给若干石子。

结论：偶数格子的异或值。

左移奇数格，下一方可以再移动一次。所以奇数格的移动是没有意义的。
而偶数格左移一格到了奇数格相当于丢弃。

Anti-SG

无法操作者 win.

无法操作者 win.

结论：

  • 当所有单个游戏 SG = 0，且所有 SG 异或和 = 0
  • 当所有单个游戏 SG > 0，且存在 SG 异或和 > 0