Auf dem Weg zum MinMax Algorithmus

Java-Forum Java-Grundlagen
1

Hallo werte Java-Freunde!

Ich habe hier ein Nullsummenspiel mit perfekter Information, das heißt es ist nach dem was
ich heute gelesen habe bestens geeignet für einen MinMax-Algorithmus, um einen Computer-
Gegner zu implementieren.

So weit so gut.

Ich erkläre vielleicht zunächst einmal das Spiel.

Das Spielfeld besteht aus 2 x 8 Felder die jeweils 2 x 4 angeordnet sind:

        • ===> Spieler A
        • ===> Spieler B

Auf jedem Feld befinden sich zu beginn zwei Spielsteine:

2 2 2 2
2 2 2 2 ===> Spieler A

2 2 2 2
2 2 2 2 ===> Spieler B

Spieler A beginnt. Wenn er nun ein Feld auswählt, werden die Steine,
die sich auf dem Feld befinden, gegen den Uhrzeigersinn auf die anderen
Felder verteilt. Auf jedem Feld, darf dabei nur ein Stein abgelegt werden.
Nehmen wir an, er hätte das vierte Feld, aus der zweiten
Reihe gewählt:

2 2 3 3
2 2 2 0 ===> Spieler A

2 2 2 2
2 2 2 2 ===> Spieler B

Nun sind auf dem dritten Feld in Reihe eins, auf dem der letzte Stein gelandet
ist, drei Steine, diese müssen weiter verteilt werden, das ganze geht solange,
bis auf einem Feld nur noch ein einzelner Stein liegen geblieben ist.

3 3 0 3
3 2 2 0 ===> Spieler A

2 2 2 2
2 2 2 2 ===> Spieler B

===========================================================

3 3 0 3
0 3 3 1 ===> Spieler A

2 2 2 2
2 2 2 2 ===> Spieler B

So, nun haben wir die Situation, dass ein einzelner Stein auf einem Spielfeld
liegt. Die Steine des Gegners auf den gegenüberliegenden Feldern werden
nun weg genommen:

3 3 0 3
0 3 3 1 ===> Spieler A

2 2 2 0
2 2 2 0 ===> Spieler B

Nun ist Spieler B an der Reihe. Das Spiel geht so lange, bis ein Spieler keine
Steine mehr hat. Dieser Spieler hat dann verloren.

Steine dürfen nur genommen werden, wenn der einzelne Spielstein bei Spieler
A in der zweiten Reihe und bei Spieler B in der ersten Reihe liegen bleibt, d.h.
bei folgendem Ergebnis hätte Spieler A keine Steine nehmen dürfen:

3 0 3 1
3 0 3 3 ===> Spieler A

2 2 2 2
2 2 2 2 ===> Spieler B

Mir sind nun einige Dinge nicht ganz klar. Zum einen die Bewertungsfunktion des
MinMax Algorithmus. Für einen Zug, der mir einen unmittelbaren Sieg einbringt,
gebe ich die Bewertung +undendlich zurück. Für einen Zug bei dem der Gegner gewinnt,
gebe ich -unendlich zurück, bei einem unentschieden 0.
Was gebe ich bei allen anderen Situationen zurück? Vielleicht die Anzahl der
Steine die genommen werden können?

Des weiteren ist mir nicht ganz klar, wie ich das ganze Code-Technisch implementieren kann.
Bis jetzt funktioniert das Spiel mit zwei Spielern (ohne Computer). Es ist möglich Züge
Rückgängig zu machen und sie zu wiederholen. Es ist außerdem möglich sich Replays von
Spielen anzugucken.

Ich speichere nämlich jeden gemachten Zug sowie die Verteilung der Spielsteine ab und
kann sie auf die Festplatte serialisieren.

Das heißt ich habe eine Liste, deren Elemente jeweils einen Spielstand darstellen.
Ich habe die Grafik und die Logik auch so weit getrennt, dass ich alles vorberechnen
könnte.

Kann mir einer bei der herangehensweise helfen?

2

Die Bewertungsfunktion könnte z.B. berechnen wieviele Möglichkeiten es gibt im nächsten Zug einen “Gewinn” zu machen.

3

Hm. Die “Anzahl der Möglichkeiten” ist vermutlich keine geeignete Quantifikation. Man muss schon beurteilen, wie “gut” eine bestimmte Spielsituation ist. Das ganze erinnert GROB an http://de.wikipedia.org/wiki/Mancala aber eben anscheinend mit zwei Spielbrettern…!?

4

Das hat aber recht wenig mit einem MinMax-Algorithmus zu tun. Wenn es einen Zug gibt der dem Gegner nur eine sichere Möglichkeit zu gewinnen gibt, so wird er diese nutzen.

Null-Summenspiel heißt, ein Spieler gewinnt, während ein anderer verliert.

Beim Min-Max trifft man zuerst Annahmen.

Der Gegner wird immer den bestmöglichen Zug machen. (Er Maximiert)

Also wählt der Spieler den Zug aus, bei dem des Gegners nächster Zug möglichst schlecht ist. (Er Minimiert des Gegners Maximum)

Da das einzig interessante Sieg oder Niederlage ist, genügt es für einen Sieg eine 1 zu vergeben und für eine Niederlage eine -1.

Wenn man nun eine Spielsituation hat bei der 2 Züge möglich sind, dann kann man einen Baum erstellen

Zug 1, Zug 2

Daraus ergeben sich für den Gegner jeweils 2 weitere Züge.
Zug 1:

  • Gegner 1 (-1)
  • Gegner 2 (+1)
    Zug 2
  • Gegner 1
  • Gegner 2

Wenn Z1 G1 zu einer Niederlage und Z1 G2 zu einem Sieg führt, dann fällt Z1 weg. Da der Gegner seinen G1 ziehen wird. Die Bewertungsfunktion für Z1 wird eine -1 zurückliefern.

Für Zug 2 gäbe es kein Endergebnis.

Bei der MinMax kann man nun verschiedene Varianten wählen.
Eine Möglichkeit ist die Berechnungstiefe. z.B. 5 Züge. Erreicht man nach einer bestimmten Tiefe kein finales Ergebnis, so gibt man eine 0 zurück.
Oder ein Depth First Search nach einem Sieg, daß allerdings nicht zwangsläufig terminieren muß.

Die Anzahl der Spielsteine ist eher Nebensächlich. Wenn es Dumm läuft, dann hast du alle 16 Steine aufeinandergestapelt und der Gegner klaut dir alle mit den letzten beiden Steinen.

5

Hm. So ganz stimme ich damit nicht überein. Es gibt natürlich auch noch andere Werte als nur -1,0 und 1. “Nullsumme” bedeutet in diesem Fall eigentlich nur, dass jeder Vorteil des einen ein Nachteil des anderen ist. Bei einem hypothetischen Spiel, wo jeder am Anfang 16 Spielsteine hat, und man die verlieren kann, wäre ein Stand von 16:5 eben mit 9 bewertet, und einer von 5:16 mit -9.
In diesem Fall geht es eben nicht um die reine Anzahl der Spielsteine, weil die Steine ja erstmal niemandem gehören. Aber trotzdem könnte und sollte man sich eine Bewertungsfunktion überlegen, die tatsächlich mit einem Wert von -unendlich bis +unendlich beschreibt, wie gut die Spielsituation gerade ist.
Eine reine MinMax-Suche wird ohnehin nur für geringe Spieltiefen praktikabel sein, vor allem, weil der Spielbaum hier SEHR schnell SEHR breit wird. Um mehr als 2, 3 Züge vorausrechenen zu können, wird man da AlphaBeta verwenden müssen.

6

Ja also -1 und 1 bzw. -unendlich und +unendlich als einzige Bewertungen reicht nicht
aus, das ich wie Marco13 bereits erwähnte, den Spielbaum nicht komplett durchrechnen
kann. Es gibt nämlich auch noch eine Variante mit 14 statt 8 Feldern.

Aber die Idee mit 16:5 = 9 und 5:16 = -9 ist doch eigentlich nicht schlecht.
Ich könnte dann für jeden vorberechneten Zug die gewonnenen oder verlorenen
Steine aufaddieren bzw. subtrahieren und so eine Bewertung berechnen.

Auf dem letzten Blatt der vorgegebenen Suchtiefe würde dann doch stehen,
mit welchen Zügen ich insgesamt die meisten Steine nehme.

Müsste doch klappen?

Wie baut man eigentlich einen Suchbaum auf? :smiley:

7

So wie jeden anderen Graphen auch (ein Baum ist schließlich nichts anderes).
Such dir eine geeignete Darstellungsform (z.B. Objekte für jeden Knoten oder eine Adjazenzmatrix) und implementiere das ganze.

Gruß

8

Klar kann man auch Eigene - Spielsteine des Gegners als Bewertungsmaßstab nehmen.
Die Frage ist halt nur, ob dass ein sinnvolles Maß ist.

Mühle z.B. könnte auch diese Bewertungsfunktion nutzen. Gute Spieler hingegen nutzen eher die Taktik den Gegner einzukesseln. Wenn der Gegner nicht mehr ziehen kann ist das Spiel auch gewonnen. Hier läuft diese Bewertungsfunktion ins offene Messer.

Schach leidet auch unter dem großen Suchbaum. Daher nutzt man zu Anfangs Eröffnungsbäume. Also eine Historie von Spieleröffnungen, die bereits erfolgreich Gespielt wurden.

Meiner Meinung nach reicht schon eine geringe Suchtiefe. Bekommt man kein Ergebnis, dann wird ein zufälliger Zug auch ein Interessantes Spielerlebnis liefern.

Aus den gespielten Partien, kann man sich dann ja auch eine Wissensdatenbank aufbauen um sich daraus gute Spieleröffnungen abzuleiten. Das wäre dann ein selbstlernendes System. Man muß nur ein paar mal KI gegen KI antreten lassen.

9

Ja, die Spielsteindifferenz ist sicher ein möglicher Aspekt, und dürfte bei einer Suchtiefe von 4 Halbzügen wohl schon zu einer KI führen, die man nicht mehr „einfach so“ schlagen könnte. Aber das alleine reicht vermutlich nicht für eine „wirklich“ gute KI. Es könnte ja sein, dass jemand ein „Bauernopfer“ eingeht. Dass er also 2, 3 Spielsteine absichtlich verliert, weil er dadurch (im 5. Halbzug) einen richtig dicken Brocken von 10 Spielsteinen absahnen kann. Man müßte irgendwie das Potential bewerten, das in einer Stellung steckt.

Beim Schach ist das genauso. Da gibt es natürlich Eröffnungsbibliotheken und komplett durchgerechnete Endspieldatenbanken, aber im Mittelspiel muss man die aktuelle Spielsituation bewerten. Da kommen dann richtig viele tricky Sachen zusammen: Einerseits zählt natürlich jede noch vorhandene Figur (Bauer 100 Punkte, Dame 800 Punkte oder so…), aber auch die Spielsituation: Zwei Bauern, die diagonal zueinander stehen (wo also einer gedeckt ist) zählen mehr, als zwei, die nebeneinander stehen. Ein Springer in der Mitte zählt mehr als ein Springer am Rand. Ein Turm auf einer Zeile/Spalte (bzw. ein Läufer auf einer Diagonalen) mit wenigen Steinen zählt mehr, als einer, der zwischen eigenen Spielsteinen eingekeilt ist. Wenn man schon eine Rochade gemacht hat, gibt das auch Punktabzug. (Die Details: http://chessprogramming.wikispaces.com/Evaluation :wink: )

Wie man bei diesem Spiel die Qualität einer Spielsituation bewerten könnte, müßte man sich genauer überlegen (auch wenn’s da garantiert tausende Seiten im Web dazu gibt).

10

Danke für die Denkanstöße.

Ich grübel dann mal paar Tage darüber nach :smiley: