PPS: Vom Spiel zur Wissenschaft SS2005: "3D 4-Gewinnt"

Inhaltsverzeichnis

Einführung

Im PPS-Kurs "Vom Spiel zur Wissenschaft", geleitet von Prof. Christian Hafner, befassten wir uns mit der Aufgabe, ein wissenschaftliches Problem einem Anwender auf spielerische Art und Weise näher zu bringen.

Wir wollten einen Computergegner für ein Brettspiel schaffen gegen den ein Mensch über das Internet antreten kann. Das Spiel sollte nicht allzu schwer zu implementieren sein, somit schied zum Beispiel Schach aus. Wir entschieden uns für Java als Programmiersprache aus zwei Gründen: Erstens haben wir uns mit dieser Sprache bereits in der Vorlesung "Informatik 2" befasst, zweitens bietet sich mit der Benutzung von Java-Applets eine relativ einfache Möglichkeit, komplexe Programme mit grafischer Oberfläche über das Internet erreichbar zu machen.

Zur Erklärung der Funktionsweise von künstlicher Intelligenz wird oft das Spiel Tic Tac Toe verwendet. Da dieses aber aufgrund der kleinen Spielfeldgrösse etwas gar schnell komplett durchgerechnet werden kann, haben wir eine erweiterte Version davon entwickelt. Das Spielfeld wurde von 3x3 auf 4x4x4 Felder (also dreidimensional) erweitert. Das Ziel ist es, 4 Steine der eigenen Farbe in einer beliebigen Gerade (vertikal, horizontal, über verschiedene Ebenen, etc.) zu setzen. Das Spiel nennen wir "Dreidimensionales 4 Gewinnt" oder kurz: "3D4G". Es kann auf zwei verschiedene Arten gespielt werden:

Funktionsweise des Applets

Zur künstlichen Intelligenz von Computerprogrammen muss man festhalten, dass ein Computerprogramm grundsätzlich nicht intelligent im menschlichen Sinne handeln kann. Es wird lediglich eine endliche Menge von Möglichkeiten mathematisch ausgewertet und eine ebenso endliche Anzahl von möglichen Handlungen vorgeschlagen. Auf eine detaillierte Erklärung des Source Codes haben wir hier verzichtet. Der interessierte Leser ist eingeladen, den kommentierten Quellcode herunterzuladen, zu kompilieren und damit zu experimentieren. Es gibt zwei verschiedene Gegner-Engines gegen die gespielt werden kann: Das Programm ist in 5 Klassen eingeteilt:

Beschreibung der Klasse BonusEngine.java, dem Kernstück von 3D4G

Es gibt 120 mögliche Linien deren Vervollständigung jeweils zu einem Gewinn führt. Wie ein menschlicher Spieler auch, zielt die Bonus-Engine darauf ab, diese zu füllen. Sie überprüft jede der 120 Linien und gibt ihr grundsätzlich umso mehr Punkte je mehr Steine (eigene und gegnerische) in der entsprechenden Linie enthalten sind. Im weiteren Verlauf wird jedes der 64 Felder iteriert. Für jedes Feld werden alle Linien-Werte, die durch das entsprechende Feld gehen, aufaddiert und in eine separate Instanz von koord geschrieben. Von den so gefundenen bewerteten Zugmöglichkeiten wird nun diejenige ausgeführt welche den höchsten Wert bekommen hat. Haben mehrere mögliche Züge dieselbe Bewertung bekommen, wird der Zug per Zufallsgenerator ausgewählt.

Die Bewertung der Linien

Es gilt, dass eine Reihe einen umso grösseren Wert erhält, je grösser die Anzahl der darauf liegenden Steine ist. Allerdings unterscheiden wir dabei zwischen eigenen und fremden Steinen. Die Punktzahlen werden gemäss nachstehender Tabelle separat für die beiden Farben ausgerechnet und dann addiert.

Anzahl vorhandener Steine 0 1 2 3 4
Eigene Steine 0 5 25 50 400
Fremde Steine 0 1 10 75 150

Diese Werte haben wir empirisch ermittelt. Möglicherweise gibt es hier noch Optimierungspotenzial. Allerdings haben wir festgestellt, dass die 3D4G-Engine damit bereits schon ziemlich stark spielt. Bis jetzt haben wir noch keinen menschlichen Gegner gefunden, der gegen sie gewonnen hat. Sollte es dir gelingen freuen wir uns auf ein kurzes Mail von dir. :-) Im Übrigen ist das auch der Grund weshalb wir von einer Implementation des MiniMax- bzw. Alpha-Beta-Algorithmus abgesehen haben.

Das Spiel

Das Java-Applet befindet sich auf einer separaten Seite.

Der Source-Code

Der Quellcode von unserer 3D4G-Implementation ist als Zip-File erhätlich. Der Code ist für jedermann kostenlos und ohne Einschränkung einsehbar. Für jede weitere Verwendung, z.B. Veränderung, Verbreitung, etc. insbesondere wenn sie kommerzieller Natur ist, bitten wir um Rücksprache zur Klärung der Modalitäten.

Das Team

Daniel Thomas (dathomas): Grafische Benutzeroberfläche

Stefan Ackermann (stefaack): Künstliche Intelligenz

Lukas Toggenburger (lukast): Dokumentation

Um Kontakt mit uns aufzunehmen schreib an benutzername@student.ethz.ch. Anstelle von "benutzername" benütze bitte die Ausdrücke in Klammern neben den Namen.



Message of the day: http://www.QualityPrint.ch hat günstige Druckerpatronen und Toner.