Graphenalgorithmen

Spielbaum

 aufwärts

Problem

Wir betrachten Zwei-Personen-Spiele wie zum Beispiel Schach, Dame oder Tic-Tac-Toe. Die beiden Spieler A und B führen abwechselnd Spielzüge aus. Nach jedem Zug befindet sich das Spiel in einer bestimmten Spielstellung. Ziel von Spieler A ist es, eine Spielstellung zu erreichen, in der er das Spiel gewonnen hat. Das Problem besteht darin, den jeweils nächsten Zug zu bestimmen, der ihn dieser Gewinnstellung näher bringt.

Spielbaum

Wir betrachten ein sehr einfaches Spiel, in dem es in jeder Spielstellung nur zwei erlaubte Züge gibt, links (l) oder rechts (r). Befindet sich das Spiel nun in einer bestimmten Spielstellung S und Spieler A führt einen Zug aus, so sind zwei Folgestellungen möglich, Sl und Sr. Bild 1 veranschaulicht diese Situation durch einen gerichteten Graphen. Die Knoten des Graphen entsprechen den Spielstellungen, die (von oben nach unten gerichteten) Kanten des Graphen entsprechen den Spielzügen. Der Graph ist ein Baum, der Spielbaum für einen Zug ausgehend von Spielstellung S.

Bild 1: Spielstellung S und zwei mögliche Spielzüge l und r
Bild 1: Spielstellung S und zwei mögliche Spielzüge l und r

Danach ist Spieler B am Zug. Je nach dem, ob er Spielstellung Sl oder Sr vorfindet und je nach dem, ob er Zug l oder Zug r ausführt, ergibt sich anschließend eine der vier möglichen Spielstellungen Sll, Slr, Srl, Srr. Nach einem weiteren Zug von Spieler A und einem weiteren Zug von Spieler B sind insgesamt 16 Spielstellungen möglich. Bild 2 veranschaulicht diese Situation wieder anhand des entsprechenden Spielbaums.1)

Bild 2: Spielbaum für vier Züge, ausgehend von Spielstellung S
Bild 2: Spielbaum für vier Züge, ausgehend von Spielstellung S

Minimax-Strategie

Wir führen eine Bewertungsfunktion ein, die jeder Spielstellung einen Zahlenwert zuweist, der umso höher ist, je günstiger die Spielstellung für Spieler A ist, und umso niedriger, je günstiger die Spielstellung für Spieler B ist. Dann ist es möglich, durch Analyse des Spielbaums den optimalen Zug für Spieler A zu finden. Die Vorgehensweise veranschaulicht Bild 3.

Bild 3: Spielbaum mit Bewertung der Spielstellungen nach zwei Zügen
Bild 3: Spielbaum mit Bewertung der Spielstellungen nach zwei Zügen

Ausgehend von Spielstellung S zieht erst Spieler A und dann Spieler B. Nach diesen zwei Zügen ergeben sich vier mögliche Spielstellungen, die mit 6, 5, 2 bzw. 9 bewertet seien.

Zieht A nach rechts, um die mit 9 bewertete Spielstellung zu erreichen, so wird B dies vereiteln, indem er nach links zieht, um die für ihn bessere und für A schlechtere, mit 2 bewertete Spielstellung zu erreichen, d.h. die Strategie von B ist, stets die minimal bewertete Spielstellung anzusteuern.

Zieht A nach links, so kann er mindestens, egal wie B dann zieht, den Wert 5 erreichen. Der in Spielstellung S für A optimale Zug ist also der Zug nach links, jedenfalls wenn wie hier nur zwei Züge vorausberechnet wird. Die Strategie von A ist, das Maximum der Minima der jeweils von B erreichbaren Spielstellungen zu berechnen und den entsprechenden Zug zu wählen. Dieses Vorgehen wird als Minimax-Strategie bezeichnet.

Bild 4 zeigt einen Spielbaum für vier Züge. Die 16 erreichbaren Spielstellungen sind mit ihren Bewertungen markiert. Die Auswertung des Spielbaums zeigt, dass A eine Spielstellung mit mindestens dem Wert 5 erreichen kann. Dieser Wert ergibt sich, indem bottom-up jeder Knoten mit dem Minimum (wenn Spieler B am Zug ist) bzw. mit dem Maximum (wenn Spieler A am Zug ist) der Werte seiner direkten Nachfolger markiert wird.

Bild 4: Bewertung der Spielstellungen nach vier Zügen (Blätter des Baumes) und Auswertung des Spielbaums (innere Knoten)
Bild 4: Bewertung der Spielstellungen nach vier Zügen (Blätter des Baumes) und Auswertung des Spielbaums (innere Knoten)

Rekursive Auswertung des Spielbaums

Die Auswertung des Spielbaums vereinfacht sich, wenn die Bewertung der Spielstellungen stets aus Sicht desjenigen Spielers vorgenommen wird, der gerade am Zug ist. Dieser Spieler berechnet stets das Maximum der aus seiner Sicht bewerteten Folgestellungen. Diese Werte sind aber gerade die mit -1 multiplizierten Werte, die sich aus Sicht des Gegners für diese Spielstellungen ergeben.

Statt also abwechselnd das Minimum und das Maximum zu bilden, wird stets das Maximum der mit -1 multiplizierten Werte gebildet; dies führt zum selben Ergebnis. Die Auswertung eval(S) des an einer Spielstellung S beginnenden Spielbaums lässt sich rekursiv wie folgt darstellen:

eval(S) = geschweifte Klammer
rate(S)    S ist ein Blatt und rate(S) ist die Bewertung von S
max{-eval(S')}    S' durchläuft alle durch einen Spielzug erreichbaren Folgestellungen von S

Die Funktion rate(S) bewertet hierbei die Spielstellung S aus Sicht des Spielers, der am Zug ist.

Implementierung

Die folgende rekursive Funktion eval wertet einen Spielbaum beginnend an einer Spielstellung s bis zur Tiefe d in Form einer Tiefensuche aus.

Ist d = 0, d.h. besteht der Spielbaum nur aus einem Blatt, so wird als Ergebnis die Bewertung rate(s) der entsprechenden Spielstellung s zurückgegeben (bewertet aus Sicht des Spielers, der am Zug ist).

Ansonsten werden mit dem Iterator NextMoveIterator(s) alle in der Spielstellung s möglichen Spielzüge durchlaufen und die sich daraus ergebenden Folge-Spielstellungen t erzeugt. Durch rekursiven Aufruf der Funktion eval werden die an diesen Spielstellungen t beginnenden Spielbäume der Tiefe d-1 ausgewertet. Von den mit -1 multiplizierten Ergebnissen wird das Maximum gebildet; hierzu wird ein MiniMaximizer verwendet.

private double eval(Configuration s, int d)
{
    if (d==0 || s.gameOver())
        return s.rate();
    Iterator<Move> it=new NextMoveIterator(s);
    MiniMaximizer<Move> minimax=new MiniMaximizer<Move>();
    Move move;
    Configuration t;
    while (it.hasNext())
    {
        move=it.next();
        t=s.copy();
        t.setMove(move);
        minimax.add(-eval(t, d-1));
    }
    return minimax.getMaxVal();
}

Bestimmen des Spielzugs

Um den optimalen Spielzug zu bestimmen, wird der erste Rekursionsschritt ausgelagert in folgende Methode findMove, die sich denjenigen Zug move merkt, der den Maximalwert liefert. Die Methode greift auf die Attribute config (die aktuelle Spielstellung) und searchdepth (dieTiefe des auszuwertenden Spielbaums, d.h. die Anzahl der vorauszuberechnenden Spielzüge) zu. Der MiniMaximizer wird hier nicht nur mit den Bewertungen der durchlaufenen Spielstellungen gefüttert, sondern zusätzlich wird auch der entsprechende Spielzug move, der zu der jeweiligen Spielstellung führt, mitgegeben. Am Ende wird derjenige Spielzug, der zur Spielstellung mit maximaler Bewertung führt, mit getMaxObj zurückgegeben.

public Move findMove()
{
    Configuration s=config;
    Iterator<Move> it=new NextMoveIterator(s);
    MiniMaximizer<Move> minimax=new MiniMaximizer<Move>();
    Move move;
    Configuration t;
    while (it.hasNext())
    {
        move=it.next();
        t=s.copy();
        t.setMove(move);
        minimax.add(-eval(t, searchdepth-1), move);
    }
    return minimax.getMaxObj();
}

Partielle Auswertung des Spielbaums

Tatsächlich brauchen in vielen Fällen nicht alle Knoten des Spielbaums berechnet zu werden. Bild 5 zeigt dies zunächst anhand des Spielbaums von Bild 3.

Bild 5: Partielle Auswertung des Spielbaums für zwei Züge
Bild 5: Partielle Auswertung des Spielbaums für zwei Züge

Egal welchen Wert x der untere rechte Knoten hat, er ändert nichts am Ergebnis 5 der Auswertung des Spielbaums. Der Wert des Knotens kann das darüber befindliche Minimum höchstens kleiner machen. Das wiederum darüber befindliche Maximum ist aber bereits größer, bleibt also erhalten.

Bild 6 zeigt anhand des Spielbaums von Bild 4, dass ganze Teilbäume nicht berechnet zu werden brauchen, weil sie zum Ergebnis nicht beitragen. Beispielsweise kann der Wert 4 unterhalb der Wurzel des Spielbaums höchstens kleiner werden, wenn der untere rechte Teilbaum ausgewertet wird. Dadurch ändert sich jedoch am Maximum 5 an der Wurzel nichts. Die Auswertung des Teilbaums ist also nicht nötig.

Bild 6: Partielle Auswertung des Spielbaums für vier Züge
Bild 6: Partielle Auswertung des Spielbaums für vier Züge
Implementierung

Die entsprechende Implementierung entsteht durch eine sehr kleine Abänderung der ursprünglichen Funktion eval.

private double eval(Configuration s, int d, double w)
{
    if (d==0 || s.gameOver())
        return s.rate();

    Iterator<Move> it=new NextMoveIterator(s);
    MiniMaximizer<Move> minimax=new MiniMaximizer<Move>();
    Move move;
    Configuration t;
    while (it.hasNext() && minimax.getMaxVal()<w)
    {
        move=it.next();
        t=s.copy();
        t.setMove(move);
        minimax.add(-eval(t, d-1, -minimax.getMaxVal()));
    }
    return minimax.getMaxVal();
}

Beim ersten Aufruf der abgeänderten Funktion eval in der Funktion findMove wird für den Parameter w der Wert Double.POSITIVE_INFINITY eingesetzt.

Literatur

[HS 81]E. Horowitz, S. Sahni: Algorithmen. Springer (1981)

1)  Es möglich, dass unterschiedliche Zugfolgen zu der gleichen Spielstellung führen. D.h. unterschiedliche Knoten des Spielbaums können gleiche Spielstellungen repräsentieren.

 

Weiter mit:   [Literatur]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 25.10.2006   Updated: 04.06.2018
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik