特立斯的终点是哪里

大家玩特立斯的时候，有没有想过一个问题，如果玩家有足够的牛B，就永远不能死。换句话说，假设你是一个邪恶的游戏机，你打算杀死你之前的玩家；在任何时机知道游戏的状态，可以准确地给玩家一个明显不合适的拦网，让玩家面对最坏的情况。那么，有没有杀死玩家或者保证玩家无论如何都有必胜策略的算法呢？

请注意，特立斯的游戏区域是一个宽10、高20的长方形，玩家可以提前看到下一个给定的方块是什么。在设计策略时，必须考虑这一点。

我相信很多人都经历过。玩特立斯的时候，开局的时候会给你一个“S”型的魔方，让完美主义者感到异常的不协调。毕竟，第二个街区是这个“S”，第三个街区仍然是“S”，相当崩溃。于是，我开始猜测，如果游戏机给了无限的“S”块，玩家可能就解不开啦。答案是否定的。如图1所示，从步骤10开始，只要整个局面循环，机器始终给予“S”块，玩家就可以重复这几个步骤，保证永远不死。

但是，这个周期发生在游戏会场变空的情况下。还有人会进一步思考，如果玩着玩着，看你形势不好，会不会突然给你好几个“S”方块。事实上，此时的局面循环如图2所示仍然可能存在。第五个“S”字型块掉到地面后，循环再次发生。

真的不能死吗？1988年，John Brzustowski的论文指出，泰特里斯游戏的无解不是不可能的。它提供了一种算法，让游戏机可以杀死玩家。即使事先要求玩家必须展示下一块的形状。结构的关键是游戏整体的棋局个数有限（2的200次方），玩家没有死的话，一定会在某个时刻重复某个状态。两次重复状态和其间的游戏过程称为“循环”，该循环实际影响的行称为“实循环区”。例如，图2是循环，该循环的“实际的循环区域”是从第4行到第7行的4行。

将宽度为10的游戏区域，从左向右用1到5的标签分割成宽度为2的5个“频道”。请注意，图1和图2这两个循环具有共同点。每个“S”块最终完全落在某个通道内。事实上，对于只有“S”四边形的循环，我们有这个结论。也就是说，如果游戏机一直给它一个“S”形的魔方，却用它们做了一个循环，那么所有的“S”形魔方的下落位置都可能没有越过通道（不像图3中的紫色魔方，而是绿色魔方）

为了证明这一点，汇总通道编号。命题P（x）表示，如果“S”的四边形（或其一部分）落在通道x的左侧，则它完全落在通道内。P（1、显然是成立的：块不能占据通道1左侧的格子，因为通道1左侧没有任何东西。接着，在P（n）为真的情况下，说明P（n+1、也是真的。

首先，必须证明，在循环中的任意时刻，在通道n的实际循环区域内绝对不可能出现两个排列的格子，例如“口■”。如图4.1所示，假设图中的星号片的行是通道n的实际循环区域内位置最低的“口■”结构。如果删除此行，则根据归纳假设，不存在哪个“S”块超出通道左边界的情况，因此只有一个可能是某个“S”块从左侧推入（图4.2、但是，这使得我们产生了更低的“口■”，自相矛盾。也就是说，星星的四边形行一直没有消失。但这也是不可能的。因为实际循环区内是新陈代谢，在旧换新的过程中，每一行最后都会被化解。

接着，考虑命题P（n+1、仅在图5的四种情况下，使通道n的格子占据“S”字形块。然而，先前已经证明通道n中不应存在“口■”，因此在该“S”形块下落之前，星形块已经存在。每个“S”立方体的下落导致“■口”结构减少，但在第一种情况下除外。为了避免“■口”结构的数量发生变化，在此基础上带来了新的东西。不能增加“■口”的个数。但是，通道n的“■口”形结构的个数应该是恒定的，因为它位于循环区域中。因此，只接受第一种情况。

因此，仅包含“S”块的循环仅在“S”块在每个通道内重叠，填充并清除几行并返回初始状态时可用。实际循环区内的每个通道，下面有0个以上的“■■”，上面有“■口”。注意，最右边的通道最上面是“■口”，右边的空白一辈子都不能用“Z”四角来填补。也就是说，在只包含“S”四角形的循环区域中，一定有一行，在其最右边是“■口”，保证该行不会仅仅消失在“Z”四角形上。如图6所示，星号位置不能用“Z”四边形填充，因此箭头所示的行不能用“Z”四边形删除。

然后给出一种游戏机杀人算法：1.持续给出“S”的四边形，表示下一个四边形也是“S”，在循环出现之前，给出2.“S”的四边形，下一个四边形显示为“Z”。3.继续给出“Z”的四边形，表示下一个四边形也是“Z”，在循环出现之前，给出“Z”的四边形，下一个四边形显示为“S”。跳回5.1重复。

这样的话，玩家为什么解不开呢。根据上述结论，在步骤1之后，游戏区域出现了不能用“Z”消除的行。填补星号空间的唯一办法就是插入“S”，因为很快就有了“Z”永远进不去的空位。然后，玩家得到一堆“Z”，最终一定会产生另一个循环该循环区位于刚才不可消除的行之上（循环区并不包含不可消除的行，如前所述，实际循环区的所有行最终都被消除，因此可以循环）此循环区最左侧的通道生成“口■”结构，该结构在“S”中无法消除。于是，游戏机又给了“S”一大堆，最终交替出现了直到游戏结束都无法消除的两种行。

值得注意的地方有两个。一、这里假设游戏机有主观能动性，但事实上，即使块是随机出现的，如果你够倒霉的话，这个特殊的块序列可能正好能把你猜好。虽然这类怪案的发生概率极低，但理论上仍有可能，所以特立斯最终不是不死，总有一天会游戏结束。二、这一结论可直接扩展到场地为任意宽度的泰特里斯博弈。当现场宽度为偶数时，上述证明同样有效。当场宽为奇数时，无限四边形立方可直接杀死玩家。