• Einleitung
• Installation und Nutzung
• Labyrinth
• Implementierung eines Dukes
• Bewertung
• Ablauf

Neuigkeiten

• Der Referenz-Duke ist verfügbar. Die Teilnahme am Programmierwettbewerb kann als Alternative zur Belegarbeit gewertet werden, wenn der eingereichte Duke besser ist als der CaffeineJunky.
• Neue Version mit Bugfixes und einer Kommandozeilenversion verfügbar.

Einleitung

Seit 1998 wird im Rahmen der Vorlesung Algorithmen und Datenstrukturen ein Programmierwettbewerb durchgeführt - das Hamsterproblem. Ziel dieses von Christian Borgelt erdachten Spiels ist es, einen Hamster, der in einem Labyrinth mit Maiskörnern ausgesetzt ist, per Programm so zu steuern, daß er möglichst viele Maiskörner sammelt und auf ein vorgegebenes Feld bringt.

Auch in diesem Jahr soll diese Tradition fortgesetzt werden, natürlich angepaßt an die neue Programmiersprache Java. Sinnvollerweise wird dabei kein Hamster durch das Labyrinth gesteuert, der Maiskörner sammelt, sondern der Duke - das Java-Maskottchen - sammelt Kaffeebohnen ein!

Installation und Nutzung

Die Aufgabe für den Programmierwettbewerb besteht nun darin, ein Java-Programm zu schreiben, das den Duke durch das Labyrinth steuert. Voraussetzung dafür ist die Wettbewerbsumgebung, die alle benötigten Klassen und Programme beinhaltet. Diese Umgebung erfordert ein JDK 1.2.2 und läft damit sowohl unter Linux, Solaris und Windows. Es funktioniert definitiv nicht mit den M$-Zeug !

Zur Installation:

1. Download der Umgebung und speichern unter dem Namen contest0515.zip
2. Auspacken des Archives mit winzip oder jar:
   

   jar xvf contest0515.zip
   	      

   Dabei entstehen
   • eine Datei contest.jar,
   • ein Verzeichnishtml mit der Dokumentation,
   • ein Verzeichnis mazes für die verschiedenen Labyrinthe
   • und ein Verzeichnis dukes für die Wettbewerbsprogramme.

• MazeEditor zum Erzeugen von Labyrinthen,
• MazeWorld als Ablaufumgebung für die Dukes,
• eine Kommandzeilenversion für schnelle Tests.

java -classpath contest.jar algds.contest.MazeEditor
	  

Ein Duke-Programm wird nun als Java-Klasse implementiert und kann in die Ausführungsumgebung geladen werden. Zuvor ist die kompilierte Klasse im Verzeichnis dukes abzulegen. Demzufolge ist dieses Verzeichnis für die Ausführungsumgebung ebenfalls in den Klassenpfad aufzunehmen (Unix/Linux):

java -classpath contest.jar:dukes algds.contest.MazeWorld
	  

java -classpath contest.jar;dukes algds.contest.MazeWorld
	  

java -classpath contest.jar:dukes algds.contest.MazeRunner \
  mazes/Contest.maze Dude
	  

Labyrinth

Ein Labyrinth besteht aus Gängen, in denen Kaffeebohnen in unterschiedlicher Anzahl abgelegt sind. Der Duke kann im Labyrinth umherlaufen, sich drehen, nach vorn schauen, Bohnen aufnehmen und ablegen. Spezielle Felder - die Beamer erlauben den Transport auf eine andere Ebene. Hier gilt, daß man von einem Ziel-Beamer-Feld durch Verlassen und Wiederbetreten zurüuck zum Ausgangsfeld gelangt.

Implementierung eines Dukes

Das Schreiben eines Duke-Programms ist relativ einfach: es stehen nur wenige Steuerbefehle zur Verfügung, die man kennen muß. Die Schwierigkeit besteht vielmehr darin, sich eine geeignete Strategie zum Erkunden des Labyrinthes und Sammeln der Bohnen zu überlegen.

Jeder Duke muß als Java-Klasse implementiert und von der Klasse algds.contest.Duke abgeleitet werden. Das Leben eines Dukes spielt sich vollständig in der Methode run ab, die für jeden Duke neu implementiert werden muß. Zur Steuerung stehen die folgenden Methoden zur Verfügung:

• turn (int direction): Ändert die Laufrichtung, wobei das aktuelle Feld nicht verlassen wird. Mögliche Parameter für die Drehrichtung sind :Duke.TURN_LEFT und Duke.TURN_RIGHT.
• boolean forward ():Bewegt den Duke um einen Schritt in der aktuellen Richtung vorwärts.
• boolean take (int num): Nimmt die angegebene Anzahl von Bohnen aus dem aktuellen Feld auf.
• void drop (int n): Legt die angegebene Anzahl von Bohnen im aktuellen Feld ab.
• int look (): Liefert Informationen über das in Blickrichtung angrenzende Feld mit folgenden Werten:
  • Duke.EMPTY: leeres Feld
  • Duke.BEANS: Feld mit Kaffeebohnen
  • Duke.WALL: Feld ist in dieser Richtung durch eine Wand begrenzt
  • Duke.BEAMER: Feld mit Beamer

Betrachten wir abschließend einen kompletten, aber ziemlich dummen Duke:

import algds.contest.Duke;

public class Dude extends Duke {
  public Dude {}

  // die Hauptmethode des Dukes
  public void run () {
    // max. 1000 Schritte
    while (getNumOfSteps () < 1000) {
      // irgendwohin gehen
      go ();
      // wenn wir zufaellig auf dem Ausgangsfeld
      // sind => Bohnen ablegen
      if (getXPos () == 0 && getYPos () == 0)
        drop (Duke.MAX_BEANS);
      else
        // sonst alles mitnehmen
        take (Duke.MAX_BEANS);
    }
  }

  protected void go () {
    // manchmal wechseln wir einfach die Richtung
    if (Math.random() > 0.9) {
      int dir = (Math.random () <= 0.5 ? Duke.TURN_LEFT : 
                                         Duke.TURN_RIGHT);
      turn (dir);
    }
    // vor einer Wand muessen wir uns aber
    // entscheiden
    while (look () == Duke.WALL) {
      int dir = (Math.random () <= 0.5 ? Duke.TURN_LEFT : 
                                         Duke.TURN_RIGHT);
      turn (dir);
    }
    // weiter gehts ...
    forward ();
  }
}
	  

javac -d dukes -classpath contest.jar Dude.java

Bewertung

Im Wettbewerb muß jeder Duke drei Labyrinthe durchlaufen, wobei eines davon zuvor bekanntgegeben wird. Es gelten dabei folgende Regeln:

• Es darf nur die dokumentierte Schnittstelle der Klasse algds.contest.Duke verwendet werden, d.h. insbesondere ist das Laden der Labyrinthe und das Auslesen der Struktur direkt durch den Duke nicht erlaubt.
• Pro gesammelter Kaffeebohne werden 20 Pukte berechnet. Es werden dabei nur die Bohnen gezählt, die auf dem markierten Ausgangsfeld (0,0) abgelegt sind.
• Der Duke kann maximal 12 Bohnen gleichzeitig tragen.
• Für jeden Schritt von Feld zu Feld wird 1 Punkt abgezogen.
• Ein Kollision mit der Wand wird mit 20 Minuspunkten bestraft.
• Der Duke verbraucht beim Bewegen natürlich Energie. Dieser Verbrauch geht zu Lasten seiner Stärke. Nach je 30 Schritten muß der Duke daher eine Kaffeebohne naschen. Dies erfolgt instinktiv (d.h. automatisch), indem eine transportierte Bohne vernascht wird. Hat der Duke keine Bohne dabei, wird im ein Stärkepunkt abgezogen.
• Unterschreitet die Stärke den Wert 0, so stirbt der Duke.
• Im Wettbewerb wird eine geeignete Zeitgrenze (z.B. 5 Minuten) festgelegt.

Die Teilnahme am Programmierwettbewerb kann als Alternative zur Belegarbeit gewertet werden, wenn der eingereichte Duke für die Wettbewerbslabyrinthe in der Summe eine bessere Punktzahl erreicht als der Referenz-Duke.

Ablauf

Teilnahmeberechtigt am Wettbewerb sind alle Studentinnen und Studenten, die die Vorlesung Algorithmen und Datenstrukturen von Prof. Saake im WS 1999/2000 sowie SS 2000 hören. Jeder Teilnehmer (einzeln oder im Team von 2 Personen) muß bis zum 18.Juni 2000 den Quelltext seines Dukes per EMail an mich senden. Der Klassenname sollte die Matrikelnummer enthalten, um eine einfache Unterscheidung zu ermöglichen. Die besten Dukes treten danach in einer Endrunde mit neuen Labyrinthen an, die in der letzten Vorlesungswoche live ausgetragen wird. Den Siegern winken natürlich tolle Preise !!!!