基础博弈

秃头王

基础算法

发布于：2022年5月4日

次浏览

博弈论

1.简介 博弈

博弈/博弈论，又称为对策论（Game Theory）、赛局理论等，既是现代数学的一个新分支，也是运筹学的一个重要学科。博弈论主要研究公式化了的激励结构间的相互作用，是研究具有斗争或竞争性质现象的数学理论和方法，博弈论考虑游戏中的个体的预测行为和实际行为，并研究它们的优化策略。

总而言之，博弈，就是两方（或者多方）在为了某一种目标进行的竞争。

在生活中，博弈无处不在，国与国之间的交锋就是一种博弈，在游戏中你与对手的有来有回也是一种博弈，面对老板提出加工资的需求又也是一种博弈，在博弈中，选择去做什么非常重要，这也是十分有研究价值的，一个有趣的题外话：从1994年诺贝尔经济学奖授予3位博弈论专家开始，共有7届的诺贝尔经济学奖与博弈论的研究有关。

2. 基础概念

　　必胜态：通过某一步可以转移到必败态的局面。 也就是说，对于一个处于必胜态的玩家，他总能找到一种合法操作，将当前局面变成一个必败态然后交给对方，如果中途不出现意外的话，最终自己就会得到胜利。但是处于必胜态并不意味着任意的操作都能将当前局面变成必败态。

　　必败态：通过某一步只能转移到必胜态的局面。 也就是说，处于必败态的玩家无论做什么操作，都只会将当前的局面变成必胜态，然后交给对方，只要对方足够聪明，那么该玩家将输掉比赛。

　　对于足够聪明的两个博弈者来说，游戏的胜负在比赛前就已经知道(当然，我这里只是说在题目里，在现实中如果是稍微复杂一点的博弈游戏，单凭人脑是很难达到那种水平)，也就是说胜利的一方总能找到胜利的路径，而输掉的那一方无论怎样走，胜利的一方都能找到对应的方法。也就是说先后手以及起始局面可以决定整场博弈的胜负。

3.思想

博弈问题的特点

a) 博弈模型为两人轮流决策的非合作博弈。即两人轮流进行决策，并且两人都使用最优策略来获取胜利

b) 博弈是有限的。即无论两人怎样决策，都会在有限步后决出胜负

c) 公平博弈。即两人进行决策所遵循的规则相同

4.学习方法

关于博弈论，最理想的学习方式还当属熟悉模型，几种常用的博弈论模型有：巴什博弈，威佐夫博弈，斐波那契博弈，尼姆博弈，通过理解模型以及他们模型可能产生的变种，面对各种题目也只是“换汤不换药”的思维。

在基本了解各类模型之后，我们可以开始学习“博弈树”和“决策树”这类算法，以及其他一些启发式算法，这与人工智能的思维很接近，此时算法难度已经直线上升，在经过这个瓶颈之后，等待你的是一片星辰大海。

巴什博弈

巴什博弈的主要内容：只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。其中它强调的是只有一堆物品：取光者胜

如果 n % (m + 1) == 0 先手必败

​ n % (m + 1) != 0 先后必败

相信大家看见这个一定有很多疑惑就是为什么这个公式就能看到结局！

1.如果它能被（m+1）整除，那么假设你先手 取p个，那么对手总能取m+1-p 个（因为1<=p<=m，那么 1<=(m+1-p)<=m 也满足对手所取数量的条件限制），这样不断循环下去，最后拿到石头的一定是对手。

2.如果它不能被（m+1）整除，那么你一定可以拿走那个余数k（k=n%(m+1)） 这样对手就相当于面对了 n%（m+1）的局面，也就是1的情况。

巴什博弈(例题)

巴什博弈-普通

http://acm.hdu.edu.cn/showproblem.php?pid=1846

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include <iostream>
using namespace std;

//  最先取光石子的一方为胜

bool Bash(int n, int m) {
    return n % (m + 1) != 0 ? 1 : 0; // 核心代码
}

int main() {
    int t, n, m; // n = 组数    n = 石子个数    m = 每回取最多个数
    cin >> t;
    for (int i = 0; i < t; i++) {
        cin >> n >> m;
        cout << (Bash(n, m) ? "first" : "second") << endl;
    }
    return 0;
}

巴什博弈-变行

http://acm.hdu.edu.cn/showproblem.php?pid=4764

1
2
3
4
5
6
7
8
9
10
11
12
13

#include <iostream>
using namespace std;

// 题目的意思就是谁取到最后一个谁输

int main() {
    int n, m;
    while (cin >> n >> m) {
        if (!(n + m)) break;
        cout << (((n - 1) % (m + 1)) == 0 ? "Jiang" : "Tang") << endl;
    }
    return 0;
}

尼姆博弈

在说尼姆博弈之前我们需要去了解一个什么呢！ 就是异或

异或

英文名字 exclusive OR

缩写 xor

数学符号 ⊕

计算机符号是 xor

但是到底异或怎么使用

比如说 4 ^ 3

就是说他们相同为0不同为1,当然在其中你应该还能看出一个问题是什么呢！

就是大家可以算一下7的二进制数是什么 1 1 1 对吧！

从此问题看出他们异或的结果就等于他们两个数相加 对吧 ！！!

就是异或也叫半加运算

这里能大家可以比如再去实验一个数比如说 1 ^ 2 = 什么对吧！！！

现在说了这么多都是什么对吧！！！ 就是为了我们之后要讲的尼姆博弈做的 铺垫！

什么是尼姆博弈

有n堆石子，两人从某一堆取任意多个，规定至少取走1个之多可以取走这堆的全部最后取光者胜。

在这里大家就可能发现了这和刚刚的巴什博弈不差什么对吧！

情况 ① 当有 1 堆石子的时候先手可以全部取走，对吧 ， 之后先手胜利

情况 ② 当有 2 堆石子时候 我们令一堆石子为 n 另一堆 m 假设 n > m —– n = 4 —- m = 3 之后先手先取 因为两个人都是顶尖聪明的人都会去去吧自己利益最大化 就是我们先取 n - m 个剩下的无论后手怎么去取我们都和后手去取相同 个数的石子这样我们一定是必胜局，

我们让异或为0也就是说我们让两个石子数量相对 之后不就像我们之前说的不管后手取多少我们先手都是必胜

情况 ③ 当有 2 堆石子时候 我们令一堆石子为 n 另一堆 m 假设 n = m —– n = 4 —- m = 4 从刚才上图看出一但出现 n == m 时候无论先手怎么取 后手就可以取和先手相同的个数 这样先手必败 （就是说因为两个都足够聪明所有说先手一定是什么比败局）

之后咱们不可能说是只有2堆是吧 可能还有 3 堆 ， 4 堆 ， 5 堆，6 堆…..等等

比如说（1， 2 ，3）这种我们能看出 先手必败

1 二进制 0 0 1

2 二进制 0 1 0

3 二进制 0 1 1 +（xor）

​ 0 0 0

随机举例

堆数

n = 5

石子个数

182 63 59 22 10

取光者胜

甲 先 乙 后

甲

乙

甲

经过几次后一定会得到情况②

尼姆博弈-代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#include <iostream>
using namespace std;

int main() {
    int n, t = 0; // n = 堆数
    cin >> n;
    while (n--) {
        int d;
        cin >> d;
        t ^= d;
    }
    if (t == 0) cout << "先手必输";
    else cout << "先手必胜";
    return 0;
}

更新于：2022年5月4日