博弈

Posted on Edited on

组合游戏

  1. 两个游戏者轮流操作
  2. 游戏的状态集有限，每种状态最多出现一次（游戏可以结束）
  3. 无法操作的输，另一个获胜（游戏必有胜负）
  4. 公平游戏。两个游戏者面对相同的状态允许有相同的操作。

状态判定

  1. 一个状态是必胜状态(N)当且仅当它至少有一个后继是必败状态。
  2. 一个状态是必败状态(P)当且仅当它的所有后继都是必胜状态。
  3. 特别地，没有后继的状态是必败状态。

后手必胜的必要条件

如果后手有必胜策略，则无论先手怎么取，都会存在后继可导致必败状态（即先手的所有后继都是必胜）。若先手能直接到达必败状态，则后手必输。

如Chomp!游戏（m*n棋盘，每次取某个点的所有右上格子，取到最后一个输）中，只要格子大于1，先手取最右上的一个格子，若后手能导致必败状态，则开局先手模仿后手的策略即可。故格子大于1时后手必败。

SG函数

设有状态x，令SG(x) = mex(S), S为x的所有后继状态的SG值的集合，mex(S)为不在集合中的最小非负整数。对于没有后继的状态，SG=0，因为S是空集。其余的SG值可由递推得到。
当且仅当SG(x) == 0, x是必败状态。

SG定理

一个总游戏的SG值等于子游戏的SG值的Nim和（异或和）

证明

  1. 证明P状态的所有后继都是N状态
    1. 异或和为零，对转移任意一状态，则异或和必不为零（新状态异或旧状态不为零），即后继必为N
  2. 证明N状态的后继存在P状态
    1. 异或和不为零，

Nim游戏

有n堆火柴，每堆有ai根火柴。每次选择一堆取走任意根，不能取的游戏者输。

考虑只有一堆的情况，设剩余火柴数为x。若x==0，没有后继状态，SG(0) = 0; 若x==1，所有后继状态的SG集合{0}，则SG(1) = 1; 若x==2，对应的S=={0，1}，SG(2) = 2; 归纳法证明SG(x) = x;

应用SG定理，对于多堆游戏，总游戏SG值为所有子游戏的SG值的Nim和，即所有堆火柴数的异或和。当且仅当异或和为0，先手必败。

组合游戏题解法

小范围内暴力计算子游戏SG值，找规律找到SG公式。

博弈搜索

CF ROUND 460 DIV2 F

题

  1. 圆桌放圆盘
    1. 对称性。先手占领圆心，后面被一步都模仿另一方。
  2. 硬币环取1-K连续
    1. 分类讨论K
  3. 威佐夫博弈：两堆石子，取任意个时可对两堆同时操作
    1. 记结论(x0=0, y0=0),(xk=mex{xi,yi}, yk=xk+k)必败
    2. $a_k=\frac{\sqrt{5}+1}{2}k$
    3. 扩展：三堆，可同时操作两堆
      1. 必败态少，跳过必胜态
  4. 每次一堆分别成异或加数两堆（每堆小于源堆）
  5. 反NIM游戏，先手必胜条件
    1. 每堆石子只有一个，NIM和为零
    2. 有一堆石子多于一个，NIM和不为零
  6. SJ定理（泛化反NIM游戏）先手必胜条件
    1. 每个子游戏SG值<=1，SG异或和为零
    2. 存在一个子游戏SG>1，SG异或和不为零
  7. Every-SG策略
    1. 必胜态使步骤尽量长
    2. 必败态使步骤尽量短
    3. 先手获胜充要条件：所有单一游戏SG值最大值是奇数
  8. 有根无向图删边游戏
    1. 若无环，Colon定理
    2. 可能有环，Fushion等价缩环变树
  9. 齐肯多夫定理：任何正整数可以唯一的表示为若干个不连续的斐波那契数之和
  10. 动态减法游戏（一倍，两倍，k倍）
  11. 翻硬币，最右必须由正变反
    1. 多种扩展
    2. 打表吧
    3. tartan定理
      1. 二维硬币分解成一维硬币的积，logn2求nim积。这种积有结合律，可扩展到更高维