© Jesse-lee Lang, 123RF.com

Singen musste zum Glück niemand. Doch auch Würfeln gerät zur Kunst, wenn es darum geht, einem Robot so viel Intelligenz einzuhauchen, dass er seine Gegner wirksam aussticht. Ein Zwischenbericht.

Seither rotieren die Achtkern-Server der Redaktion bei Loads bis 130, um die Ergebnisse der Endrunde auszuwürfeln. Die Finalisten stellt das Linux-Magazin im kommenden Heft vor, lüftet aber bereits vorab Geheimnisse und Erkenntnisse in Sachen Statistik und Strategie der Implementationen.

Die eingereichten Sprachen decken ein sehr weites Spektrum ab, von Klassikern der Programmierkunst wie C, Perl und Tcl über moderne Hochsprachen wie Java und C++ bin hin zu einer Menge Skriptsprachen wie Ruby oder Python. PHP scheint durchaus eine nennenswerte Fangemeinde außerhalb der Webprogrammierung zu besitzen, denn ein halbes Dutzend Bots leben in dieser Sprache.

Wie in Babel

Sie zeigen, dass entgegen verbreiteter Vorurteile auch strukturierter PHP-Code möglich ist. Der Teilnehmer »notdefine« von Thomas Eimers in Abbildung 1 beispielsweise hat eine abstrakte Klasse »dice_game« geschrieben, die er mit »dice_game_logic« überlädt und so die Strategie verfeinert. Diesen Ansatz haben mehrere Leser gewählt. Zeitweise waren mehrere Dutzend Varianten eines einzelnen Bots auf dem Trainingsplatz, um ihre Strategien auszuprobieren und zu verbessern [2].

Abbildung 1: Allen Gehässigkeiten aus dem Java-Lager zum Trotz: Mit PHP lässt sich auch objektorientierter Code schreiben, wie »notdefine« von Thomas Eimers zeigt.

Eine ganze Reihe von Entwicklern hauchten ihren Bots eine Menge Ratschläge ein, die plausibel erscheinen und damit einen großen Vorteil haben: Sie sind für Menschen einfach zu verstehen. So betrachten sie den Abstand der eigenen Punkte zu denen des Gegeners, würfeln wagemutiger, wenn sie ohnehin weit zurückliegen oder agieren vorsichtiger, sollte der Mitspieler weit zurückliegen.

Viele Entwickler beschäftigte weiterhin die Frage, wie weit sie wohl mit dem Wohlwollen der Stochastik kommen, indem sie ihr Glück herausfordern. So ist der großen Mehrheit zwar bekannt, dass ein einzelner Wurf bei einem fairen Würfel den folgenden Wurf nicht beeinflusst. Dennoch werden Sequenzen komplett ohne die gefährliche Sechs immer unwahrscheinlicher, umso länger sie geraten. Wer zu konservativ handelt und zu früh abgibt, verschenkt möglicherweise Punkte. Umgekehrt riskieren Glücksritter mit langen Wurffolgen ihr mühsam erworbenes Guthaben.

Martin Sigloch näherte sich empirisch diesem Problem und simulierte eine große Zahl an Spielen, bei denen je ein Bot bei einer festen Zahl an erworbenen Punkten abgibt. Für dieses Limit trug er wie in Abbildung 2 auf, wie viele Runden er benötigte, um zu 50 Punkten zu gelangen und wie häufig dies gelang. Wer die feine grüne Linie verfolgt, stellt fest, dass bei etwa 16 Punkten Limit pro Runde die geringste Zahl von Runden zum Sieg notwendig waren.

Abbildung 2: Martin Sigloch gab in einer Simulation seinen Bots unterschiedliche Limits vor und beobachtete, wie viele Runden sie damit zum Sieg benötigten. Die Häufigkeit trug er in der Abbildung auf und zeichnete grün den Mittelwert ein.

Klare Grenzen ziehen

Die Wahrscheinlichkeit, drei Würfe ohne Sechs zu überstehen, liegt bei knapp 58 Prozent, bei vier Würfen nur noch bei etwa 48 Prozent. Da der Erwartungswert eines Wurfes, der keine Sechs enthält, bei exakt drei Augen liegt, deutet diese schon auf die Größenordnung der empirisch ermittelten Werte hin.

Tatsächlich haben Teilnehmer im Wiki in großen Versuchsreihen bemerkenswert gute Ergebnisse mit der Bot-Strategie »ROLL16« erzielt, die nach 16 Würfen abgibt. Die Variante »ROLL17« wagt noch einen Punkt mehr. Noch ist das Kopf-an-Kopf-Rennen zwischen diesen beiden Varianten nicht entschieden.

Trotz der simplen Aufgabenstellung erkannten die meisten Teilnehmer schnell, dass es keine einfache Lösung für das Problem gibt, selbst dann nicht, wenn Rechenzeit und Speicherplatz keine Rolle spielen [3]. Das Kernproblem ist nämlich der Gegner: Es ist ziemlich schwer vorauszusagen, wie der sich verhalten wird. Wie einige Teilnehmer in zahlreichen Diskussionen im Wettbewerbs-Wiki bemerkten, ist es relativ einfach, “optimal” gegen “optimale” Bots zu spielen. Einige mutmaßten sogar ein großes Unentschieden aller Bots, die schließlich bei hinreichend vielen Spielen jeweils die Hälfte gewönnen und verlören.

Kühle Mathematik

Dazu entwarfen viele große Tabellen, die oft einen ähnlichen Aufbau hatten: Sie teilten das Spiel zunächst in Runden ein, die damit beginnen, dass ein Spieler entweder beginnt oder vom Mitspieler den Würfel erhält. Die Runde endet mit einer Sechs, bei der Spieler alle in der Runde erwürfelten Punkte verliert, oder sie endet damit, dass er abgibt. Die Punktzahl des eigenen Bots und die des Mitspielers bei Beginn einer Runde ergeben die beiden Indices einer 50×50-Tabelle. In sie tragen einige Bots ein, wie viele Augen sie in dieser Runde würfeln wollen, bevor sie abgeben.

Die Bot-Designer haben eine erstaunliche Anzahl von Verfahren entwickelt, um diese Tabellen zu füllen. So kamen feste Werte nach Gefühl, aber auch viele iterative Methoden zum Einsatz, die Gewinnwahrschenlichkeiten ausgehend von bekannten Randwerten solange für die einzelnen Zustände berechneten, bis diese sich nicht mehr nennenswert änderten. Das hatte auch Folgen für die Implementation. Die Umsetzung von »asinusphi«, entwickelt von Andreas Barth, besteht beispielsweise aus einem C-Programm, das einmalig rund 50 Sekunden durchläuft und schließlich den Quelltext eines 377 KByte großen Tcl-Skriptes erzeugt. Dieses Skript läuft dann während des eigentlichen Spieles ab und beschränkt sich weitgehend auf das Nachschlagen in der großen Tabelle (siehe Zeile 45 in Listing 1).

01 #
02 # play.tcl - asinusphi von Andreas Barth
03 #
04 [...]
05 # decide wheather to roll the dice or save the points
06 proc decide {mN mS yN yS} {
07         set index [expr (($mN*($mN+1))/2+$mS)*1275+($yN*($yN+1))/2+$yS]
08         if {$index > 1625625} {set index 1625625}
09         if {$index == 134428} {return 1}
10         if {$index == 134461} {return 1}
11 
12 # [ ... 7200 Zeilen gelöscht ... ]
13 
14         if {$index >= 1574625 && $index <= 1574645} {return 1}
15         if {$index >= 1574648 && $index <= 1574652} {return 1}
16         if {$index >= 1575900 && $index <= 1575914} {return 1}
17         if {$index >= 1575916 && $index <= 1575920} {return 1}
18         if {$index == 1575927} {return 1}
19         if {$index >= 1577175 && $index <= 1577189} {return 1}
20         if {$index == 1577195} {return 1}
21         if {$index >= 1578450 && $index <= 1578459} {return 1}
22         if {$index == 1578464} {return 1}
23         if {$index >= 1579725 && $index <= 1579730} {return 1}
24         if {$index == 1579734} {return 1}
25         if {$index >= 1581000 && $index <= 1581002} {return 1}
26         if {$index == 1582275} {return 1}
27         return 0
28 }
29 
30 [ ... Verbindungsaufbau gelöscht ... ]
31 
32 # So much for that, now the real thing...
33 while {1>0} {
34         set command [split [gets $iog]]
35         set cmd [lindex $command 0]
36 
37         if {[string compare -nocase $cmd $CMD_DENY]==0} {
38                 # we are kicked off :-(
39                 exit -2
40         } elseif {[string compare -nocase $cmd $CMD_TURN]==0} {
41                 if {$state==$STATE_YOURS} {
42                         # You must have saved your points
43                         set yS $yN
44                 }
45                 # it is our turn so we need to make a decision
46                 if {[decide $mN $mS $yN $yS] == 1} {
47                         # We save
48                         set mS $mN
49                         putsf $iop "$CMD_SAVE"
50                         set state $STATE_YOURS
51                 } else {
52                         # We roll the dice
53                         putsf $iop "$CMD_ROLL"
54                         set state $STATE_ROLL
55                 }
56 [...]

Solche Tabellen können auch andere Sprachen gut verarbeiten. Der Bash-Sed-Hybride »sainthuck« von Christian Gießen etwa sucht sich mit dem Stream-Editor die richtigen Zahlen aus einer Tabelle. Zwar ohne Tabelle, dafür aber auch ohne Bash kommt der Bot »bsd« (“Bots sind Dumm”) von Matthias Intemann dar. Er implementiert seine Spiellogik komplett mit Hilfe von Sed-Kommandos (siehe Listing 2).

01 #! /bin/sed -nuf
02 
03 # Dieses Skript ist zum Vergnügen entstanden und kann gerne von jedem
04 # frei genutzt und modifiziert werden. Auch ist das Stellen unter
05 # allgemein als frei akzeptierte Lizenzen explizit erlaubt, so
06 # gewährleistet ist, dass die Namen aller Autoren genannt bleiben.
07 # Autor dieser Datei: Matthias Intemann, 2010
08 
09 # Anmeldung in der ersten Zeile nach einem Alaaf!
10 1 s/^HELO .+/AUTH bsd - Bots Sind Dumm 1.0/p
11 
12 # Sind wir bei einem Wurf dran, dann zählen wir...
13 # Für jeden Wurf ein w anhängen und für jedes Auge ein r voranstellen, 
14 # wenn wir an der Reihe sind. Bei 6 müssen wir alles zurücksetzen - 
15 # erst vormerken, dann ausführen.
16 /^THRW [1-6]/ {
17  x
18  /WirSindDran/ {
19   s/.*/&w/
20   x
21   s/^THRW 1.*/r/
22   s/^THRW 2.*/rr/
23   s/^THRW 3.*/rrr/
24   s/^THRW 4.*/rrrr/
25   s/^THRW 5.*/rrrrr/
26   s/^THRW 6.*/Reset/
27   G
28   s/n//
29   s/.*Reset.*//
30  }
31  h
32  d
33 }
34 
35 # Sollen wir Würfeln? Hier ist die Intelligenz!
36 # Zunächst erkennen wir den Endspurt (wir ab 47 und Gegner ab 40 oder
37 # Fall ohne Hoffnung bei < 10 zu >=42...).
38 /^TURN 4[789] 4[0-9]|^TURN [0-9] 4[2-9]/ {
39  x
40  s/^$/WirSindDran/
41  s/WirSindDran/WirSindDranMitEndspurt/
42  x
43 }
44 # Und nun werten wir alles an Information aus.
45 # Würfeln, wenn Endspurt, Augen<16, Würfe<7. Sonst abgeben und löschen.
46 /^TURN [0-9]+ [0-9]+/ {
47  g
48  s/^$/WirSindDran/
49  h
50  s/.*WirSindDranMitEndspurt.*/ROLL Endspurt!/
51  s/r{16}.*/SAVE Ausreichend Augen, danke./
52  s/.*w{7}/SAVE Oft genug geworfen, danke./
53  s/.*WirSindDran.*/ROLL Ich bekomme einfach nicht genug, weiter bitte./
54  p
55  /SAVE/ {
56   s/.*//
57   h
58  }
59  d
60 }
61 
62 # Alles hat ein Ende, nur wir haben zwei zur Wahl.
63 /^WIN .+ .+|^DEF .+ .+/ {
64  s/^WIN (.+) (.+)|^DEF (.+) (.+)/Spielende: 13 zu 24/w /dev/stderr
65  q 0
66 }
67 
68 # Bei mangelnder Gastfreundschaft ...
69 /^DENY/ {
70  w /dev/stderr
71  q 1
72 }
73 
74 # Sollten wir die Zeile nicht erkannt haben, ignorieren wir sie.

Mehrere Entwickler haben sich gefragt, ob die Entscheidungstabellen ein Muster enthalten, sodass sich daraus vielleicht ein einfacher Algorithmus ableiten ließe. Diese Hoffnung macht Joachim Breitner zunichte. Da er seine Ferien ohne Computer, aber mit dem Linux-Magazin verbrachte, näherte er sich dem Problem von der theoretischen Seite.

Die beste Strategie

Er teilte mit, er habe mittels Banachschem Fixpunktsatz bewiesen, dass seine Gewinnwahrscheinlichkeiten, die er mit einer rekursiven Gleichung beschrieb, auch dann nicht sinken, wenn der Gegner eine andere Strategie wählt. Um diese Ergebnisse zu visualisieren, renderte er nach seinem Urlaub anschließend mit Paraview [4] die Grenzfläche, ab der sich zu sichern lohnt (siehe Abbildung 3).

Abbildung 3: Joachim Breitner berechnete mit dem Banachschen Fixpunktsatz eine Grenzfläche, die die Punktzahl visualiert, ab der sich eine Konfiguration zu sichern lohnt. Die Abbildung zeigt, wie nichtlinear sich das Problem darstellt.

Diese theoretischen Ansätze haben jedoch einen Pferdefuß: Sie gehen davon aus, dass ihre Gegner so optimiert spielen wie sie selbst, was sich als gefährlicher Irrtum herausstellen könnte. Es zeigte sich, dass es – wie in anderen Ligen – darauf ankommt, bei schwachen Gegnern zu punkten und bei starken Gegnern so gut wie möglich zu verteidigen. Es gilt also, sich an den Mitspieler anzupassen. Das versuchen einige Bots, indem sie exotische Sprachen wie Haskell, Vala, Scheme oder Common Lisp verwenden.

Schwache Gegner schlagen

Einen anderen Ansatz verfolgt Adrian Leip mit seinem genetisch mutierten »kainunddolly«. Dazu verbindet er Aggressivität (“Kain”) und Klontechnik (“Dolly”). Er ließ seinen Bot in der Trainingsphase von einem »ROLL16« ausgehend mutieren (was übrigens nebenbei die endemische Nebenlinie »galapagos« hervorbrachte) und verpackte das Ergebnis in ein Bash-Skript. Ebenfalls mit Gentechnik befasste sich Wolfgang Rossner. Sein Java-Bot »genom2« besitzt ein neuronales Netz, das der Entwickler gegen »ROLL17« trainierte.

Einen völlig anderen Ansatz verfolgte die im Wiki “Chinesische Methode” getaufte Idee: Wenn sich ein Bot identifizieren ließe, der im Training gut spielt, könnte der Chinese versuchen, ihn zu imitieren, am einfachsten durch Abhören. In eine ähnliche Richtung geht der Gedanke von Torsten Harling, der anfragte, ob sein Bot Code verwenden dürfe, der nach 31 Würfen immer zwei Zahlen ausschließen kann. Sein Bot würde dann immer weiter würfeln, wenn er sich sicher wäre, keine Sechs zu würfeln.

Mögen die Spiele beginnen

Die Jury erlaubte solche Ansätze im Grundsatz, behielt sich jedoch vor, keine Angaben über den Zufallszahlengenerator im späteren Turnier zu machen. Die Voraussage gelingt nämlich nur, wenn der Gameserver mit »rand()«-Funktion der Glibc Modulo 6 würfelt [5]. Ohnehin diskutierten viele Teilnehmer die Bedeutung des Glücks zum Sieg (siehe Kasten “Zufälliger Zufall”).

Damit dies keine zu große Rolle spielt, sollen alle Bots die Chance erhalten, hinreichend oft gegen alle anderen Gegner zu spielen, und zwar jeweils gleich oft als erster und als zweiter Spieler. Derjenige mit Vorhand hat nämlich einen kleinen Vorteil gegenüber demjenigen Bot, der nachzieht.