Document ID: /fineweb-2-swissfilter-quality_10-filterrobots/filtered/03525.jsonl.gz/1216

PPS: Vom Spiel zur Wissenschaft SS2005: "3D 4-Gewinnt"
Inhaltsverzeichnis
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:
- Free: Die Steine können auf einer beliebigen Höhe platziert werden.
- Dropdown: Insofern dem zweidimensionalen "Vier gewinnt" ähnlich, dass auch hier Steine nur auf die unterste Ebene bzw. gerade ein Feld über ein besetztes Feld gelegt werden dürfen. Die Steine fallen sozusagen herunter, daher auch der Name.
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:
- Die Random-Enginge: Die Züge werden von einem Zufallsgenerator erzeugt. Dies war unsere erste Implementation des Computergegners die primär dazu diente, unsere grafische Oberfläche (GUI) auf korrektes Funktionieren zu testen.
- Die Bonus-Engine: Sie überprüft ihre möglichen Züge, bewertet sie jeweils mit einem Zahlenwert und führt schlussendlich den für am besten befundenen Zug aus. Eine ausführliche Erklärung dieser Engine folgt weiter unten.
Das Programm ist in 5 Klassen eingeteilt:
- Gui.java: Gibt alle sichtbaren Elemente (Spielfeld, Spielsteine, Buttons, etc.) aus, ruft die anderen Klassen auf.
- Engine.java: Überprüft verschiedene Zustände: Ob das Spiel gewonnen wurde, ob ein Zug gültig ist (insbesondere bei Spielmodus Dropdown) etc.
- koord.java: Stellt einen Datentyp "koord" bereit. Dieser wird benötigt um Koordinatenpositionen zu speichern und zu bearbeiten. Um die 64 möglichen Felder anzusteuern werden entweder ein Wert (0 bis 63) oder drei Werte (x,y,z) verwendet.
- ChaosEngine.java Generiert zufällig Züge.
- BonusEngine.java Generiert einen Zug nach Bonus-System.
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.
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 Java-Applet befindet sich auf einer separaten Seite
.
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.
Daniel Thomas
(dathomas): Grafische Benutzeroberfläche
Stefan Ackermann
(stefaack): Künstliche Intelligenz
Lukas Toggenburger
(lukast): Dokumentation
Um Kontakt mit uns aufzunehmen schreib an <email-pii>
. 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.