博弈论讲解（二）

文章目录斐波那契博弈问题：结论证明：尼姆博奕(Nimm Game)问题：结论：证明：代码：公平组合博弈（Impartial Combinatori Games）
理论知识
（1）、若面临末状态者为获胜则末状态为胜态否则末状态为必败态。
（2）、一个局面是胜态的充要条件是该局面进行某种决策后会成为必败态。
（3）、一个局面是必败态的充要条件是该局面无论进行何种决策均会成为胜态 斐波那契博弈 问题：

有一堆数量为n的石子，游戏双方轮流取石子，满足：

（1）先手不能在第一次把所有的石子取完；

（2）之后每次可以取的石子数介于1到对手刚取的石子数的2倍之间（包含1和对手刚取的石子数的2倍）。

约定取走最后一个石子的人为赢家。
求必败态

结论

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

证明：

齐肯多夫(zeckendorf)定理：
任何正整数都可以表示成若干个不连续的斐波那契数(不包括第一个斐波那契数)之和
比如n=54，
n还可以写成：n=2+5+13+34
先手A取两个，后手B取的范围是1~4，也就是5之后取不了，那第五个肯定被A拿了（因为至少拿一个），也就是拿走了5的最后一颗，接下来，A也能拿走13的最后一颗，拿走34的最后一颗，这样A就赢了。
反之如果n是斐波那契数，A就输了

尼姆博奕(Nimm Game) 问题：

有三堆各若干个物品，数量分别是（a,b,c），两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限，最后取光者得胜。

结论：

如果每堆物品数全部异或起来，得到的值时0则先手必败，反之先手则赢

(a,b,c)的必败态等于a ^ b ^ c =0

如果石头有n堆，如果每堆数目进行异或后为0，则是必败态

证明：

略。。

代码： for(int i=1;i>ans; sum^=ans; } if(sum==0) cout<<"后手必胜"<<endl; else cout<<"先手必胜"<<endl; 公平组合博弈（Impartial Combinatori Games）

这个第一次见，还没搞懂

Jozky86 原创文章 87获赞 4访问量 1298 关注 私信 展开阅读全文
作者：Jozky86

博弈 博弈论