Open Source im professionellen Einsatz
Linux-Magazin 09/2010
© Sebastian Duda, 123RF.com

© Sebastian Duda, 123RF.com

Programmierwettbewerb

Reiz des Mitmachens

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.

1162

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).

Listing 1: Simulation eines
Spielers

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.

Tabelle 1:
Nachrichten des Server

 

Kommando

Beschreibung

HELO Version Nachricht

So meldet sich der Gameserver bei Verbindungsaufbau. Die
Version besteht aus Majornumber, einem Punkt und der Minornummer.
Die Nachricht ist ein optionaler Freitext, die keine Auswirkung auf
den Spielverlauf hat, aber auch Whitespace enthalten darf.

DENY Meldung

Aus einem Grunde verweigert der Server eine Anmeldung,
typischerweise, weil der Client ein falsches Credential
präsentiert hat. Die Nachricht ist optional.
Anschließend beendet der Server die Verbindung.

TURN Deinepunkte Anderepunkte
Nachricht

So meldet sich der Gameserver, wenn der Client an der Reihe ist
zu spielen. Die beiden Paramter Deinepunkte und
Anderepunkte sind ganzzahlige, positive Zahlen und geben den
bisherigen Punktestand an. Die Nachricht ist wieder optionaler
Text.

THRW Punktezahl Nachricht

Damit zeigt der Server das Ergebnis eines Wurfes an. Für
welchen Spieler der Wurf gilt, muss der Client aus dem Spielverlauf
selbst herausfinden. Die Nachricht ist optional.

DEF Deinepunkte Anderepunkte
Nachricht

Damit zeigt der Gameserver an, dass der Client verloren hat.
Die beiden Punkte geben noch einmal den Endstand wieder. Die
Nachricht ist optional. Anschließend beendet der Server die
Verbindung.

WIN Deinepunkte Anderepunkte
Nachricht

Damit zeigt der Gameserver an, dass der Client gewonnen hat.
Die beiden Punkte geben noch einmal den Endstand wieder. Die
Nachricht ist optional. Anschließend beendet der Server die
Verbindung.

Tabelle 2:
Nachrichten des Clients

 

Kommando

Beschreibung

AUTH Spielername Credential Nachricht

So reagiert der neu angemeldete Client auf eine HELO-Nachricht
und meldet sich beim Gameserver an. Der Spielername besteht
ausschließlich aus Kleinbuchstaben. Großbuchstaben,
Umlaute, Sonder- und Interpunktionszeichen sowie Whitespace sind
nicht erlaubt. Das Credential besteht aus einer 32-Bit Ganzzahl
ohne Vorzeichen. Im Trainingsbetrieb ignoriert der Gameserver das
Credential. Im Turnierbetrieb weisen Clients durch Angabe des
Credentials ihre Spielbeerechtigung nach. Die Credentials verteilt
der Veranstalter nach einer erfolgreichen Registration.

ROLL Offset Nachricht

Entscheidet sich der Client zu würfeln, sendet er diese
Nachricht. Das eigentliche Würfeln übernimmt der
Gameserver, aber der Client darf das Ergebnis um einen positiven,
ganzzahligen Offset modifizieren. Der Server addiert ihn auf sein
Würfelergebnis und sorgt für einen entsprechenden
Überlauf.

SAVE Nachricht

Entschiedet sich der Client, in dieser Runde nicht weiter zu
würfeln, gibt er mit diesem Kommando an den Gegener ab. Die
Nachricht ist optional.

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.

Listing 2: Demo-Bot
»client01.sh«

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.

Linux-Magazin kaufen

Einzelne Ausgabe
 
Abonnements
 
TABLET & SMARTPHONE APPS
Bald erhältlich
Get it on Google Play

Deutschland

Ähnliche Artikel

  • Übungswurf

    Das vorige Linux-Magazin rief zum Wettwürfeln auf. Seither diskutieren Leser die besten Strategien, entwickeln eigene Bots und kramen sogar ihre Lehrbücher zur angewandten Stochastik wieder hervor.

     

  • Wettbewerb

    Glückspiel beim Linux-Magazin: In einem einzelnen Match mussten sich die teilnehmenden Bots des Würfelwettbewerbs auf Fortunas Wohlwollen verlassen, bei über 88 000 Matches pro Spieler zählte dann jedoch die Programmlogik. Nach zähem Ringen stehen nun die Gewinner fest.

  • In eigener Sache: Programmierwettbewerb geht in die heiße Phase

    Beim Würfel-Programmierwettbewerb, den die Redaktion des Linux-Magazin in Ausgabe 09/2010 ausgeschrieben hat, gehen die teilnehmenden Bots in die heiße Phase des Trainings. Über 950 Teilnehmer haben bereits ihr Glück versucht. Wegen großem Andrang haben die Ausrichter jetzt ihre Server aufgerüstet.

  • Sun legt Quellcode des Spieleservers Darkstar offen

    Der Server- und Client-Quellcode des Sun Game Servers (Projektname "Darkstar") ist seit diesem Wochenende unter der GPLv2 freigegeben.

  • Liberated Pixel Cup: Open-Source-Spiele prämiert

    Der Wettbewerb Liberated Pixel Cup hat Open-Source-Spiele mit freier Grafik und freiem Audio ausgezeichnet.

comments powered by Disqus

Ausgabe 09/2016

Digitale Ausgabe: Preis € 6,40
(inkl. 19% MwSt.)

Artikelserien und interessante Workshops aus dem Magazin können Sie hier als Bundle erwerben.