俄罗斯方块可以永无止境的玩下去吗？

huangqinfeifei

叫我feifei吧http://t.qq.com/huangqinfeifei

1楼大中小发表于 2009-7-12 19:14 只看该作者

俄罗斯方块可以永无止境的玩下去吗？

答案是不可以。

大家在玩俄罗斯方块的时候有没有想过这样一个问题：如果玩家足够牛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”；  

5\. 跳回1并重复执行。

这样的话，玩家为什么会无解呢？由上面的结论，在第1步后，游戏区域中出现了一个不能用“Z”消除的行。即使再给你一个“S”形方块，这一点仍然无法挽救，因为填充星号空格的唯一途径就是插一个“S”进去，但这立即又产生了一个“Z”永远放不进去的空位。然后，玩家就拿到了一大堆“Z”，最终必然会产生另一个循环，且这个循环区在刚才那个无法消去的行之上（循环区不可能包含一个不能消除的行，因为正如前面所说，一个实际循环区的所有行最终都是会被消掉的，这样才可能循环）。这个循环区的最左边那个通道将会产生一个“□■”结构，是“S”所不能消去的。于是，游戏机又给出一大堆的“S”，最终使得两种无法消去的行交替出现，直至Game

Over。

有两点值得注意。一、虽然我们这里假设游戏机是有主观能动性的，但事实上呢，即使方块是随机出的，如果你足够倒霉的话，这个特殊的方块序列恰好就让你一个不错地碰上了；虽然这种怪事的发生概率极低，但理论上说仍然是可能的，因此俄罗斯方块终究不是玩不死的，总有一个时候会Game Over。二、这个结论可以直接扩展到场地为任意宽度的俄罗斯方块游戏。当场地宽为偶数时，上述证明同样有效；当场地宽为奇数时，无穷多个方形方块就可以直接干掉玩家。  

Terminusbot 整理，讨论请前往 2049bbs.xyz

藏獒兄

狼牙山五壮士要多壮有多壮 @wang2

2楼大中小发表于 2009-7-12 20:14 只看该作者

喔！

老李飞镖

3楼大中小发表于 2009-7-12 20:27 只看该作者

好文章。。。

Auo

一脸迷惘

4楼大中小发表于 2009-7-12 20:33 只看该作者

我玩死的情况主要是想垒那种很高的一个竖杠全消的大方块结果一致不出竖杠 ….

numberscis

收二手或库存的老钢笔、蘸水笔。免费维修钢笔，免费调校、打磨笔尖。尊重世界上所有以匠人性格工作和治学的民族，毋论是日耳曼还是和族。

5楼大中小发表于 2009-7-12 21:46 只看该作者

虽然死机发生的概率极低，但理论上说仍然是可能的…..

Yahoo!

syriana

FREE TALK 組長 1st Gen / 隱於市朝 • 與84諸兄相望江湖

6楼大中小发表于 2009-7-14 01:58 只看该作者

引用:

原帖由 Auo 于 2009-7-12 20:33 发表

我玩死的情况主要是想垒那种很高的一个竖杠全消的大方块结果一致不出竖杠 ….

跟我差不多，我每垒一排就留最后一竖行，然后等一个长条来，一消消好多。。。

huangqinfeifei

叫我feifei吧http://t.qq.com/huangqinfeifei

7楼大中小发表于 2009-7-14 14:04 只看该作者

回复 4楼 Auo 的话题

这是俄罗斯方块的基本定律

[17]堂吉柯德

Frake集团的牛三少爷，诸神国驻人间特派员，人类行为分析者

8楼大中小发表于 2009-7-16 00:15 只看该作者

我基本通关，除了实在不想玩的时候

username

在这金色的大门旁, 我要为他们把灯举起

9楼大中小发表于 2009-7-16 15:20 只看该作者

转了

恕我冒昧请问是否原创？

huangqinfeifei

叫我feifei吧http://t.qq.com/huangqinfeifei

10楼大中小发表于 2009-7-16 17:54 只看该作者

回复 9楼 username 的话题

不是

核子力量

Twitter.com/hzpower

11楼大中小发表于 2009-7-17 18:07 只看该作者

很深奥的样子

我爱玛丽

Twitter: @BenMQ

12楼大中小发表于 2009-7-18 20:34 只看该作者

LZ不厚道。转帖不写出处…… matrix67.com

左岸←右岸

把你的子宫钉到我的墙上，这样我便会记得你。我们必须走了。明天，明天…

13楼大中小发表于 2009-7-18 21:18 只看该作者

媽的又來接受貧下中農再教育鳥

水若吟

14楼大中小发表于 2009-7-18 21:32 只看该作者

没看懂……不过以前经常玩这个，用黑白的手掌机……怀念啊

Cre∫endo

15楼大中小发表于 2009-7-19 12:19 只看该作者

其实不按暂停的话，没人能够坚持等到机器来害你的……

不过作为不折腾不舒服的一部分，是要研究一下这样的程序-_-b

火疖子

友爱部101房小卒癸

16楼大中小发表于 2009-7-19 19:44 只看该作者

电池早没电了

玉古台

17楼大中小发表于 2009-7-20 21:33 只看该作者

很深奥，不看了。

拳击手

18楼大中小发表于 2009-7-20 21:40 只看该作者

只看结论

大菜

19楼大中小发表于 2009-7-20 22:29 只看该作者

等一竖条

我也喜欢叠很高然后用一竖条把他统统消光。。。。＝＝＃＃这样有成就感。。。糊糊

louy0427

送外卖的……

20楼大中小发表于 2009-7-22 12:02 只看该作者

专业……我喜欢一开始就把速度调到最快。

piero2007

21楼大中小发表于 2009-7-22 22:26 只看该作者

太牛了

技术贴留名

WJ87

无产阶级煽动家

22楼大中小发表于 2009-7-29 12:59 只看该作者

S与Z型之间可以相互转换的吧，难道这篇文章所使用的是不同版本

[ 本帖最后由 WJ87 于 2009-7-29 13:03 编辑 ]

无穷无尽

23楼大中小发表于 2009-8-13 13:39 只看该作者

哦，这个可没想过

废种豆豉

死胎 @vanlulnav http://www.bullock.cn/blogs/vanlulnav/

24楼大中小发表于 2009-8-13 14:56 只看该作者

棗糕….還以為政壇的俄羅斯政策方塊可以無止境無法無天的玩下去給中國學習的好榜樣的以為….原來真是俄羅斯方….塊

废种豆豉

死胎 @vanlulnav http://www.bullock.cn/blogs/vanlulnav/

25楼大中小发表于 2009-8-13 14:58 只看该作者

回复 23楼 WJ87 的话题

s和z都有左右即系四種狀況即便轉換了不對合還是玩死

黯歆

发一贴5毛，请管理员主动联系付帐。

26楼大中小发表于 2009-8-17 17:53 只看该作者

你丫也不累？何必呢……

大杨树

27楼大中小发表于 2009-8-18 13:39 只看该作者

引用:

原帖由 Auo 于 2009-7-12 20:33 发表

我玩死的情况主要是想垒那种很高的一个竖杠全消的大方块结果一致不出竖杠 ….

這種情況我一般稱之為：條一色，單吊幺雞

Pilz

28楼大中小发表于 2009-8-22 20:48 只看该作者

引用:

原帖由大杨树于 2009-8-18 13:39 发表

這種情況我一般稱之為：條一色，單吊幺雞

这么精屁……大伙都这样啊，我也这样，所以经常死