Am Anfang waren es bunte Glitzersteinchen, danach blecherne Roboter, im dritten freiesMagazin-Wettbewerb musste man vor Zombies flüchten und diesmal geht es um den schnöden Mammon, den ein schwerreicher Multimillionär unter die Leute bringen will.

Vorgeschichte

Ein Multimillionär verdient täglich so viel Geld, dass er gar nicht mehr weiß, wohin damit. Anstatt einen neuen Geldspeicher zu bauen, will er das Geld lieber in einem Experiment unter die Leute bringen. Dazu lädt er zwei Testsubjekte ein und begrüßt sie mit den Worten: „Ich habe hier 1000 Euro. Das Geld gebe ich Testsubjekt A. Dieses muss dann einen selbst festgelegten Betrag X zwischen 0 und 1000 dem Testsubjekt B anbieten. Das kann also auch alles oder nichts sein! Testsubjekt B hat nun zwei Möglichkeiten: Entweder es akzeptiert den Betrag X. Dann erhält Testsubjekt B den Betrag X und Testsubjekt A natürlich den Restbetrag 1000-X. Testsubjekt B kann das Angebot aber auch ablehnen. Dann bekommt keiner die 1000 Euro und ich behalte das Geld. Damit es ausgeglichen ist, gebe ich danach Testsubjekt B ebenfalls 1000 Euro, welches auf die gleicher Art und Weise handeln muss.“

Beide Testsubjekte schauen erstaunt und wollen sich schon miteinander abstimmen, um einen größtmöglichen Gewinn zu erhalten, aber da springt der Millionär dazwischen: „Na na, Reden ist verboten. Ihr werdet beide in verschiedene Räume gesetzt und könnt nur über eine reine Zahlentastatur miteinander kommunizieren und die Beträge anbieten, annehmen oder ablehnen.“ Die beiden Testsubjekte sind enttäuscht, aber machen dennoch mit, schließlich gibt es viel Geld zu gewinnen.

„Ach, noch was.“ sagt der Millionär. „Das Spielchen wiederholen wir insgesamt 2500 Mal, weil es so viel Spaß macht. Ich bin gespannt, wer von Euch beiden mit mehr Geld nach Hause geht.“

Sicherheitshinweis: Der obige Text ist fiktiv! Uns ist kein Millionär bekannt, der sein Geld so unter den Leuten verteilen will. Sorry!

Spielprinzip

Das Spielprinzip wurde in der Vorgeschichte schon exakt wiedergegeben. Von allen Teilnehmern treten immer zwei gegeneinander in einem Match an. In jedem Match gibt es 2500 Runden. Pro Runde muss der jeweilige Startspieler einen Wert zwischen 0 und 1000 anbieten. Der andere Spieler erfährt diesen Betrag und muss diesen annehmen oder ablehnen. Danach werden beide über den gewonnenen Betrag informiert und der Startspieler wechselt. Der Ablauf ist dann wie oben. Mit der erneuten Mitteilung des gewonnenen Betrages ist eine gesamte Runde zu Ende und es beginnt die nächste, wobei der Startspieler wieder wechselt. Insgesamt sind somit im Bestfall 5.000.000 Punkte unter den zwei Spielern aufzuteilen.

Dieses Spiel spielt jeder Spieler gegen jeden anderen Spieler. Das heißt, bei vier Spielern gibt es insgesamt 4·3 Spiele. Bei fünf Spieler sind es 5·4 Spiele, bei N Spielern somit N·(N−1) Spieler. Da nacheinander jeder gegen jeden spielt, spielt also auch Spieler A gegen B und Spieler B gegen A (Hin- und Rückrunde).

Um Zufallstreffern aus dem Weg zu gehen, wird dieser Ablauf 100 Mal wiederholt und aus den Punkten der Mittelwert gebildet. Dies soll helfen, zufällige Gewinne etwas zu relativieren.

Obwohl das Spielprinzip so einfach ist, ist die Taktik ganz spielentscheidend, schließlich will man seinen Gewinn maximieren. Ist man zu gierig und bietet nur eine geringe Punktzahl an, lehnt der Mitspieler wohl einfach ab. Auf der anderen Seite sollte man als Mitspieler auch nicht immer ablehnen, da man so auch keinen Gewinn einstreichen kann.

Dass die Teilnehmer vorher und während des Spiels nicht miteinander kommunizieren können, ist ein essentieller Bestandteil des Spiels. In der Spieltheorie nennt sich dieses Experiment „Ultimatumspiel“. Hilfreich sind vielleicht auch die Hinweise zum ähnlich gelagerten Gefangenendilemma. Auf der Webseite findet man auch viele Strategien, die man umsetzen kann. Dabei sollte man aber beachten, dass alle Mitspieler nun ebenfalls diese Taktiken kennen. Wer es schafft, die Taktik seines Mitspielers zu erraten (daher die 2500 aufeinanderfolgenden Spiele), kann sein eigenes Verhalten gegebenenfalls entsprechend anpassen.

Expliziter Hinweis: Die 2500 Spiele gegen einen Mitspieler finden in einem Prozessaufruf statt. Das heißt, man kann sich die Spieldaten intern in seinem Bot direkt merken und muss die Ergebnisse nicht auf HD zwischenspeichern.

Zweiter expliziter Hinweis: Es ist nur erlaubt, die vom Server verschickten Daten für eine Analyse der gegnerischen Strategie zu benutzen. Zugriffe auf Inhalte außerhalb des Spiels (Dateisystem, Prozesstabelle, fremder Speicher) ist nicht erlaubt.

Spielengine

Die Spielengine ist in C++ geschrieben; die Kommunikation mit den Bots geschieht aber allein über Standardeingabe und -ausgabe. Das heißt, jeder Bot muss einfach nur die Standardeingabe abfragen, um Nachrichten zu empfangen, und danach seine Antwort auf der Standardausgabe ausgeben. Dies sollte es bei der Umsetzung extrem einfach machen.

Im Download ist ein Beispielbot mit drei sehr simplen Taktiken enthalten, der sich jede Runde gleich verhält. Diesen Bot kann man als Sparringpartner für eine eigene Implementierung benutzen. Man sollte aber nicht davon ausgehen, dass sich alle echten Gegner genauso verhalten.

Download der Spielengine

Die Spielengine kann nach dem Download und Entpacken einfach mit make kompiliert werden. Ein C++-Compiler ist natürlich Pflicht. Für einen ersten Testlauf sollte man noch die Dateien unter bots/dummybot ebenfalls mit make kompilieren.

Danach kann man einen einzelnen Durchlauf z. B. mittels

ablaufen lassen. Den kompletten Wettbewerb startet man über

Eine Kurzanleitung hierzu befindet sich in der Datei strong README.

Weil die Anfrage sicher kommt: Wir können nicht anbieten, dass die Engine als Programm auf unserem Server läuft und die Teilnehmer dort gleich online gegen andere Mitspieler-Bots antreten können. Dies hat vor allem sicherheitsrelevante Gründe. Stattdessen kann uns jeder Teilnehmer aber seinen Bot zuschicken und wir testen diesen dann lokal bei uns.

Eigenen Bot erstellen

Wie oben geschrieben, geschieht die Kommunikation mit der Spielengine über die Standardeingabe und -ausgabe.

Folgende Kommandos müssen eingehend verstanden werden:

• RUNDEN <WERT> – Anzahl der insgesamt zu spielenden Runden. Es ist geplant, 2500 Runden zu spielen. Da die Zahl aber ggf. aus Zeitgründen variiert wird, sollte man den Bot entsprechend variabel kodieren.
• RUNDE <WERT> – Eine neue Runde startet. Der Rundenzähler beginnt bei 1.
• ANGEBOT <WERT> – Die vom Mitspieler angebotene Punkte. <WERT> liegt zwischen 0 und 1000.
• PUNKTE <WERT> – Die Engine teilt mit, wie viele Punkte man erhält. <WERT> liegt zwischen 0 und 1000. Die Punkte kann man auch selbst mitzählen und den übertragenen Wert zur Kontrolle nutzen.
• START – Man muss einen Wert zwischen 0 und 1000 anbieten.
• ENDE – Das Spiel ist zu Ende, man kann aufhören den Bot laufen zu lassen.
• JA – Das eigene Angebot wurde vom Mitspieler angenommen.
• NEIN – Das eigene Angebot wurde vom Mitspieler abgelehnt.

Folgende Kommandos müssen ausgehend verschickt werden:

• JA – Man nimmt das Angebot des Mitspieler an.
• NEIN – Man lehnt das Angebot vom Mitspieler ab.
• <WERT> – Die direkte Antwort auf das Kommando START und damit das Angebot an den Gegner. Der Wert <WERT> muss zwischen 0 und 1000 liegen.

Kommunikation zwischen Servern und Bots.

Auswertung

Die wichtigste Frage ist sicherlich noch: Wie werden die Gewinner des Wettbewerbs ermittelt? Dies geht ganz einfach. Für jedes Spiel zweier Bots wird die Punktzahl gespeichert, welche diese erreicht haben. Nachdem alle Bots gegeneinander gespielt haben, wird diese Punktezahl addiert. Wer dann die meisten Punkte hat, hat gewonnen.

Wenn man z. B. die drei Dummybots einmal über

gegeneinander spielen lässt und die Auswertung mittels des Skriptes

durchführt, ergibt sich so eine Ausgabe:

Der Bot simple hat also den ersten Platz erzielt, weil er die meisten Pluspunkte gesammelt hat.

Sollte es dazu kommen, dass zwei Bots den gleichen Platz belegen, entscheiden die Minuspunkte. Entgegen mancher Erwartung ist bei Gleichstand ein hoher Wert von Vorteil, da dieser gewinnt. Wieso das? Ganz einfach: Wer es schafft, die meisten Punkte zu ergattern, aber gleichzeitig so spielt, dass auch die anderen Spieler nicht leer ausgehen (man bedenke, dass es um virtuelles Geld geht und man seinen „Gegner“ nicht in Grund und Boden wirtschaften muss), hat aus Gemeinschaftssicht definitiv besser gehandelt.

Zu gewinnen gibt es natürlich auch wieder etwas. Diesmal sind wir weg von festen Preisen bzw. Gutscheinen gekommen und wollen die Preise ergebnisorientiert vergeben. Das heißt, die ersten drei Plätze mit den meisten Punkten gewinnen einen Gutschein. Der Wert ist abhängig von den erzielten Pluspunkten. Da die erreichten Punkte von der Anzahl der gespielten Spiele und diese wiederum von der Anzahl der Teilnehmer abhängen (siehe oben), muss der Wert herausgerechnet werden.

Die ersten drei Plätze erhalten somit einen Amazon-Buchgutschein im Wert von P / ( 20000·(N−1) ), wobei P die erzielten Pluspunkte sind und N die Anzahl der Teilnehmer am Wettbewerb. (Die Konstante 20000 ist notwendig, weil wir sonst mehrere Millionen an Preisgeld ausgeben müssten. ;) )

Update 19.10.2011: Bei der Formel oben wurde einmal zu viel durch N geteilt, sodass bei vielen Spieler der maximale Gewinn immer kleiner wurde. Dies wurde korrigiert.

Taktische Hinweise

Es folgen hier ein paar Hinweise, die bei der Erstellung des Bots bzw. einer Taktik helfen könnten.

Kaum einer der Mitspieler wird mehr als 500 Punkte anbieten. Auf so ein tolles Angebot sollte man also nicht warten. Das heißt, man muss sich wohl oder übel damit abfinden, dass der Gegner nur Angebote macht, bei denen er besser dasteht. Der Trick ist es, dass man dies durch die beiden Teilrunden in den 2500 Runden so dreht, dass man am Ende besser dasteht.

Wobei es auch nicht zwingend erforderlich ist, dass man in jedem Spiel besser dasteht als der Gegner, da die Gesamtsummer aller Spiele zählt. Als (schlechtes) Beispiel kann man sich den Beispielbot mit der Taktik more anschauen. Dieser kann rein taktisch kein Spiel verlieren, da er immer 499 anbietet und nur Angebote größer 500 annimmt. Da kaum ein Gegenspieler die 499 Punkte liegen lässt, bekommt der Bot also auch Punkte und gewinnt so immer (ganz knapp) jedes Spiel. Dadurch, dass er aber so oft das gegnerische Angebot ablehnt, erhält er keine Punkte und steht somit nicht zwingend als bester Spieler da.

Auf der anderen Seite sollte man natürlich auch nicht jedes Angebot annehmen. Bietet der Gegner nur 1 Punkt, geht man bei der Annahme zwar nicht leer aus, aber viel erreicht man nicht damit und der Gegner erhält einen großen Vorsprung. Wo man seine eigene Schmerzgrenze zieht und ob diese fest oder dynamisch ist, muss man selbst entscheiden.

Das eigene Ergebnis hängt sehr stark von den gegnerischen Spielern und Spielen ab. Wie bei dem more-Bot sieht man, dass man zwar persönlich den besten Bot haben kann. Wenn die anderen Mitspieler aber aufgrund einer anderen Taktik mehr Punkte untereinander aufteilen, kann man am Ende nicht gewinnen. Es empfiehlt sich, den Wikipedia-Artikel zum Ultimatumspiel durchzulesen und die psychologische Komponente der anderen Programmierer nicht außer Acht zu lassen.

Wer es schafft, die Taktik des Gegners zu erraten, hat gute Karten, einen optimalen Gewinn zu erzielen. Wenn der Gegner natürlich wie der more-Bot spielt und nur Angebote größer 500 annimmt, hilft einem das nur wenig weiter. In der Regel wird aber kaum ein Bot so restriktiv agieren.

Ganz wichtig: Am Ende gewinnt der Bot, der in Zusammenspiel mit allen Gegenspielern die beste Taktik hatte. Käme theoretisch ein weiterer Bot hinzu, der nicht zwingend gut sein muss, kann sich die Platzierung bzw. die Punkteverteilung zu Gunsten oder Ungunsten der eigenen Person verschieben. Dies sollte man bei der Teilnahme am Wettbewerb nicht vergessen.

Teilnahmebedingungen

Der Wettbewerb ist frei für jeden, der teilnehmen möchte (mit Ausnahme der freiesMagazin-Teammitglieder). Das Spielprinzip und die Technik ist mit Absicht simpel gehalten, sodass man für die reine Implementierung des Grundgerüsts nur ein bis zwei Stunden benötigen wird. Für die eigentliche Taktik seines Bots muss man vermutlich etwas länger nachdenken.

Die Programmiersprache ist wie immer jedem freigestellt. Da die Schnittstelle nur stdin und stdout zur Kommunikation nutzt, sollte es keinerlei Anbindungsprobleme geben.
Für die Teilnahme am Wettbewerb gibt es zwei Bedingungen. Die erste Bedingung ist, dass der Bot für einen Komplettdurchlauf gegen sich selbst über das Startskript oben (start.sh) auf dem Wettbewerbsrechner nicht mehr als eine Minute benötigt. Die Zeit kann man mittels

messen. Entscheidend ist, dass bei real eine Null vor dem m steht. (Obige Zeitangabe hilft grob, die Leistung des eigenen Rechners einzuschätzen. Man sollte natürlich nebenbei keine Videobearbeitung laufen lassen oder den Kernel kompilieren.)

Die zweite Bedingung ist, dass der Quellcode selbst verfasst wurde und unter einer freien Lizenz vorliegt. (Hilfe bei der Auswahl einer geeigneten Lizenz bieten wir gerne an.)

Der Wettbewerb startet am 1. Oktober 2011 und läuft bis zum 30. November 2011 (dies ist der Einsendeschluss). Jeder Teilnehmer kann mit genau einem Bot teilnehmen, mehrfache Ausbesserungen sind bis zum Einsendeschluss aber möglich. Im Dezember 2011 findet dann die Auswertung statt, sodass pünktlich zum Weihnachtsfest die Gewinner bekannt gegeben werden können.

Wir wünschen allen Teilnehmern viel Erfolg und freuen uns über zahlreiche Einsendungen. Für Fragen und Hinweise steht die natürlich zur Verfügung.

PS: Um immer auf den aktuellen Stand zu sein, was den Wettbewerb angeht, können Sie die Kommentare zu dieser Seite per RSS abonnieren. Kommentare können hier aber nur vom freiesMagazin-Team verfasst werden!

Häufig gestellte Fragen (FAQ)

Wenn ich das start-Skript ausführe, erhalte ich keine Rückmeldung und das Programm bleibt stehen. Was mache ich falsch?

In der Regel wartet der Server dann auf die Antwort eines Bots. Das Debugging des Servers hilft ebenfalls bei der Analyse.

Bekannte Probleme bei der Implementierung eines eigenen Bots können sein:

1. Nach dem Schreiben auf stdout fehlt das Flushen der Daten. Das ist bei manchen Sprachen notwendig, damit auch wirklich gesendet wird.
2. Das Auslesen der Daten muss zeilenweise passieren. Versucht man mehr Daten zu lesen oder zeichenweise, kann dies zu einer Problem führen.

Wie aktiviere ich den Debug-Modus des Servers?

In manchen Fällen kann es hilfreichen sein, zu schauen, was der Server tut bzw. ob er auf etwas wartet. Hierfür muss man nur in den Makefile-Dateien im Ordner libserver und libengine die CXXFLAGS-Zeile wie folgt ändern:

Danach muss man aber noch ein

ausführen, damit die Engine aktualisiert wird.

Müssen die Daten der 2500 Spiele gegen einen anderen Bot von mir gespeichert werden?

Nicht persistent auf der Festplatte oder ähnliches. Die 2500 Spiele finden aus einem Prozess heraus statt, der erst am am Ende mit dem Kommando ENDE unterbrochen wird.

Darf ich Dateien anlegen und wenn ja, wie viele?

Prinzipiell ja. Wer Daten über mehrere Spiele, d.h. mehrere Gegner, hinweg in Dateien speichern will, kann dies tun. Eine Datei bleibt erhalten, bis der Bot, der sie erstellt hat, löscht. Als Pfad kann man entweder in /tmp speichern oder direkt im aktuellen Arbeitsverzeichnis. Da keine RAM-Disk (im Gegensatz zum vorletzten Wettbewerb) benutzt wird, ist auch die Speichergröße der Dateien nicht beschränkt. Sie sollte aber bitte keine Gigabyte-Dimensionen einnehmen.

Es sei aber darauf hingewiesen, dass der Informationsgehalt einer solchen Speicherung sehr gering ist. Ein Bot wird seitens des start-Skriptes nicht darüber informiert, gegen welchen Gegner er spielt und auch nicht, um das wievielte Spiel es sich in einem Durchlauf handelt bzw. ob überhaupt ein richtiger Wettbewerb begonnen hat oder es sich nur um ein Testspiel handelt. Insofern könnte es schwer werden, aus den gespeicherten Daten irgendeinen Nutzen zu ziehen.

Wie wird die Reihenfolge der Matches pro Wiederholung gebildet?

Die Reihenfolge der Matches in den 100 Wiederholungen ist immer gleich. Das heißt, man trifft im x-ten Match immer auf den gleichen Gegner.

Achtung: Es wird explizit nicht 100 Mal nacheinander die Begegnung Bot A gegen Bot B gespielt, sondern es wird ein kompletter Wettbewerb mit allen Bots abgehalten und dieser dann 100 Mal wiederholt.

Was ist mit Hin- und Rückrunde gemeint?

Wie beschrieben, besteht ein Match aus zwei Bots, die gegeneinander in 2500 Runden antreten. Jede Runde darf zuerst Bot A und danach Bot B den Startspieler geben und einen Wert anbieten. Dies ist nicht mit Hin- und Rückrunde gemeint.

Hin- und Rückrunde bezeichnet die zweite Begegnung der beiden Bots in einem zweiten Match, bei dem Bot B den ersten Startspieler gibt und Bot A den zweiten. Die Rückrunde ergibt sich automatisch, wenn alle n Bots gegen alle anderen n-1 Bots antreten.

Beispiel: Bei drei Bots A, B, C sind die Begegnungen wie folgt: A-B, A-C, B-A, B-C, C-A, C-B (siehe Datei start_contest.sh).

Spielen die Dummybots später mit im Wettbewerb?

Nein, die Dummybots sind nur als Sparring-Partner gedacht und werden später nicht am Wettbewerb teilnehmen.

Ist es erlaubt, den gegnerischen Bot zu erkennen?

Ja, aber nur mit Hilfe der Daten, die der Server einen zukommen lässt. Es ist damit nicht erlaubt, zum Beispiel über die Prozessliste den Dateinamen eines Bots auszulesen. Auch andere externe Hilfsmittel sind verboten!

Werde ich disqualifiziert, wenn mein Bot länger als 1 Minute braucht?

Das kommt auf das wie viel länger an. Wer nur wenige Sekunden darüber liegt, hat nichts zu befürchten. Liegt man aber weit darüber (d.h. ca. das Doppelte), werden wir den Entwickler ansprechen, damit er noch Optimierungen vornehmen kann.

Werden nach beendetem Wettbewerb eigentlich die Quellcodes aller Bots veröffentlicht?

Ja, wie die Jahre zuvor veröffentlichen wir die Bots nach dem Ende des Wettbewerbs.