關於支援科學新聞業
如果您喜歡這篇文章，請考慮透過支援我們屢獲殊榮的新聞業 訂閱。透過購買訂閱，您正在幫助確保關於塑造我們今天世界的發現和想法的有影響力的故事的未來。
影片遊戲俄羅斯方塊是有史以來最受歡迎的電腦遊戲之一，也許部分原因是它的難度使其令人上癮。遊戲的目標是移動和旋轉下落的幾何形狀，以在遊戲板底部形成完整的行。現在科學家們已經用數學方法證明，由俄羅斯方塊的下落四格骨牌提出的問題是最難解決的問題之一，即使你知道接下來會出現哪些方塊。
馬薩諸塞理工學院的 Erik D. Demaine、Susan Hohenberger 和 David Liben-Nowell 確定俄羅斯方塊符合 NP 完全問題的條件。也就是說，雖然檢查問題的一個解決方案是否有效相對容易，但是沒有有效的方法來最佳化遊戲的任何目標。這些目標包括最大化消除的行數，最大化在失敗前成功放置的方塊數，最大化“俄羅斯方塊”（同時消除四行）的數量，以及在整個遊戲過程中儘可能保持網格的高度較低。而且在研究小組研究的模擬遊戲中，玩家提前知道所有即將到來的方塊——這種情況應該比真實情況更簡單，在真實情況中，隨機選擇的方塊會從螢幕頂部快速落下。
研究人員進一步發現俄羅斯方塊是一個 NP 難問題，這意味著它至少與任何其他 NP 問題一樣難以解決。“當你在玩俄羅斯方塊時，你實際上是在解決難題，”Demaine 說。有趣的是，另一個看似簡單但高度令人上癮的遊戲掃雷也是一個 NP 難問題。所以下次你在這兩個遊戲中失敗時，可以安慰自己，計算機可能也做得不會好多少。