作者 | 大小吳來源 | 大小吳的數學課堂
2020 年先祝大家新年快樂！出門記得戴口罩喲~
呆在家大家可能都悶壞了吧，大小吳今天來給大家解解悶，我們來說說遊戲的那些事。
俄羅斯方塊大家都不陌生吧！為了懷舊，大小吳還特意買了遊戲機充電寶。
大家在玩俄羅斯方塊的時候有沒有想過這樣一個問題：如果玩家足夠厲害，是不是永遠也玩不死？換句話說，如果你是萬惡的遊戲機，你知道遊戲任意時刻的狀態，並可以有針對性地給出一些不合適的方塊，儘量迫使對面的玩家面對最壞的情況。那麼，你有沒有一種算法能保證害死玩家呢？
1 俄羅斯方塊中的循環
我們先來回憶一下俄羅斯方塊的遊戲介面：
俄羅斯方塊區域是一個寬為 10，高為 20 的矩形，並且玩家可以看到下一個方塊是什麼。
相信很多人都有過這樣的經歷：玩俄羅斯方塊的時候，如果開局就給你一個 S 形方塊，這會讓完美主義者感到崩潰。
如果第二個還是 S，第三個仍然是 S，那我們可能就放棄重新開始下一局了。
那麼，假如遊戲機真的給你無窮個 S 形方塊，玩家是不是沒有解了呢？
答案是否定的！
我們看下圖：
我們會發現，只要機器給的一直是 S 形方塊，玩家可以不斷重複這幾個步驟，保證永遠也不會死。
不過，這個循環是在遊戲場地清空的情況才產生的。
要是玩著玩著，機器看著你局勢不好時突然給你無窮多個 S 形方塊呢？事實上，此時局面的循環依然存在。
在第 5 個 S 形方塊落地後，循環再次產生。
2 俄羅斯方塊中的「通道」
俄羅斯方塊究竟是否存在必死的情況呢？
1988 年，約翰·布茹斯托斯基的一篇論文給出肯定的答案。他給出了一種算法，可以保證遊戲機能夠害死玩家，即使要求它必須提前向玩家展示下一個方塊的形狀。
我們將兩次重複狀態及其之間的遊戲過程叫做一個「循環」，這個循環實際影響到的那些行叫做「實際循環區」。例如前文提到的一種情況就是一個循環，這個循環的「實際循環區」是從第 4 行到第 7 行。
我們把寬為 10 的遊戲區域劃分為5 個寬為 2的「通道」，從左至右用 1 到 5 標號。注意到前文中提到的兩個循環都有一個共同點：每個 S 形方塊最終都完全落在某個通道內。也就是，如果遊戲機一直給你 S 形的方塊，只要所有 S 形方塊的下落位置都沒有跨越通道（如下圖中的 A、B 那樣），你就能弄出一個循環！為了證明上述這一點，我們對通道編號實施歸納。
考慮命題 ：如果某個 S 形方塊（或它的一部分）落在了通道 的左邊（或者說是前 列里），那它一定完全落在某個通道內。
：成立，方塊不可能落到通道 1 左邊的格子，因為通道 1 左邊什麼也沒有。
假如 為真，下面我們說明 為真。
在說明 為真之前，我們首先來證明一個引理：在循環中的任意時刻，通道 的實際循環區內絕不可能出現形如「」的兩個並排的格子。
如下圖所示:
假設圖形陰影部分方塊是在通道 的實際循環區內最低的 的結構。假如這一行被消掉，由歸納假設，不存在 S 形方塊跨越該通道左邊界，因此只有一種可能，某個 S 形方塊從左側擠了進來，如下圖所示。但這樣就產生了一個更低的 ，矛盾。證畢。
接下來，我們來說明 為真。
要想讓 S 形方塊占據通道 的格子，只有以下 4 種情況
由於我們證明了通道種不能存在 ，因此陰影部分在 S 形方塊下落前就存在。注意到，每一個 S 形方塊下落使得 結構減少，但第一種情況除外——它消除了一個，但上方又帶來了一個新的 結構，所以 結構個數保持不變。因此只有第一種情況才能夠被接受。
也就是說，僅含有 S 形方塊的循環只有一種情況——S 形方塊在各個通道內重疊，填滿並消除若干行後回到初始狀態。
注意，最右側通道的最頂端是一個「」，右邊的空白永遠不能用 Z 形方塊填上。
3 必輸的俄羅斯方塊遊戲
下面我們就給出遊戲機害死玩家的算法。
（1）不斷給出 S 形方塊直到出現一個循環。
（2）給出一個 S 形方塊，顯示下一個方塊為 Z 形。
（3）不斷給出 Z 形方塊直到出現一個循環。
（4）給出一個 Z 形方塊，顯示下一個方塊為 S 形。
（5）跳回（1），重複執行。
這樣的話，為什麼一定會死呢？
由上面的結論，在（1）後，遊戲區域中出現一個不能用 Z 形消除的行。即使給你一個 S 形，你也無法挽救，因為這又立即產生一個 Z 形永遠放不進的空位。然後，玩家又拿到一大堆 Z 形，最終必然產生一個 S 形無法消除的行。於是，遊戲機又給出一大堆 S，最終使得兩種無法消去的行交替出現，直至遊戲結束！
到此為止，我們便完成了證明！
有人或許會說：現實的遊戲機並沒有主觀能動性啊？
事實上，即使方塊是隨機給出，如果你倒霉到家了，這種特殊的序列可能恰好讓你碰上了。雖然這種怪事發生的機率非常低，但理論上是可能的，因此俄羅斯方塊終究不是玩不死的，總有一個時刻會 Game Over。
參考文獻[1]顧森.思考的樂趣——Matrix67 數學筆記[M].人民郵電出版社，2012.