© chriskuddl | ZWEISAM, Photocase.com

Obwohl er einfachen Regeln gehorcht, fordert der Würfelwettbewerb Lösungen heraus, die erst einmal in ein Programm gewandelt sein wollen. Die Implementation humanoider Vorgehensweisen konkurriert dabei mit Brute-Force-Algorithmen. Doch vor dem Showdown steht erst einmal Systempflege.

121 Bots tragen die Meisterschaft im Würfeln beim in Linux-Magazin 09/10 ausgelobten Wettbewerb gegeneinander aus [1]. Was erst als einfache Aufgabe erschien, entpuppte sich als ausgewachsene Logistikfrage. Dass der Wettbewerb die Rahmenbedingungen der Teilnahme vergleichsweise locker spezifiziert, bezahlte die Jury teuer mit dem Einrichten der Turnierumgebung. Allein das Extrahieren der Bots und das Sichten der Begleitschreiben forderte einige Zeit. Anschließend ging es darum, die Bots in einer einheitlichen Umgebung zu entpacken und die notwendige Software zu installieren.

Zwar haben sich die meisten Teilnehmer an die Vorgaben gehalten, die benötigten Debian-Pakete für einen aktuellen Ubuntu-Server anzugeben, aber einzelne baten auch darum, Softwarepakete aus Quell-Repositorys herunterzuladen und zu übersetzen. Manche Sprachen wie Haskell oder Ruby setzen zudem auf eigenen Bibliotheksverwaltungen. Inklusive Abhängigkeiten fanden insgesamt 299 neue Pakete für Compiler, Interpreter und Bibliotheken gegenüber der Standardinstallation ihren Weg auf den Server.

Die meisten Teilnehmer haben ein Makefile beigelegt, mit dem sich sowohl der Code übersetzen als auch der resultierende Bot starten ließ, sofern es sich um eine Compilersprache wie C oder Java handelte. Aber auch bei PHP, Perl oder Python kann das helfen, besonders wenn alle Programme gleichermaßen skriptgesteuert starten sollen.

Kontrahenten abschirmen

Jeder Bot bekam aus Sicherheitsgründen seinen eigenen Sandkasten, wenn auch keinen Sicherheitstrakt: Pro Teilnehmer gibt es auf dem Server einen eigenen Benutzer mit passenden Schreib- und Leserechten, damit niemand über Nachbars Zaun schielen kann, um dort Würfelgeheimnisse zu stehlen. Um die einzelnen Spieler von einem zentralen Verteiler aus zu starten, bekam die Konfigurationsdatei von Sudo eine Anpassung, die die Benutzerübergänge modellierte.

Verkleideter Gameserver

Bei einer anderen Konfigurationsfrage behalf sich die Redaktion mit einem Trick: Die meisten Einsendungen hatten den Host »wettbewerb.linux-magazin.de« und Port 3333 voreingestellt. Anstatt alle diese Angaben auf den zum Turnierbetrieb auserkorenen Mehrkernrechner zu ändern, trug sie in »/etc/hosts« einfach 127.0.0.1 für diesen Hostnamen ein. Durch den Betrieb auf Localhost versprach sie sich einen schnelleren Durchsatz.

Bei näherer Betrachtung war das aber gar nicht der limitierende Faktor: Spielten in der Vorrunde alle Bots in dem Tempo, das sie für richtig hielten, galt es nun die Spielpaarungen in eine deterministische Reihenfolge zu bringen, damit auch jeder gegen jeden antritt. Diese Serialisierung erwies sich als komplizierter als erwartet, zumindest wenn es darum geht, eine größere Anzahl von Matches parallel zu absolvieren.

Der vom Magazin-Leser Roman Held entwickelte Dice-or-Die-Server ist immerhin in der Lage, rund 120 Begegnungen auf einmal zu koordinieren. Da weder der Server noch das Würfelprotokoll Synchronisationsmechanismen zwischen den einzelnen Spielen vorsehen, muss der Turnierleiter abschätzen, ob eine Paarung die virtuellen bereits Würfelbecher in die Hand genommen hat, bevor er die nächsten beiden Kandidaten an den Tisch bittet. Dazu kommt die Erkenntnis, dass zu viele Lagen an Aufrufskripten ihren Tribut zollen: Ein Steuerskript wählt die Paarungen aus, ein zweites bereitet den UID-Übergang zu den individuellen Bots vor, ein Wrapper startet Make mittels »make game«, manchmal zunächst ein Netcat-Wrapper (siehe “Bash Bashing” in dieser Ausgabe), der dann einen Interpreter aufruft, der seinerseits schließlich das eigentliche Skript ausführt. Solche Stacks belegen viele Ressourcen, wie Abbildung 1 zeigt. Viel mehr als 16 parallele Bots sind kaum handhabbar.

Abbildung 1: Gut ausgelasteter Wettbewerbsort: Während des Turniermodus hat der Mehrkern-Server einiges zu tun. Tiefere Einkerbungen in der Lastkurve entstehen übrigens vorrangig durch einzelne Prozesse, die hängen und damit weitere Spielpaarungen blockieren.

Bots in Uniform

Die Alternative wäre ein expliziterer Aufruf der einzelnen Bots. Das erfordert aber ein wesentlich einheitlicheres Verhalten aller Bots, die sich gegenwärtig noch stark in Speicherverbrauch, Robustheit gegenüber kleineren Protokollverstößen der Gegner, der Menge und Art ihrer Ausgaben, Rückgabecodes und in ihrer Laufzeit unterscheiden. Brauchen die meisten Skripte gegen einen fixen Gegner nur einen Bruchteil einer Sekunde, so benötigt der langsamste Bot gegen einen direkt reagierenden Gegner über 6 Sekunden und noch einmal deutlich länger, wenn er gegen andere langsame Gegner spielt.

Das Limitieren von Ressourcen mit dem Shell-Builtin »ulimit« hat ironischerweise selbst Grenzen, da sich damit beispielsweise keine reale Laufzeit eines Prozesses begrenzen lässt [2]. Die Folge ist eine Verschränkung, wenn sich Bots gegenseitig einfach blockieren, aber selbst kaum CPU benötigen. Ein Job-Scheduler für diesen Zweck wäre erst zu entwickeln und anzupassen.

Weitere Stolpersteine sind Signale, die ein Bot sendet und die dafür sorgen, dass Shellskripte, die im Hintergrund ablaufen, zunächst wieder stoppen. Dies kann ein Subprozess mit einem ungewöhnlichen Rückgabewert sein, den dann der Make-Aufruf in Signale wandelt und die Verarbeitung anhält.

Um zu gewährleisten, dass keiner in einem durchgehenden Turnier den Betrieb aufhält, spielten alle Bots bis zum Redaktionsschluss noch in einem Modus, bei dem zufällige Paarungen gegeneinander antreten. Das Skript achtet darauf, dass jeder Teilnehmer annähernd ähnlich häufig zum Zuge kommt – eine Eigenschaft, die im reinen Trainingsbetrieb nicht gegeben war.

Einige Bots erledigen den Verbindungsaufbau und den Handshake schneller als andere: Die schnellsten 100 Bots brauchen im Schnitt nur 80 Millisekunden für ein Match gegen einen Referenzgegner. Die 20 langsamsten hingegen brauchen im Schnitt jedoch das 14-fache, nämlich über 1100 Millisekunden, der längste sogar über 5 Sekunden gegen die Referenz. Treffen zwei langsame Gegner aufeinander, verstärkt sich der Effekt noch. Bei 14 520 Paarungen summiert sich die Rechenzeit. Tabelle 1 stellt die Zwischenergebnisse von etwa zwei Turnierläufen dar.

Das Feld der Favoriten

Die Rangliste führt der in Perl entwickelte Bot »Toralf« von Entwickler Toralf Förster an (siehe Listing 1). Er setzt eine vergleichsweise einfache Strategie um, die er in den Zeilen 3 bis 6 formuliert: Niemals direkt wieder an den Gegner abgeben, eine Abwägung der Gewinnchancen vom eigenen Bot und des Gegners, etwas mehr Risiko im Angesicht der Ziellinie und dann, wenn das Glück bislang nicht so hold war, wie es es laut Statistik sein sollte. Viel mehr als ein paar Hilfskonstrukte, die die statistischen Daten des Spiels verwalten, enthalten die 326 Zeilen Code kaum. Das zeigt, was sich mit feiner Abstimmung der Parameter alles erreichbar ist.

01   ###################################################
03   # our rule set contains 4 rules :
05   # 1)    roll if it is the 1st throw
06   # 2)    roll if SAVE doesn't make sense
07   # 3)    roll if the finish is within $Mean distance
08   # 4)    roll if we've less than the $Mean
10   ###################################################
11   my $Action = "SAVE";          # defense programming
12 
13   # trivial, BTW it is subset of rule 4)
14   #
15   if ($t == 0)    {
16           $Action = "ROLL";
17           $Game{History} .= "t";
19   }
21   # use "<=" to not SAVE if our chance is not better
22   #
23   if ($pWin[$a1] <= $pWin[$a2] / (1 - $pWin[$a2])) {
24           $Action = "ROLL";
25           $Game{History} .= "c";
26 
27   }
28 
29   # use "<=" to include the border too
30   #
31   if (50 - $a1 <= ValueToPoints ($Mean)) {
32           $Action = "ROLL";
33           $Game{History} .= "f";
35   }
36 
37   # use "<" b/c getting the mean is sufficient enough
38   #
39   if ($a1 - $Saved < ValueToPoints ($Mean)) {
40           $Action = "ROLL";
41           $Game{History} .= "m";
42   }
43 
44   print $Socket "$Action", "n";
45   Log 4, "$Action", "n";

Einen ganz anderen Ansatz verfolgt der gegenwärtig Zweiplatzierte »genom2« von Leser Wolfgang Rossner. Er trainierte im Vorfeld ein neuronales Netz mit einem guten Dutzend Knoten und implementierte in Java ein Expertensystem, das aus dem Eingabetripel der eigenen Punkte, der Punkte des Spielers am Anfang seines Zuges und der Augenzahl des Gegners eine Empfehlung abgibt, ob der Bot weiterspielen soll oder nicht. Listing 2 zeigt den Kern dieser Idee, wobei die einzelnen Gewichte gegenüber dem Orginal aus Lesbarkeitsgründen auf zwei Nachkommastellen gekürzt sind. Ihre unmittelbare Bedeutung offenbart sich nicht, aber der Bot kommt damit offenbar zu guten Ergebnissen.

01 public class genom2 {
02    static class NN {
03       double   temperature;
04       int      depth;
05       int[]    layer;
06       double[] weight;
07 
08       NN(double t, int d, int[] l, double[] w) {
09          temperature = t; depth = d;
10          layer = l;       weight = w;
11       }
12       double sigmoid(double x) {
13          return (1.0 / (1.0 + Math.pow(2.7182818, -x / temperature)));
14       }
15       boolean wantToSave(int pts, int old, int opp) {
16          return evaluate(new double[] {pts, old, opp}) < 0.5;
17       }
18 
19       double evaluate(double[] input) {
20          int Weight = 0, Out = 0;
21          double[] cell = new double[20];
22          for (int i = 0; i < input.length; i++) cell[i] = input[i];
23          for (int level = 1; level < depth; level++) {
24             int In = Out;
25             Out += layer[level - 1];
26             for (int j = 0; j < layer[level]; j++) {
27                double s = weight[Weight++]; // bias
28                for (int i = 0; i < layer[level - 1]; i++)
29                   s += weight[Weight++] * cell[In + i];
30                   cell[Out + j] = sigmoid(s);
31             }
32          }
33          return cell[Out];
34       };
35     }
36 /* Das Neuronale Netz wurde offline und einem Genetischen Algorithmus,
37    gegen Roll17 trainiert, der die Weights evolviert */
38 static NN net5328=new NN(0.13, 3, /*layer*/ new int[] {3, 8, 1, }, new double[]  {
39  /* in1.1 */ -373.1,  /*w3_0*/ 108.8,  /*w3_1*/-255.6,  /*w3_2*/  -0.2,
40  /* in1.2 */   53.7,  /*w4_0*/   3.6,  /*w4_1*/   0.2,  /*w4_2*/  -0.6,
41  /* [...] */
42  /* in1.8 */    2.3, /*w10_0*/  5.6, /*w10_1*/  -0.1, /*w10_2*/  49.9,
43  /* on2.1 */    0.1, /*w11_0*/ -0.1, /*w11_1*/   0.1, /*w11_2*/  -7.2,
44                      /*w11_3*/424.1, /*w11_4*/ 108.8, /*w11_5*/-246.8,
45                      /*w11_6*/ -0.1, /*w11_7*/  -0.0, });

Würfel-APIs bestücken

Die gleiche Schnittstelle implementiert auch Python-Entwickler Stefan Schwarzburg in der Funktion »turn()« seines Bots »xubuntix« und kommt dabei mit neun Zeilen Code aus (siehe Listing 3). Dort formuliert er drei Bedingungen, wann er würfelt, andernfalls gibt er ab. Das Muster dieser Einreichung wiederholt sich bei vielen Varianten, etwa bei »smitty« von Christoph Tenzer, der den gleichen Python-Wrapper namens »DiceBot« verwendet, aber dessen Schwellwerte etwas anders wählt (siehe Listing 4).

01 def turn(self, mine, opp):
02     if opp>30 or (mine>40 and opp<20) or (mine>41):
03         self.roll()
04         return
05     elif sum(self.points) > 13:
06         self.save()
07     else:
08         self.roll()
09         return

01 def turn(self, mine, opp):
02     if opp>30 or (mine>42 and opp<17) or (mine>40):
03         self.roll()
04         return
05     elif sum(self.points) > 13:
06         self.save()
07     else:
08         self.roll()
09         return

Rund 600 Zeilen kompakten Code benötigt C-Programmierer Simon Schuler für seinen Bot »polyflex«. Der Quelltext, der die »TURN«-Direktive behandelt, zeigt dass Entwickler in C viele Aufgaben von Hand umsetzen müssen, die in anderen Sprachen bereits eingebaut sind, etwa Netzwerksupport oder Regular Expressions (siehe Listing 5).

01 void handle_turn(char *line) {
02       char *throwstr = "ROLLn", *savestr = "SAVEn";
04       int mecur;
05       if(last > 0) {
06              set_max(me,you,last);
07              last = 0;
08       }
09       turn = 1;
10       mecur = atoi(line + match[1].rm_so);
11       you = atoi(line + match[2].rm_so);
12       int cur = mecur - me;
13       int res;
14       char *msg;
15       if(cur >= get_limit(me,you)) {
16              msg = savestr;
17              me = mecur;
18              turn = 0;
19       } else {
20              msg = throwstr;
21       }
22       write_msg(msg);
23 }

Auf reichhaltige Bibliotheken und funktionale Programmierkonzepte greifen Haskell-Freunde zurück. Wie knapp sich damit nicht nur Algorithmen notieren, sondern auch Netzwerkverbindungen verwalten lassen, beweist der Ausschnitt aus den nur 80 Zeilen Code von Frank Recker, der damit den Bot »utz« verfasst hat (siehe Listing 6).

01   h <- connectTo "wettbewerb" (PortNumber 3333)
02 loop h z = do
03      f <- hGetLine h
04      putStrLn f
05      case (zerlege_string f) of
06        "HELO":_ -> helo h z
07        "TURN":x:y:_ -> turn h z (read x) (read y)
08        "THRW":x:_ -> thrw h z (read x)
09        [...]
10        _ -> error $ "loop: " ++ show f
11 
12 helo h Vor_Auth = sende h Nach_Auth "AUTH utz"
13

Er lässt sich dabei von Haskells Network-Package helfen [3]. Mittels »connectTo« holt er sich eine TCP-Verbindung zum Gameserver, iteriert über die Zeilen der Serverantworten und bearbeitet sie zeilenweise mit Hilfe von »hGetLine« in Zeile 9. Die folgenden Zeilen mit ihrem Case-Statement geben einen guten Eindruck von Haskells Arbeitsweise: Die Protokolleinheiten zerlegt die Sprache so, wie sie in der Spezifikation stehen. Passende Funktionen führen die jeweils nötige Arbeiten aus, wie ab Zeile 20.

Als Exot für die Netzwerkprogrammierung darf die Statistiksprache R gelten [4]. Das hielt Detlef Steuer nicht davon ab, seinen Bot »beatme« damit zu implementieren (siehe Listing 7). Verblüffenderweise hat er damit auch eines der kürzesten Programme abgeliefert, denn auch sein Code ist nur 80 Zeilen lang.

01 server <- "wettbewerb.linux-magazin.de"
02 port <- 3333
03 socket <- make.socket(server, port)
04 
05 load("Gp.Rdata")
06 
07 debug <-FALSE
08 ncat <- function(...) if (debug) cat(..., "n")
09 
10 dec <- function ( xa, xc, y) {
11   pass <- 1- Gp[y+1, y+1, xc+1]
12   wurf <- 1 - Gp[y+1, y+1, xa +1]
13   for (zahl in 1:5) {
14     if (xc+1+zahl > 50) wurf <- wurf +1 else  wurf <- wurf + Gp[xa+1, xc+1+zahl , y+1]
15   }
16   wurf <- wurf/6
17   if (pass > wurf) return(0) else return(1);
18 }
19 
20 myturn <- FALSE
21 while (TRUE){
22   server.message <- read.socket(socket)
23   command.lines<-strsplit(server.message, "n")[[1]]
24   for (lines in 1:length(command.lines)) ncat("SERVER:", command.lines[[lines]]  )
25   server.message <- command.lines[[ length(command.lines)]]
26   server.message<-strsplit(server.message, " ")
27   server.command <- server.message[[1]][1]
28   if (server.command == "DENY") break
29   if (server.command == "WIN") break
30   if (server.command == "DEF") break
31   if (server.command == "TURN") {
32     if (! myturn) {
33       myturn <- TRUE
34       xa <- as.numeric(server.message[[1]][2])
35       y <- as.numeric(server.message[[1]][3])
36       ncat("Spielstand zu Beginn:", xa, " ", y)
37       ncat("ROLL")
38       write.socket(socket, "ROLLn")
39     } else {
40       xc <-  as.numeric(server.message[[1]][2])
41       ncat("Spielstand:", xa, " ", xc, " ", y)
42       decision <- dec(xa, xc, y)
43       if (decision == 0 )
44          [...]

Sprachhits

Lag beim letzten Programmierwettbewerb [5] Python noch knapp vor Perl (18,7 Prozent der Einsendungen), so hat Larry Walls Skriptsprache diesmal hauchdünn die Nase vorn gegenüber 18,9 Prozent von Python. C++ bleibt auf einem komfortablen dritten Platz (14,6 Prozent). C und Bash (je 10,6 Prozent, zur Bash zählen auch einige hybride Sed- und Awk-Varianten) machen vermutlich wegen der Aufgabenstellung Plätze gut, dafür fallen Java (8,9 Prozent) und vor allem Ruby (3,3 Prozent) deutlich zurück. Für kleine Überraschungen auf dem siebten Platz sorgte einerseits PHP, sonst als Websprache bekannt (5,7 Prozent) und der funktionale Block, bestehend aus viel Haskell, etwas Lisp und ein wenig Scheme mit zusammen 4,9 Prozent. Außerhalb der Massenwertung standen die alte Lehrsprache Pascal, die sich im Java-Umfeld tummelnden Scala und Vala, die Wissenschaftssprache R sowie etwas Tcl (siehe Tabelle 2).

Es ist aber nicht nur der Code, der Aufschluss über die Menschen hinter den Bots gewährt, sondern auch seine Bezeichnung: So verwendet jeder sechste Programmautor den eigenen Namen oder einen Teil davon bei der Anmeldung beim Spielserver. Ob das jedoch eine Kompensationshandlung für Elterngefühle gegenüber den eigenen Skripten ist oder schlicht der Wunsch, aufwändige Arbeiten an willfährige Maschinen zu delegieren, konnte noch niemand klären.

Nomen est omen

Der Wortbestandteil “Dice”, “Würfel” oder “Bot” kommt in etwa 25 Prozent aller Teilnehmer vor. Neben dem »Würfler« und »Würfelglück« gibt es noch die »Würfelqualle«, die ebenso Maritimies im Namen trägt wie der »klabautermann«. Überhaupt geht es viel um Gut und Böse, wie »picard« und »locutus« beweisen, hauptsächlich aber friedlich oder spirituell zu, etwa mit »shalom«, »Pfarrbot« oder »Sainthuck«. Einzig »DiceVader« hat eine schwarze Seele und verhöhnt jedes Mal lachend nach Schurkenmanier den Gegner, wenn er eine Sechs würfelt.

Ob ihm das im Turnier nutzt, bleibt abzuwarten. Das nächste Heft enthält nämlich die Wettkampfresultate: Bis dahin muss jeder Bot nachweisen, dass er genügend Wissen übers Würfeln getankt hat.