@KTzone » 遊戲 - NDS/3DS討論 » 技術文章?用數學計算玩俄羅斯方塊不死奧秘


2011-11-15 02:25 CJ君人
技術文章?用數學計算玩俄羅斯方塊不死奧秘

大家在玩俄羅斯方塊的時候有沒有想過這樣一個問題:如果玩家足夠牛B的話,是不是永遠也不可能玩死?換句話說,假設你是萬惡的遊戲機,你打算害死你面前的玩家;你知道任意時刻遊戲的狀態,並可以有針對性地給出一些明顯不合適的方塊,儘量迫使玩家面對最壞情況。那麼,你有沒有一種演算法能保證害死玩家,或者玩家無論如何都存在一種必勝策略呢?  注意,俄羅斯方塊的遊戲區域是一個寬為10,高為20的矩形,並且玩家可以預先看到下一個給出的方塊是什麼。在設計策略時,你必需考慮到這一點。
   [url=http://www.tgbus.com/image.html?url=http://www.tgbus.com/image.html?url=http://ps3.tgbus.com/UploadFiles/201111/20111106114351899.jpg][img]http://ps3.tgbus.com/UploadFiles/201111/20111106114351834.jpg[/img][/url]
  相信很多人有過這樣的經歷:玩俄羅斯方塊時一開局就給你一個“S”型方塊,讓完美主義者感到異常彆扭;結果,第二個方塊還是這個“S”,第三個方塊依舊是“S”,相當令人崩潰。於是,我們開始猜測,如果遊戲機給你無窮個“S”形方塊,玩家是不是就沒有解了?答案是否定的。如圖1,從第10步開始,整個局面產生一個迴圈;只要機器給的一直都是“S”方塊,玩家可以不斷重複這幾個步驟,保證永遠也死不了。
   [url=http://www.tgbus.com/image.html?url=http://www.tgbus.com/image.html?url=http://ps3.tgbus.com/UploadFiles/201111/20111106114351695.jpg][img]http://ps3.tgbus.com/UploadFiles/201111/20111106114351543.jpg[/img][/url]
  不過,這個迴圈是在遊戲場地清空了的情況下才產生的。有人會進一步想了,要是在玩著玩著,看著你局勢不好時突然給你無窮多個“S”方塊呢?事實上,此時局面的迴圈依然可能存在,如圖2。在第5個“S”形方塊落地後,迴圈再次產生。
  俄羅斯方塊真的不可能玩死嗎?1988年,John Brzustowski的一篇論文指出,俄羅斯方塊遊戲無解並非不可能。它給出了一種演算法可以保證遊戲機能夠害死玩家,即使我們要求它必須提前向玩家展示出下一個方塊的形狀。構造的關鍵在於,整個遊戲的局面個數是有限的(2的200次方),如果玩家一直不死,在某一時刻必然會重複某一狀態。我們把兩次重複狀態及其之間的遊戲過程叫做一個“迴圈”,這個迴圈實際影響到的那些行就叫做“實際迴圈區”。例如,圖2就是一個迴圈,這個迴圈的“實際迴圈區”是從第4行到第7行這四行。
   [url=http://www.tgbus.com/image.html?url=http://www.tgbus.com/image.html?url=http://ps3.tgbus.com/UploadFiles/201111/20111106114351358.jpg][img]http://ps3.tgbus.com/UploadFiles/201111/20111106114351255.jpg[/img][/url]
  我們把寬為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)也為真。
   [url=http://www.tgbus.com/image.html?url=http://www.tgbus.com/image.html?url=http://ps3.tgbus.com/UploadFiles/201111/20111106114351117.jpg][img]http://ps3.tgbus.com/UploadFiles/201111/20111106114351352.jpg[/img][/url]
  我們首先要證明一個引理:在迴圈中的任意時刻,通道n的實際迴圈區內絕對不可能出現形如“口■”的兩個並排的格子。如圖4.1,假設圖中星號方塊所在行是通道n的實際迴圈區內位置最低的“口■”的結構。假如這一行被消掉了,又由歸納假設,不存在哪個“S”形方塊跨越了該通道的左邊界,因此只有一種可能:某個“S”形方塊從左側面擠了進來(如圖4.2)。但這樣一來,我們又產生了一個更低的“口■”,矛盾。這就是說,星號方塊所在行一直沒被消去。但這也是不可能的,因為實際迴圈區內是一個新陳代謝、以舊換新的更替過程,每一行最後都是會被消除的。
   [url=http://www.tgbus.com/image.html?url=http://www.tgbus.com/image.html?url=http://ps3.tgbus.com/UploadFiles/201111/20111106114351940.jpg][img]http://ps3.tgbus.com/UploadFiles/201111/20111106114351494.jpg[/img][/url]
  接下來,考慮命題P(n+1)。要想讓“S”形方塊佔據通道n的格子,只有圖5這四種情況。但是,由於我們之前證明了通道n中不能存在“口■”,因此在這個“S”形方塊落下之前,星號方塊都是已經有了的了。注意到,每一個“S”形方塊的下落都致使“■口”形結構的減少,但第一種情形除外——它消除了一個“■口”形結構,但在其上方帶來了一個新的,使得“■口”形結構個數保持不變。沒有哪種情形能夠增加“■口”的個數。但是,通道n的“■口”形結構個數應該是恒定的,因為它在一個迴圈區裡。因此,只有第一種情況才能夠被接受。
  因此,僅含有“S”形方塊的迴圈只有一種情況——“S”形方塊在各個通道內重疊,填滿並消除若干行後回到初始狀態。實際迴圈區內的每個通道都是一個模樣:底下是0個或多個“■■”,頂部一個“■口”。注意,最右側那個通道的最頂端是一個“■口”,右邊這個空白一輩子也不可能用“Z”形方塊填上。也就是說,在一個隻含“S”形方塊的迴圈區內,必然會有某一行,它的最右側是一個“■口”,它保證了該行不能僅用“Z”形方塊消掉。如圖6所示,箭頭所指的行無法單用“Z”形方塊消除,因為星號位置不可能用“Z”形方塊填充。
   [url=http://www.tgbus.com/image.html?url=http://www.tgbus.com/image.html?url=http://ps3.tgbus.com/UploadFiles/201111/20111106114351554.jpg][img]http://ps3.tgbus.com/UploadFiles/201111/20111106114351305.jpg[/img][/url]
  下面我們給出遊戲機害死人的演算法:
  1. 不斷給出“S”形方塊並顯示下一個方塊也為“S”,直到出現一個迴圈;
  2. 給一個“S”形方塊並顯示下一個方塊為“Z”;
  3. 不斷給出“Z”形方塊並顯示下一個方塊也為“Z”,直到出現一個迴圈;
  4. 給一個“Z”形方塊並顯示下一個方塊為“S”;
  5. 跳回1並重複執行。
   [url=http://www.tgbus.com/image.html?url=http://www.tgbus.com/image.html?url=http://ps3.tgbus.com/UploadFiles/201111/20111106114351227.jpg][img]http://ps3.tgbus.com/UploadFiles/201111/20111106114351431.jpg[/img][/url]
  這樣的話,玩家為什麼會無解呢?由上面的結論,在第1步後,遊戲區域中出現了一個不能用“Z”消除的行。即使再給你一個“S”形方塊,這一點仍然無法挽救,因為填充星號空格的唯一途徑就是插一個“S”進去,但這立即又產生了一個“Z”永遠放不進去的空位。然後,玩家就拿到了一大堆“Z”,最終必然會產生另一個迴圈,且這個迴圈區在剛才那個無法消去的行之上(迴圈區不可能包含一個不能消除的行,因為正如前面所說,一個實際迴圈區的所有行最終都是會被消掉的,這樣才可能迴圈)。這個迴圈區的最左邊那個通道將會產生一個“口■”結構,是“S”所不能消去的。於是,遊戲機又給出一大堆的“S”,最終使得兩種無法消去的行交替出現,直至Game Over。
  有兩點值得注意。一、雖然我們這裡假設遊戲機是有主觀能動性的,但事實上呢,即使方塊是隨機出的,如果你足夠倒楣的話,這個特殊的方塊序列可能恰好就讓你一個不錯地碰上了;雖然這種怪事的發生概率極低,但理論上說仍然是可能的,因此俄羅斯方塊終究不是玩不死的,總有一個時候會Game Over。二、這個結論可以直接擴展到場地為任意寬度的俄羅斯方塊遊戲。當場地寬為偶數時,上述證明同樣有效;當場地寬為奇數時,無窮多個方形方塊就可以直接幹掉玩家。

2012-1-17 19:42 w000186846
看帖就要回才有禮貌,感激您的分享。[url=http://www.wretch.cc/blog/gsk9683/] [/url] [url=http://www.wretch.cc/blog/ereruseyer/] [/url] [url=http://www.wretch.cc/blog/grewetset/] [/url] [url=http://www.wretch.cc/blog/urtrtuyrt/] [/url] [url=http://www.wretch.cc/blog/andy.andy18/] [/url] [url=http://www.wretch.cc/blog/bendybendy22/] [/url] [url=http://www.wretch.cc/blog/cakemoonc/] [/url] [url=http://www.wretch.cc/blog/directordirector12/] [/url] [url=http://www.wretch.cc/blog/emaremar45/] [/url] [url=http://www.wretch.cc/blog/zoom98987/] [/url] [url=http://www.wretch.cc/blog/fanny9195/] [/url] [url=http://www.wretch.cc/blog/aojdh8b/] [/url] [url=http://www.wretch.cc/blog/bojdh8b/] [/url] [url=http://www.wretch.cc/blog/bpydd6c/] [/url] [url=http://www.wretch.cc/blog/copy7h/] [/url] [url=http://album.blog.***/fannyfanny24/] [/url] [url=http://www.wretch.cc/blog/sjow5k/] [/url] [url=http://www.wretch.cc/blog/kegp2t/] [/url] [url=http://www.wretch.cc/blog/tdjpew8d/] [/url] [url=http://www.wretch.cc/blog/lpdq4h/] [/url] [url=http://www.wretch.cc/blog/juytr8k/] [/url] [url=http://www.wretch.cc/blog/s5r6g7/] [/url] [url=http://www.wretch.cc/blog/kdgl98d/] [/url] [url=http://www.wretch.cc/blog/j703920153/] [/url] [url=http://www.wretch.cc/blog/t104934467/] [/url] [url=http://www.wretch.cc/blog/l468736937/] [/url] [url=http://www.wretch.cc/blog/fannyfanny24/] [/url] [url=http://www.wretch.cc/blog/fanny52078/] [/url] [url=http://www.wretch.cc/blog/m122230906/] [/url] [url=http://www.wretch.cc/blog/r900947529/] [/url] [url=http://www.wretch.cc/blog/e770269649/] [/url] [url=http://www.wretch.cc/blog/l969672798/] [/url] [url=http://www.wretch.cc/blog/o948768148/] [/url] [url=http://www.wretch.cc/blog/s106626797/] [/url] [url=http://www.wretch.cc/blog/n545013811/] [/url] [url=http://www.wretch.cc/blog/w608691875/] [/url] [url=http://www.wretch.cc/blog/w441267510/] [/url] [url=http://www.wretch.cc/blog/r136263496/] [/url] [url=http://www.wretch.cc/blog/z013281582/] [/url] [url=http://www.wretch.cc/blog/j911129895/] [/url] [url=http://www.wretch.cc/blog/v122058740/] [/url] [url=http://www.wretch.cc/blog/w457936316/] [/url] [url=http://www.wretch.cc/blog/d594324704/] [/url] [url=http://www.wretch.cc/blog/g042035119/] [/url] [url=http://www.wretch.cc/blog/g691818942/] [/url] [url=http://www.wretch.cc/blog/p983723245/] [/url] [url=http://www.wretch.cc/blog/u801069370/] [/url] [url=http://www.wretch.cc/blog/d799897572/] [/url] [url=http://www.wretch.cc/blog/q900946528/] [/url] [url=http://www.wretch.cc/blog/t236825295/] [/url] [url=http://www.wretch.cc/blog/f747450576/] [/url] [url=http://www.wretch.cc/blog/u261981471/] [/url] [url=http://www.wretch.cc/blog/j873393464/] [/url] [url=http://www.wretch.cc/blog/o025f5238u/] [/url] [url=http://www.wretch.cc/blog/f549m8980f/] [/url] [url=http://www.wretch.cc/blog/g246t1471s/] [/url] [url=http://www.wretch.cc/blog/g800a1868p/] [/url] [url=http://www.wretch.cc/blog/r09433435w/] [/url] [url=http://www.wretch.cc/blog/q244o52022/] [/url] [url=http://www.wretch.cc/blog/y837232458/] [/url] [url=http://www.wretch.cc/blog/c243925932/] [/url] [url=http://www.wretch.cc/blog/w000186846/] [/url] [url=http://www.wretch.cc/blog/q675032956/] [/url] [url=http://www.wretch.cc/blog/p691585382/] [/url] [url=http://www.wretch.cc/blog/i930161325/] [/url] [url=http://www.wretch.cc/blog/e609803608/] [/url] [url=http://www.wretch.cc/blog/f067378973/] [/url] [url=http://www.wretch.cc/blog/m459128003/] [/url] [url=http://www.wretch.cc/blog/c947529939/] [/url] [url=http://www.wretch.cc/blog/q525905694/] [/url] [url=http://www.wretch.cc/blog/b470697720/] [/url] [url=http://www.wretch.cc/blog/d448278700/] [/url] [url=http://www.wretch.cc/blog/z234270852/] [/url] [url=http://www.wretch.cc/blog/c001578476/] [/url] [url=http://www.wretch.cc/blog/t761429660/] [/url] [url=http://www.wretch.cc/blog/h541488458/] [/url] [url=http://www.wretch.cc/blog/z503836485/] [/url] [url=http://www.wretch.cc/blog/b2j2n8e23r/] [/url] [url=http://www.wretch.cc/blog/o6j4q9q47u/] [/url] [url=http://www.wretch.cc/blog/c5d7s3e53f/] [/url] [url=http://www.wretch.cc/blog/k0b8v3r72x/] [/url] [url=http://www.wretch.cc/blog/b4q4j2v59y/] [/url] [url=http://www.wretch.cc/blog/v7z3i7294b/] [/url] [url=http://www.wretch.cc/blog/f8y3m25781/] [/url] [url=http://www.wretch.cc/blog/s5t3v55993/] [/url] [url=http://www.wretch.cc/blog/m0t6l8x478/] [/url] [url=http://www.wretch.cc/blog/m937657148/] [/url] [url=http://www.wretch.cc/blog/x902170481/] [/url] [url=http://www.wretch.cc/blog/z5o1i6462f/] [/url] [url=http://www.wretch.cc/blog/hzz2w2805k/] [/url] [url=http://www.wretch.cc/blog/ufc5y4t460/] [/url] [url=http://www.wretch.cc/blog/s0y1a55269/] [/url] [url=http://www.wretch.cc/blog/d1y9x0z57k/] [/url] [url=http://www.wretch.cc/blog/fsp6m9j18q/] [/url] [url=http://www.wretch.cc/blog/cxt0f65636/] [/url] [url=http://www.wretch.cc/blog/cwh6i4746s/] [/url] [url=http://www.wretch.cc/blog/vjr1z9f47g/] [/url] [url=http://www.wretch.cc/blog/ark9z6a12c/] [/url] [url=http://www.wretch.cc/blog/cdc1q7647z/] [/url] [url=http://www.wretch.cc/blog/fic5w7o01s/] [/url] [url=http://www.wretch.cc/blog/blg9e6y23v/] [/url] [url=http://www.wretch.cc/blog/unv1r1o26l/] [/url] [url=http://www.wretch.cc/blog/fpn4r0k44x/] [/url] [url=http://www.wretch.cc/blog/ndd7w2o280/] [/url] [url=http://www.wretch.cc/blog/aev9c4792b/] [/url] [url=http://www.wretch.cc/blog/xny5m17318/] [/url] [url=http://www.wretch.cc/blog/i9z7t2p62v/] [/url] [url=http://www.wretch.cc/blog/cpr4j2w59y/] [/url] [url=http://www.wretch.cc/blog/w2a3j7394c/] [/url] [url=http://www.wretch.cc/blog/sml8z7n23j/] [/url] [url=http://www.wretch.cc/blog/qsq2t41890/] [/url] [url=http://www.wretch.cc/blog/ofw7o9158b/] [/url] [url=http://www.wretch.cc/blog/c4p1n7b601/] [/url] [url=http://www.wretch.cc/blog/srl3r6c49c/] [/url] [url=http://www.wretch.cc/blog/bek8v0h169/] [/url] [url=http://www.wretch.cc/blog/p8w6g4q45i/] [/url] [url=http://www.wretch.cc/blog/wpr6z0d94z/] [/url] [url=http://www.wretch.cc/blog/tjs6f8h90s/] [/url] [url=http://www.wretch.cc/blog/jjp5z45765/] [/url] [url=http://www.wretch.cc/blog/n7r8i22844/] [/url] [url=http://www.wretch.cc/blog/qqb2g2k78a/] [/url] [url=http://www.wretch.cc/blog/otw9z8k54f/] [/url] [url=http://www.wretch.cc/blog/o8m5w7q72h/] [/url] [url=http://www.wretch.cc/blog/s8m8m9k72s/] [/url] [url=http://www.wretch.cc/blog/mfp2m5s70m/] [/url] [url=http://www.wretch.cc/blog/hry8k4c15z/] [/url] [url=http://www.wretch.cc/blog/mok3m1l47k/] [/url] [url=http://www.wretch.cc/blog/tuq4y5d07r/] [/url] [url=http://www.wretch.cc/blog/n8f4d4g27t/] [/url] [url=http://www.wretch.cc/blog/esm9i8680e/] [/url] [url=http://www.wretch.cc/blog/pgj3i4f010/] [/url] [url=http://www.wretch.cc/blog/sac1z40628/] [/url] [url=http://www.wretch.cc/blog/mbd3p9i07j/] [/url] [url=http://www.wretch.cc/blog/nbs0t8m807/] [/url] [url=http://www.wretch.cc/blog/xlt2b9h58i/] [/url] [url=http://www.wretch.cc/blog/l5u3j0o46q/] [/url] [url=http://www.wretch.cc/blog/aaz0n6236w/] [/url] [url=http://www.wretch.cc/blog/jxp2n99567/] [/url] [url=http://www.wretch.cc/blog/i7k7g78815/] [/url] [url=http://www.wretch.cc/blog/gmb1i6f14j/] [/url] [url=http://www.wretch.cc/blog/obp1d8u97w/] [/url] [url=http://www.wretch.cc/blog/pjh0a5z945/] [/url] [url=http://www.wretch.cc/blog/m2xq250o4f/] [/url] [url=http://www.wretch.cc/blog/l8en03dg6p/] [/url] [url=http://www.wretch.cc/blog/x2hx05xu74/] [/url] [url=http://www.wretch.cc/blog/x9ek27cp8g/] [/url] [url=http://www.wretch.cc/blog/u3uu56mh37/] [/url] [url=http://www.wretch.cc/blog/x7d670h58w/] [/url] [url=http://www.wretch.cc/blog/q0ku25kn8w/] [/url] [url=http://www.wretch.cc/blog/n82i61ig3q/] [/url] [url=http://www.wretch.cc/blog/l4x473v830/] [/url] [url=http://www.wretch.cc/blog/d76789zu7k/] [/url] [url=http://www.wretch.cc/blog/c4rt38fa6m/] [/url] [url=http://www.wretch.cc/blog/d61b266x36/] [/url] [url=http://www.wretch.cc/blog/s955l0502s/] [/url] [url=http://www.wretch.cc/blog/w56178710s/] [/url] [url=http://www.wretch.cc/blog/g324u8224x/] [/url] [url=http://www.wretch.cc/blog/o82688624q/] [/url] [url=http://www.wretch.cc/blog/l946t9827g/] [/url]

頁: [1]


Powered by Discuz! Archiver 5.5.0  © 2001-2006 Comsenz Inc.