博弈论基础
博弈论又被称为对策论(Game Theory)，既是现代数学的一个新分支，也是运筹学的一个重要学科。博弈论主要研究公式化了的激励结构间的相互作用，是研究具有斗争或竞争性质现象的数学理论和方法。博弈论考虑游戏中的个体的预测行为和实际行为，并研究它们的优化策略。
引入：囚徒困境
囚徒困境的故事讲的是,两个嫌疑犯小A、小B作案后被警察抓住,分别关在不同的屋子里接受审讯。警察知道两人有罪,但缺乏足够的证据。警察告诉每个人:如果两人都抵赖,各判刑一年;如果两人都坦白,各判五年;如果两人中一个坦白而另一个抵赖,坦白的放出去,抵赖的判十年。
于是,每个囚徒都面临两种选择:坦白或抵赖。
在不和小B商量的情况下，作为小A的你是选择招供坐牢5年或0年，还是会选择抵赖坐牢10年或1年呢？
一般的人都会选着保险一点的招供吧。
反观小B，也一定会做出同样的选择，也就是招供。换句话说，只要两名囚徒都是自私且理性的，那么双方都会同时选择招供，结果就是双方各判5年。
在这个场景中，双方都无法单方面改变自己的博弈策略（单方面改变只会让自己蒙受损失），使得局面进入了一个微妙而又稳定的平衡，这个平衡被称为纳什均衡。
在现实中,也有很多类似的现象,比如家长给孩子报越来越多的课外班,比如高三考生备战高考,卷起来了啊.从局外人看来,许多竞争都是显而易见双输的局面,但是我们没有办法,因为我们都是参与博弈的“囚徒”。
ICG博弈
所讨论的博弈问题满足以下条件： 玩家只有两个人，轮流做出决策。 游戏的状态集有限，保证游戏在有限步后结束，这样必然会产生不能操作者，其输。 对任何一种局面，胜负只决定于局面本身，而与轮到哪位选手无关。
取石子游戏：取石子游戏是一个古老的博弈游戏，发源于中国，它是组合数学领域的一个经典问题。它有许多不同的玩法，基本上是两个玩家，玩的形式是轮流抓石子，胜利的标准是抓走最后的石子。玩家设定： 先取石子的是玩家A（先手A），后取石子的是玩家B（后手B）。
经典的三种玩法 一、巴什博奕(Bash Game) 二、尼姆博奕(Nimm Game) 三、威佐夫博奕(Wythoff Game)
（一）巴什博弈
1堆n个石子每次最多取m个、至少取1个
Case 1:如果n=m 1，那么由于一次最多只能取m个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜。 Case 2:n=(m 1)*r s，(r为任意自然数，s≤m),那么先取者要拿走s个物品，如果后者拿走k(1≤k≤m)个，那么先取者再拿走m 1-k个，结果剩下(m 1)(r-1)个，以后保持这样的取法，那么先取者肯定获胜。 Case 3:n=r*(m 1)，先手拿走k(1≤k≤m)个，那么后手再拿走m 1-k个，结果剩下(m 1)(r-1)个，以后保持这样的取法，则后手胜，先手必败。
总之，要保持给对手留下（m 1）的倍数，就能最后获胜。
术语:正经人称(m 1)的局面为奇异局势
变相的玩法
两个人轮流报数，每次至少报一个，最多报十个，谁能报到100者胜。（等价于从一堆100个石子中取石子，最后取完的胜）
例题：2368 — Buttons (poj.org)
题面：
题面意思：有一堆k个的石头，每人轮流拿1,2，..L个石头，数据范围是3 <= K <= 100 000 000 ，2 <= L < K。输入k的值，要求输出最小的L，使得后者胜。
在理解了巴什博弈之后来看这题还是思路比较清晰的，首先想让后手胜，就必须把（1 L）的局面留给先手。这题没问我们谁会赢，问的是后手要赢的最小L值为多少。那我们就找到能被k整除的最小大于2的因数，之后减1输出就是答案了。
于是有了以下代码注意下（poj用不了万能头文件，编译器要求有点严格。）：
代码语言：javascript复制//#include<bits/stdc .h>
#include<iostream>
using namespace std;
typedef long long ll;
const int N=100005;
ll n;//石子数量
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
ll i;
for(i=2;i<n;i )//依次找最小的因子
{
if(n%(i 1)==0)
{
cout<<i<<endl;
break;
}
}
if(i==n) cout<<0<<endl;//找不到的情况下输出0
return 0;
}就是说数据范围1e8，就超时快乐，TEL了哈哈哈哈哈哈。由于循环2~n，时间复杂度是O(n)。
代码语言：javascript复制再有一个新的思路就是，遍历一遍所有的n的因数，存起来，在输出最小大于等于3的因数减一。一下代码时间复杂度为O(log n)。AC快乐。
//#include<bits/stdc .h>
#include<algorithm>
#include<math.h>
#include<iostream>
#include<stdio.h>
using namespace std;
typedef long long ll;
const int N=100005;
ll n,a[N];//n为石头总数，a[i]存n的因数
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
int temp=0;
for(int i=1;i*i<=n;i )
{
if(n%i==0&&i*i!=n) a[temp ]=i,a[temp ]=n/i;
//注意要区别开类似n=4时，因数为1,2,4.而不是1,2,2,4的情况
else if(n%i==0&&i*i==n) a[temp ]=i;
}
sort(a,a temp);//从小到大排序一下
for(int i=0;i<temp;i )
{
if(a[i]>=3)//找到最小大于等于3的因数，减一输出
{
cout<<a[i]-1<<endl;
break;
}
}
return 0;
}（二）尼姆博弈
有n堆石子，每堆石子的数量是a1,a2,a3……，二个人依次从这些石子堆中的一个拿取任意的石子，至少一个，最后一个拿光石子的人胜利
n=1: 先手全拿，先手必胜。 n=2:有两种情况，一种可能相同，一种情况一堆比另一堆少（多） (m,m) 按照“有一学一，照猫画猫”法，先手必输。 (m,M)先手先从多的一堆中拿出(M-m)个，此时后手面对(m,m)的局面先手必胜。 术语:正经人称(m,m)的局面为奇异局势 n=3:(m,m,M)先手必胜局，先手可以先拿M,之后变成了(m,m,0)的局面，是不是很熟悉~ (a1,a2,a3)的话，举个例子(1,2,3),先手取完之后可能的局面为(0,2,3),(1,1,3),(1,0,3),(1,2,2),(1,2,1),(1,2,0)都是之前讲过的，情况如下：
前人告诉我们的规律是：异或的结果均为0
获胜情况的讨论
面对异或结果为0的玩家必输。
结果不为0，则玩家有获胜的取法。
例题：891. Nim游戏 – AcWing题库
题面：
看懂了尼姆博奕，这个题目就是分分钟AC咯。
上代码：
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
typedef long long ll;
const int N=100005;
ll n,a[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=0;i<n;i )
cin>>a[i];
int ans=a[0];
for(int i=1;i<n;i ) ans^=a[i];//^就是做异或运算
if(ans==0) cout<<"No"<<endl;
else cout<<"Yes"<<endl;
return 0;
}(三)威佐夫博弈
有两堆各若干个物品，两个人轮流从任一堆取至少一个或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。
举一个例子:局势是(1,2)，先手有四种取法，动动你聪明的脑子就会发现无论先手怎么取，后手都能胜利，也就是说(1,2)是奇异局势。
没脑子的人来看看分析咯：
先手从第一堆里面拿1个，后者拿光后面的2个，后者胜。
先手从第一堆和第二堆里面同时拿1个，后者只能拿走第二堆剩下的1个，后者胜。
先手从第二堆里面拿2个，后手拿走第一堆的1个，后者胜.
先手从第二堆里面拿1个，后手从第一堆和第二堆里面同时拿走1个，后者胜。
假设现在的局势是（3,5)：
（1）先手在“3”中取1个，后手就可以在“5”中取走4个，这样就变成了（1，2）的局势
（2）先手在“3”中取2个，后手就可以在 “5” 中取走3个，这样也变成了（1,2）的局势
（3）先手在“5”中取1个，后手就在 “3”和“5” 中各取走2个，这样成了（1，2）的局势
（4）先手在”5”中取2个,后手就在 “3”和”5”中各取走3个,这样变成了(0，0)的局势，先手输
（5）先手在“5”中取3个，后手就在 “3”和“5” 中各取走1个，也变成了（1，2）的局势
（6）先手在“5”中取4个，后手在“3”中取走1个，还是（1，2）的局势
我们可以来找找那些先手必输局势的规律（奇异局势）
- 第一种（0，0）
- 第二种（1，2）
- 第三种（3，5）
- 第四种 (4 ，7）
- 第五种（6，10）
- 第六种 (8，13）
- 第七种 (9 ，15）
- 第八种 (11 ，18）
- 第n种（a，b）
我们会发现他们的差值是递增的，分别是0,1,2,3,4,5,6,7……n 还有一个规律(正常人都发现不了):a=(b-a)*1.618向下取整
就是：a = int(b – a)*1.618
注：这里的int是强制类型转换，注意这不是简单的四舍五入，假如后面的值是3.9，转换以后得到的不是4而是3，也就是说强制int类型转换得到的是不大于这个数值的最大整数。
有些题目要求精度较高，我们可以用下述式子来表示这个值: 1.618 = (sqrt(5.0) 1) / 2 头文件：include<math.h>
例题：1067 — 取石子游戏 (poj.org)
题面：
代码：
代码语言：javascript复制//#include<bits/stdc .h>
#include<algorithm>
#include<math.h>
#include<iostream>
#include<stdio.h>
using namespace std;
typedef long long ll;
const int N=100005;
ll a,b;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
while(cin>>a>>b)//多组输入！！！
{
double flag= (sqrt(5.0) 1) / 2.0;//精度高一些用double来存1.618
if(a>b) swap(a,b);//保证b要比a大，后面有用到b-a
if(a==int((b-a)*flag))cout<<0<<endl;//先手面对奇异局势必输
else cout<<1<<endl;
}
return 0;
}版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/181728.html原文链接：https://javaforall.cn
