俄罗斯方块可以一直玩下去吗?

作者 | 大小吴来源 | 大小吴的数学课堂

2020 年先祝大家新年快乐!出门记得戴口罩哟~

呆在家大家可能都闷坏了吧,大小吴今天来给大家解解闷,我们来说说游戏的那些事。

俄罗斯方块大家都不陌生吧!为了怀旧,大小吴还特意买了游戏机充电宝。

一局俄罗斯方块可以一直玩下去吗?

大家在玩俄罗斯方块的时候有没有想过这样一个问题:如果玩家足够厉害,是不是永远也玩不死?换句话说,如果你是万恶的游戏机,你知道游戏任意时刻的状态,并可以有针对性地给出一些不合适的方块,尽量迫使对面的玩家面对最坏的情况。那么,你有没有一种算法能保证害死玩家呢?

1 俄罗斯方块中的循环

我们先来回忆一下俄罗斯方块的游戏界面:

一局俄罗斯方块可以一直玩下去吗?

俄罗斯方块区域是一个宽为 10,高为 20 的矩形,并且玩家可以看到下一个方块是什么。

相信很多人都有过这样的经历:玩俄罗斯方块的时候,如果开局就给你一个 S 形方块,这会让完美主义者感到崩溃。

一局俄罗斯方块可以一直玩下去吗?

如果第二个还是 S,第三个仍然是 S,那我们可能就放弃重新开始下一局了。

那么,假如游戏机真的给你无穷个 S 形方块,玩家是不是没有解了呢?

答案是否定的!

我们看下图:

一局俄罗斯方块可以一直玩下去吗?

我们会发现,只要机器给的一直是 S 形方块,玩家可以不断重复这几个步骤,保证永远也不会死。

一局俄罗斯方块可以一直玩下去吗?

不过,这个循环是在游戏场地清空的情况才产生的。

要是玩着玩着,机器看着你局势不好时突然给你无穷多个 S 形方块呢?事实上,此时局面的循环依然存在。

一局俄罗斯方块可以一直玩下去吗?

在第 5 个 S 形方块落地后,循环再次产生。

2 俄罗斯方块中的“通道”

俄罗斯方块究竟是否存在必死的情况呢?

1988 年,约翰·布茹斯托斯基的一篇论文给出肯定的答案。他给出了一种算法,可以保证游戏机能够害死玩家,即使要求它必须提前向玩家展示下一个方块的形状。

我们将两次重复状态及其之间的游戏过程叫做一个“循环”,这个循环实际影响到的那些行叫做“实际循环区”。例如前文提到的一种情况就是一个循环,这个循环的“实际循环区”是从第 4 行到第 7 行。

我们把宽为 10 的游戏区域划分为5 个宽为 2的“通道”,从左至右用 1 到 5 标号。注意到前文中提到的两个循环都有一个共同点:每个 S 形方块最终都完全落在某个通道内。也就是,如果游戏机一直给你 S 形的方块,只要所有 S 形方块的下落位置都没有跨越通道(如下图中的 A、B 那样),你就能弄出一个循环!为了证明上述这一点,我们对通道编号实施归纳。

考虑命题 :如果某个 S 形方块(或它的一部分)落在了通道 的左边(或者说是前 列里),那它一定完全落在某个通道内。

:成立,方块不可能落到通道 1 左边的格子,因为通道 1 左边什么也没有。

假如 为真,下面我们说明 为真。

在说明 为真之前,我们首先来证明一个引理:在循环中的任意时刻,通道 的实际循环区内绝不可能出现形如“”的两个并排的格子。

如下图所示:

一局俄罗斯方块可以一直玩下去吗?

假设图形阴影部分方块是在通道 的实际循环区内最低的 的结构。假如这一行被消掉,由归纳假设,不存在 S 形方块跨越该通道左边界,因此只有一种可能,某个 S 形方块从左侧挤了进来,如下图所示。但这样就产生了一个更低的 ,矛盾。证毕。

一局俄罗斯方块可以一直玩下去吗?

接下来,我们来说明 为真。

要想让 S 形方块占据通道 的格子,只有以下 4 种情况

一局俄罗斯方块可以一直玩下去吗?

由于我们证明了通道种不能存在 ,因此阴影部分在 S 形方块下落前就存在。注意到,每一个 S 形方块下落使得 结构减少,但第一种情况除外——它消除了一个,但上方又带来了一个新的 结构,所以 结构个数保持不变。因此只有第一种情况才能够被接受。

也就是说,仅含有 S 形方块的循环只有一种情况——S 形方块在各个通道内重叠,填满并消除若干行后回到初始状态。

注意,最右侧通道的最顶端是一个“”,右边的空白永远不能用 Z 形方块填上。

3 必输的俄罗斯方块游戏

下面我们就给出游戏机害死玩家的算法。

  • (1)不断给出 S 形方块直到出现一个循环。
  • (2)给出一个 S 形方块,显示下一个方块为 Z 形。
  • (3)不断给出 Z 形方块直到出现一个循环。
  • (4)给出一个 Z 形方块,显示下一个方块为 S 形。
  • (5)跳回(1),重复执行。

这样的话,为什么一定会死呢?

由上面的结论,在(1)后,游戏区域中出现一个不能用 Z 形消除的行。即使给你一个 S 形,你也无法挽救,因为这又立即产生一个 Z 形永远放不进的空位。然后,玩家又拿到一大堆 Z 形,最终必然产生一个 S 形无法消除的行。于是,游戏机又给出一大堆 S,最终使得两种无法消去的行交替出现,直至游戏结束!

到此为止,我们便完成了证明!

有人或许会说:现实的游戏机并没有主观能动性啊?

事实上,即使方块是随机给出,如果你倒霉到家了,这种特殊的序列可能恰好让你碰上了。虽然这种怪事发生的概率非常低,但理论上是可能的,因此俄罗斯方块终究不是玩不死的,总有一个时刻会 Game Over。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 206599465@qq.com 举报,一经查实,本站将立刻删除。
分享本页
返回顶部