技術帝：俄羅斯方塊可以永遠的玩下去嗎？

大家在玩俄羅斯方塊的時候有沒有想過這樣一個問題：如果玩家足夠牛B的話，是不是永遠也不可能玩死？換句話說，假設你是萬惡的游戲機，你打算害死你面前的玩家；你知道任意時刻游戲的狀態(tài)，并可以有針對性地給出一些明顯不合適的方塊，盡量迫使玩家面對最壞情況。那么，你有沒有一種算法能保證害死玩家，或者玩家無論如何都存在一種必勝策略呢？

注意，俄羅斯方塊的游戲區(qū)域是一個寬為10，高為20的矩形，并且玩家可以預先看到下一個給出的方塊是什么。在設計策略時，你必需考慮到這一點。

相信很多人有過這樣的經(jīng)歷：玩俄羅斯方塊時一開局就給你一個“S”型方塊，讓完美主義者感到異常別扭；結果，第二個方塊還是這個“S”，第三個方塊依舊是“S”，相當令人崩潰。于是，我們開始猜測，如果游戲機給你無窮個“S”形方塊，玩家是不是就沒有解了？答案是否定的。如圖1，從第10步開始，整個局面產(chǎn)生一個循環(huán)；只要機器給的一直都是“S”方塊，玩家可以不斷重復這幾個步驟，保證永遠也死不了。

不過，這個循環(huán)是在游戲場地清空了的情況下才產(chǎn)生的。有人會進一步想了，要是在玩著玩著，看著你局勢不好時突然給你無窮多個“S”方塊呢？事實上，此時局面的循環(huán)依然可能存在，如圖2。在第5個“S”形方塊落地后，循環(huán)再次產(chǎn)生。

俄羅斯方塊真的不可能玩死嗎？1988年，John Brzustowski的一篇論文指出，俄羅斯方塊游戲無解并非不可能。它給出了一種算法可以保證游戲機能夠害死玩家，即使我們要求它必須提前向玩家展示出下一個方塊的形狀。構造的關鍵在于，整個游戲的局面?zhèn)€數(shù)是有限的（2的200次方），如果玩家一直不死，在某一時刻必然會重復某一狀態(tài)。我們把兩次重復狀態(tài)及其之間的游戲過程叫做一個“循環(huán)”，這個循環(huán)實際影響到的那些行就叫做“實際循環(huán)區(qū)”。例如，圖2就是一個循環(huán)，這個循環(huán)的“實際循環(huán)區(qū)”是從第4行到第7行這四行。

我們把寬為10的游戲區(qū)域劃分為5個寬為2的“通道”，從左至右用1到5標號。注意到圖1和圖2中的兩個循環(huán)都有一個共同點：每個“S”形方塊最終都完全落在某個通道內(nèi)。事實上，對于任意一個只有“S”形方塊的循環(huán)，我們都有這個結論。也就是說，如果游戲機一直給你“S”形的方塊，你卻用它們弄出了一個循環(huán)，那只有一種可能：所有“S”形方塊的下落位置都沒有跨越通道（就像圖3中的紫色方塊那樣，而非綠色方塊那樣）。

為了證明這一點，我們對通道編號施歸納。令命題P(x)表示，如果某個“S”形方塊（或它的其中一部分）落在了通道x的左邊，那它一定完全落在某個通道內(nèi)。P(1)顯然成立：方塊根本不可能占據(jù)通道1左邊的某個格子，因為通道1左邊啥都沒有。下面我們說明，當P(n)為真時，P(n+1)也為真。