如何搭建个人网站,做内容的网站,招个网站建设维护,柳州网站建设公司文章目录博弈论常见模型必胜点和必败点的概念#xff1a;必胜点和必败点的性质#xff1a;巴什博弈斐波那契博弈威佐夫博弈尼姆博弈SG函数与SG定理博弈论
博弈论 #xff0c;是经济学的一个分支#xff0c;主要研究具有竞争或对抗性质的对象#xff0c;在一定规则下产生的…
文章目录博弈论常见模型必胜点和必败点的概念必胜点和必败点的性质巴什博弈斐波那契博弈威佐夫博弈尼姆博弈SG函数与SG定理博弈论
博弈论 是经济学的一个分支主要研究具有竞争或对抗性质的对象在一定规则下产生的各种行为。博弈论考虑游戏中的个体的预测行为和实际行为并研究它们的优化策略。
通俗地讲博弈论主要研究的是在一个游戏中进行游戏的多位玩家的策略。
算法中常见的博弈论题目一般是公平组合游戏那么什么是公平组合游戏呢
公平组合游戏的定义如下
游戏有两个人参与二者轮流做出决策双方均知道游戏的完整信息
任意一个游戏者在某一确定状态可以作出的决策集合只与当前的状态有关而与游戏者无关
游戏中的同一个状态不可能多次抵达游戏以玩家无法行动为结束且游戏一定会在有限步后以非平局结束。
大部分的棋类游戏都 不是 公平组合游戏如国际象棋、中国象棋、围棋、五子棋等因为双方都不能使用对方的棋子。
常见模型
几种模型均存在奇异局面即双方均采取最优策略若处于奇异局面必败。
所谓奇异局面就是必败点。
必胜点和必败点的概念
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;
elsereturn second win;
斐波那契博弈
1堆石子有n个,两人轮流取.先取者第1次可以取任意多个但不能全部取完.以后每次取的石子数不能超过上次取子数的2倍。取完者胜.
结论当n为斐波那契数时先手必败。
分析见 https://blog.csdn.net/dgq8211/article/details/7602807
模板
void Init()//斐波那契数列先打表范围看情况
{f[0]f[1]1;for(int i2;i55;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;
elsereturn second win;威佐夫博弈
有两堆各若干个物品两个人轮流从任意一堆中取出至少一个或者同时从两堆中取出同样多的物品规定每次至少取一个至多不限最后取光者胜利。
结论若两堆物品的初始值为(x,y)则令z absy-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;elsereturn second win;尼姆博弈
有任意堆物品每堆物品的个数是任意的双方轮流从中取物品每一次只能从一堆物品中取部分或全部物品最少取一件取到最后一件物品的人获胜。
结论判断这几堆物品的异或运算结果是否为0如果为零则先手必败。
分析https://blog.csdn.net/Elliot_Alderson/article/details/84778775?utm_mediumdistribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.controldepth_1-utm_sourcedistribute.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;
elsereturn second win;台阶-Nim游戏
题目描述 现在有一个n级台阶的楼梯每级台阶上都有若干个石子其中第i级台阶上有ai个石子(i≥1)。两位玩家轮流操作每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中不能不拿。已经拿到地面上的石子不能再拿最后无法进行操作的人视为失败。问如果两人都采用最优策略先手是否必胜。
此时我们需要将奇数台阶看做一个经典的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;SG函数与SG定理
https://www.cnblogs.com/ECJTUACM-873284962/p/6921829.html
