Haben Sie auch schon Stunden damit verschwendet, »Candy Crush« zu spielen? Falls ja, sind Sie keine Ausnahme. Das 2012 veröffentlichte Spiel war lange Zeit das beliebteste auf Facebook und auch in der ersten Jahreshälfte von 2023 wurde es mehr als 106 Millionen Mal heruntergeladen – was es zur am zweithäufigsten gedownloadeten Spiele-App machte. Und auch Prominente haben sich schon als Candy-Crush-Fans geoutet, so der Linken-Politiker Bodo Ramelow, der während politischer Konferenzen und Besprechungen an seinem Handy spielte, weil es ihn nach eigenen Angaben entspanne.

Das Prinzip des Spiels ist simpel: Auf einem Spielbrett, das mit verschiedenfarbigen Süßigkeiten gefüllt ist, muss man versuchen, waagerechte oder senkrechte Ketten aus mindestens drei gleichen Süßigkeiten zu bilden, indem man benachbarte Süßigkeiten miteinander vertauscht. Sobald eine solche Kette entsteht, verpuffen die dazugehörigen Süßigkeiten und die darüber befindlichen Feldelemente rücken nach. Die verschiedenen Level des Spiels haben unterschiedliche Zielsetzungen, eine besteht zum Beispiel darin, eine Mindestanzahl an Ketten mit einer Höchstzahl an Vertauschungen zu bilden. Durch seine Einfachheit erfreut sich das Spiel großer Beliebtheit – vielleicht sogar etwas zu sehr: Candy Crush steht in der Kritik, ein hohes Suchtpotenzial zu haben.

»Die mathematische Betrachtung von Candy Crush kann genauso süchtig machen wie das Spielen selbst«Toby Walsh, Informatiker

»In gewisser Weise kann die mathematische Betrachtung von Candy Crush genauso süchtig machen wie das Spielen selbst«, schrieb der Informatiker Toby Walsh von der University of New South Wales in Sydney in einem Artikel bei »American Scientist«. Ihn hat das Candy-Crush-Fieber im Jahr 2014 ebenfalls gepackt. Doch anders als die meisten anderen Fans hat er nicht versucht, das Spiel möglichst gut zu meistern. Er wollte verstehen, wie komplex Candy Crush aus mathematischer Sicht ist. Sprich: Wie schwer ist es für einen Computer, mit maximal k Vertauschungen mindestens s Dreier-Süßigkeiten-Ketten zu bilden?

Wie komplex können Spiele sein?

Um Aufgaben in verschiedene Schwierigkeitsgrade einzuteilen, haben theoretische Informatiker so genannte Komplexitätsklassen eingeführt. Zum Beispiel gibt es Probleme, bei denen man nicht weiß, ob ein Computer jemals zu einer Antwort gelangt: Er könnte bis in alle Zeit weiterrechnen, ohne zu einem Ergebnis zu kommen. Das sind gewissermaßen die schwierigsten aller Aufgaben. Wie sich 2019 herausstellte, gehört das Kartenspiel »Magic: The Gathering« zu dieser Kategorie. Es können Spielsituationen entstehen, bei denen sich nicht mehr entscheiden lässt, welcher der Spieler (selbst unter optimalen Bedingungen) gewinnen wird.

Um die Komplexität eines Spiels zu bestimmen, muss man wissen, ob sich ein vorgeschlagener Lösungsweg schnell überprüfen lässt. Wenn man Ihnen zum Beispiel ein ausgefülltes Sudoku-Rätsel vorsetzt, können Sie ohne viel Aufwand prüfen, ob die Lösung korrekt ist. Wenn die Rechenzeit eines Computers bei der Überprüfung nur polynomiell mit der Größe der Aufgabe zunimmt, dann gehört das Problem zur Klasse »NP«. Das ist auch bei Candy Crush der Fall: Indem man Schritt für Schritt die verschiedenen Vertauschungen nachvollzieht, die angeblich s Süßigkeiten-Ketten entstehen lassen, kann man schnell entscheiden, ob die Behauptung stimmt.

Dass ein Problem in NP liegt, sagt aber nichts darüber aus, wie schwer oder einfach es ist, es zu lösen. Denn innerhalb von NP liegen auch Probleme der Kategorie »P«: Hier wächst die Rechenzeit eines Computers zur Lösung nur polynomiell mit der Größe der Aufgabe an. Das klingt zunächst ähnlich wie die Definition zu NP – mit dem wesentlichen Unterschied, dass es sich hierbei um die Rechendauer zur Lösung einer Aufgabe und nicht zur Überprüfung einer Aufgabe handelt. Probleme in P lassen sich also sowohl effizient lösen als auch überprüfen. Zu diesen »einfachen« Problemen gehört zum Beispiel das Sortieren einer Liste. Die Rechenzeit wächst im ungünstigsten Fall mit dem Quadrat der Listengröße an. Wenn sich die Anzahl der Elemente verdoppelt, muss man also viermal so lange warten, bis die Liste sortiert ist. Das klingt zwar nach viel Zeit, ist aber aus Sicht von Informatikern kein großes Problem. Daher gelten Aufgaben, die in P liegen, als einfach: Sie lassen sich in der Regel mit nicht allzu viel rechnerischem Aufwand lösen.

Demgegenüber gibt es in NP aber auch Probleme, die sich nur schwer lösen lassen. Die Rechenzeit wächst für die Lösung exponentiell mit der Größe des Problems an. »Auf meinem Computer habe ich ein Programm, das ein paar Stunden braucht, um die optimale Streckenführung für zehn Lkws zu finden. Aber für 100 Lkws würde das gleiche Programm mehr als die Lebenszeit des Universums benötigen«, erklärte Walsh in seinem Artikel. Optimale Routenplanungen zählen zu Paradebeispielen für NP-schwere Probleme – so werden Aufgaben genannt, die mindestens so schwer zu lösen sind wie die komplexesten Probleme aus NP.

Angesichts dieser Definitionen leuchtet ein, dass man fast immer Verallgemeinerungen eines Spiels betrachten muss, um dessen Komplexität zu bewerten. Denn Schach, Go oder auch Candy Crush besitzen eine durch das Spielfeld festgelegte Größe. Daher untersuchen theoretische Informatiker in diesen Fällen häufig fiktive Erweiterungen der Spiele, bei denen das Spielbrett und die Anzahl der Figuren, Steine oder Süßigkeiten beliebig groß sein können.

Wie hängt Candy Crush mit logischen Aussagen zusammen?

Walsh stellte sich die Frage, zu welcher Komplexitätsklasse Candy Crush zählt. Kann ein Computer ohne viel Aufwand immer eine effiziente Lösungsstrategie finden? In diesem Fall wäre Candy Crush in P. Oder hat auch ein Rechner mit dem Finden der passenden Vertauschungen zu kämpfen? Um das herauszufinden, hat Walsh eine gängige Methode aus der theoretischen Informatik verwendet, die so genannte Reduktion. Um zu beweisen, dass ein Problem NP-schwer ist, muss man zeigen, dass sich alle anderen Probleme in NP darauf zurückführen lassen. Das heißt: Aufgabe A ist NP-schwer, falls ein Lösungsalgorithmus von A auch alle anderen NP-Probleme lösen kann.

Damit hatte Walsh einen Plan. Es gibt nämlich einen ganzen Satz aus bekannten Problemen, die in NP liegen und NP-schwer sind. Wenn er zeigen könnte, dass sich eines davon auf Candy Crush zurückführen lässt, hätte er bewiesen, dass das beliebte Süßigkeiten-Spiel auch aus mathematischer Sicht komplex ist. Walsh entschied sich dafür, das NP-schwere »3-SAT-Problem« mit Candy Crush zu vergleichen.

3-SAT ist eine Aufgabe aus der Logik, bei der zu beurteilen ist, ob eine Verkettung logischer Ausdrücke korrekt ist – oder zu einem Widerspruch führt. Ein Beispiel für eine solche Verkettung ist: x ∧ ¬x. Auf den ersten Blick sieht das kompliziert aus. Die Aussage lässt sich aber schnell übersetzen, wenn man weiß, dass »∧« für »und gleichzeitig« steht sowie »¬« eine Negation darstellt. Damit lässt sich die Aussage übersetzen zu: x und gleichzeitig nicht x. Die Aufgabe besteht nun darin, der Variablen x den Wert »wahr« oder »falsch« zuzuordnen, damit die Gesamtaussage wahr wird (also keinen Widerspruch erzeugt). In diesem Fall ist das unmöglich, denn man erhält entweder: wahr und gleichzeitig nicht wahr (für x = wahr) oder falsch und gleichzeitig nicht falsch (für x = falsch). Beide Aussagen ergeben keinen Sinn: Etwas kann nicht wahr und falsch zugleich sein. Daher ist diese Verkettung von Ausdrücken nicht erfüllbar.

3-SAT-Probleme umfassen verkettete Aussagen, die jeweils drei Variablen direkt miteinander verknüpfen, in Form von: (a₁ ∨ b₁ ∨ c₁) ∧ (a₂ ∨ b₂ ∨ c₂) ∧ … ∧ (a_n ∨ b_n ∨ c_n). Ein Computer muss versuchen, den Variablen Wahrheitswerte zuzuordnen, damit die Gesamtaussage wahr wird. Und wie sich herausstellt, ist diese Aufgabe NP-schwer. Mit wachsender Aufgabenlänge steigt die benötigte Rechenzeit exponentiell an.

Walsh musste nun zeigen, dass sich jedes 3-SAT-Problem in Candy Crush darstellen lässt und dass eine Lösung des Candy-Crush-Problems automatisch das dazugehörige 3-SAT-Problem löst. Dafür hat er Konfigurationen von Süßigkeiten im Candy-Crush-Spiel mit Variablen und logischen Verknüpfungen im 3-SAT-Problem identifiziert. Auf diese Weise konnte der Informatiker beweisen, dass sich jede logische Aussage in Form von 3-SAT durch eine geeignete Verteilung von Süßigkeiten in Candy Crush darstellen lässt.

»Das könnte ein Grund dafür sein, warum das Spiel so süchtig macht. Wäre es so einfach zu lösen wie Tic-Tac-Toe, wäre es nicht annähernd so fesselnd«Toby Walsh, Informatiker

Und das funktioniert folgendermaßen: Wenn man als Spieler eine bestimmte Vertauschung vornimmt, interpretiert Walsh das mit dem Zuweisen eines Wahrheitswerts für eine Variable, zum Beispiel: »Variable 1 ist falsch.« Jede Vertauschung verändert das Spielfeld. Zudem kann sie eine Dreier-Süßigkeiten-Kette entstehen lassen, die sogleich verschwindet und andere Süßigkeiten auf dem Spielfeld nachrücken lässt. Hat man ebenso viele Vertauschungen vorgenommen, wie das entsprechende 3-SAT-Problem an Variablen besitzt, lässt sich aus den übrigen Süßigkeiten auf dem Spielfeld ablesen, ob die zugehörige 3-SAT-Aussage zugewiesenen wahr oder falsch ist. Zum Beispiel: Falls das Feld in der dritten Reihe, zweite Spalte nach allen Vertauschungen einen gelben Zitronen-Drop enthält, entspricht das der Aussage »wahr«. Walsh hat im Vorfeld die Süßigkeiten so auf dem Spielfeld verteilt, dass der gelbe Zitronen-Drop nur dann in diesem Feld landet, falls die Mindestanzahl an Dreier-Süßigkeiten-Ketten gebildet wurde – und die Candy Crush-Aufgabe somit erfolgreich gelöst wurde.

So konnte Walsh im März 2014 beweisen, dass Candy Crush NP-schwer ist – und damit auch aus mathematischer Sicht kompliziert. Das mag vielleicht beruhigend sein, wenn man wieder einmal bei einem Candy-Crush-Level scheitert. Diese Komplexität hat aber auch ihren Reiz, wie Walsh schreibt: »Das könnte ein Grund dafür sein, warum das Spiel so süchtig macht. Wäre es so einfach zu lösen wie Tic-Tac-Toe, wäre es nicht annähernd so fesselnd.«