2009-07-12 0:20|
39 Comments | 本文内容遵从
转载请注明出自matrix67.com 大家在玩俄罗斯方块的时候有没有想过这样一个问题：如果玩家足够牛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。二、这个结论可以直接扩展到场地为任意宽度的俄罗斯方块游戏。当场地宽为偶数时，上述证明同样有效；当场地宽为奇数时，无穷多个方形方块就可以直接干掉玩家。
Posted in
Trackback: http://www.matrix67.com/blog/archives/2134/trackback
我猜您可能还喜欢：
39 条回复
楼层: 沙发 |
2009-07-12 0:24
| 说：
sf？？
楼层: 板凳 |
2009-07-12 1:03
A13 说：
楼层: 地毯 |
2009-07-12 7:09
我还以为是NOI 2002的题解。偶写了个贪心，只能过6个。再写了个随机。只能过两三个。太纠结了！！！
楼层: 地板 |
2009-07-12 9:03
我是俄罗斯极弱玩家= =...
楼层: 地下室 |
2009-07-12 9:51
耶？好神奇~~~~
楼层: 地基 |
2009-07-12 10:34
crazylamb 说：
还真没这么想过
楼层: 地壳 |
2009-07-12 11:01
文章后半部分基本没有看懂，太复杂了。。。。
楼层: 地幔 |
2009-07-12 11:44
一特 说：
其实现在的游戏系统为了防止这种咯硬人的情况发生都是用的伪随机序列生成，每次生成一套七个。所以现代的俄罗斯方块是可以无穷地玩下去的。不仅可以无限玩下去，游戏中还经常可以出现“全清”的情况；有的游戏甚至为这种情况提供奖励分。
楼层: 地核 |
2009-07-12 12:20
我好差，玩不了机关就game over了。
楼层: 10楼 |
2009-07-12 17:59
[quote] 大家在玩俄罗斯方块的时候有没有想过这样一个问题：如果玩家足够牛B的话，是不是永远也不可能玩死？[/quote]
这个~还真没想过~~
楼层: 11楼 |
2009-07-12 19:05
后面带着星号那些图我没怎么看明白...
楼层: 12楼 |
2009-07-13 10:00
当场地宽为奇数时，无穷多个方形方块就可以直接干掉玩家。
这个为什么?
楼层: 12a楼 |
2009-07-13 12:06
纯粹崇拜！！！
居然能够这方分析俄罗斯方块
楼层: 14楼 |
2009-07-13 12:08
因为方形方块的宽度为2 是偶数个。。。永远不可能填满一排。。
楼层: 15楼 |
2009-07-13 14:50
我囧了
我没看见“方形”两个字。。。＝ ＝
楼层: 16楼 |
2009-07-13 16:59
楼层: 17楼 |
2009-07-13 17:17
Jollwish 说：
这个问题我是想过的。。。
我用行动不完全归纳了它。。。
楼层: 18楼 |
2009-07-14 0:50
冬冬 说：
这次E3上的trine ，matrix玩了没有 很好的解谜游戏哦 推荐给你
楼层: 19楼 |
2009-07-14 11:11
楼层: 20楼 |
2009-07-14 22:05
Ro in 说：
作为一个俄罗斯方块菜鸟，我也考虑过这个问题。我认为应该还有别的可以卡死玩家的策略。
这个可以拿来害人哈。
楼层: 21楼 |
2009-07-14 22:08
Ro in 说：
不知道用那两种像钩子一样的能不能构造出这种。或者把7种全用上。
楼层: 22楼 |
2009-07-15 12:40
R 说：
M牛，上次你给的情景迷题（situation puzzle）我到班上推广，很有人气，可惜只有40题，请问有续集么？
楼层: 23楼 |
2009-07-15 18:14
Xiaoy.com 说：
专家都是做什么吃的哦...这么弱智的问题...不知道你所谓的一循环是几次.如果不能为偶数是没有用的,如果超过6次也是浪费,所以循环为6.
当出了6个S,我想很多人会有一个想法,把6这个S全落到一起,靠边.这样其实是蛮整齐然后更换6个Z,靠另边全落到一起..6个S或者Z落一起为高13宽2的面积..这样想来即使你再循环,也不会死..因为我们也循环..当然不考虑速度与失误的问题.
楼层: 24楼 |
2009-07-15 18:22
Xiaoy.com 说：
专家都是做什么吃的哦...这么弱智的问题...不知道你所谓的一循环是几次.如果不能为偶数是没有用的,如果超过6次也是浪费,所以循环为6.
当出了6个S,我想很多人会有一个想法,把6这个S全落到一起,靠边.这样其实是蛮整齐然后更换6个Z,靠另边全落到一起..6个S或者Z落一起为高13宽2的面积..这样想来即使你再循环,也不会死..因为我们也循环..当然不考虑速度与失误的问题.
以下为图示例
□ □ □ □ □ □ □ □ □ □
□ □ □ □ ■ □ □ □ □ □
□ □ □ □ ■ ■ □ □ □ □
□ □ □ □ □ ■ □ □ □ □
□ □ □ □ □ □ □ □ □ □
□ □ □ □ □ □ □ □ □ □
□ □ □ □ □ □ □ □ □ □
□ ■ □ ■ □ □ ■ □ ■ □
■ ■ ■ ■ □ □ ■ ■ ■ ■
■ ■ ■ ■ □ □ ■ ■ ■ ■
■ ■ ■ ■ □ □ ■ ■ ■ ■
■ ■ ■ ■ □ □ ■ ■ ■ ■
■ ■ ■ ■ □ □ ■ ■ ■ ■
■ ■ ■ ■ □ □ ■ ■ ■ ■
■ ■ ■ ■ □ □ ■ ■ ■ ■
■ ■ ■ ■ □ □ ■ ■ ■ ■
■ ■ ■ ■ □ □ ■ ■ ■ ■
■ ■ ■ ■ □ □ ■ ■ ■ ■
■ ■ ■ ■ □ □ ■ ■ ■ ■
■ □ ■ □ □ □ □ ■ □ ■
楼层: 25楼 |
2009-07-18 10:49
路人甲 说：
一开始我也在考虑楼上说的问题，但是，作者说了，是不断给出一只到出现循环，楼上的说法还没有出现循环呢。。。
实话楼主的证明我没有看太明白，不过总感觉其中有漏掉的东西，但是又指不出来。。。所以只能暂且承认正确喽~呵呵。
数学归纳法的确是个不错的工具。
楼层: 26楼 |
2009-08-04 13:39
太牛逼了！！！
楼层: 27楼 |
2009-09-04 20:38
bill 说：
你不会每快都横过来放吗？
楼层: 28楼 |
2009-09-07 18:54
fan 说：
27楼，如果横着放就只能在更高的地方形成循环了吧，下面浪费了不是死的更快？循环要求每个s型必须落在某个通道里，M牛的归纳法已经证明了。
楼层: 29楼 |
2009-10-05 23:50
Icewolf 说：
虽然这种怪事的发生概率极低，但理论上说仍然是可能的
这种怪事发生的概率为必然，也就是概率为1.哈哈，大牛也范小错误啊！
楼层: 30楼 |
2009-10-05 23:52
Icewolf 说：
更准确地说，对于任意长度为n的方块序列s，如果方块的发生是完全随机的，则s出现的可能性为1.
楼层: 31楼 |
2009-10-29 16:34
BY 说：
我刚写了一个俄罗斯方块程序 我们的AI课作业
楼层: 32楼 |
2010-01-26 0:39
shinwar 说：
不错，有点意思。
楼层: 33楼 |
2010-05-06 19:25
[...] 大家也许想过，如果玩家足够牛 B 的话，俄罗斯方块游戏是不是永远也玩不死呢？不是的。我曾经在这里介绍过，理论上说，俄罗斯方块游戏是不能永无止境地玩下去的，总有一个时候你会死掉。事实上，如果允许电脑不随机出牌，可以有意为难你的话，电脑可以利用一个简单的算法迅速把你整死。倘若电脑真的能故意陷害你，玩俄罗斯方块会是什么样的呢？ 今天，我还真找到了这么一个在线俄罗斯方块游戏 HATETRIS 。在这个游戏中，下一个方块并不是随机给的，游戏将精心为你挑选一个对你最不利的方块。毫不夸张地说，在这个游戏中，即使想消掉一行也是一件很困难的事。 游戏是用 JavaScript 写的，你可以在下面这个框架中点 start new game 直接开始游戏。游戏没有重力因素（方块不会自动下落），这可以给你充分长的思考时间。技术细节和高分记录请移步这里。 想让俄罗斯方块更变态一些，方法不止一种。如果喜欢这个游戏，欢迎挑战我自己原创的变态俄罗斯方块 PiTetris 。 [...]
楼层: 34楼 |
2010-08-12 16:45
[...] 原帖来源：http://www.matrix67.com/blog/archives/2134 [...]
楼层: 35楼 |
2010-10-30 16:53
不明真相 说：
用Z不是就可以直接了结玩家麽……Z块可以循环起来？
楼层: 36楼 |
2010-11-01 9:31
[...] 您的位置: 首页 文化 正文俄罗斯方块可以永无止境地玩下去吗？ 2010-11-01 09:30 小编: 兽兽 来源: 网络 浏览:
我要评论 字号: 大 中 小 推荐到抽屉 分享到QQ空间 分享到网易微博 转发到新浪微博 转帖到人人网摘要:原文：http://www.matrix67.com/blog/archives/2134 大家在玩俄罗斯方块的时候有没有想过这样一个问题：如果玩家足够牛B的话，是不是永远也不可能玩死？换句话说，假设你是万恶的游戏机，你打算害死你 面前的玩家；你知道任意时... google_ad_client = "pub-0051655280484421"; /* 336x280, luobo 09-9-26 */ google_ad_slot = "0312300031"; google_ad_width = 336; google_ad_height = 280;
原文：http://www.matrix67.com/blog/archives/2134大家在玩俄罗斯方块的时候有没有想过这样一个问题：如果玩家足够牛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。二、这个结论可以直接扩展到场地为任意宽度的俄罗斯方块游戏。当场地宽为偶数时，上述证明同样有效；当场地宽为奇数时，无穷多个方形方块就可以 直接干掉玩家。 [...]
楼层: 37楼 |
2011-02-25 18:03
COT 说：
看不太懂，但感觉很强大。用数学方法证明，水平高没用，RP不好，也会像我这样的菜鸟GAME OVER
楼层: 38楼 |
2011-04-16 22:05
游荡 说：
你好，我是成都外国语学校的学生。我和我同学想办一本科学杂志（非营利性校刊……事实上第一期至少要亏几千块……），印量大概在300-500本左右。我们对这篇文章很感兴趣，希望能刊载在杂志上。希望获得您的同意。
可以联系我一下吗？E-mail：youdangls@gmail.com或534440305@qq.com
楼层: 39楼 |
2011-06-21 7:10
这还真没想到，俄罗斯方块能不能玩死也有这么强大的证明在里面。
您也随便说几句吧：
您的昵称（必填）
您的E-mail地址（必填）
您的网站（可选）
您可以在
设置您的头像。
Category
Su cribe
Control Panel
Random Articles
Recent Comments
上的评论
cctv 在
上的评论
上的评论
Ark Xu 在
上的评论
上的评论
上的评论
上的评论
上的评论
Blogroll
Powered by
. Theme by
, Revised by你见过这样玩俄罗斯方块的吗
视频标题和链接已经复制，现在可以粘贴给QQ，MSN聊天好友拉~
你见过这样玩俄罗斯方块的吗
http://v.ku6.com/show/_yDZWjb-xrmkw7CW.html
提示：根据颜色的选择，html代码、flash地址会自动改变。
Flash播放器的代码：
转帖到论坛、博客的HTML代码：
发布者：
发表于 1年前
http://i22.ku6.com/20106/9/12/7756520935085847/3.jpg
（酷6搞笑频道） 你见过这样玩俄罗斯方块的吗
（酷6搞笑频道） 你见过这样玩俄罗斯方块的吗
A .createComment();
本周最受欢迎视频
视频频道：
CopyRight 2006-2010