SUN-Preis 2002 - Aufgabenstellung

Regeländerungen

• 31.7.: Wenn ein Roboter geschoben wird, erleidet er einen geringfügigen Schaden (oder muss sein Weltbild wieder in Ordnung bringen) und führt daher in der nächsten Runde die Aktion "Stehenbleiben" aus. Das macht das Spiel interessanter, da man (unter anderem) jetzt andere Roboter z.B. in eine Aliensiedlung schieben kann oder in einen Tunnel, und dann die entsprechenden Aktionen nach dem Stehenbleiben ausgeführt werden.

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:

• nach vorne ziehen
• nach hinten ziehen
• rechts drehen
• links drehen
• stehenbleiben

• Steppe ("normale Felder"): Hier macht der Roboter, was man ihm sagt.
• Berge: Hier kommt der Roboter nicht weiter, auf ein solches Feld kann nicht gezogen werden.
• Sümpfe (verschiedener Tiefe): Hier ist es schwieriger, voran zu kommen. Der Roboter muss (je nach Tiefe des Sumpfes) eine oder mehrere Runden pausieren.
• Gletscher: Hier kann der Roboter sich nicht halten und rutscht in eine bestimmte Richtung ab.
• Wirbelstürme: Hier wird der Roboter in eine bestimmte Richtung gedreht (um 90, 180 oder 270 Grad).
• Tunnel: Von einem Ende eines Tunnels wird der Roboter zum anderen befördert (und natürlich umgekehrt).
• Alien-Siedlungen: Die Planetenbewohner freuen sich nicht über den Besuch und bringen den Roboter daher in die Nähe des letzten erreichten Zieles zurück.

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.):

• Sicht der Spieler (die Werte von drei der Sensoren werden als RGB-Farbwerte interpretiert und entsprechend dargestellt). Die Zahlen geben die Ziele an. Die Bilder markieren die Position der Roboter (jeder Teilnehmer soll ein eigenes Bild bereitstellen).
  
• Sicht des Spielleiters
  

Detailliertere Regeln

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:

• Spieler 1 erhält die Aufforderung, einen Zug zu machen.
• Spieler 1 meldet dem Server seinen Zug. Wenn er nicht innerhalb von n ms (Zeitspanne wird noch festgelegt) seinen Zug dem Server mitteilt, wird dies als "Stehenbleiben" interpretiert.
• Der Zug von Spieler 1 wird durchgeführt.
• Alle Spieler bekommen die neue Spielfeldsituation mitgeteilt.
• Dies wiederholt sich für alle Spieler in der Reihenfolge ihrer Starnummern, bis ein Spieler alle Zielpunkte in der richtigen Reihenfolge erreicht hat. (Falls dies auch nach einer großen Rundenzahl nicht absehbar ist, kann das Spiel abgebrochen werden.)

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

• F: Wrappt die Karte, also komm ich vom obersten rechten Feld mit einem Schritt nach rechts auf das linke oberste Feld?
  A: Nein, man kann sich das Spielfeld als von Bergen umgeben vorstellen, d.h. man kann nicht runterfallen und nicht außen herum gehen.
• F: Braucht man in einem Tunnel Zeit oder taucht man bei einem Schritt auf ein Tunnelende sofort auf der anderen Seite auf?
  A: Der Tunnel wirkt sofort, d.h. als Effekt des Feldes. Wenn man wieder zurück will, muss man nur einmal stehenbleiben.
• F: Funktionieren die Tunnel in beide Richtungen?
  A: Ja.
• F: Was passiert wenn auf dem Tunnelende schon ein anderer Roboter steht?
  A: In dem Fall ist der Tunnel blockiert. Man bleibt also stehen.
• F:Ist das Satellitenbild "nur" auf den Farbwerten verrauscht, oder können auch benachbarte Felder vertauscht werden?
  A: Vertauschen der Felder ist nicht vorgesehen, man kann sich jedoch einen Einfluss benachbarter Messwerte vorstellen. Die genaue Verteilung kann beliebig komplex werden.
• F: Wie gut ist das Satelitenbild aufgelöst? Kann ich mich drauf verlassen, dass die Anzahl der Messwerte des Satelitenbildes der Anzahl der Felder auf dem Spielfeld entspricht?
  A: Ja.
• F: Wie groß ist der Sichtradius des Roboters? Sieht er nur das Feld auf dem er steht oder kann er weiter sehen? Merkt der Roboter, wenn sich seine Position verändert, obwohl er sich nicht bewegt hat? Hat er ein GPS und einen Kompass eingebaut? Weiss der Roboter, wo sich die anderen Roboter befinden?
  A: Der Roboter sieht und merkt eigentlich garnichts. Der Spieler sieht (fast) alles, z.B. die aktuellen Positionen aller Roboter.
• F: Ist es erlaubt andere Roboter absichtlich in eine Aliensiedlung oder einen Sumpf zu schieben? Wird das Ereignis auf dem Feld auf das man geschoben wird ausgeführt?
  A: Achtung Regeländerung! Ja. Ja, indirekt. Nach dem Schieben muss der andere Roboter eine Runde stehenbleiben. Dann wird die Aktion ausgeführt.
  (früher: A: Ja. Nein (der andere Spieler kann also von dem Feld noch herunterziehen, wenn das möglich ist).)
• F: Ist Knowledge Sharing mit anderen Robotern erlaubt?
  A: Das ist nicht vorgesehen, es gibt nur Client-Server Kommunikation. Man könnte sich jedoch Kommunikation durch eine Art "Bienentanz" vorstellen. Diese wäre erlaubt.
• F: Sind interpretierte Sprachen erlaubt? Auf der Webseite steht, jede Sprache, die auf dem Rechner kompiliert werden kann. Ich würde halt gerne in XYZ programmieren. Der Interpreter kann auf jeden Fall auf Intel/Linux kompiliert werden.
  A: Das sollte kein Problem sein, solange wir es einfach zum Laufen bringen.
• F: Was passiert, wenn ein Roboter auf ein Gletscher geht, der auf einen Gletscher "zeigt"? Wird die Aktion des Gletschers damit aufgehoben?
  A: Es wird nach jeder Bewegung eines Roboters genau einmal die Aktion des Feldes, auf dem er zu stehen kommt, ausgeführt. In dem o.g. Fall würde er also z.B. in der ersten Runde auf den anderen Gletscher rutschen. Wenn er sich nicht bewegt, würde er dann wieder auf den ersten Gletscher rutschen.
• F: Was passiert, wenn ein Roboter auf ein Gletscher geht, der auf einen Felsen "zeigt"? Wird die Aktion des Gletschers damit aufgehoben?
  A: Ja, auf einen Felsen (Berg) kann man nicht geschoben werden. Der (dann doch nicht) geschobene Roboter muss dann auch nicht aussetzen.
• F: Wie äussert sich das aussetzen bei Sümpfen? Wird der entsprechende Client einfach übersprungen, wird die Aktion, die zur dosomething-Aufforderung gesendet wird ignoriert, oder kommt eine donothing-Anweisung?
  A: Der Client erhält die Meldung "marsh /Tiefe/" und wird übersprungen.
• F: Hat ein Feld genau eine Eigenschaft?
  A: Ja.
• F: Warum ist die Eigenschaft "Farbe" beim "Field" mehrdimensional? Erhält jeder Spieler andere Meßwerte?
  A: Nein, jeder Spieler erhält das gleiche Feld. Der Satellit liefert eben mehrere Messwerte pro Feld. Die ersten drei kann man dann als Farbwerte (R,G,B) darstellen.
• F: Startet Player n von Startposition n ? Wie ist im Protokoll implementiert, welche Startposition welchem Spieler zugeordnet wird?
  A: Ja. Die Position richtet sich also nach der Anmeldungsreihenfolge. Im Turnier wird das vorgegeben sein, um evtl. Startreihenfolgen geeignet zu permutieren.
• F: Ist die Startrichtung immer "north"/Norden?
  A: Ja.
• F: Startet man immer von einem "normalen Feld"?
  A: Ja.
• F: Erfährt man auf welche Art von Feld man selber getreten ist, oder kann man dies nur aus der Aktion interpretieren?
  A: Letzteres.
  F: z.B. ich stehe im Sumpf und möchte vorwärts gehen. Kann ich unterscheiden, ob ich wegen des Sumpfes nicht voran komme, oder ob sich evtl. ein Fels vor mir befindet.
  A: Bei einem Sumpf kommt der Spieler nicht zum Zug. Aber ein entgegengesetzter Gletscher und ein Berg können schwer zu unterscheiden sein.
• F: Kann man mehrere Roboter, die hintereinander stehen, schieben ?
  A: Ja. Es müssen dann alle geschobenen Roboter aussetzen.
• F: Können Gletscher auch wie Tunnel "blockiert" sein ? Oder schiebt man eine Roboter, der am Gletscherausgang steht, bei der Ausführung der Gletscheraktion automatisch, falls dieses geht, weiter ?
  A: Letzteres; sofern Schieben möglich ist.
• F: Kann ich Pseudospieler anmelden (zum Beispiel durch Freunde) und somit durch einen "Bienenentanz" einen Roboter z.B. vordefiniert das Spielfeld ablaufen lassen damit der andere daraus Informationen über das Spielfeld erhält?
  A: Interessante Idee, die man unter den Punkt "unfaires Verhalten" einstufen sollte. Das ist natürlich schwer nachzuprüfen, aber die Information des Bienentanzes ist für alle Spieler wertvoll, es ergibt sich also kein direkter Vorteil.
• F: Gibt es nur Sümpfe der Tiefe 1 bis 3?
  A: Ja.
• F: Ist es Richtig, dass wenn man einen Roboter von vorne oder von hinten schiebt, das dieser, egal auf welches Feld er geschoben wurde, im nächsten Zug sofort einfach zurückschieben kann ? (Dies bedeutet das man den Roboter nur in Fallen schieben kann wenn man ihn von der Seite schiebt)
  A: Nach der Regeländerung gilt dies nicht mehr, da ein geschobener Roboter nun einen Zug aussetzen muss.(Antwort vor der Regeländerung war: Ja, Zurückschieben ist möglich. Das setzt natürlich voraus, dass der andere Roboter immer auf die geschilderte Weise reagiert.)
• F: Wird die Karte so gestellt, das es keine Fallen gibt aus denen man nicht heraus kommen kann?
  A: Das kann nicht garantiert werden, ist aber unwahrscheinlich und wird versucht zu vermeiden.
• F: Wird die Karte rein zufällig generiert oder werden z.B. Irrgärten oder dergleichen eingebaut?
  A: "Rein zufällig", aber das ist ein dehnbarere Begriff. Die Zufallsverteilung könnte z.B. nur Irrgärten produzieren.
• F: Wird der Wettbewerb in nur einer Runde mit allen Spielern ausgetragen oder gibt es ein Rundensystem in dem z.B. die ersten beiden Spieler, oder die Punktbesten Spieler weiterkommen?
  A: Das steht noch nicht fest, aber ein Rundensystem ist wahrscheinlich.
• F: Welcher Verteilung unterliegt das Rauschen der Sensordaten?
  A: Das ist "unbekannt". Die Verteilung ist das einzige, das nicht bekannt gegeben wird, da das Lernen sonst unnatürlich einfach wird (in praktischen Sitauation kennt man die Verteilung i.d.R nicht).
• F: Unterscheiden sich Gletscher unterschiedlicher Richtung, Sümpfe unterschiedlicher Tiefe oder Wirbel unterschiedlicher Drehung prinzipiell in den Sensordaten?
  A: Das kann nicht ausgeschlossen werden.
• F: Wie wird die Rechenzeit aufgeteilt ? Kann ich Prozesse "forken" um so mehr Rechenzeit zu haben? Habe ich nur Rechenzeit wenn ich am Zug bin?
  A: Das würde unter "unfaire Mittel" eingestuft und zur Disqualifizierung führen. Rechenzeit steht ständig zur Verfügung.
  Hinweis: Das Attribut "unfair" bezieht sich nur auf den eventuellen Versuch, VIELE Prozesse zu forken, mit dem Ziel deutlich mehr Rechenzeit als die anderen Spieler zu erhalten (wobei eine genaue Definition von "viele" Schwer ist, aber sicher mehr als zwei; außerdem wird das Problem möglicherweise dadurch gelöst, dass jeder Client auf genau einem Rechner läuft). Zwei Threads zu haben (z.B. einen für die Kommunikation, einen zur Planung) ist sicherlich OK.
  
• F: Können Sie Angaben zur verfügbaren Zeit pro Zug machen in Bezug auf den Rechner auf dem die Programme laufen?
  A: Noch nicht. Die Rundenzeit wird so kurz gewählt werden, dass eine große Anzahl von Spielen bei erträglicher Zeit möglich ist. Man sollte also auf Effizienz achten. Keine Antwort wird allerdings als "Stehenbleiben" interpretiert, so dass es nicht zum Abbruch des Spiels führen muss. Eine Zugzeit von 200 ms scheint sich abzuzeichnen.
• F: Können Sie Angaben zur verfügbaren Zeit pro Zug machen in Bezug auf die grösse des Problems ? (ein Spielfeld mit 10x10 Kästen benötigt sicher weniger Rechenleistung als ein Spielfeld mit 1000x1000 Kästchen)
  A: Die Größe des Spielfeldes wird nicht zu groß werden, da es am Bildschirm zu verfolgen sein sollte und nicht zu viele Züge brauchen sollte.
• F: Ist der Arbeitsspeicher begrenzt ? (Auch in Bezug der Problemgröße)
  A: Ja, in etwa durch (Hauptspeicher-Serverressourcen-Betriebssytemressourcen)/#Spieler.
• F: Wird der Spieler von einem Alien immer GENAU auf den letzten erreichten Zielpunkt gebracht?
  A: Nein, falls das Feld besetzt ist, wird eines der umliegenden Felder ausgesucht.
• F: Wohin wird der Spieler von einem Alien gebracht, bevor er den ersten Zielpunkt erreicht hat?
  A: Auf den Startpunkt.
• F: Kann sich die Orientierung des Spielers ändern, wenn er bewegt wird (Tunnel, Alien, Schieben)?
  A: Nein.
• F: Sind die Startpunkte und Zielpunkte immer normale Felder?
  A: Ja.
• F: Sind die Sensoren-Messwerte immer im Bereich 0-255?
  A: Ja.
• F: Ist ein Überlappen der Verteilungen der Messdaten möglich? (Oder: Wenn zwei Felder die selben Sensorwerte haben, verbirgt sich dann hinter diesem Feld auch die selbe Funktion oder sind die Messdaten so stark verrauscht, dass einen solche Überlagerung vorkommen kann?)
  A: Ja. (Eine solche Überlagerung kann vorkommen.) Es ist jedoch nicht klar, wie wahrscheinlich das ist...
• F: Können mehrere Aktionen nacheinander passieren (z.B. das Rutschen über mehrere Gletscherfelder?
  A: Nein. Es wird immer genau eine Aktion ausgeführt, und zwar genau die, die zu dem Feld gehört, auf dem der Spieler nach seinem Zug steht.
• F: Kann man aus der Verteilung der Felder in den Beispielszenarien auf die Verteilung im Wettbewerb schließen?
  A: Jein. Man sollte sich nicht darauf verlassen, dass die Verteilungen identisch sind, aber einen Zusammenhang wird es geben, da man aus den Beispielen ja lernen soll.
• F: Gibt es irgendwo außer im Server bzw im Client ne gescheite Definition des Kommunikationsprotokolls?
  A: Nein. Bisher nicht.
• F: Der Spieler wird aber nur über "marsh" informiert, nicht über Berge und so, oder?
  A: Richtig.
• F: Generell: wird hierbei die Nachricht z.B. "marsh 2" als broadcast geschickt oder nur an den betreffenden Spieler?
  A: Nur an den Spieler.
• F: Sind die Zielpunkte fuer alle Spieler die selben?
  A: Ja.
• F:Zu dem erforderlichen Bild für den Roboter tauchten noch Fragen auf: Welche Auflösung ist empfohlen? Die Beispielbilder sind ja alle recht groß, werden aber vergleichsweise klein dargestellt. Wenn wir das Bild nun direkt in der richtigen Auflösung abgeben, wäre das der Qualität sicher zuträglich.
  A: Die Bildschirmauflösung hängt unter anderem auch von der Spielfeldgröße ab, aber die Bilder sollten so sein, dass sie auch bei kleiner Auflösung gut zu erkennen sind. Also keine Auflösung empfohlen.
• F: Müssen wir für jede Richtung ein eigenes Bild abgeben oder nur eine Standard-Ansicht (z.B. Nord)?
  A: Eine Standard-Ansicht reicht, wer möchte kann auch alle vier Ansichten abgeben.
• F: Kann man, falls zur Ermittlung des Siegers tatsächlich mehrere Läufe durchgeführt werden, bereits gewonnene Daten aus einem Lauf auf der Festplatte speichern und im nächsten laden, so dass einem diese bereits zu Beginn dieses nächsten Laufs zur Verfügung stehen?
  A: Nein, das wäre nicht zulässig.
• F: Macht Verschieben durch einen Gletscher genauso Schaden wie Verschieben durch einen anderen Roboter, muss man also in beiden Fällen eine Runde aussetzen?
  A: Nein, ein Gletscher verursacht keinen Schaden.
• F: Wird Push-Schaden absitzen auf die Sumpf-Zeit angerechnet?
  A: Nein. Der Schaden fuehrt ja erst dazu, dass man im Sumpf stecken bleibt, wenn man hineingeschoben wird.
• F: Startet die Sumpf-Aussetz-Zeit ein zweites Mal, wenn man sich nach Ablauf der ersten Wartezeit auf dem Sumpffeld dreht?
  A: Ja.
• F: Ist die Reihenfolge der Input-Daten stabil?
  A: Ja.
• F: Koennen wir davon ausgehen, dass die Startnummern bei 0 anfangen?
  A: Ja
• F: Ist die Nachricht "marsh (tiefe)" immer die absolute tiefe oder die noch "abzusitzenden" tiefenlevel?
  A: Letzteres.
• F: Darf der Beispielcode im eigenen Projekt beliebig verwendet und modifiziert werden? (Lizenzrechtliche Gründe?)
  A: Ja. (Solange das "nicht kommerziell" geschieht.)
• F: Welche meldung bekommt man, wenn man wegen Schadens aussetzen muss?
  A: Keine. Man wird eine Runde übersprungen. (Man koennte das z.B. daran merken, dass der Roboter sich bewegt hat, ohne dran zu sein.)
• F: Was passiert, wenn in der unmittelbaren Umgebung des letzten Zielfeldes kein Platz mehr ist, und ein Spieler ein Alienfeld erreicht?
  A: In dem Fall wird das Spiel annuliert und wiederholt.
• F: Dürfen andere Libraries benutzt werden?
  A: Ja, alle frei verfuegbaren Libraries dürfen genutzt werden.
• F: Was passiert, wenn ein Roboter aus dem Sumpf herausgeschoben wird?
  A: In dem Fall muss er trotzdem weiter aussetzen. (Der Roboter muss sich erst von seinem Aufenthalt im Sumpf erholen/reinigen.)