## 组合博弈 玩家:2人 道具：23张扑克牌 规则: 1. 双方轮流取牌 2. 没人每次仅限于取1张、2张或者3张 3. 扑克牌取光，游戏结束 4. 最后取牌的一方为胜者 如何取胜？ 倒退过来，当还有4张牌但是轮到对手抽的的时候，你就赢了。 那么8张...20张，即你一开始抽3张牌。 这个游戏的本质是： > **每一轮两个人加起来必须拿4张** 什么是组合游戏 1. N 个玩家 2. 游戏的操作状态是一个有限的集合（比如，限定大小的棋盘，一定的牌数） 3. 游戏双方轮流操作 4. 双方的每次操作必须符合规定 5. 当一方不能将游戏继续进行，游戏结束； 6. 无论如何操作，游戏总能在有限次操作后结束 取子游戏 必败点 （P点）:前一个选手（previous player)对方将取胜的位置称为必败点 必胜点(N点):下一个选手(Next Player )将取胜的位置称为必胜点（至少有一种方法可以赢） **P点（必败点）**：轮到当前玩家时 **必输** **N点（必胜点）**：轮到当前玩家时 **有至少一种方法可以赢赢** 终结点：游戏结束；比如说0张牌 必败点：还剩4张牌。 必胜点：比如还剩1-3张牌 如果换成只能取2或者3，终结点就是1或者0 因此，所有终结点一定是必败点，而必败点不一定是终结点 从任何必胜点操作，至少有一种方法(让对手)进入必败点。 23张牌就是必胜点 无论如何操作，从必败点都只能进入(对手的)必胜点 4张牌就是必败点 N点一定 **存在 → P** P点一定 **全部 → N** 算法实现—— 1. 将所有终结位置标记为必败点（P点） 2. 将所有/ 一步操作能进入必败点（P点）的位置标记为必胜点（N点） 3. 如果从某个点开始的 /所有一步操作都只能进入必胜点（N点）,则将该点标记为必败点（P点） 4. 如果在步骤3未能找到新的必败点（P点），终止，否则，返回步骤2. 从0这个终结位置开始倒推，直到到23张牌是必败or必胜点 | 0 | 1 | 2 | 3 | 4 | 5 | | ---- | ---- | ---- | ---- | ---- | ---- | | P | N | N | N | P | N | 怎么求得呢？ > **每一轮两个人加起来必须拿4张** | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | | P | N | P | N | N | N | N | P | 14张牌的时候？ 可以见得这是7张牌一循环，那么为必败 n行m列，右上角放一个硬币，每个人可以向左、向下、向左下移动，直到不可移动。 那么先手是必赢还是必输 左下角必败点，那么围绕的三个格子为必胜点。 倒数第一行为PN交替 倒数第二行为全为N... 所以nxm满足什么条件，先手是P点？ 即，n、m为奇数则为P点 有一个偶数则为N点 Nim 两个玩家 有三堆扑克牌（比如5，7，9） 玩家每次操作是选取其中一堆牌，然后取走任意张 最后一次取的一方为获胜方 先手如何获胜？ (0,0,0) 终结点，N (0,0,x) N (0,k,k) P 必败 Nim-Sum 定义:假设$(x_m,,,x_0)_2和(y_m...y_0)_2$的nim-su $(x_m,,,x_0)_2 \oplus (y_m...y_0)_2=(z_m,...,z_0)_2 \\ z_k=x_k+y_k (mod \ 2) (k=0 ...m )$ 对于nim游戏的某个位置（x1,x2,x3)，当且仅当它的各部分nim-sum=0时（$x_1\oplus x_2 \oplus x_3 =0$），则当前位置必然为必败点。 异或运算就是不进位加法 状态dp就是运用异或运算 5->0101 7->0111 9->0010，2 奇数个1变成0，偶数个1，总是让其异或结果变成0 如果是非0的状态，然后继续走到0的状态 对于必胜点，如何判断有几种可行的操作方案？ 假设三堆牌数为{a,b,c}，当前异或值$s=a \oplus \ b \oplus \ c \neq 0$ - 对每一堆 $x \in {a,b,c}$，尝试计算 $x⊕s$。 - 如果 $x⊕sx$，则不可行（因为取牌只能减少，不能增加）。 - 数一数满足$x⊕s|...| B[2.0,0] B --> F[0,0,0] B -->C C[1,0,0] --> F D[0,1,0] -->F E[0,0,1] -->F ``` $g(x)=min \{n \ge 0: n<>g(y) for y \in F(x)\}$ 也就是说，X节点的SG值是去除X后的后继节点的 SG值后的最小非负整数 必败点：节点sg(x) =0 必胜点:节点x的sg(x) >0 终结状态，没有后继sg(x)=0 只要是必胜点，后继一定会指向一个0，即必胜。 而无论哪一步都会走到必胜点，那么都>0,那么=0，即必败点。 SG函数还能解决什么问题呢？ 组合游戏的并 如果一个游戏是几个游戏组合在一起的，就是组合游戏的并 大游戏的SG值由子游戏的SG值异或得来 继续分析SG值，相当于579->131 输入： 2 2 5 表示两种取牌规则，要么2张要么5张 3 有3个案例 2 5 12 两堆牌 3 2 4 7 3堆排 4 2 3 7 12 4堆排 输出先手LWW 0结束 ``` #include using namesapce std; int k,a[100],f[100]; int sg(int p); { int i,t; bool g[101]={0} //g[]数组的用途是记录，代表对应下标的sg值有没有用过 if (f[p]!=-1) return f[p]; // 记忆化，确保sg值算一次就够了 for (int i=0; i