欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

反Nim博弈

程序员文章站 2022-03-11 12:05:34
考虑怎么借用到nim博弈的结论,取最后的石头的获胜,那么所有个数异或不为0先手必胜。反nim博弈:最后取完的人输。考虑特殊情况:全为1的时候,奇数先手必败,偶数先手必胜。其余情况。将所有的石子堆数异或如果为1 那么只要有大于1的石子堆数必胜,因为我掌握了胜败态的主动权,也就是我能够控制最后一堆取完还是留1个给对面取前提是有大于1的石子堆。举栗:W:必胜 L:必败个数为1的堆数为偶 大于1的堆数异或不为0 先手必胜:先手拿大于1的堆数变L态,如果后手一直跟着取那么先手最后留一个,变奇数个...

考虑怎么借用到nim博弈的结论,取最后的石头的获胜,那么所有个数异或不为0先手必胜。

反nim博弈:最后取完的人输。
考虑特殊情况:全为1的时候,奇数先手必败,偶数先手必胜。
其余情况。
将所有的石子堆数异或如果为1 那么只要有大于1的石子堆数必胜,因为我掌握了胜败态的主动权,也就是我能够控制最后一堆取完还是留1个给对面取前提是有大于1的石子堆。

举栗:
W:必胜 L:必败
个数为1的堆数为偶 大于1的堆数异或不为0 先手必胜:
先手拿大于1的堆数变L态,如果后手一直跟着取那么先手最后留一个,变奇数个1,后手必败。但是有一种情况就是最后的堆就是1,需要排除这种情况,考虑当后手取得还剩1的时候,如果除这堆异或为0,那么先手拿走这堆,如果不是,那么我需要改变考虑奇异局势(1,2,3),这会儿后手取1,不行,取2(1,1,3),先手取为(1,1,1),奇数必败,后手取3(1,2,1),先手取2(1,1,1),nim博弈推广到一般情况, 后手造成了1的贡献,如果1这一位没有贡献,先手改为奇异局势其实没有改变最后1的贡献,如果1这一有贡献,那先手改为奇异局势一定删除了该1,其实最终1的个数还是为偶数,先手必胜。
如果后手取个数为1的,先手紧接的也取,个数为1的堆数还是为偶,最后还是留一个,后手败。
这种情况是先手必胜的。

如果个数为1的是奇数,其他大于1的堆数的异或值为为0,先手拿个数为1的堆,变偶数,剩余的为奇异局势,根据上面分析,先手必胜。
如果个数为1的是奇数,大于1的堆异或值不为0,那么先手取不改为奇异局势,如果后手改为奇异局势,那么先手拿个数为1的,让后手自己取奇异局势。如果后手也不改为奇异局势,那么先手只需要维持二进制最后一位异或的贡献为奇数,奇数+奇数为偶数,先手必胜。
口胡一下 严谨的具体数学符号推导不会
综上所由石子异或不为0,且有大于1的堆数,先手必胜。
特殊考虑全为1的。

本文地址:https://blog.csdn.net/weixin_43958964/article/details/108532114