© Sebastian Duda, 123RF.com

Siegen künstliche Intelligenz, kühle Stochastik oder schlichte Kühnheit? Bis Mitte September dürfen Leser selbst programmierte Bots einsenden, die gegeneinander um die Wette würfeln müssen .

Die Aufgabe erscheint simpel: Ein Spieler würfelt wiederholt und addiert seine Augenzahlen. Wirft er eine Sechs, muss er alle Punkte streichen und von vorne beginnen. Gilt es etwa, eine Summe von 50 Punkten zu erreichen, sind im Durchschnitt knapp 122 Würfe nötig, wie etwas Stochastik oder ein empirisches Perl-Skript offenbaren (Listing 1).

01 #!/usr/bin/perl
02 # simuliert einen einzelnen Würfelspieler
03 srand(time ^ $$);
04 
05 foreach $i (1 .. 1000) { # Zahl der Testläufe
06     $turns = $sum = 0;
07     while ($sum < 50) {  # Nötige Punktzahl
08         $turns++;
09         $wurf = int(rand(6) + 1);
10         $sum += $wurf;
11         $sum  = 0 if ($wurf == 6);
12     }
13     $sumsum += $turns;
14 }
15 print "Mittlere Züge: ", $sumsum/1000, "n";

Mehr Spannung kommt auf, wenn zwei Spieler abwechselnd gegeneinander antreten: Wer nun die Sechs wirft, verliert seine gesammelten Punkte und der Mitspieler ist am Zug. Der aktive Spieler darf jedoch auch freiwillig an den Gegner abgeben: In dem Falle sichert er sich die bis dato gesammelten Punkte und fällt bei einer späteren Sechs nur auf diesen Stand zurück.

Spieltaktik mit Intelligenz

Ließ sich die erste Variante noch mit Schulmathematik in den Griff bekommen, erweist sich die zweite als kniffliger: Es kommt auf die Spieltaktik des Gegenübers an. Verspricht es mehr Erfolg, konservativ Punkte zu sammeln und fix abzugeben? Gelangt jener schneller ans Ziel, der mitzählt, wie häufig er schon der Sechs ausgewichen ist? Welchen Einfluss hat die Taktik des Mitspielers?

Um diese Fragen zu klären, schreibt das Linux-Magazin einen Wettbewerb aus, bei dem selbst programmierte Bots der Leser über das Netz gegeneinander antreten werden. Auf TCP-Port 3333 von [wettbewerb.linux-magazin.de] läuft dazu ein vorgegebener Gameserver, der Mitspieler vermittelt und auf die Einhaltung der Regeln achtet. Die Kommunikation erfolgt über ein einfaches Textprotokoll, das der Tradition vieler Unix-Handshakes wie etwa SMTP folgt. Tabelle 1 beschreibt die Kommandos des Servers, Tabelle 2 die Nachrichten des Spielers.

Die Details des Ablaufes verdeutlicht Abbildung 1: Zunächst meldet sich ein Client beim Server mit der »AUTH«-Meldung und einem Namen an. Der Gameserver wählt aus, wer beginnt: Sobald ein Spieler an der Reihe ist, teilt das der Server mit der »TURN«-Meldung mit. Der Spieler hat dann zwei Optionen: Entscheidet er sich für »ROLL«, begibt er sich in Fortunas Hand und würfelt.

Abbildung 1: Zustände des Protokolls zwischen Gameservern (links) und einem Spieler-Client (rechts): Die abgerundeten Flächen zeigen Zustände, die eckigen Kästen enthalten die Nachrichten, die die jeweilige Seite versendet. Bei Nachrichten mit dickem Rand endet ein Spiel.

Sendet er »SAVE«, ist der Mitspieler an der Reihe – dafür sind dem Spieler die bislang erzielten Punkte sicher. Über die Statusmeldung »THRW« erhält der Client Informationen darüber, wie viele Augen ein Wurf zählte, und zwar sowohl für den eigenen wie für den gegnerischen Spieler. Derjenige Spieler, der als erster 50 Punkte oder mehr erzielt, hat gewonnen und beendet damit das Spiel. Es gibt keine Möglichkeit des Nachziehens. Abbildung 2 zeigt, wie ein Spiel manuell per Telnet abläuft.

Abbildung 2: Zu Testzwecken lässt sich der Gameserver auch manuell ansteuern – etwa mit einem Telnet-Client. So verfolgen Entwickler das Protokoll.

Trainingslager

Ein naiver Client könnte beispielsweise immer so lange per »ROLL« würfeln, bis er entweder gewinnt »WIN« oder der andere Spieler an der Reihe ist. Listing 2 implementiert diesen Ansatz als Bash-Skript, das Anwender mit dem Netcat-Aufruf »nc -e client01.sh wettbewerb.linux-magazin.de 3333« starten. Netcat kümmert sich dabei um den Aufbau der Verbindung und verdrahtet die Standard-Ein- und -Ausgabe mit dem Skript. Als Kniff gibt dieser Bot mit einer Wahrscheinlichkeit von 1:4 (Zeile 13) an seinen Mitspieler ab, um Punkte zu sichern.

01 #!/bin/bash
02 
03 name=tux
04 
05 while read command a1 a2 a3
06 do
07    case $command in
08       HELO)
09          echo "AUTH $name Ich bin bereit!"
10          ;;
11       TURN)
12          echo "Spielstand ${a1}:${a2}" >&2
13          if (($RANDOM % 4 == 1))
14          then
15            echo "SAVE Das reicht erstmal ..."
16            active=0
17          else
18            echo "ROLL Auf gut Glück!"
19            active=1
20             fi
21          ;;
22       THRW)
23          if [ "$active" = "1" ]
24          then
25             echo "Ich würfle eine $a1." >&2
26             if [ "$a1" = "6" ]
27             then
28                echo "Du bist dran!" >&2
29                active=0
30             fi
31          else
32             echo "Du würfelst eine $a1." >&2
33             if [ "$a1" = "6" ]
34             then
35                echo "Ich bin dran!" >&2
36                active=1
37             fi
38          fi
39          ;;
40       WIN|DEF)
41          echo "Spielende: $command" >&2
42          exit 0
43          ;;
44       *)
45          echo "Unbekannt: $command" >&2
46          ;;
47    esac
48 done

Bis zum 12. September 2010 haben die Bots Zeit, eine ausgefeiltere Taktik zu finden. Bis zu diesem Termin dürfen Leser ihre Programme an [wettbewerb@linux-magazin.de] einsenden, um am Abschlussturnier teilzunehmen. Dabei treten alle Teilnehmer mehrfach gegen jeden anderen Teilnehmer an. Jeder Leser darf nur mit einem einzigen Bot teilnehmen. Erhält die Redaktion mehrere Einsendungen vom selben Absender, startet die letzte fristgerechte Einsendung.

Jede Sprache ist erlaubt

Die Einsendungen müssen im Quelltext geschehen, unter einer freien Lizenz stehen und entsprechend dokumentiert sein, sodass die Jury die Bots in Betrieb nehmen kann. Dazu soll ein Makefile oder ein ähnliches Skript beiliegen, das mit »make build« den Code baut und mit »make game« ein Spiel startet.

Erlaubt ist jede Programmiersprache, die sich durch den Paketmanager auf einem aktuellen Ubuntu 10.04 installieren lässt. Jeder Bot muss autonom agieren. Eine Netzverbindung ist nur zum Gameserver erlaubt. Der Bot darf beliebige Ausgaben machen, sollte aber keine dauerhaften Dateien anlegen. Um das Notieren der Ergebnisse kümmert sich der Gameserver.

Pro Durchlauf hat der Bot maximal 1 GByte virtuellen Hauptspeicher zur Verfügung, was die Jury mittels »ulimit -v 1000000« auf dem Client durchsetzt. Maximal darf der Prozess 600 CPU-Sekunden pro Spiel verbrauchen. Die Jury prüft jede Einsendung darauf, ob die technischen Vorraussetzungen erfüllt sind, und räumt bei Problemen zwei Tage zur Nachbesserung ein.

Protokoll

Das Protokoll besteht aus einzeiligen Direktiven, die durch ein Newline abgeschlossen sind. Der zugrunde liegende Zeichensatz ist ein Subset aus UTF-8, also auch aus ISO-8859-15 und damit auch aus Ascii, und besteht aus den Buchstaben A bis Z in Groß- und Kleinbuchstaben, Ziffern, dem Punkt, Leerzeichen, Tabulatoren und Newlines.

In den optionalen Nachrichtenfeldern, die der Server nicht interpretiert, sind beliebige UTF-8 Zeichen erlaubt, in den für das Spiel relevanten Protokollfeldern benutzen Client und Server jedoch ausschließlich Zeichen, die auch Teil von Ascii sind.

Der Client muss auf Nachrichten des Servers binnen 5 Sekunden reagieren, sonst bricht der Gameserver die Verbindung ab und zählt das Spiel als verloren. Das gilt auch, wenn sich ein Client nicht an das Protokoll hält.

Der Server selbst reagiert ebenfalls spätestens in dieser Zeitspanne, allein nach der »AUTH«-Nachricht des Clients darf der Gameserver länger warten, um einen Spielpartner ausfindig zu machen. Im Übungsbetrieb meldet sich spätestens nach einer Minute ein Trainingsclient, wenn sich keine anderen Spielpartner am Gameserver anmelden.

Sollte es Fragen oder Ideen zum Protokoll oder sonstigen Wettbewerbsablauf geben, haben die Teilnehmer Gelegenheit, sich auf der Wettbewerbsseite auszutauschen und ihre Bots zu trainieren [1].

Für Ruhm und Gewinne

Nach Ablauf der Einsendefrist spielt die Linux-Magazin-Redaktion eine Endrunde mit allen eingesandten Clients in einem Liga-Modus alle gegen alle aus. Jede Paarung tritt insgesamt mehrfach gegeneinander an, um Zufallseffekte auszumitteln. Dabei darf jeder Spieler der Paarung bei der Hälfte aller Spiele beginnen. Für jeden Sieg erhält der Spieler einen Punkt. Der Bot mit den meisten Punkten gewinnt. Sollten mehrere Clients die gleiche Punktzahl erringen, treten diese erneut gegeneinander an, bis ein Sieger ermittelt ist.

Der Erstplatzierte gewinnt ein Linux-Micro-Netbook Ben Nanonote für die Hosentasche. Das Gerät wiegt 126 Gramm, ist etwa so groß wie eine Zigarettenschachtel, hat aber eine vollständige Tastatur und ein Farbdisplay [2]. Die Zweit- und Drittplatzierten erhalten eine Würfelappliance im edlen Green-Dice-Finish mit je sechs Cores. Die bestplatzierten und spannendsten Teilnehmer stellt das Linux-Magazin ausführlich vor. Mögen die Würfel fallen.