技術(shù)帝：俄羅斯方塊可以永遠(yuǎn)的玩下去嗎？

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

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

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

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

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

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

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