Aussichtsreiche Würfelkandidaten unter der Lupe

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.

Tabelle 1: Top-20-Bots

Platz	Bot	Quote	Züge
1	Toralf	63.35	5.21
2	genom2	61.93	5.80
3	xubuntix	61.88	5.43
4	smitty	59.67	5.49
5	pftest	59.32	5.31
6	benhoof	58.92	5.51
7	jodado	58.89	5.73
8	massimo	57.38	5.37
9	topo	57.37	5.39
10	rockNroll	57.22	5.45
11	frankomat	57.10	5.25
12	pyfectbot	56.97	5.55
13	jdice	56.87	5.31
14	aki	56.77	5.51
15	picard	56.74	5.41
16	visqfixo	56.53	5.74
17	klabautermann	56.49	5.54
18	sainthuck	56.40	5.58
19	incubus	56.37	5.34
20	wubbel	56.20	5.14

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.

Listing 1: »Toralf« (Perl)
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";

Listing 1: »Toralf«
(Perl)

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.

Listing 2: »genom2« (Java)
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, });

Listing 2: »genom2«
(Java)

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, });

« Zurück 1 2 3 4 Weiter »

Diesen Artikel als PDF kaufen

Express-Kauf als PDF

Umfang: 4 Heftseiten

Preis € 0,99
(inkl. 19% MwSt.)

Als digitales Abo

Als PDF im Abo bestellen

Bots in Uniform

Das Feld der Favoriten

Diesen Artikel als PDF kaufen

Express-Kauf als PDF

Als digitales Abo

Weitere Produkte im Medialinx Shop »

Versandartikel

Onlineartikel

Ähnliche Artikel

Ausgabe 07/2013

Insecurity Bulletin

Linux-Magazin auf Facebook