前言

被Alice狠狠薄纱，Alice啊！我的Alice?。于是开启博弈论的学习之路(❁´◡`❁)~~（主要是发现前几天刚学了一点现在就忘得差不多了?，故决定记录一下）~~

博弈论

博弈论，是经济学的一个分支，主要研究具有竞争或对抗性质的对象，在一定规则下产生的各种行为。博弈论考虑游戏中的个体的预测行为和实际行为，并研究它们的优化策略。

通俗地讲，博弈论主要研究的是：在一个游戏中，进行游戏的多位玩家的策略。

几种博弈游戏

公平组合游戏

公平组合游戏（Impartial Game）的定义如下：

1、游戏有两个人参与，二者轮流做出决策，双方均知道游戏的完整信息；

2、任意一个游戏者在某一确定状态可以作出的决策集合只与当前的状态有关，而与游戏者无关；

3、游戏中的同一个状态不可能多次抵达，游戏以玩家无法行动为结束，且游戏一定会在有限步后以非平局结束。

在算法竞赛中出现的博弈论题目通常是ICG（(Impartial combinatorial game，公平组合游戏），所以接下来重点介绍的也是ICGᓚᘏᗢ

非公平组合游戏

非公平组合游戏（Partizan Game）与公平组合游戏的区别在于在非公平组合游戏中，游戏者在某一确定状态可以做出的决策集合与游戏者有关。大部分的棋类游戏都不是公平组合游戏，如国际象棋、中国象棋、围棋、五子棋等（因为双方都不能使用对方的棋子）。

反常游戏

反常游戏（Misère Game）按照传统的游戏规则进行游戏，但是其胜者为第一个无法行动的玩家。以 Nim 游戏为例，Nim 游戏中取走最后一颗石子的为胜者，而反常 Nim 游戏中取走最后一刻石子的为败者。

公平组合游戏（ICG，Impartial combinatorial game）

巴什博弈与P-position、N-position

问题描述：

有1堆石子，总个数是n，两名玩家轮流在石子堆中拿石子，每次至少取1个，至多取m个。取走最后一个石子的玩家为胜者。判定先手和后手谁胜。

结论：

当n % (m + 1) = 0时先手必败，否则先手必胜

分析：

1、n <= m时，先手可以一次拿完所有的石子，先手必胜
2、n = m + 1时，无论先手取多少个石子，留给后手的必然是m ~ 1个石子，后手必胜
3、n = k * (m + 1)时，无论先手取什么，后手都能控制两人所取的石子的总数为m + 1，最后局面将转移到2，后手必胜
4、n $\neq$ k * (m + 1)时，先手拿走n % (m + 1)个，那么局面变成3的情况，先手必胜

Roy&October之取石子

题目背景

Roy 和 October 两人在玩一个取石子的游戏。

题目描述

游戏规则是这样的：共有 $n$ 个石子，两人每次都只能取 $p^{k}$ 个（ $p$ 为质数， $k$ 为自然数，且 $p^{k}$ 小于等于当前剩余石子数），谁取走最后一个石子，谁就赢了。

现在 October 先取，问她有没有必胜策略。

若她有必胜策略，输出一行 October wins!；否则输出一行 Roy wins!。

输入格式

第一行一个正整数 $T$ ，表示测试点组数。

第 $2$ 行 $\sim$ 第 $T + 1$ 行，一行一个正整数 $n$ ，表示石子个数。

输出格式

$T$ 行，每行分别为 October wins! 或 Roy wins!。

样例 #1

样例输入 #1

样例输出 #1

October wins!October wins!October wins!

我的代码

#include <iostream>#define int long longvoid solve(){    int n;    std::cin>>n;    if(n % 6 == 0){        std::cout<<"Roy wins!\n";    }else{        std::cout<<"October wins!\n";    }}signed main() {    std::ios::sync_with_stdio(0);    std::cin.tie(0);std::cout.tie(0);    int t;    std::cin>>t;    while(t --){        solve();    }    return 0;}

题目分析

通过手玩小样例不难得到下面这张表( ´･･)ﾉ(._.`)
图片[1]-学不会的博弈论——初级篇-五八三
1、当n % 6 == 0时，无论先手取多少个石子，后手都能控制剩下的石子的数量为6的倍数，后手必胜
Q：先手不能一次全拿完吗？
A：6 = 2 * 3 -> 6 * k = k * 2 * 3,2、3是不同的素数，所以，6 * k不可能是 $p^{m}$ (●’◡’●)

P-position、N-position与动态规划

P-position的定义

P-position为前一个玩家（Previous Player，即刚刚走步的玩家）的必胜位置。

N-position的定义

N-position为下一个玩家（Next Player，即将要走步的玩家）的必胜位置。

当前位置是N-position表示马上走步的玩家必胜，即先手必胜，当前位置是P-position表示上一个走步的玩家必胜，即先手必败

尼姆游戏

问题描述

给定n堆物品，第i堆物品有 $a_{i}$ 个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可把一堆取光，但不能不取。取走最后一件物品者获胜。两人都采取最优策略，问先手是否必胜。

结论：

定义 $S (N i m - s u m) = \oplus_{i = 1}^{n} a_{i}$ 。先手必胜当且仅当 $S \neq 0$ 。

分析

1、最终状态只可能是：所有石子均被取完，此时异或和为0；

2、必定能从N-position转换到P-position，换句话说，先手处于必胜点时（即 $a_{1} \oplus a_{2} \oplus . . . \oplus a_{n} = k （ k \neq 0 ）$ ），一定能通过拿走一些石子，让 $a_{i}$ 变成 $a_{i}^{'}$ 让后手必败(即 $a_{1} \oplus a_{2} \oplus . . . \oplus a_{i}^{'} \oplus . . . \oplus a_{n} = 0$ )。不妨存在某个 $a_{i}$ ，它的二进制表示在K的最高位上是1。这时 $a_{i} \oplus k < a_{i}$ 一定成立。那么我们可以将 $a_{i}$ 改变成 $a_{i}^{'}$ 使 $a_{i}^{'} = a_{i} \oplus k$ ,此时有( $a_{1} \oplus a_{2} \oplus . . . \oplus a_{i}^{'} \oplus . . . \oplus a_{n} = a_{1} \oplus a_{2} \oplus . . . \oplus a_{n} \oplus k$ )

Q:为什么 $a_{i} \oplus k < a_{i}$ 一定成立？
A:我们需要先知道一些异或运算的性质：
只有在两个比较的位不同时其结果是1，否则结果为0
图片[2]-学不会的博弈论——初级篇-五八三
不难知道 $a_{i} \oplus k <= a_{i}$ 又因为当且仅当 $k = 0$ 时， $a_{i} \oplus k = a_{i}$ ，但 $k \neq 0$ ，所以 $a_{i} \oplus k < a_{i}$

ps：这里推荐一篇位运算的文章点击传送门ヾ(≧▽≦*)o

3、对于某个局面，若 $a_{1} \oplus a_{2} \oplus . . . \oplus a_{n} = 0$ ，一定不存在某个合法的移动，将 $a_{i}$ 变成 $a_{i}^{'}$ 后满足 $a_{1} \oplus a_{2} \oplus . . . \oplus a_{i}^{'} \oplus . . . \oplus a_{n} = 0$ ，因为异或运算满足消去律，由 $a_{1} \oplus a_{2} \oplus . . . \oplus a_{n} = a_{1} \oplus a_{2} \oplus . . . \oplus a_{i}^{'} \oplus . . . \oplus a_{n}$ 可以得到 $a_{i} = a_{i}^{'}$ ，所以将 $a_{i}$ 变成 $a_{i}^{'}$ 不是一个合法移动。

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

Author

lcy

我的代码

#include<bits/stdc++.h>#define int long longsigned main() {    std::ios::sync_with_stdio(false);    std::cin.tie(0);    std::cout.tie(0);    int m;    while(std::cin>>m && m != 0) {        int sum = 0;        int a[m + 1];        for (int i = 1; i <= m; i++) {            std::cin >> a[i];            sum ^= a[i];        }        if (sum == 0) {//先手必败的局面            std::cout << "0\n";        } else {//先手必胜的局面            int ans = 0;            for (int i = 1; i <= m; i++) {                if ((sum ^ a[i]) <= a[i]) {//如果存在某种操作能使先手将状态转移到P-position                    ans++;                }            }            std::cout << ans << "\n";        }    }    return 0;}

Sprague – Grundy函数

定义

任何一个公平组合游戏都可以通过把每个局面看成一个顶点，对每个局面和它的子局面连一条有向边来抽象成这个“有向图游戏”。
下面我们就在有向无环图的顶点上定义Sprague-Grundy函数。首先定义mex(minimal excludant)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、mex{1,3,5}=0、mex{}=0。
这里我们用巴什游戏图来举例子，根据游戏规则我们不难画出下图（不记得游戏规则的同学可以回翻到前面看看(✿◕‿◕✿)）
图片[3]-学不会的博弈论——初级篇-五八三
我们不难得到下面的规律
$x = 0, s g (0) = 0$ ，因为0没有后继点，mex{} = 0；
$x = 1, s g (1) = 1$ ，因为1的后继点为0，mex{0} = 1；
$x = 2, s g (2) = 2$ ，因为2的后继点为0，1，mex{0，1} = 2；
$x = 3, s g (3) = 0$ ，因为3的后继点为1，2，mex{1，2} = 0；
……
所以可以得到下面这张表
图片[4]-学不会的博弈论——初级篇-五八三
所以，在这个游戏中，SG函数值就等于 $n$ ，跟我们上面巴什博弈的结论一样ヾ(≧▽≦*)o

Brave Game

Problem Description

十年前读大学的时候，中国每年都要从国外引进一些电影大片，其中有一部电影就叫《勇敢者的游戏》（英文名称：Zathura），一直到现在，我依然对于电影中的部分电脑特技印象深刻。
今天，大家选择上机考试，就是一种勇敢（brave）的选择；这个短学期，我们讲的是博弈（game）专题；所以，大家现在玩的也是“勇敢者的游戏”，这也是我命名这个题目的原因。
当然，除了“勇敢”，我还希望看到“诚信”，无论考试成绩如何，希望看到的都是一个真实的结果，我也相信大家一定能做到的~

各位勇敢者要玩的第一个游戏是什么呢？很简单，它是这样定义的：
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

Author

lcy

我的代码

#include <bits/stdc++.h>#define int long longconst int N = 1e3 + 5;int sg[N],s[N];void solve(){    int n,m;    std::memset(sg,0,sizeof(sg));    std::cin>>n>>m;    for(int i = 1;i <= n;i ++){        std::memset(s,0,sizeof(s));//s模拟mex运算        for(int j = 1;j <= m && j <= i;j ++){            s[sg[i - j]] = 1;//将i的后继点的sg值标记        }        for(int j = 0;j <= n;j ++){            if(!s[j]){                sg[i] = j;//mex运算，把没有出现的最小自然数赋值给sg[i]                break;            }        }    }    if(sg[n]){        std::cout<<"first\n";    } else{        std::cout<<"second\n";    }}signed main() {    std::ios::sync_with_stdio(0);    std::cin.tie(0);std::cout.tie(0);    int t;    std::cin>>t;    while (t --){        solve();    }    return 0;}

Fibonacci again and again

Problem Description

任何一个大学生对菲波那契数列(Fibonacci numbers)应该都不会陌生，它是这样定义的：
F(1)=1;
F(2)=2;
F(n)=F(n-1)+F(n-2)(n>=3);
所以，1,2,3,5,8,13……就是菲波那契数列。
在HDOJ上有不少相关的题目，比如1005 Fibonacci again就是曾经的浙江省赛题。
今天，又一个关于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

Author

lcy

我的代码

#include <bits/stdc++.h>#define int long longconst int N = 1e3 + 5;int sg[N],s[N],fibo[17];void getFibo(){    fibo[1] = 1;    fibo[2] = 2;    for(int i = 3;i <= 16;i ++){        fibo[i] = fibo[i - 1] + fibo[i - 2];    }}signed main() {    std::ios::sync_with_stdio(0);    std::cin.tie(0);std::cout.tie(0);    int stone[3];    getFibo();    while (std::cin >> stone[0] >> stone[1] >> stone[2] && !(stone[0] == 0 && stone[1] == 0 && stone[2] == 0)) {        int sum = 0;        for(int k = 0;k < 3;k ++) {//计算出每一堆的SG函数的异或和            std::memset(sg, 0, sizeof(sg));            for (int i = 1; i <= stone[k]; i++) {//计算每堆的SG函数                std::memset(s, 0, sizeof(s));//模拟mex运算                for (int j = 1; fibo[j] <= i; j++) {                    s[sg[i - fibo[j]]] = 1;                }                for (int j = 0; j <= stone[k]; j++) {                    if (!s[j]) {                        sg[i] = j;                        break;                    }                }                sum ^= sg[stone[k]];            }        }        if (sum == 0) {            std::cout << "Nacci\n";        } else {            std::cout << "Fibo\n";        }    }    return 0;}

Q:为啥fibo只需要算到fibo[16]？
A:因为fibo[16] = 987，fibo[17] = 1597，而题目的数据范围是 $1 <= m, n, p <= 1000$ ，所以fibo只需要算到fibo[16]就完全够用ヾ(≧▽≦*)o