你在俄罗斯方块中输掉比赛只是因为你没有发挥出最佳状态或者犯了错误吗?即使有足够的时间思考,不利的棋子顺序也无法挽救。决定性因素是五条窄巷和奇数。我们考虑一个具有\(10\)列和\(20\)行的游戏场,没有剪贴板(按住):每个新石头都是独立抽取的,并且从七个四格骨牌中均匀分布。每个形状由四个相连的正方形组成。整个情节可能是提前知道的。
游戏几乎肯定会结束这一事实并不意味着所有可以想象的棋子序列都会结束。纯粹的 O 形棋子序列可以无限地玩:五个相邻的方块删除两行并清空棋盘。在 7-Bag 中,每个随机混合的袋子仅包含一次所有七个形状;我们的机会论证不适用于此。在《如何输掉俄罗斯方块》中, Heidi Burgiel 展示了一个即使完美的游戏也无济于事的序列: \(S,Z,S,Z,\ldots\) 。
S和Z是镜像,不是同一块石头的不同旋转。随附的解释描述了我们在这里提出的作为反证法的几何概念。 “在某些时候只有 Z 棋子出现,没有行随之消失”这一明显的说法是错误的。只需五个相同的、垂直放置的 S 石即可在最初空的棋盘上提供以下排列。相同的字母表示相同的石头;点标记可用空间:
a.b.c.d.e.
aabbccddee
.a.b.c.d.e
中间行已完成并删除。如果你镜像这种排列,你会得到与 Z 宝石相同的反例。问题不在于删除单个行,而在于您是否可以控制无限数量的宝石中出现的所有不平衡问题。让我们对列进行编号,从\(1\)到\(10\) 。通过\(b_i\)我们表示放置在\(i\)列中的所有新单元格的总数,包括后来删除的单元格。
\(h_i\)计算中间列\(i\)的水平 S 或 Z 棋子, \(v_i\)列\(i\)和\(i+1\)中的垂直棋子。计数器记录游戏的进程,而不仅仅是当前可见的堆栈。水平石头将其细胞按比例\(1,2,1\)分布在三列中,垂直石头按比例\(2,2\)在两列中。两个镜像具有相同的列平衡。如果您将所有展示位置的这些贡献相加,则每列都会得到:
$$b_i=2v_{i-1}+2v_i+h_{i-1}+2h_i+h_{i+1}.$$
在棋盘外,我们将所有计数器设置为\(0\) ;特别是\(v_0=v_{10}=h_0=h_1=h_{10}=h_{11}=0\) 。这种边缘约定可以防止天平计算超出比赛场地边缘的棋子。我们的模型不允许这样的放置。如果所考虑的 S/Z 序列在已填充的棋盘上开始,则设\(a_i\)为最初占用的单元格, \(c_i\)为列\(i\)中当前占用的单元格。在\(R\)删除行之后是:
$$c_i=a_i+b_i-R,$$
$$b_i-b_j=(c_i-c_j)-(a_i-a_j).$$
只要游戏正在运行,所有\(a_i,c_i\)都在\(0\)和\(20\)之间。因此\(|b_i-b_j|\leq40\)适用。如果棋盘最初是空的\(20\)就足够了。每个删除的行都会从每一列中删除一个单元格。这就是为什么在比较两列时删除的行数会减少,即使设置单元格的计数器继续增长也是如此。您计算占用的单元格而不是堆栈高度;两种尺寸在孔方面有所不同。如果我们将此限制一般写为\(D\) ,则结果在左边缘或右边缘:
$$2v_2+h_2+h_3=b_2-b_1\leq D,$$
$$2v_8+h_8+h_9=b_9-b_{10}\leq D.$$
对于内部列对,我们添加两个受限列差异:左侧的\(b_4-b_3\)和\(b_2-b_1\) ,右侧的\(b_7-b_8\)和\(b_9-b_{10}\) 。插入列天平后,其间的计数器完全相互抵消。这使得每个左侧仅留下非负贡献,这些贡献由\(2D\)共同界定。这也为我们提供了两个内部对各自放置数量的上限:
$$\begin{aligned}2v_4+h_4+h_5&=(b_4-b_3)+(b_2-b_1)\\&\leq2D,\\2v_6+h_6+h_7&=(b_7-b_8)+(b_9-b_{10})\\&\leq2D.\end{aligned}$$
如果我们将四个不等式相加,则每块水平棋子都会被计算一次。四种类型的跨轨道垂直放置也具有正系数。水平石头占据了三根柱子,因此并不完全适合稍后考虑的两柱路径之一。对于垂直的石头,我们根据左栏来区分轨迹。由于所有计数器都是非负的,因此这些贡献都不能被另一个计数器取消:
$$\sum_{i=2}^{9}h_i+2(v_2+v_4+v_6+v_8)\leq6D.$$
因此,带有直左列的水平放置和垂直放置在空板上最多可出现\(120\)次,在任何预填充板上最多可出现\(240\)次。这是一个上限,而不是声称它实际上可以实现。无论如何,这些回避动作不可能无限次地使用。现在我们假设您可以无限期地播放交替序列。
在最后一次有限次数的躲避移动之后,只能在五个固定车道中进行垂直放置: \((1,2),(3,4),(5,6),(7,8),(9,10)\) 。相同的形状以阶梯状图案相互配合:底部与前一块石头的匹配顶部相接。从 S 更改为 Z,反之亦然,会留下一个单元格宽、两个单元格深的间隙。细节显示 Z 宝石位于 S 宝石之上;两个“o”标记间隙:
.Z
ZZ
Zo
So
SS
.S
同一车道上的另一个垂直石头无法填补这个空白:它的第二列会与相邻的被占据的单元相碰撞。只要间隙存在,删除行也没有帮助,因为两行都不完整。修复需要已排除的跨轨道或水平放置之一。在最后一次规避动作之后,这种差距将是永久性的。有限的棋盘上不可能出现无限数量的新的、不相交的间隙。
因此,轨道上的形式变化只能是有限的。最初空的车道不会改变这一点:你的第一个 S 或 Z 石头已经在地板上留下了单列间隙,无法通过进一步的纯车道游戏来关闭。在所谓的无限游戏中,每条车道也必须容纳无限数量的棋子。如果某个泳道在某个时刻保持不变,则由于列平衡有限,剩余泳道中只能容纳有限数量的细胞。
因此,我们到达了一个时间点,所有五个车道都被永久占用并牢固地分配给一个表单。从这一点开始,我们数出\(t\)个更多的石头,并用\(n_j(t)\)轨道\(j\)中的数量。每块石头都为其轨道的每一列贡献两个单元。由于行删除同等对待所有列,因此差异\(n_j(t)-n_k(t)\)仍然有限。从长远来看,所有五个泳道都必须持有五分之一的棋子:
$$\frac{n_j(t)}{t}\longrightarrow\frac15.$$
如果五个车道中的\(k\)条保留给 S 石,那么它们的份额应约为\(k/5\) 。然而,在交替序列中它是\(1/2\) :在每个前缀中,S 和 Z 宝石的数量最多相差\(1\) 。车道的划分必须同时满足这两个部分。然而,一半的份额不能代表整个五分之一的总和。这就是交替形式的频率和奇数个相同使用的轨道聚集在一起的地方。这将是强制性的:
$$\frac{k}{5}=\frac12\quad\Longrightarrow\quad k=\frac52.$$
车道数是整数。这一矛盾结束了无限博弈的假设。这个论点还说明了为什么板宽度是其中的一部分:对于四个列车,这种矛盾不能排除划分为两个 S 和两个 Z 列车的可能性。对于随机证明,我们需要一个有限的块长度\(N\) ,无论当前的板如何,都会导致损失。仅“每种策略都会在某个时刻失败”是不够的。
一致性来自有限数量的可能状态。每次完成放置后,最多有\(2^{200}\)个占用模式。还有关于接下来出现的是 S 还是 Z 的信息,即最多\(2^{201}\)个状态。如果你要从\(N=2^{201}\)颗石头中幸存下来,这些移动之前和之后的\(N+1\)状态将会重复。由于相同的棋盘和相同的下一个形状,两者之间的合法移动将可以重复任意多次:刚刚排除了无限游戏。
该限制还计算了无法达到的棋盘模式,并且不预测实际的游戏长度。 Burgiel 的更精细的几何计数给出了更小的界限;这里有限的\(N\)就足够了。它适用于所有允许的初始分配以及 S/Z 序列的两个阶段。让我们将无限随机序列分解为长度为\(N\)的不相交块。每个块都是指定的序列\(S,Z,S,Z,\ldots\) ,概率为\(q=7^{-N}>0\) 。这些块是独立的。因此,前\(m\)个块可能都不包含此序列:
$$\mathbb P(\text{kein Treffer in }m\text{ Blöcken})=(1-q)^m\longrightarrow0.$$
因此,有概率\(1\)在某个时刻会出现致命方块,除非游戏在此之前结束。这也适用于任何时间思考它并完整了解整个宝石序列的知识。这并不会导致实际演奏时间变短。一个没有重点的、糟糕的开局并不意味着失败;它也意味着失败。令人惊讶的卷土重来当然是有可能的。所以,不要灰心,享受这款永恒的游戏吧。