关于NIM博弈结论的证明
2024-10-07 07:15:33
关于NIM博弈结论的证明
NIM博弈:有k(k>=1)堆数量不一定的物品(石子或豆粒…)两人轮流取,每次只能从一堆中取若干数量(小于等于这堆物品的数量)的物品,判定胜负的条件就是,最后一次取得人即获胜(也就是说不能取得人失败)
假设这两个人A,B,并且有若干堆物品,A先手,那么A必胜,还是B必胜,必胜的策略是什么?
为了更容易的理解,现在考虑一种特殊情况,如果只有两堆物品,如果两堆物品相同的话,A先从一堆中取走x个物品,那么B只需要从另一堆中同样取走x个物品保证两堆物品的数量相同,那么这样就能保证B获得最后的胜利,这样就得到必胜的策略,保证每堆物品的数量是相同的。
这种2-堆的NIM博弈,也可以扩展到k-堆的NIM博弈中,任意一个数都可以表示成n个二进制的加和,例如 57=2^0+2^3+2^4+2^5,我们可以将这堆物品(57个)是有2^0个,2^3个,2^4个,2^5个这些子堆组成的,显然如果最后每种 子堆的数量是偶数,那么先手必败,如果是奇数那么先手必胜,这就是如果n堆物品的异或为零,那么每种 子堆的数量就是偶数,先手必败,如果不为零,那么每种 子堆的数量就是奇数,先手必胜,到此NIM博弈结论证明完毕。
最新文章
- 编码转换的处理 DreamWeaver SC6 打开会出现javacsript出现问题的处理
- Best Practices for Performance_1、2 memory、Tips 性能和小的优化点、 onTrimMemory
- Android notification的使用
- 相关css 细节处理 neat.css
- App_Code 引起的 ambiguously 问题
- RedHat/CentOS6.4---永久关闭iptables
- Swift属性
- java比.net优美的一个小地方
- discuz! X3.2 自定义后台门户模块模板里的标签
- poj 2417 Discrete Logging(A^x=B(mod c),普通baby_step)
- Java中的Runtime类
- Spring Boot 学习笔记
- Windows中通过命令行新建文件夹、新建文件,和一些常用命令
- python自学——文件处理(截取文件内容)
- WinPE无法识别NVMe SSD硬盘,如何重装系统
- Spark数据本地性
- underscore objects
- springboot-19-整合dubbox
- java web开发环境配置系列(一)安装JDK
- Jenkins使用jenkins-cli.jar进行远程调用时出现“ERROR: No such job 'test'”或者权限不够等问题解决(Windows)