组合游戏"/>
简单博弈论:公平组合游戏
若一个游戏满足:
- 由两名玩家交替行动
- 在游戏进行的任意时刻,可以执行的合法行动与轮到哪位玩家无关
- 不能行动的玩家判负
则称该游戏为一个公平组合游戏。
尼姆游戏(NIM)属于公平组合游戏,但常见的棋类游戏,比如围棋就不是公平组合游戏,因为围棋交战双方分别只能落黑子和白子,胜负判定也比较复杂,不满足条件2和3。
有向图游戏
将公平组合游戏看作一个有向无环图,图中有一个唯一的起点,在起点放有一枚棋子。两名玩家交替把这枚棋子沿着有向边进行移动,每次可以移动一步,无法移动判负。任何一个公平组合游戏都可以转化为有向图游戏。具体方法是,把每个局面看成图中的一个节点,并且从每个局面向沿着合法行动能够到达的下一个局面连接有向边。
Mex运算
设 S S S表示一个非负整数集合,定义 m e x ( S ) mex(S) mex(S)为求出不属于集合 S S S的最小非负整数的运算即: m e x ( S ) = m i n ( x ) mex(S) = min(x) mex(S)=min(x), x x x属于自然数,且 x x x不属于集合 S S S。
例如:集合$S = {1, 2, 3} $,那么 m e x ( S ) = 0 mex(S) = 0 mex(S)=0, 0 0 0为不在集合 S S S中的最小自然数。
SG函数
在有向图游戏中,对于每个结点 x x x,设从 x x x出发共有 k k k条边,分别到达节点 y 1 , y 2 , . . . , y k y_1, y_2, ..., y_k y1,y2,...,yk,定义 S G ( x ) SG(x) SG(x)为 x x x的后继节点 y 1 , y 2 , . . . , y k y_1, y_2, ..., y_k y1,y2,...,yk的 S G SG SG函数值构成的集合S、再执行 m e s ( S ) mes(S) mes(S)运算的结果,即: S G ( x ) = m e x ( S G ( y 1 ) , S G ( y 2 ) , . . . , S G ( y k ) ) SG(x) = mex(SG(y_1), SG(y_2), ..., SG(y_k)) SG(x)=mex(SG(y1),SG(y2),...,SG(yk))
特别地,整个有向图游戏 G G G的 S G SG SG函数值被定义为有向图游戏起点 S S S的 S G SG SG函数值, S G ( G ) = S G ( S ) SG(G) = SG(S) SG(G)=SG(S)
例如,有如下有向图游戏,黄色为起点,绿色为终点,首先定义 S G ( 终 点 ) = 0 SG(终点) = 0 SG(终点)=0,那么可以推导出其它各点的 S G ( ) SG() SG()函数值:
在有向图游戏中判断某个状态 x x x(图中一点),如果:
- S G ( x ) = 0 SG(x) = 0 SG(x)=0,为必败态。首先终点状态是 0 0 0,任何一个 0 0 0状态,在有向图中都无法直接到达一个 0 0 0状态。先手如果为0,无法通过操作将状态变为0,即留给后手一个必胜态。
- S G ( x ) ≠ 0 SG(x) ≠ 0 SG(x)=0,为必胜态。任何一个非 0 0 0状态,在有向图中必然可以直接到达一个 0 0 0状态。先手如果非 0 0 0,可以通过操作将状态变为 0 0 0,即留给后手一个必败态。
有向图游戏的和
设 G 1 , G 2 , . . . , G m G_1, G_2, ... , G_m G1,G2,...,Gm是 m m m个有向图游戏。定义有向图游戏 G G G,它的行动规则是任选某个有向图游戏 G i G_i Gi,并在 G i G_i Gi上行动一步。 G G G被称为有向图游戏 G 1 , G 2 , . . . , G m G_1, G_2, ... , G_m G1,G2,...,Gm的和。
有向图游戏的和的 S G SG SG函数值等于它包含的各个字游戏 S G SG SG函数值的异或和,即:
S G ( G ) = S G ( G 1 ) ⊕ S G ( G 2 ) ⊕ . . . ⊕ S G ( G m ) SG(G) = SG(G1) \oplus SG(G2) \oplus ... \oplus SG(G_m) SG(G)=SG(G1)⊕SG(G2)⊕...⊕SG(Gm)
证明:参考尼姆游戏的证明。
#include <bits/stdc++.h>using namespace std;const int N = 110, M = 10010;
int k, n;
//s[]表示每次拿取的石子数量的集合
//dp[]记忆化搜索,dp[i]记录sg[i]
int s[N], dp[M];int sg(int x){//记忆化搜索,如果已经计算过,直接返回if(dp[x] != -1) return dp[x];//S存放从x出发、所有能到的局面的sg函数值set<int> S; for(int i = 0; i < k; i++){int sum = s[i]; //取走个数if(x >= sum){ //能从x中能取走sumS.insert(sg(x - sum)); //将取走后的局面加入到集合S中}}//mex(S),求集合S中不存在的最小的自然数for(int i = 0; ; i++){if(S.count(i) == 0) return dp[x] = i;}}int main(){memset(dp, -1, sizeof dp);cin>>k;for(int i = 0; i < k; i++) cin>>s[i];cin>>n;int res = 0;for(int i = 0; i < n; i++){int x;cin>>x;res ^= sg(x);}if(res) puts("Yes");else puts("No");return 0;
}
更多推荐
简单博弈论:公平组合游戏
发布评论