有哪些两个人玩的推理性很强的游戏？
------------------------------2016年2月2日更新---------------------------------- 收到了一个私信，第一个游戏已经被这位童鞋做成 iOS 版本啦！ 这里是链接，大家可以去下载！ 简直不能更赞 -----------------------------------原答案-------------------------------------- 给大家转载一些比较有趣的数学游戏。 果壳网有篇文章叫《超高端桌游：一点一线烧糊你的大脑》，完美符合题主“两个人玩”和“推理性很强”这两个条件。 下面是文章内容： 三国杀越来越复杂了，不停地出扩展包，以至于我都不会玩了。其实在死理性派心中，简单中玩出大花样，那才叫高端。有些游戏，点几个点就能玩，虽然全程你也就连几条线，却绝不会感到丝毫无聊。这就是我们今天的主角——点线游戏，它可谓是居家旅行谈恋爱甚至搞基之必备。不过游戏有风险，玩者需谨慎，小心烧糊大脑。 这是一个双人对弈的游戏，道具很简单，纸和笔就行。规则也不复杂，首先游戏者要在纸上点出一些矩形点阵，如下图所示，矩阵的大小没有限制。 之后双方轮流选取两个相邻的点，用水平或者垂直的线段将它们连起来（每两点之间只能连一次）。如果某个 1×1 的小正方形（以下称为小方块）的 4 条边都被连上了，那补齐这个小方块的一方就获得 1 分（在这个封闭小方块里写一个代表玩家的字母表示得分），得分的玩家被奖励多走一步，再连一条线。在所有可连接的线都连完后游戏结束，得分高的一方获胜。如果共计有偶数个方块，最终双方得分相同，算后手的玩家赢。 对新手来说 3×3 的点阵比较合适，高手之间推荐玩 7×7 的点阵。不妨来看个简单的例子，上图其实就是 3×3 点阵的一个游戏过程：后手的人每次都做出与先手对称的操作，企图把点阵平分成两部分，两个人得到相同数量的方块，最后依靠后手取胜。然而在第 7 步时，先手者补齐了左上角那个方块的第三条边，做出了一个 让步 的操作。对方果断上钩，立刻放弃了对称操作，补齐了左上方块得到 1 分，但与此同时他必须再操作一次，连上一条新的线。在这条线的帮助下，先手的人在第 9 步连续补齐了 3 个方块，赢得了胜利。 到这里，你已经明白这其实是一款策略性很强的游戏。用什么样的策略才能让自己取胜？在回答之前，我们再来看一个例子。 假如面对 1 这种情况，你会怎么办？ 如果像 2 这样操作，把所有可以取得的 4 个方块都拿走，那么对方将拿走剩下的5个方块，于是你输了。 更高明的方法是像 3 这样，只取走 2 个方块，剩下 2 个留给对手。如果对手拿走你留下的 2 个，你就可以拿走剩下的5个。如果对手不拿留下的这 2 个，那你就能拿走所有方块，不管对手怎么操作都是你胜利。 这种“在所有可以取走的方块中留下 2 个，剩下的都取走”的策略叫做“双十字策略”。在详细说明双十字策略之前先介绍一个概念： 链 。在开始阶段，由于没什么限制，连线的选择基本是随机的，唯一要注意的是避免补上某个方块的第三条边。 一直持续这样操作就会使得所有剩下的方块变成一些链，也就是一些只补上了 2 条边、 连在一起的小方块， 它们会因为补上任何一条连线而让对手得到这条链里所有的小方块。 1 中就有一条长度为 4 的链和一条长度为 5 的链，而长度为 4 的那条链已经被操作过了。 要说的是，不管链中有多少个方块，双十字策略都可以使用。只要链足够长，链中方块的个数大于 2，在之前每个的链中舍去 2 个方块，而在最后一个链里拿走所有方块的策略总是可以赢。因此，两个高手较量时，焦点便是谁能让对手操作第一个长链（给这个长链的某个方块补第三条边）。对一个不懂让步意义的对手，高端玩家只需要做出足够的让步就能“捕获”他。如果对手知道让步所包含的阴谋，高玩则必须在游戏初始阶段控制对手可以做出的让步数量，迫使对方第一个操作长链。 为什么控制可以做出的让步数量就能迫使对方第一个操作长链？因为在游戏中没有理由不去接受一个让步。正如上面 3 的分析一样，如果不接受让步，对手可以很轻松地、没有任何损失地拿回这个让步（并最后获胜）。因此让步总是要接受的，真正要考虑的是接受让步后怎么办。因为对手总要接受让步，所以设计好巧妙的让步就能迫使对方操作第一个长链。 但双十字策略并非无敌。经验丰富的玩家可以通过游戏早期的操作将方块分割来避免这种利用链的策略。只要链的长度不够长，双十字策略就没有什么用武之地了。 当然，正方形点阵还是比较轻松的，如果你已厌倦在矩形，也可以试试在三角形和六边形的点阵里重新激活自己的大脑。 上面的方方正正你还能算的过来，下面这个光是数点你可能就乱套了。它叫做“Sprouts”。实际上，这个游戏的规则和上面一个同样简单，纸上随便点上几个点（但不要点太多，否则耗时太久）。双方轮流用一条线连接某两个点，或者从某个点开始画一个环连回自身，完成连线后再在这条线上加个点。操作过程中需注意以下事项： 让我们来看一个实际的例子。上图展示了有 2 个初始点的游戏过程。经过 4 步操作后，大多数的点都 死了 （已经连接了 3 条线），还剩两个绿色的点依然 活着 ，但根据游戏规则，这两个点再也不能“在一起”了。因此先手的人输了。这些在游戏结束后依然活着的点称为 幸存点 ，它们在游戏中的作用至关重要。 看起来游戏好像永不会停止，因为每一回合都新增加了一个点。但是当我们从 命 的角度来看的话，游戏就显然会停止了。 命指的是每个点还可以连接的线条数 ，比如说初始的点有 3 条命，上图中的红色点都只剩下 1 条命，死了的点（黑色点）就没有命了（废话）。对于每一步操作，连接 2 个点会消耗 2 条命，而新增 1 个点只会增加 1 条命，所以每次操作都会减少 1 条命。假设最开始有 n 个点，一共就有 3n 条命，当游戏一共只剩下一条命的时候（也就是连接了最后两个幸存点），游戏肯定结束了。也就是说，这个游戏在 3n-1 个操作之内必定结束。 既然可以在 3n-1 步内结束游戏，那可以算出这个游戏至少可以持续多久吗？可以，用类似的思路，我们可以分析出这个游戏至少可以持续 2n 步。分析前先介绍一个概念: Pharisee 。 当游戏结束时，每个幸存点（上图绿点）一定刚好有两个死掉的相邻点（上图黑点）。任何死掉的点都不可能与 2 个不同的幸存点相邻，否则将会有一个操作可以连接这 2 个幸存点。 那些与幸存点不相邻的死亡点称为Pharisee ，简称 P点 。 假设游戏有 n 个初始点， m 步之后游戏结束，游戏结束时有 p 个 P 点。就会有 n + m = 3n - m + 2（ 3n - m ） + p 怎么理解这个等式呢？先来解释一下各个小式子。 n+m ：每个操作会新增一个点，于是游戏结束时所有的点有 （n+m）个。 3n-m ：游戏结束时每个幸存点肯定都只剩下1 条命（若某个 1 个点有 2 条命，它至少可以做出连接到自己的操作，这时游戏未结束）。而从之前的分析我们又知道，游戏结束时一共剩下 3n - m 条命，所以游戏结束时幸存点的个数是 3n - m。 2（3n-m） ：每个幸存点与 2 个死亡点相邻，于是与幸存点相邻的死亡点的个数为2（3n-m）。 整个等式的意义就是 在游戏结束时所有的点 = 幸存点 + 与幸存点相邻的死亡点 + P点 将上式整理得到 m = 2n + p / 4 所以游戏结束时至少会进行 2n 步，而且 P 点的个数总是 4 的倍数。 游戏输赢取决于游戏进行了奇数步还是偶数步，而 p 点的数量决定了整个数字是奇是偶，所以实际上博弈的焦点就在于要创造 p 点还是避免 p 点被创造出来。其中一方会试图将幸存点包含在一个封闭的区域内，减少 P 点的个数，这将导致游戏结束的步数减少。而另一方会试图增加 P 点的个数，这又会导致游戏结束的步数增加。 其实这个游戏有四个很重要的特征： 因此这个游戏是一个组合游戏（Impartial Combinatorial Games，简称ICG）。组合游戏里有两个很重要概念： 必胜态 和 必败态 ： ●那些无法操作的状态都是必败态 ●可以移动到必败态的状态都是必胜态（因为当你面对这个状态时，你就可以将这个状态变成必败态交给对手） ●只能移动到必胜态的状态也都是必败态（因为你面对这个状态时怎么操作对方都会面对必胜态）。 只要局面不出现重复，我们就可以用倒推的方式计算出某个状态是必胜态还是必败态。所以，只要给定了 Sprouts 游戏的初始点数，就必定存在一个完美策略使得先手必胜或者必败。这个完美策略可以通过博弈树（用来描述必胜必败态之间的转移）来找到。但是 Sprouts 游戏只有在点数很少的时候才能手动计算博弈树（不信的话你试看看）。 在 1982 年出版的一本叫 《Winning Ways for your Mathematical Plays》 的书中有人用了47页纸来证明初有 6 个初始点的 Sprouts 游戏是必胜的。直到 1990 年，卡内基•麦隆大学的 David Applegate 、 Guy Jacobson 和 Daniel Sleator才使用当时最好的计算机将必胜必败的证明发展到了 11 个点。 3 人通过观察，猜想当初始点个数除以 6 的余数是 3、 4、 5 时先手是必胜的。 后来到 2011 年，这个证明终于推进到了 44 个点，另外初始点数为 46,47,53 的结果也已经证明。到目前为止所计算出来的结果均符合上面的猜想。 不过既然用计算机计算必胜必败态都这么麻烦，那在实际游戏中就不用担心某一方知道必胜策略而导致游戏不平衡了。点上6个点，开动你的脑筋吧！ 主要参考资料： [1] 维基百科： Dots and Boxes [2] 维基百科： Sprouts (game) 本文版权属于果壳网（guokr.com），转载请注明出处。商业使用请联系果壳 Matrix67大神也推荐过不少两个人玩的很有意思的数学游戏。 我最喜欢的是这个： 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）。 有没有什么图形能够让先走者必胜，不管先走者是谁呢？当然有。我们只需要把刚才的图形中任意一处线条扭一下，得到的新图形就满足要求了。先走的人就先把这里进行细化，整个图形就退化成了原来的图，先走的人此时也就成为了后行者，便能套用刚才的必胜策略了。 当然，也存在这样的初始局面，使得必胜者并不是由先行后行直接决定的，还要具体看先行者是谁后行者是谁。这里就不再举例了。有没有什么更有意思的初始局面？判断必胜方有什么简便方法吗？能否迅速找出必胜策略呢？似乎目前都还没有什么漂亮的答案。 原文链接：