简单博弈
简单博弈
博弈的本意是下棋,现在也引申为:在一定条件下,遵守一定的规则,一个或几个拥有绝对理性思维的人或团队,从各自允许选择的行为或策略进行选择并加以实施,并从中各自取得相应结果或收益的过程。下面介绍一下简单博弈。
必胜点与必败点
####问题引入
现在设计一个抽牌问题。有26张牌,小明和小红两个人轮流摸牌,每次可以摸取1~3张牌,最后一个将牌摸完的人获胜。现在小明先手,假设两人都聪明绝顶,请问小明有没有必胜策略?显然,当牌剩下1~3张时,摸牌的人必胜。而当牌剩下4张时,摸牌的人必输。
现在引入必胜点与必败点的概念。
必胜点(N点) :下一个选手(Next player)将取胜的位置称为必胜点。
必败点(P点) :前一个选手(Previous player)将取胜的位置称为必败点。必败(必胜)点的属性:
(1) 所有终结点是必败点(P点);
(2) 从任何必胜点(N点)操作,至少有一种方法可以进入必败点(P点);
(3)无论如何操作, 从必败点(P点)都只能进入必胜点(N点).
那么,分析此问题。当没有牌时,肯定是P点(必败点)。当有1~3张牌时,总有方法走到终结点,所以它们是N点(必胜点)。当有四张牌时,无论如何走到P点,所以它是P点。枚举26张牌的情况,可以得出每张牌是否是必胜点。
题目参考:
Nim游戏
Nim游戏是博弈论中最经典的模型(之一),它又有着十分简单的规则和无比优美的结论 Nim游戏是组合游戏(Combinatorial Games)的一种,准确来说,属于“Impartial Combinatorial Games”(以下简称ICG)。
条件
满足以下条件的游戏是ICG(可能不太严谨):1、有两名选手;2、两名选手交替对游戏进行移动(move),每次一步,选手可以在(一般而言)有限的合法移动集合中任选一种进行移动;3、对于游戏的任何一种可能的局面,合法的移动集合只取决于这个局面本身,不取决于轮到哪名选手操作、以前的任何操作、骰子的点数或者其它什么因素; 4、如果轮到某名选手移动,且这个局面的合法的移动集合为空(也就是说此时无法进行移动),则这名选手负。根据这个定义,很多日常的游戏并非ICG。例如象棋就不满足条件3,因为红方只能移动红子,黑方只能移动黑子,合法的移动集合取决于轮到哪名选手操作。
问题引入
有两个玩家;
有三堆扑克牌(比如:可以分别是 5,7,9张);
游戏双方轮流操作;
玩家的每次操作是选择其中某一堆牌,然后从中取走任意张;
最后一次取牌的一方为获胜方;
问题分析
经过初步分析,我们发现
- (0,0,0) —— P点
- (0,0,x) —— N点
- (0,y,y) —— P点
- (14,35,46) ???
显然,通过枚举的方式判断每个情况的必胜属性是不可取的。下面引入Nim和的概念。
Nim-Sum
定义:
假设 $(x_m · · · x_0)_2$ 和$(y_m · · · y_0)_2$ 的nim-sum是$(z_m · · · z_0)_2$,则我们表示成 $(x_m · · · x_0)_2 ⊕ (y_m · · · y_0)_2 = (z_m · · · z_0)_2$, 这里,$z_k = x_k + y_k (mod 2)(k=0…m)$.
对于Nim游戏的某个位置$(x_1,x_2,x_3)$,当且仅当它各个部分的nim-sum等于0时,(即$x_1⊕x_2⊕x_3$),则当前位置位于必败点。这个方法适用于n堆的情况。
思考
思考(1):有了定理一,如何判断某个游戏的先手是输还是赢?
判断先手状态的nim和是否为0即可。如果非0,则必定可以通过一种或多种方法使nim和变为0。
思考(2):对于必胜点,如何判断有几种可行的操作方案?
如上,只需要判断每一堆最高位1的数量即可。
题目参考
SG函数
Sprague-Grundy定理(SG定理)
游戏和的SG函数等于各个游戏SG函数的Nim和。这样就可以将每一个子游戏分而治之,从而简化了问题。而Bouton定理就是Sprague-Grundy定理在Nim游戏中的直接应用,因为单堆的Nim游戏 SG函数满足 SG(x) = x。
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时。
我们回到一开始的摸牌问题,用SG函数来表示。
由于0没有后继状态,所以SG(0) = 0;
1的后继状态只有0,因为1可以到达0。所以SG(1) = mex(0) = 1
2的后继状态有0和1,SG(2) = mex({0,1}) = 2
SG(3) = mex({0,1,2}) = 3
4的后继状态为1,2,3,所以SG(4) = mex({1,2,3}) = 0
由于SG函数的终态为SG(0) = 0,所以当且仅当SG(x) = 0时,x为必败点。
SG函数模板
//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;
}
}
}
题目参考
HDOJ1848
顺便贴出代码
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
int f[] = {1,2,3,5,8,13,21,34,55,89,144,233,377,610,987};
int flag[1001]; //记录后继状态
int SG[1001];
void solve()
{
int i,j;
SG[0] = 0;
SG[1] = 1;
SG[2] = 2;
SG[3] = 3;
for(i=4;i<=1000;i++)
{
memset(flag,0,sizeof(flag));
for(j=0;f[j] <= i && j <= 14;j++)
{
flag[SG[i - f[j]]] = 1;
}
for(j=0;j<=1000;j++)
if(flag[j] == 0)
{
SG[i] = j;
break;
}
}
}
int main()
{
int m,n,p,ans;
solve();
while(scanf("%d%d%d",&m,&n,&p) != EOF && (m!=0 && n!=0 && p!=0))
{
ans = SG[n] ^ SG[m] ^ SG[p];
if(ans == 0) printf("Nacci\n");
else printf("Fibo\n");
}
}