最难的组合游戏:To Knot or Not to Knot

标签: 趣题 Brain Storm 博弈 游戏 拓扑学 | 发表时间:2011-08-25 02:55 | 作者:Matrix67 loudly
出处:http://www.matrix67.com/blog

    A Midsummer Knot’s Dream 简直可以说是去年学术界的一篇奇文,大家点进去看看就知道了。论文里讲了一个基于纽结理论的双人对弈游戏,名字也非常有艺术感: To Knot or Not to Knot 。这个游戏可能是最难的组合游戏了,它的数学性极强,思考难度非常大,甚至比 ERGO 更不容易上手。一场游戏下来,究竟谁赢谁输可能都不好判断。

    To Knot or Not to Knot 的游戏规则非常简单。用铅笔在纸上画一个封闭的、可以自相交的回路,然后 A 、 B 两人轮流在图形中选取一个尚未被处理过的交叉点,并用橡皮擦对图形进行“细化”,明确两根线条的位置关系(可以抛掷硬币决定谁先行动)。A 的目的是要让最终的图形变成一个结,而 B 的目的则是避免图形打结。下面是其中一种可能的游戏过程,双方约定 B 先走。两人轮流对交叉点进行细化,七步之后,整个图形并未打结(你能看出来吗), B 获得胜利。

      

    注意,这是一个决策透明、信息公开的游戏,并且游戏不可能有平局产生。因此,即使双方都使出最佳策略,也必然有一个人会赢有一个人会输。也就是说,任意给定一个初始状态,总有一方有必胜的策略。不过,难就难在,究竟谁有必胜策略,必胜策略是什么,这并不容易判断。让我们来做一个练习题吧:下面的图形中,如果 A 先走,B 后走,谁有必胜策略?如果 B 先走,A 后走呢?记住,A 的任务是要让最终的图形打成结,而 B 的任务则是避免图形打结。

      


 
 
 
 
 
 
 
 
 
 
 
 
 
 
      

    答案是,两种情况下,后走的人都是必胜的。为了便于叙述,我们用 a 、 b 、 c 、 d 、 e 、 f 来标记图中的六个交叉点。对于两根线条连续两次相交的地方,最终只可能是右图所示的 I 、 II 、 III 、 IV 四种情形之一。我们把前两种情形叫做“假交叉”,把后两种情形叫做“真交叉”。

    注意到,如果 B 能把 (e, f) 变成假交叉,那么不管下面四个交叉点是什么样,整个图形必然不打结。因此,如果 B 是后走的,那么 B 一定可以获胜:一旦 A 动了 e 、 f 中的一个交叉点,那么 B 立即细化另一个交叉点,让它成为假交叉;否则, B 就陪着 A 在下面四个交叉点中玩。但是,下面只有四个交叉点,是一个偶数,因而最终 A 将被迫对 e 或者 f 进行细化,从而宣告 B 的胜利。

 
      

    如果 A 是后走的人呢? A 也将必胜。 A 可以把六个交叉点分成 (a, b) 、 (c, d) 、 (e, f) 三组,然后 B 细化了哪一个交叉点, A 也就跟着修改同组的另一个交叉点,从而决定每组交叉点的交叉类型。 A 可以把 (e, f) 变成真交叉,把 (a, b) 和 (c, d) 当中的一个也变成真交叉,另一个变成假交叉,这便能保证让整个图形打结(如图 1)。需要注意的是,把下面两组交叉变成一真一假,这是必需的。如果下面两组都是假交叉,得到的图形仍然不算打结(如图 2);而如果下面两组都是真交叉的话,最终的图形也不见得就一定是一个结(如图 3)。

 
    有没有什么图形能够让先走者必胜,不管先走者是谁呢?当然有。我们只需要把刚才的图形中任意一处线条扭一下,得到的新图形就满足要求了。先走的人就先把这里进行细化,整个图形就退化成了原来的图,先走的人此时也就成为了后行者,便能套用刚才的必胜策略了。

      

    当然,也存在这样的初始局面,使得必胜者并不是由先行后行直接决定的,还要具体看先行者是谁后行者是谁。这里就不再举例了。有没有什么更有意思的初始局面?判断必胜方有什么简便方法吗?能否迅速找出必胜策略呢?似乎目前都还没有一个漂亮的答案。

相关 [组合 游戏 to] 推荐:

最难的组合游戏:To Knot or Not to Knot

- loudly - Matrix67: My Blog
    A Midsummer Knot’s Dream 简直可以说是去年学术界的一篇奇文,大家点进去看看就知道了. 论文里讲了一个基于纽结理论的双人对弈游戏,名字也非常有艺术感: To Knot or Not to Knot. 这个游戏可能是最难的组合游戏了,它的数学性极强,思考难度非常大,甚至比 ERGO 更不容易上手.

游戏指南

- Blacat - 韩寒
这是一个复杂的国度,人们并不是那么渴望文人范畴里的自由,如果你上街问问,大家都觉得自己过的挺自由. 人们已经习惯了在台上台下的两种话语,你只要不冲进他......>>点击查看新浪博客原文.

游戏开发商开源HTML5游戏

- - Solidot
游戏工作室Wooga开源了其开发的HTML5游戏Pocket Island,源代码托管在GitHub上,该公司在官方博客上介绍了他们的开发经验,认为HTML5游戏有潜力,但尚未做好准备,开源的意图将是让其他人了解他们的工作,学习和改进. Wooga认为,2012年也许不是HTML5的黄金时代,但它的黄金时代即将到来.

JS游戏引擎

- 米随随 - HTML5研究小组
If you don’t have anything better to do and want to help fellow redditors interested in JS game dev out, feel free to fork the list and modify it as you like.

Google+加入游戏

- Thomas - Solidot
Google宣布了Games in Google+,为旗下社交网站引入了游戏功能,Google+正从类似Twitter的信息交流平台变得更像是其竞争对手Facebook. 游戏暂时还没有对所有用户开放,但Google承诺会在不久以后让每一位Google+用户都能玩上游戏. 目前提供的游戏包括了愤怒的小鸟,数独,Bejeweled Blitz等.

我的iPad游戏

- Aim - Aether
说是以办公和看书为主,实际上从使用时间来看也是这样,但是不知不觉还是买了一屏的游戏(整个桌面也才三屏而已),这还不包括随时删掉的无数没啥意思的游戏. 晒一下清单,有兴趣的同学可以拿去. 支持多人对战基本都属于必买的游戏. 和iPhone、Touch,以及电脑上的多人联机游戏不一样的是,iPad的大屏幕和多点触摸允许多达四个人在一个iPad上面对面的游戏,这种体验和任何网络游戏只能面对冰冷屏幕的感觉是完全不一样的.

体感游戏合家欢

- Duo - 南都周刊-热点新闻
就像当初满腔豪情买下后最终被落满尘的跑步机健身器材一样,Wii在很多人家里也陆续步入 “偶尔想起来玩儿一下”“现在基本没碰”的阶段. 美国艺电(EA)总裁John Riccitiello认为未来体感游戏的发展应该建立在一个“更加细分的市场”上. 打打Wii还能稍微让身体动一下. 任晓米,24岁,游戏年龄:4年.

spy++和游戏修改器

- 大宝PKU - C++博客-首页原创精华区
这几天做了两个东西,spy++ 和游戏修改器. spy++ 就是模仿 vs的那个工具spy++. 游戏修改器,就是暴力搜索内存,找到我们关心的数据,然后进行更改. 总之这些东西做过之后感觉就是都不难,但是在做的时候多少会感觉点吃力. 闲下来无事,记录下它们的过程吧. spy++ 分析(用vs2005做的——).

与月亮一起游戏

- mechelle.04 - 碌碡画报