俄羅斯方塊可以永無止境地玩下去嗎？

大師在玩俄羅斯方塊的時辰有沒有想過這樣一個問題：若是玩家足夠牛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。二、這個結論可以直接擴展參加地為肆意寬度的俄羅斯方塊游戲。就地地寬為偶數時，上述證實同樣有用；就地地寬為奇數時，無限多個方形方塊就可以直接干失落玩家。

文 | Matrix67

發表于 2019-08-15 02:00
閱讀 ( 776 )
分類：其他類型

俄羅斯方塊可以永無止境地玩下去嗎？

你可能感興趣的文章

相關問題

0 條評論

作家榜 ?

推薦文章