7.000 Zombies überfordern die Engine: Offensichtlicher Menschensieg, totaler Systemstillstand

7.000 Zombies überfordern die Engine: Offensichtlicher Menschensieg, totaler Systemstillstand

SpieleentwicklungRustAlgorithmenSystemarchitektur

Quellen:HN + web research

Die Partie auf dem Bildschirm steht in Zug 58 still. Auf der einen Spielfeldseite drängen sich 7.258 Zombies, während der verteidigende Spieler nur noch 31 Lebenspunkte besitzt. Ein Angriff mit gerade einmal 16 Zombies würde das Match sofort beenden. Stattdessen friert die Regel-Engine für einen Einzelschritt 35 Sekunden lang ein – nur um am Ende zaghaft einen einzigen Zombie nach vorne zu schicken, der den Gegner anstupst.

Diese bizarre Szene erlebte der Entwickler Levi Neuwirth beim Testen von Arcana, einer in Rust geschriebenen Regel-Engine für Magic: The Gathering (MTG), mit der KI-Algorithmen evaluiert werden sollten. Er schickte 64 Archetyp-Decks in 403.200 automatisierte Partien. Am Ende stießen neun Durchläufe an das Zwei-Stunden-Limit und wurden vom System zwangsweise abgebrochen.

Der Code enthielt keinerlei Endlosschleifen. Was das System in die Knie zwang, war die den Spielmechaniken innewohnende exponentielle Explosion. Als tausende Kreaturen gleichzeitig das Feld fluteten, fraß die mikroskopische Totalüberprüfung schlagartig sämtliche Rechenleistung auf.

Dass Magic mathematisch turing-vollständig ist, wurde bereits vor Jahren bewiesen. Doch die praktische Software-Implementierung ist eine völlig andere ingenieurtechnische Herausforderung. Ein Mensch erkennt den Sieg in Sekundenbruchteilen, doch die Engine muss für jede einzelne Kreatur das gesamte Spielfeld neu scannen. Wenn ein Spieler ruft „Alles greift an!“, entstehen im Code Millionen kombinatorischer Verzweigungen.

Acht Landfunde erzeugen 6.000 Schädlinge: Der exponentielle Ausbruch

Magic: The Gathering erschien 1993. Jede Karte trägt eigene Regeln, die Basisregeln jederzeit überschreiben können. Wenn mehrere Karten mit Kaskadeneffekten zusammentreffen, geraten Zahlenwerte blitzschnell außer Kontrolle.

Die Karte „Skute-Schwarm“ (Scute Swarm) ist ein Paradebeispiel. Jedes Mal, wenn ein Land ins Spiel kommt, erzeugt sie eine Kopie von sich selbst. Aus einer werden zwei, aus zwei vier – jede Aktion verdoppelt den Bestand.

In den Tests traf sie auf Lebenspunkte-Generierer und Spielstein-Verdoppler. Nach acht aufeinanderfolgenden Landfunden wimmelten 6.561 Schwärme auf dem Feld. Der Lebenspunktestand des Spielers kletterte auf 26.240. Ein normales Spiel startet bei 20 Punkten; dieser Wert sprengte die Grenzen traditioneller Kartenspiele völlig.

Vergleich der Wachstumskurven Abb.: Exponentielles Wachstum im Vergleich zwischen Scute Swarm und Lilianas Emblem; jede Hauptskaleneinheit steht für eine Verzehnfachung. Quelle: Levi Neuwirth

Sitzen sich Menschen am Spieltisch gegenüber, legen sie zwei Würfel auf die Karte, um tausende Tokens darzustellen. Ein Softwareprogramm hingegen muss im Speicher für alle 6.561 Entitäten eigenständige Datenstrukturen instanziieren.

35 Sekunden pro Zug: Verdopplungsmechanik frisst Speicher auf

Ein Insektenschwarm ist zwar gefährlich, lässt sich aber mit einem einzigen Flächenzauber auslöschen. Was die Engine wirklich lahmlegte, war die ultimative Fähigkeit der Planeswalkerin Liliana. Diese Fertigkeit hinterlässt außerhalb des Spielfelds ein unzerstörbares Emblem.

Die Regel des Emblems ist denkbar kurz: Zu Beginn deines Endsegments erzeugst du X Zombie-Spielsteine, wobei X gleich der Anzahl deiner Zombies plus zwei ist. In jeder Runde verdoppelt sich die Zombieanzahl plus zwei. Nach nur acht Auslösungen summierten sich 510 Zombies auf dem Feld.

Selbst wenn der Gegner das Feld leerfegt, bleibt das Emblem in der Kommandozone unangetastet. Im nächsten Zug erscheinen zwei neue Zombies, und die Verdopplungskette startet von vorn. Diese unzerstörbare Selbstvermehrung wurde zum Albtraum des Regelsystems.

Neuwirth analysierte die eingefrorene Partie Frame für Frame. In Zug 52 dauerte die Abwicklung eines einzigen Emblem-Triggers 1,72 Sekunden. In Zug 54 stieg die Zeit auf 7,78 Sekunden. In Zug 56 schoss sie auf 35,15 Sekunden empor.

Zustandsabwicklungszeit Abb.: Mit jeder Verdopplung der Zombies auf dem Feld stieg die Abwicklungszeit pro Zustandsschritt um etwa das 4,5-Fache. Quelle: Levi Neuwirth

Verdoppelte sich die Zahl der Zombies, vervierfachte sich die Abwicklungsdauer um den Faktor 4,5 – ein überlinearer Rechenkollaps. Jedes Mal, wenn eine neue Kreatur das Feld betritt, muss die Engine das gesamte Spielfeld durchlaufen und alle passiven Fähigkeiten prüfen. Tausende Objekte interagieren paarweise miteinander und verwandeln die Regelprüfung in einen Rechensumpf.

7.000 Zombies auf dem Feld, Suchbudget reicht nur für einen

In Zug 58 erreichte die Zombiehorde 7.258 Einheiten. Der Verteidiger hatte nur noch 31 Lebenspunkte und keine ausreichenden Blocker. Ein Vorstoß von 16 Zombies mit 32 Schadenspunkten hätte die Partie augenblicklich entschieden.

Genau hier geschah das Absurde: Nach langem Nachdenken schickte die KI lediglich einen einzelnen Zombie mit Stärke 2 in den Angriff. Er tippte eine gegnerische Kreatur harmlos an. Mit einer gewaltigen Übermacht von über 7.000 Einheiten verzichtete die dominierende Seite freiwillig auf den sicheren Sieg.

Partie-Replay Abb.: Replay-Ansicht von Zug 58 mit 7.234 Zombies in einem Stapel gegen einen Gegner mit 31 Lebenspunkten. Quelle: Levi Neuwirth

Die Ursache lag in der Schutzlogik des Zuggenerators. Wenn tausende Kreaturen mehrere Ziele attackieren können, explodiert der kombinatorische Raum astronomisch. Um Timeouts zu verhindern, hatte der Entwickler ein Limit von 1.024 Kandidatenzügen fest im Code verankert.

Der Generator listete Einzelangriffe prioritär auf. Bei 7.258 Zombies füllten bereits die Varianten einzelner Angreifer das gesamte Kontingent von 1.024 Zügen vollständig aus. Gruppenangriffe und kollektive Vorstöße lagen weiter hinten in der Warteschlange und wurden gar nicht erst generiert.

In Runde 44 mit 58 Kreaturen wurden 229 Züge berechnet, darunter vier koordinierte Mehrfachangriffe. In Runde 50 stieß der Generator an die Obergrenze, und Züge mit mehreren Angreifern sanken auf null. Die Schutzlogik gegen das Einfrieren blendete ausgerechnet die Siegesoptionen vollständig aus.

Menschliche Intuition vs. Millionen Rechenverzweigungen

Ein menschlicher Spieler nähert sich dieser Situation vollkommen anders. Selbst bei zehntausend Zombies zählt niemand einzelne Laufwege aus. Da die Gesamtangriffskraft die gegnerischen Lebenspunkte bei Weitem übersteigt, beendet ein Generalangriff das Spiel in konstanter Zeit O(1).

Computerprogrammen fehlt diese Makroabstraktion. Die Engine folgte stur der Mikroperspektive und zerlegte jede Entität akribisch in Datenstrukturen. Bei wenigen Kreaturen garantiert diese erschöpfende Traversierung absolute Regelpräzision.

Überschreitet die Objektzahl jedoch den Schwellenwert, schlägt die mikroskopische Erschöpfung in eine lähmende Last um. Die Summe kleinster legaler Schleifen saugt die gesamte Prozessorleistung auf. Der Rechner wurde nicht dümmer; er verfing sich schlicht in bedeutungslosen Mikrodetails.

Zwischen theoretischer Vollständigkeit und praktischer Machbarkeit klafft eine tiefe Kluft. Magic erlaubt es Karten, Kernregeln beliebig zu verändern, was dem Spiel seine enorme Vielfalt verleiht. Trifft diese Freiheit jedoch auf exponentielle Vervielfachung, steuert die Regelsimulation unweigerlich auf den Abgrund zu.

Ein 500-Permanents-Schutzschalter rettet das Experiment

Damit die automatisierten Massentests weiterlaufen konnten, baute Neuwirth eine pragmatische Notbremse ein: Befinden sich mehr als 500 bleibende Karten auf dem Spielfeld, wird die Partie als unkontrollierbar eingestuft und als Unentschieden gewertet.

Nach Aktivierung des Schutzschalters liefen die Tests wieder reibungslos. Partien, die zuvor zwei Stunden feststeckten, beendete das System nun in 0,16 Sekunden, sobald die Marke von 576 Objekten erreicht war. Grenzen für unendliche Expansion zu definieren, erwies sich als unverzichtbare Maßnahme zur Sicherung des Gesamtfortschritts.

Auch tiefergehende architektonische Umbauten laufen bereits. Die Engine speichert häufig geprüfte Zustände im Cache, um Spielfeld-Neuscans bei Token-Erzeugungen zu vermeiden. Zudem priorisiert der Zuggenerator Makroentscheidungen wie den Generalangriff direkt in der Warteschlange.

Der Zwischenfall mit 7.258 Zombies markiert die Grenze zwischen Regelsimulation und echter Intelligenz. Während Computer mikroskopische Pfade in rasender Geschwindigkeit abarbeiten, trifft der Mensch dank ganzheitlicher Intuition sofort ins Schwarze. Wenn Regeln unbegrenztes exponentielles Wachstum zulassen, gerät Code ohne Makroperspektive außer Kontrolle. Er berechnet jede minimale Verzweigung fehlerfrei – und ertrinkt im selbst erzeugten Zahlenmeer.

Weiterführende Links:

  • Levi Neuwirth Original-Blogbeitrag
  • Arcana Open-Source-Regel-Engine Repository
  • Hacker News Diskussion