Die Gewinner des sechsten Programmierwettbewerbs

Vom 1. Dezember 2012 bis zum 31. Januar 2013 fand der sechste freiesMagazin-Programmierwettbewerb statt. In diesem Zeitraum konnten Programmierinteressierte ein Programm (einen so genannten Bot) einreichen, der versucht auf einer untergehenden Insel Felder trockenzulegen, um möglichst lange zu überleben. Die Auswertung der eingereichten Beiträge ist beendet und die Gewinner stehen fest.

Teilnehmer

Insgesamt haben 20 Teilnehmer für den Wettbewerb einen Bot eingereicht. Damit war die Akzeptanz sehr hoch, was uns natürlich freut. Auch zwei Schulklassen des Gymnasiums Egg haben unter Lehrer Dominik Bartenstein teilgenommen. Es freut uns ebenso, dass die Aufgabe auch als Schulstoff dienen konnte.

Unter den Einsendungen waren wieder verschiedenste Sprachen vertreten, darunter wohl-bekannte wie C++, Python und Java, aber auch „Exoten“ wie Haskell oder Scala wurden genutzt.

Als Gewinn konnten die ersten drei Plätze einen der folgenden drei Preise mitnehmen:

Zusätzlich gab es für die Plätze 1 bis 10 eine Doppel-CD des letztjährigen Free! Music! Contest 2012.

Auswertung

Nachdem am 31. Januar 2013 alle Einsendungen vorlagen, wurde nach etwas Vorbereitungsarbeit der Wettbewerb gestartet. Dabei wurde jeder Bot je 1000 Mal auf den vorhandenen Inseln/Spielfeldern getestet und am Ende der Mittelwert der überlebten Runde für jedes Spielfeld berechnet. Diese häufige Wiederholung wurde durchgeführt, da die Felder einer Insel zufällig überflutet wurden und durch die Wiederholung und den Mittelwert eine bessere Aussage über die „Intelligenz“ eines Bots getroffen werden konnte.

Insgesamt mussten die Bots auf 22 Spielfeldern ihr Geschick beweisen. 12 Inselfelder stammten dabei von der Wettbewerbsleitung und waren bis auf die Beispielinsel island.txt den Teilnehmern nicht bekannt. Die restlichen 10 Inselfelder wurden von Teilnehmer selbst eingereicht, die dazu die Möglichkeit hatten.

Am 1. Februar 2013 startete die Auswertung der Bots und war am 15. Februar 2013 zu Ende. Trotz der Zeitbegrenzung von 0,1 Sekunden pro überlebter Runde dauerte die Berechnung also noch zwei Wochen, in denen der Testrechner 24 Stunden pro Tag durchlief. Im Vorfeld hätte wir diesen Aufwand nicht angenommen. Glücklicherweise nutzten nur wenige Teilnehmer das Zeitlimit bis zum Anschlag aus, sonst wäre der Wettbewerb auch nach einem Monat noch nicht zu Ende gewesen. Der „Worst Case“ eines Teilnehmers lag bei ca. vier Tagen Berechnungszeit für die 1000 Iterationen auf den 22 Spielfeldern.

Die Gewinner

Um es nicht unnötig spannend zu machen, hier die Auswertung des Wettbewerbs:

Platz Name Punkte Dauer (in h) Sprache Lizenz
1. Philipp Staudinger 3187,325 6:50 Java LGPLv3
2. Christoph Staudinger 3167,576 9:23 Python GPLv3
3. Horst Hettrich 3166,223 25:38 Python GPLv3
4. Tom Richter 3160,519 44:02 Python GPLv3
5. Florian Satzger 3117,693 0:14 C++ LGPLv3
6. Patrick Uhlmann 3108,073 18:43 Mono Apache
7. Momme Maraun 3101,950 1:02 C++ LGPLv3
8. Harald Demel 3101,891 89:47 Groovy FreeBSD
9. Markus Brenneis 3082,350 0:20 C++ GPLv3
Dominik Wagenführ 3080,946 117:40 C++ LGPLv3
10. Markus Braun 3058,158 0:14 C++ LGPLv3
11. Tobias Groß 3028,445 11:50 Ruby WTFPL
12. Justus Richter 3025,668 22:33 Python GPLv3
13. M.Hummel & K.Kleine 2963,948 55:34 Python BSD
14. Heiko Blobner 2926,775 8:55 Scala GPLV3
15. Thomas Pummer 2818,245 1:03 Python GPLv3
16. Dominik Bartenstein 2788,766 1:31 Python LGPLV3
17. Gymnasium Egg, 8bn 2730,113 0:58 Python LGPLv3
18. Gymnasium Egg, 6bn 2711,855 0:56 Python LGPLv3
19. Robert Knauer 2535,100 0:17 C++ GPLv2
20. Alexander Rampp 2388,842 3:20 Scala WTFPL

Wir gratulieren an dieser Stelle Philipp Staudinger, Christoph Staudinger und Horst Hettrich für die Belegung der ersten drei Plätze. Vor allem Platz 2 und 3 liegen sehr dicht beisammen. Wie man auch sieht, heißt langes Rechnen nicht auch zwingend, dass ein Bot besser ist als andere. Ebenso spielt die verwendete Sprache keine große Rolle.

Die detaillierte Auswertung mit den gemittelten Rundenzahlen pro Spielfeld und Teilnehmer kann separat als Open-Document-Tabelle (ODS) heruntergeladen werden. Die Log-Dateien der einzelnen Teilnehmer werden aufgrund der Größe von ca. 400 MB pro Teilnehmer (ungepackt, entspricht ca. 50 MB gepackt) nicht zum Download angeboten, können aber bei Interesse erfragt werden.

Ebenso gibt es natürlich den Quellcode aller Bots zum Download:

Komplettarchiv (inkl. Engine, Inselfelder und aller Teilnehmer-Bots, 1652 KB).

Noch ein paar Hinweise:

  • Philipp und Christoph Staudinger haben uns versichert, sich nicht gegenseitig abgesprochen zu haben. Die Bots unterscheiden sich sowohl in Sprache als auch in ihrer Strategie.
  • Der Bot von M.Hummel und K.Kleine hat auf einer Insel leider die Rekursionstiefe von Python gesprengt, weswegen dort keine Punkte erzielt werden konnten.
  • Wettbewerbsleiter Dominik Wagenführ hat außer Konkurrenz auch teilgenommen und erhält deswegen keine Platzierung. (Er wäre aber auch disqualifiziert worden, weil sein Bot länger als die vorgeschriebene Zeit benötigt hat. ;))

In der nächsten Ausgabe von freiesMagazin sollen die Gewinner-Bots dann etwas näher vorgestellt werden.

Feedback

Wir freuen uns, dass der Wettbewerb so gut angenommen wurde und es so viele, teilweise altbekannte Teilnehmer gab. Dies motiviert uns, auch im Jahr 2013 wieder einen freiesMagazin-Programmierwettbewerb zu veranstalten. Vorausgesetzt natürlich wir haben eine Idee und die Zeit lässt es zu. Die Erstellung der Spiele-Engine und der grafischen Oberfläche sowie die Auswertung im Nachhinein ist auch immer mit viel Aufwand für uns verbunden.

Trotzdem oder gerade vielleicht deshalb sind wir auf das Feedback der Teilnehmer und Nicht-Teilnehmer gespannt. Was können wir verbessern? Wieso haben Sie z.B. nicht teilgenommen, obwohl Sie theoretisch gerne gewollt hätte? Sollen die Vorabergebnisse während der Einreichungsphase aller Teilnehmer auf der Webseite veröffentlicht werden, sodass man einen direkten Vergleich zu seinen Konkurrenten hat? Oder haben Sie eine Idee für den nächsten Wettbewerb? Schreiben Sie uns in den Kommentaren oder per E-Mail unter redaktion ETT freiesmagazin PUNKT de.

Pingback

[...] war gerade bei freiesMagazin zu lesen, der sechste Programmierwettberb ist zu Ende. Mein Rechner freut sich auf eine Abkühlung, nachdem er jetzt schon 14 Tage auf 100% Last läuft. [...]

Oh, Glückwunsch an die

Oh, Glückwunsch an die Gewinner. :) Ich freu mich jetzt schon auf die Erklärung der Strategien in der kommenden Ausgabe. :)

Eine kleine Frage habe ich dennoch: Hätte es einen Unterschied gemacht, wenn pro Insel nur 100 (250, 500…) Runden gespielt worden wären? Ich kann das leider nicht selbst nachrechnen, das das ODS-Dokument nur die Mittelwerte angibt. Da euer Cheffe Mathematiker ist, hat er aber auch sicher Spaß mir das auszurechnen. ;) Also: Ändert sich was an der Reihenfolge bei etwas weniger Runden? Wie groß ist die Standardabweichung?

Grüße, Keba, der leider aus Zeitgründen nicht teilgenommen hat.

Re: Abweichung

Ich habe mit 100 Wiederholungen einmal den Wettbewerb vorab gerechnet und es ändert sich wenig. Dennoch gibt es aufgrund der zufälligen Ausführung manchmal kleine Unterschiede. Platz 2 und 3 liegen extrem dicht beisammen, wenn man wenig Runden spielt. Je mehr es sind, desto klarer wird die der Unterschied, auch wenn er immer noch sehr gering ist.

Standardabweichung müsste ich erst ausrechnen. Vll. erstelle ich noch eine Liste mit den ganzen Zahlen zum Download. Dann kannst Du es selbst berechnen. :)

Ja, natürlich werden die

Ja, natürlich werden die Unterschiede klarer, wenn mehr Runden gespielt werden. Nur da der Zeitrahmen hier ja schon zu explodieren drohte, hab ich mich eben gefragt, ob man nicht etwas mehr in Richtung Zeitaufwand optimieren sollte. Faktor 10 macht ja schließlich einiges aus. ;)

Also ich persönlich habe

Also ich persönlich habe meine unterschiedlichen Taktiken nur mehr mit 10000 Durchläufen getestet.
Dies erzeugt bei der "island"-Map eine Standardabweichung von ca. 0.05 im Gegensatz zu fast 0.2 bei 1000 runs.
Für meine Feinoptimierung war das nötig, auch wenn es sehr Mühsam ist immer so lange zu warten.

1000 Durchläufe sind mMn also leider wirklich ein Minimum um eine zuverlässige Aussage treffen zu können.

VG, Philipp

Eine gute Sache

In der Liste fehlt mir die Größe des Quelltextes oder die Anzahl der Zeilen.
Es ist ja auch immer gut, wenn ein Programm die Aufgabe nicht nur schnell löst, sondern auch möglichst klein ist.

Ich finde eure Wettbewerbe toll und hätte immer gerne mitgemacht, aber einmal fehlt wie immer die Zeit und vermutlich kann ich noch nicht gut genug Programmieren. Versuchen würde ich es trotzdem gerne!

Es wundert mich, dass nur 20 Leute mitgemacht haben. Leser habt ihr doch deutlich mehr, oder? :D

Ich hoffe ihr habt auch weiterhin die Zeit und gute Ideen um solche Programmier-Wettbewerbe zu veranstalten, so dass ich auch mal teilnehmen kann!

Herzlichen Glückwunsch an die Gewinner und Danke an alle Teilnehmer, deren Quelltext ich mir gerne ansehe um daraus zu lernen (vorallem Python).

Re: Eine gute Sache

„Lines of Code“ ist in meinen Augen ein extrem schlechter Indikator dafür, wie gut oder schlecht ein Programm ist. So hängt dies von der Sprache ab. In C ist es kein Problem, den gesamten Quelltext in eine Zeile zu schreiben, auch wenn das nicht mehr lesbar ist. In Python ist die Struktur mit den Einrückungen und den neuen Zeilen fest eingebaut. Daneben kann man sehr lange darüber streiten, ob eine objektorientierte Lösung, die in der Regel wesentlich größer als eine prozedurale ist, schlechter ist, nur weil mehr Code entstanden ist.

Ob man „gut genug“ für den Wettbewerb ist, erfährt man erst durchs Mitmachen. Und dann sollte natürlich immer vorrangig der Spaß und der Lernwille an erster Stelle bei so etwas stehen. Sicherlich ist es schön, wenn man eine eigene gute Strategie entwickelt hat. Aber genauso interessant ist es, zu erfahren, wie die (ggf. besseren) Lösungen der anderen Teilnehmer ausschauen.

Vielleicht hast Du ja beim nächsten Wettbewerb Zeit und Lust mitzumachen. Wir würden uns freuen!

Pingback

[...] Bots eingereicht. Damit liegt die Teilnehmerzahl hinter denen der letzten beiden Wettbewerbe aus 2012 mit 20 bzw. 2011 mit 26 Teilnehmern. Auch die verwendeten Sprachen konzentrierten sich dieses Mal [...]