2008-02-26 22:53| 
13 Comments | 本文内容遵从 
有这样的一类组合游戏，对于任一个游戏局面，游戏双方的合法决策都完全一样，游戏对战双方的唯一区别就是看谁先走。这样的游戏叫做Impartial Games。像什么报数啊，取火柴啊，取石子啊，这些游戏都属于Impartial Games；而象棋、围棋等要分棋子颜色的游戏则不属于Impartial Games。共享状态的游戏几乎没有可玩性，因为游戏开始前我们就能知道谁赢谁输（如果双方均使用最佳策略）。棋局的任一状态只有两种，面对这个棋局的人要么必胜要么必败。考虑这样的一个递推关系：如果一个状态是必胜态，那至少有一种走法能走成一个必败态留给对方；如果一个状态是必败态，那它怎么走都只能走到必胜态。运用这样的关系，我们可以自底向上推出初始状态是必胜还是必败。
近来有人提出一个名为Atropos的游戏，它就是一个即使计算机也很难办的Impartial Game，它能保证这个游戏仍然具有可玩性。游戏在一个Sperner三角形上进行，上图就是一个边长为7的Sperner三角形。游戏开始后，双方依次在白色的圆圈里涂上红色、绿色或者蓝色，已经涂过颜色的圆圈不能再涂色。另外，只要有可能，所涂的圆圈都必须紧挨着上次对方涂的那个圆圈。谁先涂出三种颜色都有的小三角形，谁就输掉这场游戏。
注意这个游戏是不可能出现平局的。当所有白色圆圈全部涂上了颜色后，至少会出现一个红绿蓝小三角形。为了证明这一点，我们可以在所有的绿色和红色圆圈中间画一个箭头，红的在箭头右边，绿的在箭头左边。这些箭头一定组成了一条一条的路径，它们既不会交汇也不会分岔。但整个图的边界上进来的箭头有4个，出去的箭头只有3个，于是至少有一条路径在里面走死了，也即迎面碰上了蓝色的圆圈。这样，我们就找到了一个红绿蓝三色都有的小三角形。
这个游戏虽然属于Impartial Games，但它仍然具有可玩性。从直觉上看，这个游戏中的先手后手几乎没有区别，谁也不占优势。这篇论文则严格证明了，判断Atropos游戏的最佳策略属于PSPACE-complete，这是所有使用多项式空间的问题中最难的一类，所有使用多项式空间的问题都可以（在多项式的时间内）约化到它。这说明，Atropos游戏没有什么很显然的“决窍”，即使利用计算机也很难确定最优决策。
在线游戏：http://cs-people.bu.edu/paithan/spernerGame/SpernerGame.html (Java Applet)
查看更多：http://cs-people.bu.edu/paithan/spernerGame/
13 条回复
您也随便说几句吧：
sofa~~~~~~~~~
又一个~~~^_^~~~~
昨晚我杂没看见这贴呢?
奇怪,没坐到沙发.
游戏在一个Sperner三角形上进行，上图就是一个边长为7的Sperner三角形。
这种证明很有意思[razz]
Matrix67的思维杂练出来的?
在百度词典上查您的名字的中文翻译，是子宫67......
以前在一本数学课外书中看到围棋理论上来说先手是有必胜策略的，要不也不会有贴目这些规定
中国象棋有没有先手必胜的策略啊?
杂还不更新捏?
我还等沙发呢..一日看三回,看的花儿落...
烦躁,郁闷,焦虑,.........中[phone]也不响.
多么像五行棋呀！
”如果一个状态是必败态，那它怎么走都只能走到必胜态。“？
"从直觉上看，这个游戏中的先手后手几乎没有区别，谁也不占优势。"
从鄙人的直觉上看，被逼走最后一步的人一定会输，也就是说，两个人轮流下，那么在开局前通过估算让自己不走最后一步的人胜算要大些（具体大多少没有分析，可能是大很多，也可能是只占微弱优势，直觉哈），所以，在开局前力争拿到有利位置还是很重要的（就是尽量让自己走先手或者走后手。）
Orz地核的五行棋……（幻想游戏？）
这个一定有三个顶点不同色是一个经典的图论证明……
关于 impartial game ，应该不仅仅是合法走法完全一致，应该还有一点任何状态对博弈双方的回报也是相同的。有个 paper & pencil 游戏 paper soccer 就是双方的合法走法都是一样，但是双方的游戏目的不一样，应该不算 impartial game ，但是不知道这个游戏有没有必胜策略。