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

© Sebastian Duda, 123RF.com

Zwischenbericht zum Programmierwettbewerb "Würfeln"

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

 

567

Das Wettwürfeln mit selbst geschriebenen Bots, die schneller als ihre Gegner 50 Punkte erreichen sollen, stößt auf reges Interesse. Obwohl der dazu aufgesetzte Gameserver bei Redaktionsschluss erst zwei Wochen lang lief, nahmen bereits weit über 500 Programme an der Trainingsphase teil.

Die Aufgabe heißt, in der Programmiersprache der Wahl einen Client zu schreiben. Der wägt ab, ob er an seine eigene Glückssträhne glaubt und weiterwürfelt oder ob er die erzielte Augenzahl sichern möchte - dafür muss er jedoch an den Mitspieler abgeben. Während eines Spielzuges addieren sich geworfene Augen, jedoch verliert derjenige alle Punkte eines Spielzuges, der eine Sechs würfelt. Einmal durch Abgeben gesicherte Punkte hingegen bleiben erhalten [1].

Der Client verbindet sich übers Netz mit dem Gameserver unter [wettbewerb.linux-magazin.de:3333] und implementiert das veröffentlichte Protokoll. So müssen sich Clients mit »AUTH« anmelden, um dann zu entscheiden, ob sie mit »ROLL« würfeln oder mit »SAVE« ihre Punkte sichern. Der Server versorgt sie währenddessen mit Informationen zum Spielstand.

Anfangs verhedderte sich mancher Bot im Protokoll und brach die Verbindung ab oder blieb stehen. Um nicht den Spielbetrieb aufzuhalten, implementiert der Gameserver daher ein Timeout von einigen Sekunden. Bots, die nicht schnell genug oder nicht protokollkonform antworten, verlieren seither. In der Summe der gut 100 000 bislang durchgeführen Spiele trifft dies jedoch auf weniger als zwei Prozent aller Matches zu.

Starke Gemeinschaft

Teilnehmer diskutieren auf dem Wiki des Wettbewerbs die erfolgversprechendsten Strategien [2]. Anfangs versuchten es Bots mit intuitiven Ansätzen wie "siebenmal würfeln, dann sichern", andere forderten so lange ihr Glück heraus, bis sie vor dem Gegner lagen, oder vertrauten schlicht auf einen Durchmarsch.

Mit einer Wahrscheinlichkeit von 83,3 Prozent pro Wurf ist keine Sechs dabei, der Erwartungswert für solch einen Wurf liegt bei drei Augen: Damit muss ein Bot schon knapp 17-mal in Folge die Sechs vermeiden, was nur in 4,2 Prozent aller Anläufe gelingt. In beispielsweise fünf Versuchen, etwa weil der Gegner seine Punkte sichert oder er eine Sechs wirft, steigert sich die Gewinnquote immerhin auf 21 Prozent - immer noch viel zu wenig, um im Spitzenfeld mitzuspielen. Im Trainingscamp gewinnen die besten Bots gut über 60 Prozent ihrer Spiele, auch über eine größere Anzahl von Matches. Die Trainingstabelle im Wiki weist nur solche Bots aus, die mindestens 100 Partien absolviert haben.

Doch das hat wohl nur wenig Auswirkung auf das Turnierergebnis, da alle Bots mehrfach gegen alle Gegner spielen. Als die Redaktion testweise einmal nur die Besten der Trainingstabelle gegeneinander antreten ließ, sank die Gewinnquote des Besten auf unter 55 Prozent: Offenbar sind erfahrene Spieler gegen Neulinge besonders erfolgreich.

Einige Teilnehmer weisen darauf hin, dass die Entscheidung fürs Würfeln von drei Faktoren abhängt: Den eigenen und den gegnerischen Punktzahlen sowie der Zahl der bereits gewürfelten Punkte in der aktuellen Runde. Damit ist der Zustandsraum 53=125 000 Einträge groß, was sich in einem Array noch bequem verwalten lässt.

Die Entwickler diskutieren nun, wie diese Tabelle zu füllen sei. Manche Bots unterstellen ihrem Mitspieler nämlich eine ähnlich strukturierte Herangehensweise und überschätzen ihn damit vielleicht. Die Variable, die gegnerische Strategie gut zu bewerten, könnte daher der Schlüssel zum Erfolg sein. Bis zum 12. September 2010 kann jeder Magazin-Leser noch seine Vorschläge für einen Bot per E-Mail an [wettbewerb@linux-magazin.de] einschicken.

Infos

[1] Nils Magnus, "Wettbewerb: Reiz des Mitmachens": Linux-Magazin 09/10, S. 94

[2] Wiki: [http://wettbewerb-linux-magazin.de]

Linux-Magazin kaufen

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

Deutschland

Ähnliche Artikel

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

  • Vom Würfeln zur Multithread-Prozessteuerung
  • 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.

  • Eurovision Bot Contest

    Singen musste zum Glück niemand. Doch auch Würfeln gerät zur Kunst, wenn es darum geht, einem Robot so viel Intelligenz einzuhauchen, dass er seine Gegner wirksam aussticht. Ein Zwischenbericht.

  • Wissenstransfer

    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.

comments powered by Disqus

Ausgabe 08/2016

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