Der erste Warrior

KI-Hinweis: Dieser Text entsteht mit Unterstützung von KI-Systemen, wird aber vor der Veröffentlichung redaktionell geprüft und verantwortet.

Core War ist ein Spiel, bei dem zwei Programme im Speicher eines virtuellen Rechners gegeneinander antreten. Sie laufen abwechselnd, sie können sich gegenseitig überschreiben, und wer als Einziger noch läuft, hat gewonnen.

Das klingt nach viel. Dein erstes Programm wird eine einzige Zeile lang sein.

A. K. Dewdney hat das Spiel 1984 in seiner Kolumne im Scientific American vorgestellt. Die Programme heißen seither Warriors, und die Sprache, in der man sie schreibt, heißt Redcode.

Die Arena

Der Kampfplatz heißt Core. Es ist ein Speicher aus 8000 Zellen, der zu einem Ring geschlossen ist: Hinter Zelle 7999 kommt wieder Zelle 0. Es gibt kein Ende, von dem man fallen könnte, und keine Wand, in die man laufen könnte.

Jede Zelle enthält genau eine Instruktion. Nicht Daten und Programm getrennt — sondern beides in denselben Zellen. Das ist der Grund, warum das Spiel überhaupt funktioniert: Was für den einen Warrior Programm ist, ist für den anderen ein Ziel.

Beide Warriors werden an zufälligen Stellen in diesen Ring geladen. Keiner weiß, wo der andere steckt. Dann läuft abwechselnd je eine Instruktion: erst der eine, dann der andere, immer im Wechsel.

Der Core ist nicht leer

Hier lohnt es sich, einen Moment innezuhalten, weil dieser Punkt in vielen Einführungen fehlt.

Man stellt sich den Speicher gern als leeres Feld vor, in dem die beiden Programme wie zwei Figuren stehen. So ist es nicht. Jede der 8000 Zellen ist vor Rundenbeginn schon gefüllt — und zwar mit dieser Instruktion:

DAT.F   $0, $0

DAT ist die einzige Instruktion in Redcode, die nichts tut. Und genau das ist tödlich: Ein Prozess, der auf ein DAT läuft, stirbt. Sofort und endgültig.

Der Core ist also kein leeres Feld, sondern ein Minenfeld, das komplett aus Minen besteht. Die beiden Warriors sind die einzigen Stellen, an denen etwas anderes steht als der sichere Tod.

Daraus folgt die erste Regel des Spiels: Ein Warrior verliert nicht dadurch, dass der Gegner ihn trifft. Er verliert dadurch, dass er auf ein DAT läuft. Der Gegner muss nur dafür sorgen, dass das passiert — meistens, indem er selbst DAT-Instruktionen dorthin schreibt, wo der andere gerade arbeitet.

Der kleinste Warrior der Welt

Und hier ist er. Der Imp, ebenfalls von Dewdney:

;redcode-94nop
;name Imp
;author A. K. Dewdney

        MOV.I   $0, $1

        END

Eine Instruktion. Übersetzt heißt sie:

Kopiere die Instruktion, die hier steht, in die Zelle direkt dahinter.

MOV steht für move, also kopieren. Das .I bedeutet: die ganze Instruktion kopieren, nicht nur einen Teil davon. $0 ist „diese Zelle hier", $1 ist „eine Zelle weiter".

Was dabei passiert

Nehmen wir an, der Imp liegt in Zelle 100.

1. Der Prozess steht auf Zelle 100 und führt MOV.I $0, $1 aus. Er kopiert den Inhalt von Zelle 100 nach Zelle 101. In Zelle 101 steht jetzt ebenfalls MOV.I $0, $1.
2. Danach rückt der Prozess eine Zelle weiter, wie immer nach einer Instruktion, die keinen Sprung enthält. Er steht nun auf Zelle 101 — auf der Kopie, die er soeben selbst geschrieben hat.
3. Die tut dasselbe: Sie kopiert sich nach Zelle 102. Der Prozess rückt vor. Und so weiter.

Der Imp wandert also durch den Core, indem er sich fortlaufend vor sich selbst kopiert und der Kopie hinterherläuft. Er hinterlässt dabei eine Spur seiner selbst — und weil der Core ein Ring ist, kommt er nach 8000 Schritten wieder dort an, wo er losgelaufen ist.

Er ist nicht schnell und nicht clever. Aber er ist außerordentlich schwer totzukriegen, und das aus einem einfachen Grund: Wer ihn überschreiben will, trifft eine Zelle, die der Imp längst verlassen hat.

Imp gegen Imp

Was passiert, wenn zwei Imps aufeinandertreffen? Über 200 Runden gemessen:

Runde-Ergebnis: 0 Siege : 0 Siege : 200 Unentschieden

Zweihundertmal Unentschieden. Kein einziger Sieg auf beiden Seiten.

Das ist kein langweiliges Ergebnis, sondern ein aufschlussreiches: Zwei Imps können einander nichts anhaben. Beide laufen, bis die Zeit abläuft. Ein Unentschieden entsteht in Core War immer dann, wenn nach einer festgelegten Zahl von Zyklen — hier 80.000 — noch beide Warriors leben.

Merk dir das: Unentschieden sind in Core War kein Ausweichergebnis, sondern ein Werkzeug. Ein Warrior, der nicht gewinnen kann, aber zuverlässig überlebt, sammelt trotzdem Punkte. Wir kommen darauf zurück.

Ein Gegner

Damit etwas passiert, braucht es jemanden, der zuschlägt. Der klassische Gegner ist der Dwarf, auch er von Dewdney:

;redcode-94nop
;name Dwarf
;author A. K. Dewdney

step    EQU     4

start   ADD.AB  #step, $bomb
        MOV.I   $bomb, @bomb
        JMP.A   $start
bomb    DAT.F   #0, #0

        END     start

Vier Zeilen, und eine völlig andere Idee. Der Dwarf läuft nicht herum. Er bleibt stehen und wirft Bomben:

• ADD.AB #step, $bomb — zählt 4 auf den Zeiger, der in der letzten Zeile steckt. Das Ziel wandert also bei jedem Durchlauf vier Zellen weiter.
• MOV.I $bomb, @bomb — kopiert die DAT-Instruktion aus der letzten Zeile dorthin, wohin der Zeiger gerade zeigt. Das ist der Bombenwurf.
• JMP.A $start — zurück an den Anfang. Endlosschleife.
• DAT.F #0, #0 — die Bombe selbst. Eine Instruktion, die tötet, wer auf sie läuft.

Der Dwarf sät also im Abstand von vier Zellen DAT-Instruktionen über den gesamten Core. Er weiß nicht, wo der Gegner ist. Er muss es auch nicht wissen — er streut einfach so lange, bis der andere in eine Mine läuft.

Warum vier und nicht eins? Weil der Dwarf mit Schrittweite 4 den Core viermal schneller einmal abdeckt. Warriors sind fast immer länger als vier Zellen, also trifft er sie trotzdem. Ein Muster, das dir in Core War immer wieder begegnen wird: Man opfert Gründlichkeit für Geschwindigkeit — bis zu dem Punkt, an dem man anfangen würde, den Gegner zu verfehlen.

Dass ausgerechnet 4 die beste Wahl ist, lässt sich nachmessen. Am Ende dieser Seite steht die Messreihe dazu — mit einem überraschenden Nebenbefund.

Das erste Duell

Imp gegen Dwarf, 2000 Runden:

Der Imp gewinnt kein einziges Mal.

Das ist kein Ausrutscher und keine Frage der Feinabstimmung. Es ist strukturell, und der Grund ist so einfach wie lehrreich: Der Imp schreibt nur MOV-Befehle in den Core. MOV ist eine ganz normale, ausführbare Instruktion — wer darauf läuft, stirbt nicht, sondern führt sie aus. Der Imp besitzt keine einzige Möglichkeit, jemanden zu töten.

Er kann überleben. Gewinnen kann er nicht.

Der Dwarf dagegen gewinnt in knapp einem Viertel der Fälle. In den übrigen drei Vierteln läuft der Imp einfach weiter, bis die Zeit abläuft — der Dwarf trifft zwar irgendwann die Zelle, auf der der Imp gerade steht, aber der ist meistens längst weitergezogen.

Warum 2000 Runden und nicht 200?

Weil die Ladepositionen bei jeder Runde neu ausgewürfelt werden und das Ergebnis davon abhängt. Zehn Läufe mit je 200 Runden ergaben für den Dwarf zwischen 42 und 51 Siege — je nachdem, wie die Würfel fielen. Das sind 21 bis 25,5 Prozent, also eine Schwankung von viereinhalb Prozentpunkten allein durch Zufall.

Bei 2000 Runden lagen drei Läufe innerhalb von 0,7 Prozentpunkten beieinander.

Merk dir das für später: Ein einzelner kurzer Messlauf sagt in Core War sehr wenig. Wer zwei Warriors über 200 Runden vergleicht und einen Unterschied von drei Prozentpunkten sieht, hat wahrscheinlich nur den Zufall gemessen. Schritt 4 des Lernpfads geht dieser Frage genauer nach.

Die Punkte dazu

Aus Siegen und Unentschieden wird eine Punktzahl. Die übliche Formel lautet:

Punkte = (Siege × 3 + Unentschieden) × 100 / Runden

Für unser Duell heißt das:

• Dwarf: (471 × 3 + 1529) × 100 / 2000 = 147,1
• Imp: (0 × 3 + 1529) × 100 / 2000 = 76,5

Der Dwarf liegt also gut doppelt so hoch. Aber sieh dir an, woher die Punkte des Imps kommen: ausschließlich aus Unentschieden. Ein Warrior, der nie gewinnt, steht trotzdem nicht bei null.

Genau diese Rechnung ist der Grund, warum Core War so tief ist. Es gibt nicht eine beste Strategie, sondern mehrere, die sich gegenseitig kontern — und Überleben ist eine davon.

Selbst ausprobieren

Du brauchst dafür nur einen Simulator. Der Klassiker ist pMARS, es gibt ihn für Windows, Linux und macOS. Leg die beiden Warriors als imp.red und dwarf.red an und ruf auf:

pmars -s 8000 -c 80000 -p 8000 -l 100 -d 100 -r 2000 imp.red dwarf.red

Die Parameter sind die Einstellungen des Standard-Regelwerks: 8000 Zellen, 80.000 Zyklen pro Runde, höchstens 8000 Prozesse, Warriors bis 100 Zellen Länge, Mindestabstand 100 Zellen beim Laden, 2000 Runden.

Deine Zahlen werden nicht exakt mit den obigen übereinstimmen — die Ladepositionen sind zufällig. In der Nähe sollten sie aber liegen: rund ein Viertel Siege für den Dwarf, der Rest Unentschieden, null Siege für den Imp. Die null ist die einzige Zahl, die exakt stimmen muss; sie ist strukturell.

Probier danach, step EQU 4 im Dwarf auf andere Werte zu setzen. Über 2000 Runden gegen den Imp gemessen:

Zwei Dinge daran sind bemerkenswert.

Dewdneys 4 ist tatsächlich die beste Wahl. Nicht ungefähr, sondern deutlich. Wer damals ohne Simulator und ohne Messreihen auf diesen Wert kam, hatte ein gutes Gespür.

Bei Schrittweite 6 verliert der Dwarf plötzlich 656-mal — gegen einen Gegner, der ihn gar nicht töten kann. Er bringt sich also selbst um. Der Grund liegt in der Ringstruktur: Der Bombenzeiger wandert in Sechserschritten durch 8000 Zellen und kommt dabei irgendwann bei der eigenen MOV-Zeile vorbei — die er dann mit einer Bombe überschreibt. Bei Schrittweite 4 kann das nicht passieren: Dort trifft der Zeiger von den eigenen vier Zellen nur die Bombe selbst, und die Bombe auf sich selbst zu kopieren bleibt folgenlos.

Merk dir diesen Effekt. Dass ein Warrior sich an der eigenen Konstruktion umbringt, ist in Core War kein Kuriosum, sondern einer der häufigsten Fehler überhaupt — und einer, den man ohne Nachmessen nicht bemerkt.

Was du jetzt weißt

• Der Core ist ein Ring aus 8000 Zellen, vollständig gefüllt mit tödlichen DAT-Instruktionen.
• Ein Warrior stirbt, wenn er auf ein DAT läuft — nicht dadurch, dass er „getroffen" wird.
• Der Imp überlebt durch Bewegung und kann nicht gewinnen.
• Der Dwarf gewinnt durch blindes Bombardieren des gesamten Speichers.
• Unentschieden bringen Punkte. Überleben ist eine Strategie.
• Eine einzige geänderte Konstante kann einen Warrior dazu bringen, sich selbst zu zerstören. Nachmessen schlägt Nachdenken.

Im nächsten Schritt sehen wir uns Redcode genauer an: welche Befehle es gibt, was die Endungen wie .I und .AB bedeuten — und warum ausgerechnet diese Endung wichtiger ist als der Befehl davor.

Imp und Dwarf stammen von A. K. Dewdney und wurden 1984 im Scientific American veröffentlicht. Alle Zahlen auf dieser Seite wurden mit pMARS unter dem Standard-Regelwerk '94nop über je 2000 Runden nachgerechnet.

← Core-War-Übersicht