SUN-Preis 2002 - Aufgabe

SUN-Preis 2002 - Aufgabenstellung

Regeländerungen können sich im Verlauf des Wettbewerbs noch ergeben. Diese werden durch die Mailingliste und auf dieser Seite bekanntgegeben. Unklarheiten bitte mitteilen.

Regeländerungen


Die Programmieraufgabe besteht darin, ein Programm zu entwickeln, das einen Spieler für das folgende Spiel implementiert.

Die Spieler kreisen in einem Raumschiff um einen entfernten Planeten. Auf diesem Planeten hat jeder der Spieler vor Beginn des Spiels einen Roboter abgesetzt, der sich auf der Planetenoberfläche bewegen kann. Ziel des Spieles ist es, mit seinem Roboter eine Reihe von vorgegebenen Zielen in der richtigen Reihenfolge anzusteuern. Das (seltsamerweise rechteckige) Spielfeld ist dazu in Planquadrate eingeteilt und in jedem Zug kann der Roboter eine von fünf möglichen Aktionen ausführen:

Dabei ist bekannt, dass auf der Oberfläche des Planeten verschiedene Beschaffenheiten existieren: Eine Schwierigkeit für die Spieler besteht nun darin, dass sie zwar wissen, welche Beschaffenheiten es gibt, aber nicht, was für eine Beschaffenheit welches Feld hat. Zu Beginn des Spieles kennen die Spieler lediglich die Daten, die ihnen ein Satellit geliefert hat. Der Satellit hat zu jedem Planquadrat Messwerte mit verschiedenen Sensoren aufgezeichnet und die Vermutung liegt nahe, dass sich diese Messwerte in Beziehung zu der Beschaffenheit des Feldes setzen lassen. Wie diese Beziehung jedoch aussieht ist zunächst nicht klar. Außerdem sind die Messdaten natürlich verrauscht, sodass der Zusammenhang nicht unbedingt eindeutig ist. Die Anzahl der Sensoren und damit der Messwerte ist zunächst nicht festgelegt.

Der Spieler muss also versuchen, aus seinen Beobachtungen und dem Verhalten der anderen Spieler zu lernen, wie dieser Zusammenhang aussehen könnte und entsprechend seiner unsicheren Information einen möglichst guten Weg planen.

Dabei können sich die Roboter natürlich auch gegenseitig behindern, da nie zwei Roboter auf einem Feld stehen können. Ein Roboter kann daher einen anderen (oder mehrere) wegschieben, sofern das möglich ist (also nicht auf Berge oder vom Spielfeld geschoben wird.) Die Züge werden entsprechend der Rundenabfolge ausgeführt (s.u.).

Beispielplanet: (Die Verteilung der Felder wird sich noch ändern (siehe Software-Seite); In diesen Beispielen ist die Zuordnung zu einfach.):

30. 9. 2002: Dank Dennis Kasprzyk und Volker Krause existieren inzwischen schönere Grafiken für die verschiedenen Feldtypen (download hier):

Detailliertere Regeln

Das Spiel läuft folgendermaßen ab:

Zunächst wird vom Spielleiter (Server) der "Planet mit dem Satelliten abgetastet" und die Position der Roboter sowie der Zielmarken bestimmt. Nun können sich die Spieler (Clients) beim Server anmelden und erhalten ihre Startnummer. Sobald alle Spieler angemeldet sind, wird das Spielfeld an alle Spieler übertragen. Die Spieler haben nun Zeit zur Initialisierung (Zeitspanne wird noch festgelegt). Nach der Initialisierungszeit beginnt das Spiel durch Wiederholung von Runden der folgenden Form:

Sobald ein Spieler alle Ziele in der richtigen Reihenfolge erreicht hat, wird nur noch diese Runde zuende gespielt. D.h. es dürfen alle Spieler mit größerer Nummer noch einmal ziehen. Für die Punktgebung ist nur entscheidend, wieviele Ziele ein Spieler erreicht hat.

Hier findet sich ein kommentiertes Protokoll einer Beispielkommunikation.

Wer versucht, die Gegenspieler mit unfairen Mitteln zu behindern oder Fehler des Servers auszunutzen, wird disqualifiziert.


(F)AQ

Nach der Proberunde zeigt sich folgendes Szenario der Spiele: Jeder Client läuft auf einem eignenen Rechner, der in etwa die Konfiguration Dual Intel PIII 750+MHz 1G / Linux haben wird. Rundenzeit 200ms.
Daniel Keysers
Last modified: Thu Nov 14 10:41:35 CET 2002