简单博弈
简单博弈
博弈的本意是下棋，现在也引申为：在一定条件下，遵守一定的规则，一个或几个拥有绝对理性思维的人或团队，从各自允许选择的行为或策略进行选择并加以实施，并从中各自取得相应结果或收益的过程。下面介绍一下简单博弈。
必胜点与必败点
####问题引入
现在设计一个抽牌问题。有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");
}
}