Rexdf

The devil is in the Details.

俄罗斯方块可以永远的玩下去吗?

| Comments

大家在玩俄罗斯方块的时候有没有想过这样一个问题:如果玩家足够牛B的话,是不是永远也不可能玩死?换句话说,假设你是万恶的游戏机,你打算害死你面前的玩家;你知道任意时刻游戏的状态,并可以有针对性地给出一些明显不合适的方块,尽量迫使玩家面对最坏情况。那么,你有没有一种算法能保证害死玩家,或者玩家无论如何都存在一种必胜策略呢? 俄罗斯方块的游戏区域是一个宽为10,高为20的矩形,并且玩家可以预先看到下一个给出的方块是什么。在设计策略时,你必需考虑到这一点。 相信很多人有过这样的经历:玩俄罗斯方块时一开局就给你一个“S”型方块,让完美主义者感 到异常别扭;结果,第二个方块还是这个“S”,第三个方块依旧 是“S”,相当令人崩溃。于是,我们开始猜测,如果游戏机给你无穷个“S”形方块,玩家是不是就没有解了?答案是否定的。如图1,从第10步开始,整个局 面产生一个循环;只要机器给的一直都是“S”方块,玩家可以不断重复这几个步骤,保证永远也死不了。 个循环是在游戏场地清空了的情况下才产生的。有人会进一步想了,要是在玩着玩着,看着你局势不好时突然给你无穷多个“S”方块呢?事实上,此时局面的循环依然可能存在,如图2。在第5个“S”形方块落地后,循环再次产生。 俄罗斯方块真的不可能玩死吗?1988年,John Brzustowski的一篇论文指出,俄罗斯方块游戏无解并非不可能。它给出了一种算法可以保证游戏 机能够害死玩家,即使我们要求它必须提前向玩家展示出下一个方块的形状。构造的关键在于,整个游戏的局面个数是有限的(2的200次方),如果玩家一直不 死,在某一时刻必然会重复某一状态。我们把两次重复状态及其之间的游戏过程叫做一个“循环”,这个循环实际影响到的那些行就叫做“实际循环区”。例如,图 2就是一个循环,这个循环的“实际循环区”是从第4行到第7行这四行。 我们把宽为10的游戏区域划分为5个宽为2的“通道”,从左至右用1到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)。要想让“S”形方块占据通道n的格子,只有图5这四种情况。但是,由于我们之前证明了通道n中不能存在“口”,因此在 这个“S”形方块落下之前,星号方块都是已经有了的了。注意到,每一个“S”形方块的下落都致使“口”形结构的减少,但第一种情形除外——它消除了一个 “口”形结构,但在其上方带来了一个新的,使得“口”形结构个数保持不变。没有哪种情形能够增加“口”的个数。但是,通道n的“口”形结构个数应 该是恒定的,因为它在一个循环区里。因此,只有第一种情况才能够被接受。 仅含有“S”形方块的循环只有一种情况——“S” 形方块在各个通道内重叠,填满并消除若干行后回到初始状态。实际循环区内的每个通道都是一个模样:底下是0个或多个“”,顶部一个“口”。注意,最 右侧那个通道的最顶端是一个“口”,右边这个空白一辈子也不可能用“Z”形方块填上。也就是说,在一个只含“S”形方块的循环区内,必然会有某一行,它 的最右侧是一个“口”,它保证了该行不能仅用“Z”形方块消掉。如图6所示,箭头所指的行无法单用“Z”形方块消除,因为星号位置不可能用“Z”形方块 填充。 下面我们给出游戏机害死人的算法: 1. 不断给出“S”形方块并显示下一个方块也为“S”,直到出现一个循环; 2. 给一个“S”形方块并显示下一个方块为“Z”; 3. 不断给出“Z”形方块并显示下一个方块也为“Z”,直到出现一个循环; 4. 给一个“Z”形方块并显示下一个方块为“S”;

Comments