囚徒困境

假设有两个小偷A和B联合犯事、私入民宅被警察抓住。
警方将两人分别置于不同的两个房间内进行审讯，对每一个犯罪嫌疑人，警方给出的政策是：如果两个犯罪嫌疑人都坦白了罪行，交出了赃物，于是证据确凿，两人都被判有罪，各被判刑8年；如果只有一个犯罪嫌疑人坦白，另一个人没有坦白而是抵赖，则以妨碍公务罪（因已有证据表明其有罪）再加刑2年，而坦白者有功被减刑8年，立即释放。如果两人都抵赖，则警方因证据不足不能判两人的偷窃罪，但可以私入民宅的罪名将两人各判入狱1年。

对于A，他做坦白是最优的，对于B也是一样的，因为你不知道对方会不会选择抵赖，如果双方都选择抵赖那自然是最好的情况，但是任何偏差都会使其情况变遭，所以坦白是一个最均衡的点（纳什均衡）

智猪博弈 Pigs payoffs

假设猪圈里有一头大猪、一头小猪。猪圈的一头有猪食槽，另一头安装着控制猪食供应的按钮，按一下按钮会有10个单位的猪食进槽，但是谁按按钮就会首先付出2个单位的成本，若小猪先到槽边，大小猪吃到食物的收益比是6∶4；同时到槽边，大小猪收益比是7∶3；大猪先到槽边，大小猪收益比是9∶1。那么，在两头猪都有智慧的前提下，最终结果是小猪选择等待。

大猪行动情况下，小猪选择等待，可以得到4的收益，而小猪行动，只能得到1的收益。
大猪等待情况下，小猪行动，小猪收益为-1，小猪等待收益为0
所以等待是最好选择

美女的硬币

一位陌生美女主动过来和你搭讪，并要求和你一起玩个游戏。美女提议：“让我们各自亮出硬币的一面，或正或反。如果我们都是正面，那么我给你3元，如果我们都是反面，我给你1元，剩下的情况你给我2元就可以了。”听起来不错的提议。如果我是男性，无论如何我是要玩的，不过经济学考虑就是另外一回事了，这个游戏真的够公平吗？

设男士正面概率为x，反面为1-x
则列出方程
3x+(-2)(1-x)=(-2)x+1(1-x)
解x=3/8;
带入表达式3x+(-2)*(1-x)可得每次的期望收入为-1/8元
设女士正面的概率为y，反面为1-y
-3y+2(1-y)=2y+(-1)(1-y)
y=3/8
带入表达式得期望收益为1/8
所以美女更有利

巴什博弈

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

问题 A: 巴什博弈
题目描述
十年前读大学的时候，中国每年都要从国外引进一些电影大片，其中有一部电影就叫《勇敢者的游戏》（英文名称：Zathura），一直到现在，我依然对于电影中的部分电脑特技印象深刻。
今天，大家选择上机考试，就是一种勇敢（brave）的选择；这个短学期，我们讲的是博弈（game）专题；所以，大家现在玩的也是“勇敢者的游戏”，这也是我命名这个题目的原因。
当然，除了“勇敢”，我还希望看到“诚信”，无论考试成绩如何，希望看到的都是一个真实的结果，我也相信大家一定能做到的~
各位勇敢者要玩的第一个游戏是什么呢？很简单，它是这样定义的：
1、 本游戏是一个二人游戏;
2、 有一堆石子一共有n个；
3、 两人轮流进行;
4、 每走一步可以取走1…m个石子；
5、 最先取光石子的一方为胜；
如果游戏的双方使用的都是最优策略，请输出哪个人能赢。
输入
输入数据首先包含一个正整数C(C<=100)，表示有C组测试数据。
每组测试数据占一行，包含两个整数n和m（1<=nm<=1000），n和m的含义见题目描述。
输出
如果先走的人能赢，请输出“first”，否则请输出“second”，每个实例的输出占一行。
样例输入
2
23 2
4 3
样例输出
first
second

如果n=m+1，一次最多只能取m个，无论先取者拿走多少个，
后取者都能够一次拿走剩余的物品，后者取胜
所以如果n=（m+1）r+s，（s≤m),那么先取者要拿走s个物品，如果后取者拿走
k（≤m)个，那么先取者再拿走m+1-k个，结果剩下（m+1）（r-1）个，以后保持这样的
取法，那么先取者肯定获胜。总之，要保持给对手留下（m+1）的倍数，就能最后获胜


#include<bits/stdc++.h>
using namespace std;

int main(){
  int t,n,m;
  cin>>t;
  while(t--){
    cin>>n>>m;
    if(n%(m+1)==0)
        cout<<"second"<<endl;   //first和second 的字样要去题目里粘，因为可能因为字体不一致导致wa了
    else 
        cout<<"first"<<endl;
    }
}

威佐夫博弈

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

奇异局势

我们用(ak, bk) ak <= bk , k = 0, 1, 2, 3, 4….n 表示两堆物品的数量并称其为局势，如果面对(0, 0) , 那么已经输了，这种局势我们称为奇异局势。
(0 , 0) , (1, 2 ) , (3, 5), (4, 7) , (6, 10) , (8, 13) , (9, 15)
a0 = b0 = 0
ak是未在前面出现过的最小自然数。
bk= ak + k

任何自然数都包含在一个且仅有一个奇异局势中
ak > ak-1

bk = ak+k > ak-1 + k -1 = bk-1 > ak-1

任何操作都可以将奇异局势变为非奇异局势
如果改变一个分量，那么另一个分量不可能在其他奇异局势中，所以是非奇异局势

如果同时改变两个分量，由于其差不变，而且不可能是其他奇异局势的差，所以也是非奇异局势。

采用适当的方法可以将奇异局势变为非奇异局势
局势(a, b)
b = a
a=ak, b > bk
a=ak,b< bk
a>ak,b = ak + k
a<ak, b= ak+k 1 : a=aj, j <k 2: a = bj, j < k

判断奇异局势
这是数学家总结的公式

ak=[k (1+√5) / 2 ), bk = ak + k. k=0,1,2,3,4…n
2/(1 + √5 ) = (√5 – 1) / 2
先求出 j = [a (√5 – 1) / 2]
若 a=[j (1 + √5) / 2] 那么 a = aj, b = bj + j
若不等于， a = aj+1，bj+1 = aj+1 + j + 1

问题 C: 威佐夫博弈
时间限制: 1 Sec 内存限制: 128 MB
题目描述
有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者？
输入
输入包含若干行，表示若干种石子的初始情况，其中每一行包含两个非负整数a和b，表示两堆石子的数目，a和b都不大于1000000，且a<=b。a=b=0退出。
输出
输出也有若干行，如果最后你是败者，则为0，反之，输出1。
样例输入
1 2
5 8
4 7
2 2
0 0
样例输出
0
1
0
1

#include<bits/stdc++.h>
using namespace std;
const double ep1=(sqrt(5)-1)/2;
const double ep2=(sqrt(5)+1)/2;

int main(){
  int n,m;
  while(cin>>n>>m){
    if(m==0&&n==0) break;
    if(m>n)
      swap(m,n);
      int k=m*ep1;
      int temp1=ep2*k,temp2=temp1+k;
      int temp3=ep2*(k+1),temp4=temp3+k+1;
      if(m==temp1&&n==temp2) cout<<"0"<<endl;
      else if(m==temp3&&n==temp4) cout<<"0"<<endl;
      else cout<<"1"<<endl;
  }
  return 0;
}

尼姆博弈

有多堆物品两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限，最后取光者获胜。
(a, b ,c)表示某种局势
(0, 0 , 0 )奇异局势
(0, n, n)
(1, 2, 3) 无论对手怎么拿，都会变成(0, n , n)

异或：按位模2加 用符号 (+) 表示
1 (+) 1 = 0
1 (+) 2 (+) 3 = 0
奇异局势(0, n ,n )也是0
对于任何奇异局势 a(+)b(+)c = 0
如何将非奇异局势(a, b, c)变为非奇异局势

问题 B: 尼姆博弈
时间限制: 1 Sec 内存限制: 128 MB
题目描述
有多堆物品两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限，最后取光者获胜。
输入
输入多组数据
第一行 输入 n ，代表有n堆物品
接下来n个数 代表每堆物品的数量
输出
如果先手必胜输出‘first" 否则输出“second”。输出不包括引号。
样例输入
3
1 2 3
4
0 0 4 4
样例输出
second
second

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n,m;
  while(cin>>n){
    int ans=0;
    for(int i=0;i<n;i++){
        cin>>m;
         ans^=m;
       }
    if(ans==0) cout<<"second"<<endl;
    else cout<<"first"<<endl;
  }
}

最后

以上就是顺心灯泡最近收集整理的关于简单博弈奇异局势的全部内容，更多相关简单博弈奇异局势内容请搜索靠谱客的其他文章。