Welfenlab Competition 2006

Wir, d.h. der Lehrstuhl Graphische Datenverarbeitung in der Fakultät Elektrotechnik und Informatik veranstalten für Schüler an niedersächsischen Gymnasien einen Wettbewerb im Bereich der Computergeometrie. Wir nennen unser Fachgebiet Welfenlab, nach dem Hauptgebäude der Universität, dem Welfenschloss, daher der Name "Welfenlab Competition". Bisher fand der Wettbewerb fünfmal statt und auch in diesem Jahr gibt es ihn wieder.

• Diesen Text als PDF Datei herunterladen

Nachdem in den letzten Jahren eher theoretische Themen wie Knoten und kürzeste Wege behandelt wurden, beschäftigen wir uns diesmal hauptsächlich mit künstlicher Intelligenz. Ihr sollt nämlich versuchen dem Computer Backgammon beizubringen.

_{(Bild: de.wikipedia.org)}

Backgammon ist eines der ältesten Brettspiele der Welt, die heute gespielte Version basiert auf einer Variante aus dem Mittelalter (siehe Abbildung). Der Erfolg beim Spiel hängt zwar auch vom Glück, vor allem aber von einer guten Strategie ab. Ziel der Competition ist es ein Programm zu schreiben, das möchlichst gut Backgammon spielt.

Unabhängig von viel Erfahrung, Ehre und Ruhm gibt es auch etwas Handfestes zu gewinnen:

Die Welfenlab Competition 2006 ist nun beendet und die Preisträger des Wettbewerbs wurden im Rahmen der Ada Lovelace Memorial Celebration geehrt. Die Gewinner sind:

1.Platz
Jan Gosmann , Bismarckschule Hannover

2.Platz
Ilya Elenskiy , KGS Ronnenberg

Wir hoffen, dass alle Teilnehmenden genauso viel Spass hatten wie wir und freuen uns auf die nächste Competition.

Einführung

Wie bewertet man aber nun, ob ein Programm gut oder schlecht Backgammon spielt? Bei allen Spielen, die vom Zufall aber auch von strategischen Faktoren abhängen (wie z.B. Kniffel, alle Pokervarianten oder auch MauMau, Skat oder Doppelkopf), kann man nach einem Spiel nicht entscheiden ob man besser als sein Gegner ist oder nicht, da eben der Zufall eine Rolle spielt (bei Kniffel oder Backgammon der Würfel, bei MauMau, Pokern, Skat und Doppelkopf die Karten). Da jedoch der Zufall auf lange Sicht eine immer kleinere Rolle spielt (keiner kann sagen ob es heute oder morgen in Hannover regnet, im Durchschnitt fallen im Jahr aber 661 mm Niederschlag) gewinnt in z.B. 100000 Spielen der bessere Spieler mit fast an Sicherheit grenzender Wahrscheinlichkeit häufiger.
Wir werden daher nach Abgabe der Programme ein Turnier veranstalten, in dem eure Programme mehrere Male gegeneinander antreten werden. In diesem Turnier werden die besten Programme ermittelt. Damit es nicht zu lange dauert, müsst ihr eine bestimmte Zeitspanne (Timeout) einhalten, d.h. euer Algorithmus muss innerhalb einer festen Zeit einen Zug berechnen können.

Es gibt bereits Programme, die sehr gut Backgammon spielen, teilweise sogar besser als jeder Mensch. Ein solches Programm zu entwickeln ist jedoch sehr schwer. Zunächst solltet ihr daher ein Programm schreiben, das die Regeln beherrscht und keine offensichtlichen Fehler macht. Habt ihr das geschafft, könnt ihr an dem Programm weiter feilen und seine Strategie nach und nach verbessern. Um dem Computer Backgammon beizubringen, müsst ihr es natürlich selber möglichst gut spielen können. Macht euch daher mit den Regeln vertraut und spielt ein paar Spiele gegen einen Freund/Freundin, eure Eltern oder sonst jemanden den ihr kennt. Vielleicht kennt ihr ja einen guten Spieler, der euch ein paar Tricks und gute Strategien verrät. Beachtet jedoch, dass es sehr schwierig sein kann eine Strategie, die ein Mensch ohne Probleme umsetzt, einem Computer beizubringen. Arbeitet euch also Schritt für Schritt vor. Die Regeln findet ihr z.B. unter http://de.wikipedia.org/wiki/Backgammon Der sonst übliche Verdoppelungswürfel soll bei unserer Backgammon-Variante nicht berücksichtigt werden.

Protokoll

Damit eure Programme gegeneinander antreten können und ihr trotzdem freie Wahl in der Programmiersprache habt, brauchen wir ein Protokoll mit dem Spieldaten ausgetauscht werden können. Außerdem muss euer Programm in der Lage sein über das Internet (mit eben jenem Protokoll) mit einem von uns bereitgestellten Backgammon-Server zu kommunizieren.

Eine vollständige Beschreibung des Protokolls werden wir innerhalb der nächsten Wochen an dieser Stelle veröffentlichen. Die Zugangsdaten für unseren Server bekommt ihr nach Anmeldung.

Aufgabenstellung

Es soll ein Backgammon-Programm entwickelt werden. In der dazugehörigen Dokumentation sollen Algorithmen und Programmaufbau verständlich dargestellt werden. Folgende Teilaufgaben sollen gelöst werden:

1. Erstelle eine grafische Oberfläche, die es zwei menschlichen Spielern ermöglicht gegeneinander Backgammon zu spielen. Das Programm soll dabei keine irregulären Züge zulassen und merken wann das Spiel zu Ende ist und wer gewonnen hat.
2. Erweitere dein Programm um eine Schnittstelle, die es ermöglicht mit dem obigen Protokoll über ein Netzwerk mit dem Backgammon-Server zu kommunizieren.
3. Entwickle eine künstliche Intelligenz, die sowohl gegen einen menschlichen Gegner als auch über das Internet über den Backgammon-Server gegen andere Computer spielen kann. Folgendes Vorgehen kann dabei zweckmäßig sein:
   • Bring dem Computer die Regeln des Spiels bei. Er darf also keine irregulären Züge machen.
   • Teste deinen Algorithmus indem du gegen ihn spielst und achte auf seine Schwächen. Der Computer dürfte z.B. anfangs sehr leicht auszutricksen sein.
   • Versuche diese Schwächen zu eliminieren indem du gezielt am Algorithmus Verbesserungen vornimmst.
   Versuche auf diese Weise die künstliche Intelligenz so stark wie irgend möglich zu machen. Achte z.B. auch darauf, dass es für nahezu jeden Würfelwurf eine passende Eröffnung gibt, die strategische Vorteile hat. Dein Algorithmus sollte mit unterschiedlichen Timeouts funktionieren. Für das Turnier wird der Timeout relativ niedrig sein (wenige Sekunden), gegen einen menschlichen Spieler könnte sich das Programm natürlich mehr Zeit lassen.

• Anmeldeschluss ist der 15. Dezember 2006.
• Gruppenmeldungen sind nicht möglich.
• Als Programmiersprache sind C, C++, Pascal/Delphi, PHP und Java zugelassen. Die Sprache muss bei der Anmeldung mit angegeben werden. Für die Client-Server-Kommunikation empfehlen wir die SDL_net-Bibliothek (http://www.libsdl.org), ihr könnt aber natürlich auch die der Programmiersprache beiliegenden Pakete benutzen. Es dürfen nur die Standard-Bibliotheken und frei verfügbare GUI-Frameworks wie z.B. wxWindows, Qt oder Gtk verwendet werden.
• Es muss eine etwa 10-seitige Ausarbeitung angefertigt werden, in der die benutzten Algorithmen erklärt werden, und in der das Programm ausführlich dokumentiert wird. Außerdem müssen alle Quellen und Hilfsmittel angegeben werden.
• Das erstellte Programm und die Ausarbeitung sind spätestens bis zum 12. März 2007 bei uns einzureichen.
• Es dürfen nur Schülerinnen und Schüler der Sekundarstufe I oder II an allgemeinbildenden Schulen, sowie an Fachgymnasien aus Niedersachsen an dem Wettbewerb teilnehmen. Die Teilnehmer dürfen max. 19 Jahre alt sein. Familienangehörige von Mitarbeitern des Fachgebietes Graphische Datenverarbeitung an der Universität Hannover sind leider ausgeschlossen.
• Der Rechtsweg ist ausgeschlossen.

Bewertungskriterien

• Lauffähigkeit und Korrektheit des Programms
• Gut verständliche Dokumentation der Algorithmen
• Besondere eigenständige Ideen
• Turnierergebnis
• In Zweifelsfällen: Strukturierter Programmierstil
• ...

Hoffentlich hast Du ein wenig Lust bekommen, an diesem Wettbewerb teilzunehmen. Es geht bei dieser Competition nicht darum, alles perfekt zu machen. Wir freuen uns auch über Teillösungen. Wenn wir merken, dass Du Dich mit der Problematik beschäftigt hast, hier und da ein paar interessante eigene Ideen hattest und Deine Gedanken und Algorithmen dokumentierst, hast Du gute Chancen unter den drei Besten zu sein. Bei Rückfragen kannst Du Dich gerne bei uns melden.

E-Mail: competition(at)gdv.uni-hannover.de

Viel Erfolg wünschen
Prof. Dr. F.-E. Wolter und das Team der Welfenlab Competition!