比想像中更困難－俄羅斯方塊

Original publish date:Nov 10, 2002

編輯 John C. H. Chen 報導

根據幾位電腦學家的研究，他們發現了俄羅斯方塊困難的原因。

大概有玩過電動玩具的人都玩過俄羅斯方塊，這個一堆形狀不同的方塊會源源不斷的自上方落下的遊戲。這個遊戲的規則極為簡單，不過卻是讓許多人手忙腳亂，但決不影響它自1985年發明以來一直受到大家喜愛。到底困難的原因何在？MIT的Erik Demaine給出了答案。

他們表示俄羅斯方塊類似於一種稱為NP-complete的問題，相類似的範例有推銷員問題(一個推銷員要如何用最短的時間走過所有的城市)。這種問題的解決需要把所有可能做過評估，然後再尋找最佳化解。這對於電腦而言就是考驗記憶體跟運算速度的時候。當在玩俄羅斯方塊的時候，玩家必須對所有可能進行嘗試，就算是沒有任何時間壓力，還是一件麻煩事，更不用說那種來有兩人對戰功能的情形了。所以要設計一種能快速有效玩俄羅斯方塊的邏輯運算幾乎是不可能的任務。

所以下次在玩俄羅斯方塊時，或許可以套句Demaine的話：我在解決一個很困難的問題。

原始論文
Demaine, E.D., Hohenberger, S. & Liben-Nowell, D. Tetris is hard, even to approximate. Preprint, (2002).

參考來源：

• Nature Science Update: Maths proves Tetris is tough

本文版權聲明與轉載授權資訊：

• 本文採用書面授權轉載模式，詳細著作權聲明與轉載規定請見 http://sciscape.org/copyright.php。