俄罗斯方块可以永无止境地玩下去吗?

    大家在玩俄罗斯方块的时候有没有想过这样一个问题:如果玩家足够牛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。二、这个结论可以直接扩展到场地为任意宽度的俄罗斯方块游戏。当场地宽为偶数时,上述证明同样有效;当场地宽为奇数时,无穷多个方形方块就可以直接干掉玩家。

48 条评论

  • Sinya

    我还以为是NOI 2002的题解。偶写了个贪心,只能过6个。再写了个随机。只能过两三个。太纠结了!!!

  • reswallow

    我是俄罗斯极弱玩家= =…

  • 燕仰

    耶?好神奇~~~~

  • crazylamb

    还真没这么想过

  • ynifbs215

    文章后半部分基本没有看懂,太复杂了。。。。

  • 一特

    其实现在的游戏系统为了防止这种咯硬人的情况发生都是用的伪随机序列生成,每次生成一套七个。所以现代的俄罗斯方块是可以无穷地玩下去的。不仅可以无限玩下去,游戏中还经常可以出现“全清”的情况;有的游戏甚至为这种情况提供奖励分。

  • 娱乐在线

    我好差,玩不了机关就game over了。

  • kshaoye

    [quote] 大家在玩俄罗斯方块的时候有没有想过这样一个问题:如果玩家足够牛B的话,是不是永远也不可能玩死?[/quote]
    这个~还真没想过~~

  • Eagle_Fantasy

    后面带着星号那些图我没怎么看明白…

  • 纳米黑客

    当场地宽为奇数时,无穷多个方形方块就可以直接干掉玩家。
    这个为什么?

  • 悉尼

    纯粹崇拜!!!
    居然能够这方分析俄罗斯方块

  • flyink

    @12
    因为方形方块的宽度为2 是偶数个。。。永远不可能填满一排。。

  • 纳米黑客

    @14
    我囧了
    我没看见“方形”两个字。。。= =

  • Jollwish

    这个问题我是想过的。。。
    我用行动不完全归纳了它。。。

  • 冬冬

    这次E3上的trine ,matrix玩了没有 很好的解谜游戏哦 推荐给你

  • Robbin

    作为一个俄罗斯方块菜鸟,我也考虑过这个问题。我认为应该还有别的可以卡死玩家的策略。
    这个可以拿来害人哈。

  • Robbin

    不知道用那两种像钩子一样的能不能构造出这种。或者把7种全用上。

  • R

    M牛,上次你给的情景迷题(situation puzzle)我到班上推广,很有人气,可惜只有40题,请问有续集么?

  • Xiaoy.com

    专家都是做什么吃的哦…这么弱智的问题…不知道你所谓的一循环是几次.如果不能为偶数是没有用的,如果超过6次也是浪费,所以循环为6.
    当出了6个S,我想很多人会有一个想法,把6这个S全落到一起,靠边.这样其实是蛮整齐然后更换6个Z,靠另边全落到一起..6个S或者Z落一起为高13宽2的面积..这样想来即使你再循环,也不会死..因为我们也循环..当然不考虑速度与失误的问题.

  • Xiaoy.com

    专家都是做什么吃的哦…这么弱智的问题…不知道你所谓的一循环是几次.如果不能为偶数是没有用的,如果超过6次也是浪费,所以循环为6.
    当出了6个S,我想很多人会有一个想法,把6这个S全落到一起,靠边.这样其实是蛮整齐然后更换6个Z,靠另边全落到一起..6个S或者Z落一起为高13宽2的面积..这样想来即使你再循环,也不会死..因为我们也循环..当然不考虑速度与失误的问题.

    以下为图示例
    □ □ □ □ □ □ □ □ □ □
    □ □ □ □ ■ □ □ □ □ □ ■
    □ □ □ □ ■ ■ □ □ □ □ ■■
    □ □ □ □ □ ■ □ □ □ □ ■
    □ □ □ □ □ □ □ □ □ □
    □ □ □ □ □ □ □ □ □ □
    □ □ □ □ □ □ □ □ □ □
    □ ■ □ ■ □ □ ■ □ ■ □
    ■ ■ ■ ■ □ □ ■ ■ ■ ■
    ■ ■ ■ ■ □ □ ■ ■ ■ ■
    ■ ■ ■ ■ □ □ ■ ■ ■ ■
    ■ ■ ■ ■ □ □ ■ ■ ■ ■
    ■ ■ ■ ■ □ □ ■ ■ ■ ■
    ■ ■ ■ ■ □ □ ■ ■ ■ ■
    ■ ■ ■ ■ □ □ ■ ■ ■ ■
    ■ ■ ■ ■ □ □ ■ ■ ■ ■
    ■ ■ ■ ■ □ □ ■ ■ ■ ■
    ■ ■ ■ ■ □ □ ■ ■ ■ ■
    ■ ■ ■ ■ □ □ ■ ■ ■ ■
    ■ □ ■ □ □ □ □ ■ □ ■

  • 路人甲

    一开始我也在考虑楼上说的问题,但是,作者说了,是不断给出一只到出现循环,楼上的说法还没有出现循环呢。。。
    实话楼主的证明我没有看太明白,不过总感觉其中有漏掉的东西,但是又指不出来。。。所以只能暂且承认正确喽~呵呵。
    数学归纳法的确是个不错的工具。

  • Blue Gene

    太牛逼了!!!

  • bill

    你不会每快都横过来放吗?

  • fan

    27楼,如果横着放就只能在更高的地方形成循环了吧,下面浪费了不是死的更快?循环要求每个s型必须落在某个通道里,M牛的归纳法已经证明了。

  • Icewolf

    虽然这种怪事的发生概率极低,但理论上说仍然是可能的
    这种怪事发生的概率为必然,也就是概率为1.哈哈,大牛也范小错误啊!

  • Icewolf

    更准确地说,对于任意长度为n的方块序列s,如果方块的发生是完全随机的,则s出现的可能性为1.

  • BY

    我刚写了一个俄罗斯方块程序 我们的AI课作业

  • shinwar

    不错,有点意思。

  • 不明真相

    用Z不是就可以直接了结玩家麽……Z块可以循环起来?

  • COT

    看不太懂,但感觉很强大。用数学方法证明,水平高没用,RP不好,也会像我这样的菜鸟GAME OVER

  • 游荡

    你好,我是成都外国语学校的学生。我和我同学想办一本科学杂志(非营利性校刊……事实上第一期至少要亏几千块……),印量大概在300-500本左右。我们对这篇文章很感兴趣,希望能刊载在杂志上。希望获得您的同意。
    可以联系我一下吗?E-mail:youdangls@gmail.com或534440305@qq.com

  • baisk

    这还真没想到,俄罗斯方块能不能玩死也有这么强大的证明在里面。

  • Orpine

    在A站上看到游民转载了这篇文章,却没注明出处……游民无节操……
    http://www.acfun.tv/v/ac256097/

  • pochioly

    TX也无节操了(他什么时候有过。。。
    http://wenwen.soso.com/z/q2006663317.htm?pid=mail.wen1

  • yh

    ubuntu自带的俄罗斯方块有个“选择困难的方块”功能,基本上就是这个目的,不过有个bug
    如图:
    http://r.0xbc.com/gnometetris.png

  • cervelo

    知道用那两种像钩子一样的能不能构造出这种。或者把7种全用上。

  • colorant

    证明不是那么简单的,找到原始论文了,比这里要多一些推导步骤,看了还是觉得有点问题,推导的步骤有些含糊过关的地方,至少很多地方前后颠倒的描述,找时间再仔细看看。

  • qirenrui

    这证明很严格啊。。。为什么你们几个都说有点问题呢。。。你们又指不出来

发表评论

77  +    =  82