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

2011 年 8 月 25 日 / 33 条评论

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 的任务则是避免图形打结。

超级游戏悖论：千万别说“让我们来玩一个游戏”

2011 年 2 月 4 日 / 42 条评论

今天听说了一个非常有趣的思想实验——超级游戏（ Hypergame ，暂且让我翻译成“超级游戏”吧）。首先，如果一个游戏能在有限步之内分出胜负，我们就把它叫做“有限游戏”。注意，一个有无穷多种状态的游戏也可以是有限游戏。虽然每一步的决策无穷多，但只要能在有限步内结束游戏，我们都把它叫做有限游戏。举个例子，玩家 1 和玩家 2 游戏，玩家 1 说出任意一个正整数 N ，然后立即获胜。这个游戏的决策有无穷多，但它显然是有限游戏。另外，一个有限游戏的总步数甚至也可以没有上限。比如说，玩家 1 说出任意一个正整数 N ，然后玩家 2 说 N – 1 ，玩家 1 说 N – 2 ，以此类推，两人轮流倒数，谁数到 0 谁就获胜。结束这个游戏所需要的步数可以是任意多，但只要是有限的，我们都把它叫做有限游戏。

下面，我们来看这个叫做“超级游戏”的游戏。在超级游戏中，首先，玩家 1 指定一个有限游戏，然后玩家 2 作为这个有限游戏的先行者与玩家 1 对弈。谁赢得了这个有限游戏，也就是这局超级游戏的获胜者。

这个异想天开的游戏可以说是一下子打开了我们的思路，很多再正常不过的事情此时都变得有争议了。比如说，超级游戏的决策树是什么样子的？超级游戏算是组合游戏吗？甚至是问，超级游戏本身是一个有限游戏吗？

There is always a bigger fish

2010 年 11 月 3 日 / 43 条评论

Always A Bigger Fish 不但是电影情节中的经典桥段，也是各种恶搞的灵感来源——小鱼总是被大鱼吃掉，而大鱼上面总还有更大的鱼。久而久之，聪明的大鱼或许就不会去吃小鱼了，否则按照传统剧情，它身后会出现一条更大的鱼。一个有趣的问题出现了：倘若所有的鱼都是理性的，那会出现怎样的情况呢？
让我们把问题重新叙述一下。假设有 n 条鱼，它们从小到大依次编号为 1, 2, …, n 。我们规定，吃鱼必须要严格按顺序执行。也就是说，大鱼只能吃比自己小一级的鱼，不能越级吃更小的鱼；并且只有等到第 i 条鱼吃了第 i – 1 条鱼后，第 i + 1 条鱼才能吃第 i 条鱼。第 1 条鱼则啥都不能吃，只有被吃的份儿。我们假设，如果有小鱼吃的话，大鱼肯定不会放过；但是，保全性命的优先级显然更高，在吃小鱼之前，大鱼得先保证自己不会被吃掉才行。假设每条鱼都是无限聪明的（并且它们也都知道这一点，并且它们也都知道它们知道这一点⋯⋯），那么第 1 条鱼能存活下来吗？

《新知客》趣题专栏 2010.08

2010 年 8 月 16 日 / 34 条评论

目前，我正在《新知客》杂志上主持一个趣题栏目。每月杂志发行后，我将在 Blog 上同步更新。点击这里可以查看往期题目。

推理
1. 下一个图形是什么？

2. 小 A 和小 B 玩游戏。小 A 取出一副扑克牌并去掉大小王，剩下红色的牌和黑色的牌各 26 张。洗好牌后，小 A 依次翻开每一张牌，让小 B 看到牌的颜色。小 B 可以在任意时刻打断小 A ，并打赌“下一张牌是红色”。如果下一张牌真是红色，小 A 给小 B 一块钱；如果下一张牌是黑色的，小 B 输给小 A 一块钱。注意，小 B 必须要在某个时刻下赌注，并且机会只有一次；如果他一直没打断小 A ，则默认他赌最后一张牌是红色。
小 B 的最佳策略是什么？在这种策略下，他有多大的概率获胜？

瓶魔悖论与不完全信息

2010 年 1 月 11 日 / 49 条评论

    The Bottle Imp 是一则有意思的短篇小说。某日，小说里的主人公遇上了一个怪老头。怪老头拿出一个瓶子，说你可以买走这个瓶子，瓶子里的妖怪就能满足你的各种愿望；但同时，持有这个瓶子会让你死后入地狱永受炼狱之苦，唯一的解法就是把这个瓶子以一个更低的价格卖给别人。如果你是小说里的主人公，你会不会买下这个瓶子呢？你会以什么价格买下这个瓶子呢？
    以什么价格买入这个瓶子，这个问题貌似并不容易回答。你当然不愿意花太多的钱，在你的愿望被满足之前你至少还得给自己留一点钱花；但你也不能花太少的钱，否则你会承担着卖不出去的风险。但是，在做出一些理性的分析后，我们得出了一个惊人的结论：任何人都不应该以任何价格购买这个瓶子。
    和很多博弈问题一样，这一系列的分析首先从最简单的情形开始。首先，你是绝对不能只出 1 分钱就买下这个瓶子的，因为这样的话这个瓶子就永远也卖不出去了——没有比 1 分钱更低的金额了。那么，用 2 分钱买瓶子呢？这样理论上貌似是可行的，但仔细一推敲你会发现还是有问题——这样你只能以 1 分钱卖掉这个瓶子，但没有人会愿意用 1 分钱去买瓶子（否则他就卖不掉了）。因此，用 2 分钱买下瓶子后，你同样找不到下一个买家。和上面的推理一样，用 3 分钱买这个瓶子也不是什么好主意，因为没有人愿意以 1 分钱或 2 分钱购入瓶子，因此你的瓶子不可能卖得掉。依此类推，你不应该以任何价钱去购买这个瓶子，因为每个人都知道，他无法以任何价格卖掉这个瓶子。