ICG游戏:证明,先手不是必胜就是必败。
简介:
ICG游戏:Impartial Combinatorial Games,公平的组合游戏。
以下是定义,来自网络,可能不够严谨:
1、两名选手;
2、两名选手轮流行动,每一次行动可以在有限合法操作集合中选择一个;
3、游戏的任何一种可能的局面(position),合法操作集合只取决于这个局面本身;局面的改变称为“移动”(move)。
4、若轮到某位选手时,该选手的合法操作集合为空,则这名选手判负。
必胜和必败,指如果若按规定且可行的方法走,则必定胜利;必败,指无论怎么走必定失败。某些资料称为奇异非奇异态,PN态,等差不多。
来源:
写这篇文章,主要是源于巧克力游戏的证明(Strategy-stealing):
有个n*m的矩阵(巧克力块),两人轮流取一个点;每次取完后,需要把其右上方所有巧克力都吃了;吃到最左下方的输。先手是否必胜?
有证明如下:
如果后手存在必胜,则只要先手第一次取最右上方的,后手取的必包含最右上方的,那先手其实第一次就可以取后手取的那个。
即后手第二步走的,先手都可以在第一步就走。由此证明后手不存在必胜,先手必胜。
补充证明:
刚看到证明,觉得只是证明了后手不存在必胜,并不能说明先手必胜。
如果加上一个条件即可:在ICG游戏中,先手不是必胜就是必败,后手同理。
证明:
双方互相决策,有限步骤,可以用树来描述,树的叶子节点是胜或者败;
由于双方都是足够聪明,所以,如果某个叶子是胜,则其父节点也是胜,因为父节点必定会选择胜利的途径;如果某子树叶子全是败,则其父节点也是败;
一直往上递推,则最后,推到根节点有若干个叶子,如果有胜节点则根节点胜;如果全是败则根节点败;
则证明,先手不是必胜就是必败。
梳理:
回到刚才的反证法,梳理下:
后手有必胜=>先手必败=>推出矛盾。则先手不是必败,又由上面证明得知先手不是必胜就是必败,所以先手必胜。
扩展:
对于这种多走一步一定不是坏事,且决策对策的游戏(可能是非ICG),都可以用类似的方法证明后手没有必胜策略。但这不代表先手有。
最新文章
- 《Entity Framework 6 Recipes》中文翻译系列 (8) -----第二章 实体数据建模基础之继承关系映射TPT
- [C#6] 6-表达式形式的成员函数
- MAC破解软件
- cannot find module 'xml2js'
- WPF 程序Form自的控件自适应方式之一
- redis.conf 配置详解 (转)
- Matplotlib中文设置
- 在windows C++中编译并使用Lua脚本
- javascript的基础(1)
- javascript之prototype原型属性案例
- Linux启动流程和脚本服务-6
- C++ string中的find()函数
- Little Red Riding Hood
- redis 哨兵模式 Connection refused
- DataFrame按行读取:DataFrame之values
- Leetcode题库——26.删除排序数组中的重复项
- git中如何查看一个文件的修改(更新)历史
- jquery翻页
- nyoj117——树状数组升级版(树状数组+离散化)
- 【leetcode】371. Sum of Two Integers
热门文章
- UE4 游戏中csv配置文件使用
- word 使用中 上标符号的实现
- Linux环境编程之同步(四):Posix信号量
- 大数据之 ZooKeeper原理及其在Hadoop和HBase中的应用
- python zfill方法给字符串前面补0
- IntelliJ IDEA、JetBrains PyCharm 注册码-收藏
- AHK按键转载
- Java 中的包装类
- mysql5.7.12/13在安装新实例时报错:InnoDB: auto-extending data file ./ibdata1 is of a different size 640 pages (rounded down to MB) than specified in the .cnf file: initial 768 pages, max 0 (relevant if non-zero
- 1027代码审计平台 1-sonar scanner