精华内容
下载资源
问答
  • 组合游戏

    千次阅读 2014-02-09 11:56:57
    组合游戏的特点  (1)两个玩家  (2)游戏的操作状态是一个有限的集合  (3)游戏的双方轮流操作  (4)双方每次操作必须符合游戏规定  (5)当一方不能将游戏继续进行的时候,游戏结束,同时对方获胜  (6)无论...

    组合游戏的特点

       (1)两个玩家

       (2)游戏的操作状态是一个有限的集合

       (3)游戏的双方轮流操作

       (4)双方每次操作必须符合游戏规定

       (5)当一方不能将游戏继续进行的时候,游戏结束,同时对方获胜

       (6)无论如何操作,游戏总能在有限次操作后结束

     


    必败点(P点)与必胜点(N点)

       必败点:前一个选手将取胜的位置称为必败点。

       必胜点:下一个选手将取胜的位置称为必胜点。

     

    必败点与必胜点的性质

      (1)所有终结点是必败点

      (2)从任何必胜点操作,至少有一种方法可以进入必败点

      (3)无论如何操作,从必败点都只能进入必胜点

     

     

    博弈典例


       1.Regional  2006 BeiJing

     

       问题描述:David玩一个石子游戏,游戏中,有n堆石子,编号为0,1,2,...,n-1。两名玩家轮流取石子,每一轮游戏,每名玩家取3堆石子i,j,k,i<j<k,且至少有一枚石子在第i堆中,从i中取出一枚石子,并向j,k中各放一枚石子,如果j=k,则向k中放2颗石子,最先不能取石子的人输。

     

      此游戏中的新操作:拿走一个非0的石堆,并放入2个规模小于它的石堆(可以为0)

     

     

    2.IPSC  2003  Got Root?

       Alice和Bob在一个无向图上玩伐木游戏,无向图有唯一的根,两人轮流从中截取一条边,将与根不相连的部分抛弃,这样,最先不能操作的人输。对于给定的无向图,Alice先行,两个人都按照最优策略操作,输出胜者的名字。

     

    思路:图转化为树-----树转化为链-----分别求出SG值,就是Nim博弈了,最后异或一下即可。



    展开全文
  • 公平组合游戏-巴什游戏、尼姆游戏和SG函数

    千次阅读 多人点赞 2020-10-08 16:03:49
    HDU-1846 HDU-1850 HDU-1907 HDU-1848 HDU-2999 HDU-1524 公平组合游戏:巴什游戏、尼姆游戏和SG函数,来玩游戏啊~~

    公平组合游戏


    公平组合游戏(Impartral Combinatorial Game)是满足以下特征的一类问题:

    1. 有两个玩家,游戏规则对两人是公平的
    2. 两人轮流交替回合,当一个玩家不能走时游戏结束
    3. 游戏状态和能走的步数都是有限的
    4. 游戏局势不能用来区分玩家身份(比如围棋有黑白方就不属于)
    • P点(P-position)是指前一个玩家(即刚走过一步的玩家)的必胜位置,表示先手必败
    • N点(N-position)是指下一个玩家的必胜位置,表示先手必胜

    巴什游戏


    巴什游戏(Bash Game)是 n n n颗石子,每次可以拿1~ m m m颗,两人轮流。
    结论是若 n n n% ( m + 1 ) = = 0 (m+1)==0 (m+1)==0则先手败,否则先手胜。

    HDU-1846

    HDU-1846 Brave Game

    Problem Description
    不重要的背景。。。
    各位勇敢者要玩的第一个游戏是什么呢?很简单,它是这样定义的:
    1、 本游戏是一个二人游戏;
    2、 有一堆石子一共有n个;
    3、 两人轮流进行;
    4、 每走一步可以取走1…m个石子;
    5、 最先取光石子的一方为胜;
    如果游戏的双方使用的都是最优策略,请输出哪个人能赢。
    Input
    输入数据首先包含一个正整数C(C<=100),表示有C组测试数据。
    每组测试数据占一行,包含两个整数n和m(1<=n,m<=1000),n和m的含义见题目描述。
    Output
    如果先走的人能赢,请输出“first”,否则请输出“second”,每个实例的输出占一行。
    Sample Input
    2
    23 2
    4 3
    Sample Output
    first
    second

    #include<bits/stdc++.h>
    using namespace std;
    int t, n, m;
    int main() {
    	scanf("%d", &t);
    	while(t--) {
    		scanf("%d%d", &n, &m);
    		if (n % (m + 1) == 0)
    			puts("second");
    		else puts("first");
    	}
    	return 0;
    }
    

    尼姆游戏


    尼姆游戏(Nim Game)是由 n n n对石子,数量分别是{a1,a2,…,an},两个玩家轮流拿石子,每次可以从任意一堆拿走任意数量的石子,拿到最后一个石子的玩家获胜。
    结论是若a1⊕a2⊕…an≠0,则先手必胜(N),否则先手必败(P)

    HDU-1850

    HDU-1850 Being a Good Boy in Spring Festival

    Problem Description
    不重要的背景。。。
    咱们玩个小游戏吧 ACM课上学的呢~
    下面是一个二人小游戏:桌子上有M堆扑克牌;每堆牌的数量分别为Ni(i=1…M);两人轮流进行;每走一步可以任意选择一堆并取走其中的任意张牌;桌子上的扑克全部取光,则游戏结束;最后一次取牌的人为胜者。
    现在我们不想研究到底先手为胜还是为负,我只想问大家:
    ——“先手的人如果想赢,第一步有几种选择呢?”
    Input
    输入数据包含多个测试用例,每个测试用例占2行,首先一行包含一个整数M(1<M<=100),表示扑克牌的堆数,紧接着一行包含M个整数Ni(1<=Ni<=1000000,i=1…M),分别表示M堆扑克的数量。M为0则表示输入数据的结束。
    Output
    如果先手的人能赢,请输出他第一步可行的方案数,否则请输出0,每个实例的输出占一行。
    Sample Input
    3
    5 7 9
    0
    Sample Output
    1

    分析
    H H H是出来 a [ i ] a[i] a[i]外的其他所有数的异或,则 a n s = H ans=H ans=H^ a [ i ] a[i] a[i]
    a n s ans ans^ a [ i ] = H a[i]=H a[i]=H ^ a [ i ] a[i] a[i] ^ a [ i ] = H a[i]=H a[i]=H
    所以 ( a n s (ans (ans^ a [ i ] ) < = a [ i ] a[i])<=a[i] a[i])<=a[i],即 H < = a [ i ] H<=a[i] H<=a[i],可以把 a [ i ] a[i] a[i]减少到 H H H,就是一种可行方案。
    实在不行这边建议打表

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn = 102;
    int m, ans, sum, a[maxn];
    int main() {
    	while (~scanf("%d", &m) && m) {
    		ans = sum = 0;
    		for (int i = 0; i < m; i++) {
    			scanf("%d", &a[i]);
    			ans ^= a[i];
    		}
    		if (ans == 0)puts("0");
    		else {
    			for (int i = 0; i < m; i++) {
    				if ((ans ^ a[i]) <= a[i])
    					sum++;
    			}
    			printf("%d\n", sum);
    		}
    	}
    	return 0;
    }
    

    HDU-1907

    HDU-1907 John

    Problem Description
    Little John is playing very funny game with his younger brother. There is one big box filled with M&Ms of different colors. At first John has to eat several M&Ms of the same color. Then his opponent has to make a turn. And so on. Please note that each player has to eat at least one M&M during his turn. If John (or his brother) will eat the last M&M from the box he will be considered as a looser and he will have to buy a new candy box.
    Both of players are using optimal game strategy. John starts first always. You will be given information about M&Ms and your task is to determine a winner of such a beautiful game.
    Input
    The first line of input will contain a single integer T – the number of test cases. Next T pairs of lines will describe tests in a following format. The first line of each test will contain an integer N – the amount of different M&M colors in a box. Next line will contain N integers Ai, separated by spaces – amount of M&Ms of i-th color.
    Constraints:
    1 <= T <= 474,
    1 <= N <= 47,
    1 <= Ai <= 4747
    Output
    Output T lines each of them containing information about game winner. Print “John” if John will win the game or “Brother” in other case.
    Sample Input
    2
    3
    3 5 1
    1
    1
    Sample Output
    John
    Brother

    分析
    这道题反过来了,拿最后一颗石子则输,反尼姆博弈,注意特殊情况处理下即可。
    特殊情况: 若所有石堆的数量都是1,那么判断奇偶即可(即异或结果等于0先手必胜)。
    否则异或结果不等于0则先手必胜。

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn = 102;
    int t, n, ans, a;
    int main() {
    	scanf("%d", &t);
    	while (t--) {
    		bool tag = false;
    		ans = 0;
    		scanf("%d", &n);
    		for (int i = 0; i < n; i++) {
    			scanf("%d", &a);
    			ans ^= a;
    			if (a > 1)tag = true;
    		}
    		if (tag && ans != 0) //全1且异或非0
    			puts("John");
    		else if (!tag && ans == 0) //否则异或为0也是先手必胜
    			puts("John");
    		else puts("Brother");
    	}
    	return 0;
    }
    

    SG函数


    SG函数(Sprague-Grundy)函数是在一个图 G ( X , F ) G(X,F) G(X,F)中,定义结点 x x x的sg函数为 s g ( x ) sg(x) sg(x),它等于没有指定给它的任意后继结点的 s g sg sg值的最小非负整数。
    有点拗口,不急,他就是找一个不属于集合里的最小非负整数,这个集合就是图的后记结点。
    在这里插入图片描述

    • sg(0)=0,因为结点0没有后继结点,0是最小非负整数
    • sg(1)=1,结点1后继结点是0,不等于sg(0)的最小非负整数是1
    • sg(2)=2,其后继节点是0和1,不等于sg(0)、sg(1)的最小非负整数是2
    • sg(3)=0,其后继节点是1和2,不等于sg(1)、sg(2)的最小非负整数是0
    • sg(4)=1,其后继节点是2和3,不等于sg(2)、sg(3)的最小非负整数是1

    SG函数求解巴什游戏

    结论
    s g ( x ) = 0 sg(x)=0 sg(x)=0的结点 x x x是先手必败点,也就是P点。
    证明

    1. 根据sg函数性质,sg(x)=0的结点,没有sg值等于0的后继节点;sg(y)>0的任意结点,必有一条边通向sg值为0的某个后记结点;
    2. 若sg(x)=0的结点时图上的终点(没有后继节点,出度为0),显示x=0,它是一个P点;若x有后继节点,那么这些后继结点都能通向某个sg值为0的结点。当玩家甲处于sg(x)=0的结点时,只能转移到sg(x)≠0的结点,下一个玩家乙必然转移到sg(x)=0的点,从而让甲不利,所以sg(x)=0的点是先手必败点。

    HDU-1846

    HDU-1846 Brave Game
    题目详情同上文

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1003;
    int t, n, m, sg[maxn], s[maxn];
    void getsg() {
    	for (int i = 1; i <= n; i++) {
    		memset(s, 0, sizeof(s));
    		for (int j = 1; j <= m && j <= i; j++)
    			s[sg[i - j]] = 1; //更新后继结点
    		for (int j = 0; j <= n; j++) //找最小非负整数
    			if (!s[j]) {
    				sg[i] = j;
    				break;
    			}
    	}
    }
    int main() {
    	scanf("%d", &t);
    	while (t--) {
    		scanf("%d%d", &n, &m);
    		getsg();
    		if (sg[n])puts("first");
    		else puts("second");
    	}
    	return 0;
    }
    

    插播反爬信息 )博主CSDN地址:https://blog.csdn.net/qq_45034708

    SG函数求解尼姆游戏

    结论
    计算每堆石子的sg值,把所有sg值异或,若结果=0则先手必败。

    HDU-1848

    HDU-1846 Fibonacci again and again

    Problem Description
    不重要的背景。。。
    今天,又一个关于Fibonacci的题目出现了,它是一个小游戏,定义如下:
    1、 这是一个二人游戏;
    2、 一共有3堆石子,数量分别是m, n, p个;
    3、 两人轮流走;
    4、 每走一步可以选择任意一堆石子,然后取走f个;
    5、 f只能是菲波那契数列中的元素(即每次只能取1,2,3,5,8…等数量);
    6、 最先取光所有石子的人为胜者;
    假设双方都使用最优策略,请判断先手的人会赢还是后手的人会赢。
    Input
    输入数据包含多个测试用例,每个测试用例占一行,包含3个整数m,n,p(1<=m,n,p<=1000)。
    m=n=p=0则表示输入结束。
    Output
    如果先手的人能赢,请输出“Fibo”,否则请输出“Nacci”,每个实例的输出占一行。
    Sample Input
    1 1 1
    1 4 1
    0 0 0
    Sample Output
    Fibo
    Nacci

    分析
    注意处理下后继节点即可,值只能取斐波那契数列,然后套结论。(该题三堆石子,多堆也一样)

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1003;
    int sg[maxn], s[maxn];
    int n, m, p;
    int fibo[15] = { 1,2,3 };
    void getsg() {
    	for (int i = 0; i <= maxn; i++) {
    		memset(s, 0, sizeof(s));
    		for (int j = 0; j < 15 && fibo[j] <= i; j++) 
    			s[sg[i - fibo[j]]] = 1;  //更新后继节点
    		for (int j = 0; j <= maxn; j++)  //找最小非负整数
    			if (!s[j]) {
    				sg[i] = j;
    				break;
    			}
    	}
    }
    int main() {
    	for (int i = 3; i < 15; i++)
    		fibo[i] = fibo[i - 1] + fibo[i - 2];
    	getsg();
    	while (~scanf("%d%d%d", &n, &m, &p) && (n + m + p)) {
    		if (sg[n] ^ sg[m] ^ sg[p])
    			puts("Fibo");
    		else puts("Nacci");
    	}
    	return 0;
    }
    

    HDU-2999

    HDU-2999 Stone Game, Why are you always there?

    Problem Description
    “Alice and Bob are playing stone game…”
    “Err… Feel bored about the stone game? Don’t be so, because stone game changes all the time!”
    “What the hell are they thinking for?”
    “You know, whenever Alice is trying to make fun of Bob, she asked him to play stone game with him.”
    “Poor Bob… What’s the rule today?”
    “It seems Alice only allows some fixed numbers of continuous stones can be taken each time. And they begin with one string of stones.”
    “A string? Formed as a circle or a line?”
    “A line.”
    “Well, I think I may help Bob with that.”
    “How?”
    “I may tell him to skip this round if he has no chance to win.”
    “Good idea maybe, I mean, Alice always let Bob play first, because she think herself is smart enough to beat Bob no matter how.”
    “Yes, she’s actually right about herself. Let me see if Bob has a chance to win…”

    Input
    There are multiple test cases, for each test case:
    The first line has a positive integer N (1<=N<=100).
    The second line contains N positive integers, a1, a2 … an, separated by spaces, which indicate the fixed numbers Alice gives.
    The third line, a positive integer M. (M<=1000)
    Following M lines, one positive integer K (K<=1000) each line. K means in this round, the length of the stone string.
    Output
    For each K, output “1” if Bob has a chance to win, output “2” if Bob has no chance, or “0” if it’s undeterminable.
    Sample Input
    3
    1 5 1
    1
    1
    Sample Output
    1

    分析
    取出连续的石子,注意位置不能合并(2拿完后,1和3认为是不相邻的),比如5个石子,S={2},拿完后剩(3,4,5)、{(1),(4,5)}、{(1,2),(5)}和(1,2,3)四种情况,只关心剩余区间的长度即{0,3}、{1,2},后继状态变成了两个子区间长度的SG函数的异或和。

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1003;
    int sg[maxn], s[maxn];
    int n, m, k, a[102];
    void getsg() {
    	for (int i = 0; i <= maxn; i++) {
    		memset(s, 0, sizeof(s));
    		for (int j = 0; j < n && a[j] <= i; j++)
    			for (int k = i - a[j]; k >= 0; k--)//两个状态异或
    				s[sg[k] ^ sg[i - a[j] - k]] = 1;
    		for (int j = 0; j <= maxn; j++)
    			if (!s[j]) {
    				sg[i] = j;
    				break;
    			}
    	}
    }
    int main() {
    	while (~scanf("%d", &n)) {
    		for (int i = 0; i < n; i++)
    			scanf("%d", &a[i]);
    		sort(a, a + n);
    		getsg();
    		scanf("%d", &m);
    		while (m--) {
    			scanf("%d", &k);
    			if (sg[k])puts("1");
    			else puts("2");
    		}
    	}
    	return 0;
    }
    

    HDU-1524

    HDU-1524 A Chess Game

    Problem Description
    Let’s design a new chess game. There are N positions to hold M chesses in this game. Multiple chesses can be located in the same position. The positions are constituted as a topological graph, i.e. there are directed edges connecting some positions, and no cycle exists. Two players you and I move chesses alternately. In each turn the player should move only one chess from the current position to one of its out-positions along an edge. The game does not end, until one of the players cannot move chess any more. If you cannot move any chess in your turn, you lose. Otherwise, if the misfortune falls on me… I will disturb the chesses and play it again.
    Do you want to challenge me? Just write your program to show your qualification!
    Input
    Input contains multiple test cases. Each test case starts with a number N (1 <= N <= 1000) in one line. Then the following N lines describe the out-positions of each position. Each line starts with an integer Xi that is the number of out-positions for the position i. Then Xi integers following specify the out-positions. Positions are indexed from 0 to N-1. Then multiple queries follow. Each query occupies only one line. The line starts with a number M (1 <= M <= 10), and then come M integers, which are the initial positions of chesses. A line with number 0 ends the test case.
    Output
    There is one line for each query, which contains a string “WIN” or “LOSE”. “WIN” means that the player taking the first turn can win the game according to a clever strategy; otherwise “LOSE” should be printed.
    Sample Input
    4
    2 1 2
    0
    1 3
    0
    1 0
    2 0 2
    0
    4
    1 1
    1 2
    0
    0
    2 0 1
    2 1 1
    3 0 1 3
    0
    Sample Output
    WIN
    WIN
    WIN
    LOSE
    WIN

    分析
    有向无环图,最后不能移动就输了,就是sg函数的定义,用dfs异或路径即可。

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1003;
    int sg[maxn], s[maxn];
    int n, m, k, mp[maxn][maxn];
    int dfs(int x) {
    	if (sg[x] != -1)return sg[x];
    	int vis[maxn] = { 0 };
    	for (int i = 0; i < n; i++)
    		if (mp[x][i])
    			vis[dfs(i)] = 1;
    	for (int i = 0; i < maxn; i++) {
    		if (!vis[i]) {
    			sg[x] = i;
    			break;
    		}
    	}
    	return sg[x];
    }
    int main() {
    	while (~scanf("%d", &n)) {
    		memset(sg, -1, sizeof(sg));
    		memset(mp, 0, sizeof(mp));
    		for (int i = 0; i < n; i++) {
    			scanf("%d", &m);
    			for (int j = 0; j < m; j++) {
    				scanf("%d", &k);
    				mp[i][k] = 1;
    			}
    			if (m == 0)sg[i] = 0;
    		}
    		while (~scanf("%d", &m) && m) {
    			int ans = 0;
    			for (int i = 0; i < m; i++) {
    				scanf("%d", &k);
    				if (sg[k] != -1)ans ^= sg[k];
    				else ans ^= dfs(k);
    			}
    			if (ans)puts("WIN");
    			else puts("LOSE");
    		}
    	}
    	return 0;
    }
    

    原创不易,请勿转载本不富裕的访问量雪上加霜
    博主首页:https://blog.csdn.net/qq_45034708
    如果文章对你有帮助,记得一键三连❤

    展开全文
  • 网络游戏-多变化组合游戏器具.zip
  • 中班游戏教案:快乐的组合游戏.doc
  • 幼儿园教案2021-中班游戏教案:快乐的组合游戏.doc
  • 可用js在网页中实现的,2048数字组合游戏flash特效,超好玩的小游戏
  • 万德·瓦尔登 组合游戏和单词组合学的斜对角数项目
  • 组合游戏.rar

    2012-08-10 13:50:37
    组合游戏 sg函数 博弈论 acm竞赛 取石子游戏
  • 从“k倍动态减法游戏”出发探究一类组合游戏问题.ppt
  • 从“k倍动态减法游戏”出发探究一类组合游戏问题.pdf
  • 组合游戏略述——浅谈SG游戏的若干拓展及变形_贾志豪.ppt
  • 组合游戏略述 浅谈组合游戏的若干拓展及变形 石家庄二中北校区 高三18班贾志豪 Evaluadon only. ch Asposeslides for ...
  • 算法合集之《从“k倍动态减法游戏”出发探究一类组合游戏问题》.
  • 2.王晓珂《解析一类组合游戏》.ppt
  • 2.王晓珂《解析一类组合游戏》.doc
  • 珠光宝气 试图重新创建组合游戏“宝石迷阵”。
  • 组合游戏 - SG函数和SG定理

    万次阅读 多人点赞 2015-05-07 08:09:04
    组合游戏的和通常是很复杂的,所以我们介绍一种新工具,可以使组合问题变得简单————SG函数和SG定理。 Sprague-Grundy定理(SG定理):  游戏和的SG函数等于各个游戏SG函数的Nim和。这样就可以将每一个子游戏...

            在介绍SG函数和SG定理之前我们先介绍介绍必胜点与必败点吧.

    必胜点和必败点的概念
           P点:必败点,换而言之,就是谁处于此位置,则在双方操作正确的情况下必败。
           N点:必胜点,处于此情况下,双方操作均正确的情况下必胜。
    必胜点和必败点的性质
            1、所有终结点是 必败点 P 。(我们以此为基本前提进行推理,换句话说,我们以此为假设)
            2、从任何必胜点N 操作,至少有一种方式可以进入必败点 P。
            3、无论如何操作,必败点P 都只能进入 必胜点 N。
    我们研究必胜点和必败点的目的时间为题进行简化,有助于我们的分析。通常我们分析必胜点和必败点都是以终结点进行逆序分析。我们以 hdu 1847 Good Luck in CET-4 Everybody!为例:
    当 n = 0 时,显然为必败点,因为此时你已经无法进行操作了
    当 n = 1 时,因为你一次就可以拿完所有牌,故此时为必胜点
    当 n = 2 时,也是一次就可以拿完,故此时为必胜点
    当 n = 3 时,要么就是剩一张要么剩两张,无论怎么取对方都将面对必胜点,故这一点为必败点。
    以此类推,最后你就可以得到;
          n    :   0    1    2    3    4   5    6 ...
    position:  P    N   N    P   N   N   P ...
    你发现了什么没有,对,他们就是成有规律,使用了 P/N来分析,有没有觉得问题变简单了。
    现在给你一个稍微复杂一点点的: hdu 2147 kiki's game

            现在我们就来介绍今天的主角吧。组合游戏的和通常是很复杂的,但是有一种新工具,可以使组合问题变得简单————SG函数和SG定理。

    Sprague-Grundy定理(SG定理):

            游戏和的SG函数等于各个游戏SG函数的Nim和。这样就可以将每一个子游戏分而治之,从而简化了问题。而Bouton定理就是Sprague-Grundy定理在Nim游戏中的直接应用,因为单堆的Nim游戏 SG函数满足 SG(x) = x。不知道Nim游戏的请移步:这里

    SG函数:

            首先定义mex(minimal excludant)运算,这是施加于一个集合的运算,表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。

            对于任意状态 x , 定义 SG(x) = mex(S),其中 S 是 x 后继状态的SG函数值的集合。如 x 有三个后继状态分别为 SG(a),SG(b),SG(c),那么SG(x) = mex{SG(a),SG(b),SG(c)}。 这样 集合S 的终态必然是空集,所以SG函数的终态为 SG(x) = 0,当且仅当 x 为必败点P时。

    【实例】取石子问题

    有1堆n个的石子,每次只能取{ 1, 3, 4 }个石子,先取完石子者胜利,那么各个数的SG值为多少?

    SG[0]=0,f[]={1,3,4},

    x=1 时,可以取走1 - f{1}个石子,剩余{0}个,所以 SG[1] = mex{ SG[0] }= mex{0} = 1;

    x=2 时,可以取走2 - f{1}个石子,剩余{1}个,所以 SG[2] = mex{ SG[1] }= mex{1} = 0;

    x=3 时,可以取走3 - f{1,3}个石子,剩余{2,0}个,所以 SG[3] = mex{SG[2],SG[0]} = mex{0,0} =1;

    x=4 时,可以取走4-  f{1,3,4}个石子,剩余{3,1,0}个,所以 SG[4] = mex{SG[3],SG[1],SG[0]} = mex{1,1,0} = 2;

    x=5 时,可以取走5 - f{1,3,4}个石子,剩余{4,2,1}个,所以SG[5] = mex{SG[4],SG[2],SG[1]} =mex{2,0,1} = 3;

    以此类推.....

       x        0  1  2  3  4  5  6  7  8....

    SG[x]    0  1  0  1  2  3  2  0  1....

    由上述实例我们就可以得到SG函数值求解步骤,那么计算1~n的SG函数值步骤如下:

    1、使用 数组f 将 可改变当前状态 的方式记录下来。

    2、然后我们使用 另一个数组 将当前状态x 的后继状态标记。

    3、最后模拟mex运算,也就是我们在标记值中 搜索 未被标记值 的最小值,将其赋值给SG(x)。

    4、我们不断的重复 2 - 3 的步骤,就完成了 计算1~n 的函数值。

    代码实现如下:

    //f[N]:可改变当前状态的方式,N为方式的种类,f[N]要在getSG之前先预处理
    //SG[]:0~n的SG函数值
    //S[]:为x后继状态的集合
    int f[N],SG[MAXN],S[MAXN];
    void  getSG(int n){
        int i,j;
        memset(SG,0,sizeof(SG));
        //因为SG[0]始终等于0,所以i从1开始
        for(i = 1; i <= n; i++){
            //每一次都要将上一状态 的 后继集合 重置
            memset(S,0,sizeof(S));
            for(j = 0; f[j] <= i && j <= N; j++)
                S[SG[i-f[j]]] = 1;  //将后继状态的SG函数值进行标记
            for(j = 0;; j++) if(!S[j]){   //查询当前后继状态SG值中最小的非零值
                SG[i] = j;
                break;
            }
        }
    }


    现在我们来一个实战演练(题目链接):

           只要按照上面的思路,解决这个就是分分钟的问题。

    代码如下:

    #include <stdio.h>
    #include <string.h>
    #define MAXN 1000 + 10
    #define N 20
    int f[N],SG[MAXN],S[MAXN];
    void getSG(int n){
        int i,j;
        memset(SG,0,sizeof(SG));
        for(i = 1; i <= n; i++){
            memset(S,0,sizeof(S));
            for(j = 0; f[j] <= i && j < N; j++)
                S[SG[i-f[j]]] = 1;
            for(j = 0;;j++) if(!S[j]){
                SG[i] = j;
                break;
            }
        }
    }
    int main(){
        int n,m,k;
        f[0] = f[1] = 1;
        for(int i = 2; i <= 16; i++)
            f[i] = f[i-1] + f[i-2];
        getSG(1000);
        while(scanf("%d%d%d",&m,&n,&k),m||n||k){
            if(SG[n]^SG[m]^SG[k]) printf("Fibo\n");
            else printf("Nacci\n");
        }
        return 0;
    }
    

    大家是不是还没有过瘾,那我就在给大家附上一些组合博弈的题目:

    POJ 2234 Matches Game
    HOJ 4388 Stone Game II

    POJ 2975 Nim
    HOJ 1367 A Stone Game
    POJ 2505 A multiplication game
    ZJU 3057 beans game
    POJ 1067 取石子游戏
    POJ 2484 A Funny Game
    POJ 2425 A Chess Game
    POJ 2960 S-Nim
    POJ 1704 Georgia and Bob
    POJ 1740 A New Stone Game
    POJ 2068 Nim
    POJ 3480 John
    POJ 2348 Euclid's Game
    HOJ 2645 WNim
    POJ 3710 Christmas Game
    POJ 3533 Light Switching Game

    (如有错误,欢迎指正,转载注明出处)


    
    
    展开全文
  • 行业分类-设备装置-蜂窝式早教组合游戏桌.zip
  • Silverlight多面体组合游戏源码 基本方式多面体的动画作品是这个应用程序如下: (1)图描述如何面临的连接是从资源加载 (2)此图是用来生成二维网 - 基本上是等价 一个纸板断路器。 (3)本净,然后用于生成3...
  • 主要从欣赏的角度引入了SG函数、游戏图、NIM游戏等概念,重点谈我对组合游戏尤其是SG函数的体会、理解;第二章主要介绍了几种不同规则的组合游戏以及相应的应对策略,旨在告诉读者,游戏规则变化之后,我们应该如何...
  • 组合游戏)SG函数与SG定理详解

    万次阅读 多人点赞 2019-03-05 19:22:33
    文章目录前言什么是组合游戏必胜点和必败点的概念Sprague-Grundy(SG)定理SG函数 前言   好久没写博客了,上一篇博客还是去年实训写的,一是因为寒假,二是因为随着难度的加深,学一个算法的时间也变长了很多...

    前言

      好久没写博客了,上一篇博客还是去年实训写的,一是因为寒假,二是因为随着难度的加深,学一个算法的时间也变长了很多(蒟蒻专有buff)。当然,最重要的还是因为自己懒~

      后面会继续努力的。(这csdn的markdown编辑器又改版了越来越难用了)


    转载请注明转自bestsort的博客


    好了,进入主题,说一下SG函数和SG定理

    什么是组合游戏

    在竞赛中,组合游戏的题目一般有以下特点

    1. 题目描述一般为 A A A, B B B 2人做游戏
    2. A A A B B B交替进行某种游戏规定的操作,每操作一次,选手可以在有限的操作(操作必须合法)集合中任选一种。
    3. 对于游戏的任何一种可能的局面,合法的操作集合只取决于这个局面本身,不取决于其它因素(跟选手,以前的所有操作无关)
    4. 如果当前选手无法进行合法的操作,则为负

    举个例子现在有一个数0,小明小红2人每次可以轮流在当前数加 1~3,谁先凑到21谁就赢

    这个描述就符合上面的条件:

    • 小明小红(满足1)
    • 每次轮流在当前数上加1~3(满足2)
    • 当前能进行的操作只取决于这个数本身(也就是这个局面),如果这个数为20,可操作的集合为+{1},如果为12,可操作的集合为+{1,2,3}(满足3)
    • 如果数字已经为21了,则不可能往上在加数字,可操作集合为 Φ \Phi Φ,当前选手为负(满足4)

    必胜点和必败点的概念

    • 必败点(P点) 前一个(previous player)选手将取胜的点称为必败点
    • 必胜点(N点) 下一个(next player)选手将取胜的点称为必胜点

    比如现在数字已经为18了,那么当前操作人只要给数字+3则必胜,我们就把在此位置称为必胜点(正常操作情况下,别杠说都18偏要+2。。。。)
    必胜点和必败点的性质:
    - 所有的终结点都是必败点
    - 从任何必胜点操作,至少有一种方式进入必败点
    - 无论如何操作, 从必败点都只能进入必胜点.

    Sprague-Grundy(SG)定理

    游戏和的SG函数等于各个游戏SG函数的Nim和。这样就可以将每一个子游戏分而治之,从而简化了问题。而Bouton定理就是Sprague-Grundy定理在Nim游戏中的直接应用,因为单堆的Nim游戏 SG函数满足 SG(x) = x。

    Nim和 : 各个数相异或的结果

    SG函数

    先定义mex(minimal excludant)运算,这是施加于一个集合的运算,表最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。
    对于任意状态 x , 定义 SG(x) = mex(S),其中 S S S x x x 后继状态的 S G SG SG函数值的集合。如 x 有三个后继状态分别为 S G ( a ) , S G ( b ) , S G ( c ) SG(a),SG(b),SG(c) SG(a),SG(b),SG(c),那么 S G ( x ) = m e x SG(x) = mex SG(x)=mex{ S G ( a SG(a SG(a, S G ( b ) SG(b) SG(b), S G ( c ) SG(c) SG(c)}。 这样 集合 S S S 的终态必然是空集,所以SG函数的终态为 S G ( x ) = 0 SG(x) = 0 SG(x)=0,当且仅当 x 为必败点P时。


    取石子问题

    有1堆n个的石子,每次只能取{ 1, 3, 4 }个石子,先取完石子者胜利,那么各个数的SG值为多少?

    SG[0]=0,f[]={1,3,4},

    x=1 时,可以取走1 - f{1}个石子,剩余{0}个,所以 SG[1] = mex{ SG[0] }= mex{0} = 1;

    x=2 时,可以取走2 - f{1}个石子,剩余{1}个,所以 SG[2] = mex{ SG[1] }= mex{1} = 0;

    x=3 时,可以取走3 - f{1,3}个石子,剩余{2,0}个,所以 SG[3] = mex{SG[2],SG[0]} = mex{0,0} =1;

    x=4 时,可以取走4- f{1,3,4}个石子,剩余{3,1,0}个,所以 SG[4] = mex{SG[3],SG[1],SG[0]} = mex{1,1,0} = 2;

    x=5 时,可以取走5 - f{1,3,4}个石子,剩余{4,2,1}个,所以SG[5] = mex{SG[4],SG[2],SG[1]} =mex{2,0,1} = 3;

    以此类推…

    x 0 1 2 3 4 5 6 7 8…

    SG[x] 0 1 0 1 2 3 2 0 1…

    由上述实例我们就可以得到SG函数值求解步骤,那么计算1~n的SG函数值步骤如下:

    1、使用 数组f 将 可改变当前状态 的方式记录下来。

    2、然后我们使用 另一个数组 将当前状态x 的后继状态标记。

    3、最后模拟mex运算,也就是我们在标记值中 搜索 未被标记值 的最小值,将其赋值给SG(x)。

    4、我们不断的重复 2 - 3 的步骤,就完成了 计算1~n 的函数值。
    模板如下:

    //f[N]:可改变当前状态的方式,N为方式的种类,f[N]要在getSG之前先预处理
    //SG[]:0~n的SG函数值
    //S[]:为x后继状态的集合
    int f[N],SG[MAXN],S[MAXN];
    void  getSG(int n){
        int i,j;
        memset(SG,0,sizeof(SG));
        //因为SG[0]始终等于0,所以i从1开始
        for(i = 1; i <= n; i++){
            //每一次都要将上一状态 的 后继集合 重置
            memset(S,0,sizeof(S));
            for(j = 0; f[j] <= i && j <= N; j++)
                S[SG[i-f[j]]] = 1;  //将后继状态的SG函数值进行标记
            for(j = 0;; j++) if(!S[j]){   //查询当前后继状态SG值中最小的非零值
                SG[i] = j;
                break;
            }
        }
    }
    
    

    其实不难发现,Nim游戏就是一个很典型的用SG定理解决的问题,因为Nim游戏在一堆n个石子中可以取1-n个石子,所以单独这一堆石子的SG值为 m e x ( n − 1 , n − 2 , n − 3 , . . . , n − n ) = n mex(n-1,n-2,n-3,...,n-n) = n mexn1,n2,n3,...,nn=n,根据SG定理,每一堆石子总数相互异或即为答案


    本文是参考其他博文+自己理解,整理而来,现附上参考博文链接:
    https://blog.csdn.net/luomingjun12315/article/details/45555495
    https://blog.csdn.net/SM_545/article/details/77340690

    展开全文
  • 贾志豪《组合游戏略述——浅谈SG游戏的若干拓展及变形
  • 组合游戏策略的分析,主要内容为nim问题、多图游戏等
  • 组合游戏入门讲解

    2012-08-10 09:38:37
    山东农业大学费玉奎 主要内容
  • 作者为UCLA的教授,介绍了博弈论中公平组合游戏的部分,其中包括经典的nim游戏,例子颇多,附有习题(可惜没答案)。
  • 优秀的基于组合的弹跳球游戏。 跑步 很多种方法: 转到 。 ./build-html.sh; cd html; python -m SimpleHTTPServer ./build-html.sh; cd html; python -m SimpleHTTPServer ,然后转到 。 ./run.sh 控件 在标题...
  • 今天看了一下午贾志豪的《组合游戏略述——浅谈SG游戏的若干拓展及变形》,真的是一篇非常优秀的论文,感觉自己又掌握了很多,给出链接https://wenku.baidu.com/view/25540742a8956bec0975e3a8.html 在这里我只...
  • 解析一类组合游戏

    2011-11-15 11:51:53
    ACM/ICPC 相关资料,希望对你们有用
  • 今天考试考了博弈论,发现对于博弈论除了原版的nim游戏之外就什么都不会了 对于作为其基础的SG函数及定理也是完全不了解,这样是不得行的 要通过不断地刷题,总结,得出一套博弈论的题的做题思路才好 看题先:...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 134,068
精华内容 53,627
关键字:

组合游戏