4 Gewinnt
Auf dem Info II Übungsblatt Nr. 12 war eine einfache Implementierung des Vier Gewinnt Spiels, mit der im folgenden beschriebenen Übungsblatt-KI als Aufgabe gestellt. Ich habe die Aufgabe mal ein wenig erweitert, nämlich um eine graphische Ausgabe sowie eine erweiterte KI.
Dies ist eine BETA-Version. Folgende KIs sind verfügbar:
Übungsblatt-KI:
- Schau ob im nächsten Zug Möglichkeit zum Win besteht. Wenn ja => Führe Zug durch.
- Schau ob Gegner im nächsten Zug Möglichkeit zum Win hat. Wenn ja => Blockiere.
- Wähle zufälligen Zug.
Eigene KI:
Diese KI ist ein wenig komplexer, und die Berechnungsdauer einzelner Spielzüge steigt mit der Schwierigkeitsstufe.
Es wird bei jedem Spielzug des Computers ein Spielbaum der Zugmöglichkeiten bis zu einer Tiefe k aufgebaut, wobei k die Schwierigkeitsstufe darstellt. In den Blättern wird die jeweilige Spielsituation mittels einer Bewertungsfunktion analysiert. Der Wert den diese Funktion ermittelt gibt an, wie gut oder schlecht die Lage für den Computer ist (Je größer der Wert desto besser). Nun wird von unten nach oben in den Knoten immer das Maximum über alle Kinds-Knoten gebildet (sofern die aktuelle Ebene einen Spielzug des Computers darstellt), bzw das Minimum gebildet (wenn die aktuelle Ebene einen Spielzug des Gegners darstellt). So pflanzen sich die Werte von den Bewertungen nach oben durch, und der Computer kann in der Wurzel den besten Zug wählen. Um nicht immer den kompletten Baum berechnen zu müssen, kann man mit dem sogenannten Alpha/Beta Schnitt Zweige abschneiden, die sowieso zu keinem Erfolg führen. Dieses Verfahren ist ein Standardverfahren bei deterministischen Spielen, bei denen das Spielbrett jederzeit für beide Teilnehmer einsehbar ist.
Die Bewertungsfunktion funktioniert folgendermaßen: Sie sucht sich für jeden Stein im Spielfeld alle möglichen Chancen auf eine 4er Reihe heraus. Pro Viererchance für den Computer wird 1 addiert, bei Chancen für den Gegner wird 1 subtrahiert. So ergibt sich die Bewertungszahl.
Quellcode
Für die Leute die es interessiert, ist hier der Quellcode für das komplette Applet:
- FourWinsApplet.java (Hauptapplet und Spiel)
- Spielfeld.java (Implementierung des Spielfeldes)
- Spieler.java (Implementierung eines Spielers)
- Spielzug.java (Implementierung eines Spielzugs)
- AIExtended.java (Implementierung des Alpha/Beta Suchverfahrens)
Internetverweise
-
http://de.wikipedia.org/wiki/Minmax-Algorithmus
Beschreibung des Min-Max-Suchverfahrens auf Wikipedia. -
http://de.wikipedia.org/wiki/Alpha-Beta-Suche
Beschreibung des Alpha/Beta Suchverfahrens auf Wikipedia. -
http://www.algorilla.de/index.php?page=UeberVierGewinnt.con
Beschreibung des rekursiven Suchverfahrens für den Spielbaum, sowie kurze Erklärung möglicher heuristischer Bewertungsalgorithmen.