学习笔记 透彻博弈论
写在之前
我打算发一个大篇的博弈论
这是一个大纲
这其中也存在来自多方大佬的转载
希望可以解答一些各位心中的疑惑
透彻博弈论
cdy:@xkj 博弈论是个啥？ ？ ？
xkj:@cdy 学科技的
我们接下来会讲些什么
1.四大经典博弈
2.博弈树(构造状态图)
3.SG函数
4.一些杂讲(这块就是比较乱)
顺序是乱的
博弈树(博弈流程图)
这玩意就跟dfs树一样 状态量一般很大
但是同样跟dfs树一样可以玄学剪枝
可以针对一些比较简单的博弈
我们就先以
言简意赅的巴士博弈为例
当然了 这里还有一道跟博弈树有关的题
【我是那道题的链接】
SG函数
一类解决博弈论的有力玄学武器
常用于解决组合问题
具体见
基本的SG定理也就是
我们将当前游戏分解为若干子游戏之后
第i个子游戏的SG直接是SG_i(1<=i<=n)
那么总的SG值就是SG_1SG_2......^SG_n
接下来是一道板子题【HDU 1848】
一道裸的SG函数题
我们仅需预处理出
1000以内的SG函数即可
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define inf 0x7fffffff
#define N 500008
#define IL inline
#define M 1008611
#define D double
#define ull unsigned long long
#define R register
using namespace std;
templatevoid read(T &a)
{
T x=0,f=1;char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-')f=0;ch=getchar();
}
while(isdigit(ch))
{
x=(x<<1)+(x<<3)+ch-'0';ch=getchar();
}
a=f?x:-x;
}
/*-------------OI使我快乐-------------*/
int fib[N],SG[N];
bool ok[N];
int n,m,k;
int main()
{
fib[0]=fib[1]=1;
for(R int i=2;i<=20;++i) fib[i]=fib[i-1]+fib[i-2];
for(R int i=1;i<=1010;++i)
{
memset(ok,0,sizeof ok);
for(R int j=1;j<=20&&fib[j]<=i;++j)
ok[SG[i-fib[j]]]=1;
for(R int j=0;;++j) if(!ok[j]) {SG[i]=j;break;}
}
read(n);read(m);read(k);
while(n&&m&&k)
{
if(SG[n]^SG[m]^SG[k]) puts("Fibo");
else puts("Nacci");
read(n);read(m);read(k);
}
return 0;
}
四大经典博弈
【一位大佬的推荐】
\(n\%(m+1)==0\) ? 后手胜:先手胜
\(a_1\)$a_2$\(a_3\)......\(a_n==0\) ? 后手胜：先手胜
当前仅当\((x,y)(x
当且仅当\(n\)是斐波那契数字时先手必败
一些杂讲
Anti—Nim
Anti-Nim与普通Nim只有胜利条件不同
先手必胜:
1.每一堆石子都只有一个 且SG_tot==0
2.至少一堆石子多于一个 且 SG_tot!=0
具体的话我们还是看
Multi-SG游戏及其所对应的SG定理
这个游戏本身并不重要 但是它所对应的SG定理确实十分重要
阶梯Nim博弈
我也是比较懒了 所以还是直接上吧
无向图上的删边游戏
我也是比较懒了 所以还是直接上
Shannon开关游戏
这个好像需要一个叫做 拟阵 的东西
除了拟阵也不知道用啥了 网上介绍也是少的可怜
本蒟蒻太辣鸡辣
所以有兴趣的自己了解一下
【国家集训队论文 刘雨辰:对拟阵的初步研究】
上手练习
我就直接上题吧 也不兜兜转转了
总结
好了 博弈论也就是这些
一般博弈论的关键是模型的转换 或者是对SG函数的处理
例如大多数都可以同nim扯上边 而这又同相关证明以及数论息息相关
所以可以的话 最好还是了解一下证明以及这背后的知识
毕竟真正实战意义下的博弈论大多都是省选以上毒瘤级别了
然而这类题又不是可以随随便便就能打出暴力的至少本蒟蒻不可以
所以还是希望各位好好透彻一下
至此 博弈论end
鸣谢单位
【GXZlegend】
【自为风月马前卒dalao】
【来自洛谷上的博弈论dalao】