Tag der Informatik -- Sun-Preis 1997
Auch in diesem Jahr werden von der Firma Sun Microsystems GmbH Preise zur Verfügung gestellt, die am Tag der Informatik (5. Dez. 1997) verliehen werden. Dazu soll eine Programmieraufgabe gelöst werden, in der eine Spielstrategie für das Spiel Wormworld zu entwickeln ist.
Die Teilnehmenden sollen eine möglichst geschickte Spielstrategie programmieren. Die einzelnen Programme spielen dann mit verschiedenen Ausgangssituationen gegeneinander. In einer Vorrunde werden zunächst die drei besten Programme ermittelt. Die Endrunde findet am Tag der Informatik statt, wo die drei besten Strategien live gegeneinander antreten.
Die Preise staffeln sich wie folgt:
| 1. Preis: |
1000,- DM
|
| 2. Preis: |
650,- DM
|
| 3. Preis: |
350,- DM
|
Teilnahmeberechtigt sind alle Studierenden der RWTH Aachen, die das Diplom noch nicht abgeschlossen haben. Insbesondere ist auch eine Teilnahme in Gruppen möglich. Das Programm kann in einer beliebigen Programmiersprache erstellt werden, muß aber auf einer Sun-Workstation unter Solaris 2.5 laufen. Einsendeschluß für die Programme ist Freitag, der 14. November 1997.
Sie sollen eine Spielstrategie für Wormworld implementieren. Das Spielfeld ist ein rechteckiges Gitter. Auf dem Spielfeld befinden sich Würmer, Hindernisse und ein Loch. Es spielen jeweils zwei Spieler gegeneinander. Jeder Spieler hat eine feste Anzahl von Würmern, welche sich zu Beginn an vorgegebenen Positionen des Spielfelds befinden. Die Würmer sind genau drei Felder des Gitters lang und besitzen einen Kopf, welcher die Bewegungsrichtung des Wurms festlegt. Ein Wurm kann in einem Schritt nur nach links, rechts oder vorne ziehen, und sein Körper rutscht nach, das heißt die ursprüngliche Kopfposition wird zur Position des zweiten Wurmglieds, und die frühere Position des zweiten Wurmglieds wird zum Schwanz. Diagonale Züge sind nicht erlaubt. Ein Zug ist natürlich nur möglich, falls die neue Kopfposition frei, d.h. nicht durch ein Hindernis bzw. einen anderen Wurm blockiert ist.
Erreicht ein Wurm bei einem Zug mit seinem Kopf die Lochposition, so rutscht er direkt durch das Loch hindurch und ist vom Spielfeld verschwunden. Die Spieler ziehen abwechselnd ihre Würmer. Kann ein Spieler keinen Wurm ziehen, da alle seine Würmer blockiert sind, muß er aussetzen, sonst muß er ziehen. Gewonnen hat der Spieler, welcher zuerst alle seine Würmer ins Loch befördert hat. Tritt eine Spielsituation ein, in der beide Spieler keinen Wurm mehr ziehen können, wenn also ein Deadlock vorliegt, endet die Partie unentschieden. Wir geben außerdem eine maximale Zugzahl vor. Hat nach diesen Zügen keiner der Spieler alle seine Würmer ins Loch befördert, gewinnt der Spieler, der weniger Würmer auf dem Spielfeld hat. Bei gleicher Würmerzahl endet die Partie ebenfalls unentschieden.
Tritt mit dem letzten Zug des Spiels ein Deadlock ein (treffen also beide der vorangegangenen Regeln zu), gewinnt der Spieler mit der geringeren Wurmzahl.
Eine mögliche Ausgangssituation ist
die folgende:
Die maximale Größe des Spielfeldes ist 30 x 30, die Zahl der Hindernisse ist nicht beschränkt. Jeder Spieler hat maximal 20 Würmer.
Ihr Programm soll im Wettkampf gegen andere Programme antreten. Deshalb muß es mit anderen Programmen kommunizieren können, um Züge des Gegners zu erhalten bzw. seine eigenen Züge auszugeben. Diese Kommunikation erfolgt textuell über die Standardein- bzw. -ausgabe. Auch die Ausgangssituation erhält ihr Programm von der Standardeingabe. Wir entwickeln ein Kontrollprogramm, welches zwei Strategieimplementierungen nebenläufig startet, beiden die Ausgangssituation mitteilt, die Kommunikation während des Spiels steuert und das Spielfeld und die Wurmbewegungen graphisch darstellt. Eine genaue Beschreibung der Schnittstelle incl. eines Beispiels finden Sie hier.
Da die Zeit, die Ihr Programm benötigt bis es einen Zug ausgibt, von der Rechnerleistung abhängt, können wir natürlich keine für Sie wirklich aussagekräftigen Vorgaben für Ihr Programm machen. Das Programm soll auf unserer Sparc Ultra maximal 2 Sekunden pro Zug rechnen, da sonst ein Echtzeitspiel nicht möglich ist. Sollte Ihr Programm zu lange rechnen werden wir mit Ihnen Rücksprache halten, und Sie können Ihr Programm noch optimieren.
Ihr Programm darf weder auf das Dateisystem, noch auf das Netzwerk zugreifen und muß mit 32 MByte Hauptspeicher auskommen. Außerdem soll ihr Programm sequentiell arbeiten, d.h. insbesondere darf es, nachdem es einen Zug ausgegeben hat und auf den Zug des Gegners wartet keine weiteren Rechnungen durchführen, da es (auf einem Einprozessorsystem) sonst seinem Gegner Rechenzeit wegnimmt.
Für Solaris 2.5 stehen viele Compiler zur Verfügung. Hier sei nur eine kleine Auswahl erwähnt. Sollten Sie einen anderen Compiler verwenden wollen, so halten Sie bitte Rücksprache mit uns.
Ihren Programm-Source-Code und eine Anleitung zur Compilation schicken
sie bitte bis zum 14. November 1997 per EMail an mich.
Außerdem sollte Ihre EMail die Namen der Teilnehmer und eine Telefonnummer,
unter der Sie zu erreichen sind, enthalten.
Sollten sich später Probleme bei der Übersetzung, oder der
Programmmausführung ergeben werde ich nocheinmal Rücksprache mit Ihnen
halten.
| Spieler | Punkte |
|---|---|
| Edmund Bayerle | 120 |
| Thomas Böttcher | 152 |
| Thorsten Brehm | 163 |
| Jörg Dölfer | 125 |
| Stefan Ehren, Thomas Herzog, Frank Reker | 165 |
| Felix H. Gatzemeier | ***** |
| Peter Kliem | 239 |
| Eike Marx | 9 |
| Rajendra Persaud, Marc Spaniol | ***** |
| Ansgar Schleicher | 213 |
| Frank Schneider | ***** |
| Volker Stolz, Nikolaus Bayer, Lucia Cloth | 245 |
| 1. Platz | Frank Schneider |
| 2. Platz | Rajendra Persaud, Marc Spaniol |
| 3. Platz | Felix H. Gatzemeier |
Dank Frank Schneider gibt es nun auch eine Gesamtdokumentation der Wormworld-Ausscheidung.