博弈论

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

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

算法中常见的博弈论题目一般是公平组合游戏，那么什么是公平组合游戏呢？

公平组合游戏的定义如下：

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

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

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

大部分的棋类游戏都 不是 公平组合游戏，如国际象棋、中国象棋、围棋、五子棋等（因为双方都不能使用对方的棋子）。

常见模型

几种模型均存在奇异局面，即双方均采取最优策略，若处于奇异局面，必败。

所谓奇异局面，就是必败点。

必胜点和必败点的概念：

​ P点：必败点，换而言之，就是谁处于此位置，则在双方操作正确的情况下必败。

​ N点：必胜点，处于此情况下，双方操作均正确的情况下必胜。

必胜点和必败点的性质：

​ 1、所有终结点是 必败点 P 。（我们以此为基本前提进行推理，换句话说，我们以此为假设）

​ 2、从任何必胜点N 操作，至少有一种方式可以进入必败点 P。

​ 3、无论如何操作，必败点P 都只能进入 必胜点 N。

我们研究必胜点和必败点的目的时间为题进行简化，有助于我们的分析。通常我们分析必胜点和必败点都是以终结点进行逆序分析。

巴什博弈

只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。

分析

当总个数小于等于m的时候，先手胜。

当总个数为m + 1的时候，后手胜。

当总个数为m + 2的时候，先手可使后手面对m + 1局面，先手胜。

可推断，若总个数为k *（m + 1）,后手胜。

若总个数为k * (m + 1) + s(s <= m),先手胜。

例题：https://ac.nowcoder.com/acm/contest/11746/D

if(n % (m + 1) != 0)
            return first win;
else
            return second win;
 

  

 

  
1
  
2
  
3
  
4
  
5
 

斐波那契博弈

1堆石子有n个,两人轮流取.先取者第1次可以取任意多个，但不能全部取完.以后每次取的石子数不能超过上次取子数的2倍。取完者胜.

结论：当n为斐波那契数时，先手必败。

分析见： https://blog.csdn.net/dgq8211/article/details/7602807

模板

void Init()//斐波那契数列，先打表，范围看情况
{
    f[0]=f[1]=1;
    for(int i=2;i<=55;i++)
    {
        f[i]=f[i-1]+f[i-2];
    }
}
int n;
int flag = 0;
for(int i = 0;f[i];i++){//分别比较，判断出n是否是斐波那契数
    if(f[i] == n){
        flag = 1;
        break;
    }
}
if(!flag)
    return first win;
else
    return second win;

  

 

  
 
 

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

威佐夫博弈

有两堆各若干个物品，两个人轮流从任意一堆中取出至少一个或者同时从两堆中取出同样多的物品，规定每次至少取一个，至多不限，最后取光者胜利。

结论：若两堆物品的初始值为(x,y)，则令z = abs（y-x）；记w =（int)[ ( (sqrt(5)+1) /2 )*z ]；若w = min(x,y)，则先手必败，否则先手必胜。

例题：https://ac.nowcoder.com/acm/contest/11746/E

分析见：https://blog.csdn.net/qq_41311604/article/details/79980882

模板

 int z = abs(y-x);
 if((int)(((sqrt(5)+1)/2)*z)!=min(x,y))
     return first win;
 else
     return second win;

  

 

  
1
  
2
  
3
  
4
  
5
 

尼姆博弈

有任意堆物品，每堆物品的个数是任意的，双方轮流从中取物品，每一次只能从一堆物品中取部分或全部物品，最少取一件，取到最后一件物品的人获胜。

结论：判断这几堆物品的异或运算结果是否为0，如果为零，则先手必败。

分析：https://blog.csdn.net/Elliot_Alderson/article/details/84778775?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.control&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.control

模板

int n;
int a;
int num = 0;
cin >> n;
for(i = 0;i < n;i++){
    cin >> a;
    num ^= a;
}
if(num)
	return first win;
else
	return second win;

  

 

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

台阶-Nim游戏

题目描述

现在，有一个n级台阶的楼梯，每级台阶上都有若干个石子，其中第i级台阶上有ai个石子(i≥1)。

两位玩家轮流操作，每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中（不能不拿）。

已经拿到地面上的石子不能再拿，最后无法进行操作的人视为失败。

问如果两人都采用最优策略，先手是否必胜。


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
 

此时我们需要将奇数台阶看做一个经典的Nim游戏，如果先手时奇数台阶上的值的异或值为0，则先手必败，反之必胜

证明：
先手时，如果奇数台阶异或非0，根据经典Nim游戏，先手总有一种方式使奇数台阶异或为0，于是先手留了奇数台阶异或为0的状态给后手
于是轮到后手：
①当后手移动偶数台阶上的石子时，先手只需将对手移动的石子继续移到下一个台阶，这样奇数台阶的石子相当于没变，于是留给后手的又是奇数台阶异或为0的状态
②当后手移动奇数台阶上的石子时，留给先手的奇数台阶异或非0，根据经典Nim游戏，先手总能找出一种方案使奇数台阶异或为0
因此无论后手如何移动，先手总能通过操作把奇数异或为0的情况留给后手，当奇数台阶全为0时，只留下偶数台阶上有石子。
（核心就是：先手总是把奇数台阶异或为0的状态留给对面，即总是将必败态交给对面）

因为偶数台阶上的石子要想移动到地面，必然需要经过偶数次移动，又因为奇数台阶全0的情况是留给后手的，因此先手总是可以将石子移动到地面，当将最后一个（堆）石子移动到地面时，后手无法操作，即后手失败。

因此如果先手时奇数台阶上的值的异或值为非0，则先手必胜，反之必败！

int res = 0;
int n;
cin >> n;

for(int i = 1 ; i <= n ; i++)
{
    int x;
    cin >> x;
    if(i % 2) res ^= x;
}
if(res) return first win;
else return second win;

  

 

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

SG函数与SG定理

https://www.cnblogs.com/ECJTUACM-873284962/p/6921829.html

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/126829264