您是否曾花費數小時玩 Candy Crush Saga？您並不孤單。自 2012 年釋出以來，它一直是 Facebook 和移動裝置上最受歡迎的遊戲之一。該應用程式在 2023 年上半年下載次數超過 1.06 億次，成為該期間下載次數第二多的遊戲應用（僅次於一款名為 Subway Surfers 的遊戲）。
該遊戲的原理很簡單：在一個佈滿各種顏色糖果的網格上，您嘗試透過相互交換相鄰的糖果來形成至少三個相同糖果的水平或垂直鏈。一旦形成這樣的鏈，其中的糖果就會消失，並且它們上方的其他糖果會向下移動。遊戲的不同關卡有不同的目標。例如，一個目標是僅使用最多次數的交換來形成至少最少數量的鏈。部分由於其簡單性，該遊戲廣受歡迎。也許它有點太受歡迎了。Candy Crush 因具有高度成癮性而受到批評——而且可能不僅僅是對其玩家而言。
“在某些方面，至少對於數學家來說，將 Candy Crush 視為數學問題可能與玩它一樣讓人上癮，”澳大利亞新南威爾士大學的計算機科學家 Toby Walsh 在為American Scientist撰寫的一篇文章中寫道。早在 2014 年，他就被 Candy Crush 的漏洞所困擾。但與大多數其他粉絲不同，他並沒有盡力掌握這款遊戲。相反，他想從數學的角度理解 Candy Crush 有多複雜。換句話說，如果給定機器最大交換糖果次數，計算機形成一定數量的三糖果鏈有多難？
支援科學新聞報道
如果您喜歡這篇文章，請考慮透過以下方式支援我們屢獲殊榮的新聞報道 訂閱。透過購買訂閱，您正在幫助確保未來能夠繼續講述關於塑造我們當今世界的發現和想法的具有影響力的故事。
遊戲能有多複雜？
為了將數學任務劃分為不同的難度級別，理論計算機科學家引入了所謂的複雜度類別的概念。例如，存在一些計算問題，尚不清楚計算機是否會得出答案；它可以無限期地計算而不會得出答案。從某種意義上說，這些是所有任務中最困難的。事實證明，紙牌遊戲Magic: The Gathering屬於此類：可能會出現遊戲情況，即使在最佳條件下，也無法確定哪個玩家會獲勝。
要確定遊戲的複雜度，您需要知道是否可以快速檢查提出的解決方案。例如，如果您面前有一個已完成的數獨謎題，您可以毫不費力地確認解決方案是否正確。如果計算機檢查解決方案的計算時間僅隨任務大小呈多項式增長，則該問題屬於非確定性多項式時間 (NP) 類——該類別描述了某些數學問題的複雜性。Candy Crush 也是如此：透過追蹤據稱建立糖果鏈的各種交換步驟，您可以快速判斷顯示的結果（被消除的糖果鏈的數量）是否正確。
但問題在於 NP 類中並不能說明解決問題有多難或多容易。這是因為多項式時間 (P) 類別中的簡單問題（另一個複雜度類別）也位於 NP 類中。對於 P 類問題，計算機解決問題的計算時間僅隨問題大小呈多項式增長。乍一看，這聽起來與 NP 的定義相似——本質區別在於，這裡我們討論的是解決任務的計算時間，而不是檢查其解決方案的計算時間。因此，P 類問題可以有效地解決和檢查。這些“簡單”的問題包括對列表進行排序。在最壞的情況下，計算時間隨列表大小的平方增長。因此，如果元素數量翻倍，您必須等待四倍的時間才能對列表進行排序。雖然這聽起來很耗時，但從計算機科學家的角度來看，這並不是什麼大問題。因此，位於 P 類中的任務被認為是簡單的：通常可以毫不費力地解決它們。
相比之下，NP 類中存在難題。解決它們所需的計算時間隨問題大小呈指數增長。“在我的臺式電腦上，我有一個程式需要幾個小時才能找到 10 輛卡車的最佳路線，並證明該解決方案是最佳的。但是對於 100 輛卡車，同樣的程式將花費比宇宙壽命更長的時間，”沃爾什在他的文章中解釋道。最佳路線是“NP-hard”問題的典型例子，NP-hard 問題是指至少與 NP 中最複雜的問題一樣難以解決的任務。
鑑於這些定義，幾乎總是必須檢視關於遊戲的概括才能評估其複雜性，這是有道理的。畢竟，像國際象棋、圍棋甚至 Candy Crush 這樣的遊戲都有由可用遊戲場地確定的大小。在這種情況下，理論計算機科學家經常研究遊戲的虛構擴充套件，其中棋盤和棋子或棋子的數量（或糖果）可以任意大。
Candy Crush 與邏輯陳述有何關係？
沃爾什提出了 Candy Crush 屬於哪個複雜度類的問題。計算機是否總是可以毫不費力地找到遊戲的有效解決方案策略？如果是這樣，Candy Crush 將屬於 P 類。或者計算機是否也難以找到要交換的合適糖果？沃爾什使用一種稱為“歸約”的常見計算機科學技術來檢驗這個問題。為了證明一個問題是 NP-hard 問題，必須證明 NP 中的所有其他問題都可以歸約到它。也就是說，如果問題 A 的解決方案演算法也可以解決所有其他 NP 問題，則問題 A 是 NP-hard 問題。
沃爾什有一個解決此問題的計劃。即，存在一整套已知問題，這些問題既屬於 NP 類又是 NP-hard 問題。如果他能證明其中一個問題類似於 Candy Crush——它們可以相互對映——他將證明這款流行遊戲從數學角度來看是複雜的。沃爾什選擇將 NP-hard 的“3-SAT 問題”與 Candy Crush 進行比較。
3-SAT 是邏輯中的一項任務，其中需要判斷邏輯表示式的連結序列或“連線”是否正確或導致矛盾。此類連線的一個示例是：x ∧ ¬x。乍一看，這看起來很複雜。但是，如果您知道“∧”代表“並且同時”，“¬”代表否定，則可以快速翻譯該語句。因此，該語句可以翻譯為：x 並且同時非 x。現在的任務是為變數x分配“真”或“假”值，以使整個語句為真（換句話說，使其不產生矛盾）。在本例中，這是不可能的，因為您要麼得到真並且同時非真（對於 x = 真），要麼得到假並且同時非假（對於 x = 假）。這兩個語句都沒有意義：某件事不可能同時為真和為假。因此，此表示式的連線無法滿足。
3-SAT 問題涉及鏈式語句，每個語句都以 (a1 ∨ b1 ∨ c1) ∧ (a2 ∨ b2 ∨ c2) ∧ ... ∧ (an ∨ bn ∨ cn) 的形式直接連結三個變數。這裡符號“∨”表示“或”。計算機必須嘗試為變數分配真值，以便使整個語句為真。事實證明，此任務是 NP-hard 問題。隨著任務長度的增加，所需的計算時間呈指數增長。
沃爾什現在需要證明任何 3-SAT 問題都可以在 Candy Crush 中表示，並且解決 Candy Crush 問題會自動解決相關的 3-SAT 問題。為此，他將 Candy Crush 遊戲中的糖果配置與 3-SAT 問題中的變數和邏輯連線相匹配，以便某種糖果模式代表一個變數。透過這種方式，他能夠證明任何 3-SAT 形式的邏輯語句都可以透過 Candy Crush 中適當的糖果分佈來表示。
以下是它的工作原理：當玩家進行特定交換時，沃爾什將其解釋為為變數分配真值——例如，“變數 1 為假”。每次交換都會更改遊戲場地。此外，它還可以建立一條立即消失的三糖果鏈，從而使其他糖果可以向下移動到棋盤上。如果他們進行的交換次數與相應的 3-SAT 問題擁有的變數數一樣多，他們就可以從棋盤上剩餘的糖果中判斷相關的 3-SAT 語句是真還是假。例如，如果在所有交換之後，第三行第二列的方格包含黃色檸檬糖，則這對應於語句“真”。沃爾什預先在遊戲場地上分配了糖果，以便只有在形成最少數量的三糖果鏈時，黃色檸檬糖才會落入該欄位——因此 Candy Crush 任務已成功解決。
這就是沃爾什如何在2014 年 3 月證明 Candy Crush 是 NP-hard 問題，因此從數學角度來看是複雜的。如果您在另一個 Candy Crush 關卡中失敗，這可能會讓您感到欣慰。但這種複雜性也具有吸引力。正如沃爾什在American Scientist中寫道，“這種特性可能是使遊戲如此令人上癮的部分原因；例如，如果它像井字棋一樣容易解決，那麼它就不會那麼吸引人了。”
本文最初發表於Spektrum der Wissenschaft，並經許可轉載。