雅虎贊助網站載入中...
技術文章？用數學計算玩俄羅斯方塊不死奧秘
# 1
大家在玩俄羅斯方塊的時候有沒有想過這樣一個問題：如果玩家足夠牛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。二、這個結論可以直接擴展到場地為任意寬度的俄羅斯方塊遊戲。當場地寬為偶數時，上述證明同樣有效;當場地寬為奇數時，無窮多個方形方塊就可以直接幹掉玩家。
相信很多人有過這樣的經歷：玩俄羅斯方塊時一開局就給你一個“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。二、這個結論可以直接擴展到場地為任意寬度的俄羅斯方塊遊戲。當場地寬為偶數時，上述證明同樣有效;當場地寬為奇數時，無窮多個方形方塊就可以直接幹掉玩家。
# 2