组合博弈

发表于 |

总结一下网上教程关于组合博弈的部分要点

Nim 博弈

Nim游戏的典型形式是假设有N堆石子数量是 $ a_1, a_2 .. a_n $，两人轮流从某一堆取若干个（不能一个不取），最后不能取的人算失败。
为了解决这个问题，先定义必败态，也就是先手必败，这里先手必败指的不是游戏开始时的先后手，而是指的当前局面的先后手。必败态的所有的下一步都是非必败态，非必败态存在某个下一步是必败态。因此假设A此时拿到一个必败态，那么无论他如何移动，都会留给B一个非必败态；而B的非必败态经过移动可以留给A一个必败态。
可以发现，如果每一堆的石子数的和异或起来为0的话，当前状态是必败态，即 $ a_1 \ xor \ a_2 \ xor \ .. \ xor \ a_n = 0 $ 是必败态（Bouton’s Theorem）。这是因为：

  1. 不能取时每一堆石子都是0，因此异或的结果还是0，因此是必败态
  2. 假设此时A是一个必败态，即 $ a_1 \ xor \ a_2 \ xor \ .. \ xor \ a_n = 0 $，假设存在$ a_i $使得取完之后的 $ a’_i $ 也满足异或结果为0。由于异或具有消去律，因此$ a’_i = a_i $
  3. 假设此时A是一个非必败态，即 $ a_1 \ xor \ a_2 \ xor \ .. \ xor \ a_n = k \neq 0 $，总能找到一个 $ a_i $ 使得 $ a_i \ xor \ k \lt a_i $，这样的构造只需要 $ a_i $ 把 $k$ 最高位的1异或掉就行了。这样把 $ a_i $ 替换成 $ a_i \ xor \ k $ 就能得到一个新的异或为0的必败态给对方。

ICG和SG函数

由此可以引出ICG和SG函数，刚才的必败态对应于SG函数中的P-position，P是Previous，指的是刚取完石子的那人赢，因为只有两个人玩，所以就是先手输。对应的状态是N-position，N指的是Next。
ICG（Impartial Combinatorial Games）指的是公平组合游戏，满足下面的性质：

  1. 两名选手轮流行动，每一次行动可以在有限合法操作集合$ f $中选择一个，若轮到某位选手时，该选手的合法操作集合为空，则这名选手判负
  2. 游戏的任何一种可能的局面（position），合法操作集合只取决于这个局面本身；局面的改变称为“移动”（move）

任何一个ICG都可以通过把每个局面看成一个顶点，对每个局面和它的子局面连一条有向边来抽象成一个有向无环图。如果 $\langle x, y \rangle \in E$，表示从x局面可以到达y局面。

首先定义mex（minimal excludant）运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。例如 $ mex \lbrace 0, 1, 2, 4 \rbrace = 3 $，$ mex \lbrace \rbrace = 0 $。
对于ICG对应的DAG中的每一个顶点（局面），定义SG函数 $ sg(x) = mex \lbrace sg(y) \mid \langle x, y \rangle \in E \rbrace $。当 $ sg(x) = k $ 时表示 $ \forall i \ , 0 \le i \lt k, \ \exists \ \langle x, y \rangle \in E, \ sg(y) = i \ $ ，也就是说，$k = sg(x)$ 是最小的不属于 $sg(y)$的值，其中$y$是$x$的所有后继局面。下面介绍这个值的具体意义。
事实上SG函数拥有和Nim游戏同样的性质，$ sg(x) = 0 $ 对应着必败态，$ sg(x) \neq 0 $ 对应着非必败态，表示通过可选操作 $ k = sg(x) $ 个可以到达一个P状态。
以一个较为简单的取石子问题为例，假设有1堆n个的石子，每次只能取1、3、4个石子，先取完石子的人胜利，求各个状态的SG值。现在定义SG函数$sg(i)$为状态i下的石子数，显然有$sg(0) = 0$，设操作$f=[1,3,4]$表示可以取1、3、4个石子。
当$x=1$时，可以取走$1$个石子（不能不取），$y = \lbrace 0 \rbrace$，$sg(1) = mex \lbrace sg(1) \rbrace = 1$
当$x=2$时，可以取走$1$个石子，$y = \lbrace 1 \rbrace$，$sg(2) = mex \lbrace sg(2) \rbrace = 0$
当$x=3$时，可以取走$\lbrace 1, 3 \rbrace $个石子，$y = \lbrace 0, 2 \rbrace$，$sg(3) = mex \lbrace sg(0), sg(2) \rbrace = 1$
当$x=4$时，可以取走$\lbrace 1, 3, 4 \rbrace $个石子，$y = \lbrace 0, 1, 3 \rbrace$，$sg(4) = mex \lbrace sg(0), sg(1), sg(3) \rbrace = 2$
当$x=5$时，可以取走$\lbrace 1, 3, 4 \rbrace $个石子，$y = \lbrace 1, 2, 4 \rbrace$，$sg(5) = mex \lbrace sg(1), sg(2), sg(4) \rbrace = 3$
现在假设A面临5个石子的局面，他选择可选操作“取3个”，将剩2个石子的局面留给B，B发现$sg(2) = 0$，是个必败态，无论他如何取都将不敌A。
对于刚才的取石子游戏，可以想象成在A和B一个有向图上从开始的点轮流沿有向边移动棋子，直到到达一个出度为0的点。而SG函数的意义表示一堆石子的个数。而现在有n堆石子，每一堆石子都对应一个SG函数，这个游戏就可以分成n个子游戏。对于这样的情况，有Sprague-Grundy Theorem给出该游戏的和的SG函数值是它的所有子游戏的SG函数值的异或，即 $ sg(G) = sg(G_1) \ xor \ sg(G_2) \ xor \ .. xor \ sg(G_n) $。

例题 POJ 2505

题意

设p初始值为1，A和B轮流对p乘上一个2和9之间的数，谁先大于等于n谁就获胜