博弈论基础和SG函数
一般的博弈论题目满足如下特点：
- 有两名选手进行回合制游戏
- 两名选手都是极其聪明的，每次都会选择最优的方案
- 两名选手每走一步都是在有限的合法集合中选取一种
- 在任何情况下，合法操作只取决于情况本身，与选手无关
- 游戏结束的条件为当某位选手进行操作时，没有合法的情况。
巴什博弈(Bash Game)
n石子，两个人每次可以取1~m个，问先手必赢还是必输(最后取光者胜)。
同余定理：n=k*(m+1)+r，先手拿走r个，然后后手无论拿多少个，先手只要保证每次拿完之后剩下的石子数量是(m+1)的倍数就必胜。反之，若一开始n就是m+1的倍数，则必输。
if (n%(m+1)) return false;
return true;威佐夫博弈(Wythoff Game)
有两堆物品，两个人轮流任意一堆中至少拿一个或者从两堆拿数量相同的物品，不能不拿。最后取光者胜。
先手的必输局势：(0,0),(1,2),(3,5),(4,7),(6,10),(8,13),(9,15),(11,18),(12,20)。从这些必输局势中可以发现，每组的第一个都是前面没有出现过的，且满足黄金分割比a_k = [k*\frac{\sqrt5+1}{2}], b_k=a_k+k。
即满足这个条件的话先手必输
double r = (sqrt(5.0)+1)/2;
int k = abs(b - a) * r;
if (k != min(a,b)) return true;
return false;斐波那契博弈(Fibonacci Nim Game)
一堆石子有n个，两人轮流取，先取者第一次可以去任意多个，但是不能取完，以后每次取的石子数不能超过上次取子数的2倍。取完者胜。
当n是斐波那契数时先手胜。
f[0] = f[1] = 1;
for (int i = 0; f[i - 1] < n; i++){
f[i] = f[i - 1] + f[i - 2];
if (f[i] == n) return true;
}
return false;尼姆博弈(Nim Game)
有n堆物品，两个人轮流取，在任意一堆中取不少于1个，最后取完者胜。
假设有3堆物品，(0,0,0)是必败态，(0,n,n)也是必败态，因为先手无论取多少，后手只要在另一堆中取同样个数，就仍能保持(0,n,n)状态，最后一定是后手先取完所有物品。然后分析发现(1,2,3)也是必败态，通过二进制分析发现：0001^0010^0011=0000。只要这n个数相异或后值为0就是必败态，其余都是必胜态。
证明：假设n个数的异或和为0，那么先手必败。当异或和为k时，k不为0，则在k的二进制下的最高位上，一定存在奇数个数字在该数位为1，随便拿出一个出来x，从它这堆石子中拿走x-x^k个，容易想到x^k是小于k的，所以这个操作是合法的，这样拿完之后，剩下的数的异或和就变成0了，这样的话后手必败，于是先手必胜。而当异或和为0时，先手不论怎么拿，得到的状态异或和一定不为0，自己就变成了必败态，于是假设成立。
int x = 0;
for (int i:nums) x ^= i;
if (x) return true;
return false;但是，实际问题中不可能给出如此标准的博弈模型，对于更加一般的博弈问题，我们该如何求解呢？通过SG函数转换为尼姆博弈。
有向图游戏和SG函数
有向图游戏是一个经典的博弈游戏，大部分的公平组合游戏都可以转化为有向图游戏。
在一个有向无环图中，只要一个起点，在最上面，然后玩家开始轮流向下沿着边推动棋子，不能走的玩家判负。
可以把博弈游戏的每一个状态都抽象成一个点，而从这个状态可能转化的其它的所有状态，都是这个点的后继状态，就是子结点。
定义mex函数：mex函数的值为不属于集合S中的最小的非负整数值。
mex(S) = min{x}(x \notin S, x \in N)
例如mex(\{0,2,4\})=1, mex(\{1,2\})=0
对于状态x和它的所有k个后继状态y_1, y_2, y_3···y_k，定义SG函数：SG(x) = mex( \{ SG(y_1), SG(y_2), SG(y_3)···SG(y_k) \} )
SG函数的值也是一个整数。
对于由n个有向无环图组合成的组合游戏，对于它们的n个起点s_1,s_2,s_3···s_n，有定理：当且仅当SG(s_1) \bigoplus SG(s_2) \bigoplus SG(s_3)···SG(s_n) \neq 0时，这个游戏先手必胜。这个定理叫做SG定理。
对于没有后继状态的终结点，它们是游戏的结束状态，应根据游戏的规则来定义SG函数的值。必败态值为0，否则为1。
将Nim游戏转化为有向图游戏
仍然是在n堆石子中取石子，每次在任意一堆中取正整数个。可以将有x个石子的堆视为结点x，那么对于那些小于等于x的y，都是x的后继结点。SG(0)=0，一堆数量为0的石子为必败态。然后可以轻易推出SG(x)=x，就可以得到Nim游戏的结论了。
S-Nim
此题不同于一般的Nim游戏，先给出一个集合S，S包含一些整数，n堆石子，每次从任意一堆中拿走的石子数量必须是S中的数字，求问先手输赢状态。
利用SG函数，SG(0)=0，然后逐个求SG(i)，有点类似背包dp的样子，，把集合S中的数一个一个拿出来，相当于是枚举i的子集，然后求mex，最后求n堆石子的SG异或和即可。异或和为0必败，为1必胜。
#include <bits/stdc++.h>
using namespace std;
int k, m, l;
int S[105], h[105], SG[10005];
bool vis[100005];
void init() {
SG[0] = 0;
for (int i=1; i<=10000; i++) {
int tmp = -1, t;
for (int j=1; j<=k && i>=S[j]; j++) {
t = SG[i-S[j]];
tmp = max(tmp, t);
vis[t] = 1;
}
SG[i] = -1;
for (int j=0; j<=tmp; j++) {
if (vis[j]) {
vis[j] = 0;
continue;
}
if (SG[i]==-1) SG[i] = j;
}
if (SG[i]==-1) SG[i] = tmp+1;
}
return;
}
int main(){
while (~scanf ("%d", &k) && k) {
for (int i=1; i<=k; i++) scanf ("%d", S+i);
sort (S+1, S+k+1);
init();
scanf ("%d", &m);
for (int i=1; i<=m; i++) {
int ans = 0, tmp;
scanf ("%d", &l);
while (l--) {
scanf ("%d", &tmp);
ans ^= SG[tmp];
}
if (ans==0) putchar('L');
else putchar('W');
}
putchar('\n');
}
return 0;
}进阶 状态的合并
我们之前分析过，有向无环图上的一个结点就相当于是一个状态，也就是说这个状态的SG函数值，就是从这个状态开始博弈的胜负状态，SG函数为0时，先手必败，否则先手胜。而有的状态是其它状态的合并，比如a和b是两个状态，而由c可以得到一个a和b共存的一个状态，ab不是相互独立的，那么他俩共存的SG函数值为SG(a) \bigoplus SG(b)，其实就相当于是一开始就有ab这两个起点，那么结果就是它们的异或和。而这个异或和其实也就是c的SG函数值。
HDU3980 Paint Chain
题意：一串珠子，N个，俩人给珠子涂色，每次必须涂连续的M个，问谁必胜。
分析：此题有特殊情况，一开始若N<M，那么先手就输了。讨论其它情况，先手一开始涂完M个珠子之后，珠子变成了一串，长度为N-M，我们可以转化一下先手，并且把N初始化为N-M，然后开始博弈。
求SG(i)，首先i减去M，然后i-M需要分成两部分a，b，a+b=i-M，此时ab是一个整体，而不是相互独立的，所以这个整体状态的SG函数值就是SG(a) \bigoplus SG(b)，然后计算出SG(N)即可判断出答案。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
int N, M, k;
bool vis[maxn];
int SG[maxn];
void solve() {
for (int i=0; i<=N; i++) SG[i] = -1;
for (int i=0; i<M; i++) SG[i] = 0;
//SG[M] = 1;
for (int i=M; i<=N; i++) {
int tmp = -1, t;
for (int j=0; j<=i-M; j++) {
t = SG[j] ^ SG[i-M-j];
vis[t] = 1;
tmp = max(tmp, t);
}
for (int j=0; j<=tmp; j++) {
if (vis[j]) {
vis[j] = 0;
continue;
}
if (SG[i]==-1) SG[i] = j;
}
if (SG[i]==-1) SG[i] = tmp+1;
}
return;
}
int main(){
scanf ("%d", &k);
for (int c=1; c<=k; c++) {
scanf ("%d %d", &N, &M);
if (N < M) {
printf ("Case #%d: abcdxyzk\n", c);
continue;
}
N -= M;
solve();
if (SG[N]) printf ("Case #%d: abcdxyzk\n", c);
else printf ("Case #%d: aekdycoin\n", c);
}
return 0;
}
0 条评论