Graphenalgorithmen

Spielbäume

 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 Spiel­stellung. Ziel von Spieler A ist es, eine Spiel­stellung zu erreichen, in der er das Spiel gewonnen hat. Das Problem besteht darin, den jeweils nächsten Zug zu bestimmen, der ihn dieser Gewinn­stellung näher bringt.

Spielbaum

Wir betrachten ein sehr einfaches Spiel, in dem es in jeder Spiel­stellung nur zwei erlaubte Züge gibt, links (l) oder rechts (r). Befindet sich das Spiel nun in einer bestimmten Spiel­stellung S und Spieler A führt einen Zug aus, so sind zwei Folge­stellungen möglich, Sl und Sr. Bild 1 veranschaulicht diese Situation durch einen gerichteten Graphen. Die Knoten des Graphen entsprechen den Spiel­stellungen, 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 Spiel­stellung 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 Spiel­stellung 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 Spiel­stellungen Sll, Slr, Srl, Srr. Nach einem weiteren Zug von Spieler A und einem weiteren Zug von Spieler B sind insgesamt 16 Spiel­stellungen möglich. Bild 2 veranschaulicht diese Situation wieder anhand des ent­sprechenden 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 Bewertungs­funktion ein, die jeder Spiel­stellung einen Zahlenwert zuweist, der umso höher ist, je günstiger die Spiel­stellung für Spieler A ist, und umso niedriger, je günstiger die Spiel­stellung für Spieler B ist. Dann ist es möglich, durch Analyse des Spielbaums den optimalen Zug für Spieler A zu finden. Die Vorgehens­weise 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 Spiel­stellung S zieht erst Spieler A und dann Spieler B. Nach diesen zwei Zügen ergeben sich vier mögliche Spiel­stellungen, die mit 6, 5, 2 bzw. 9 bewertet seien.

Zieht A nach rechts, um die mit 9 bewertete Spiel­stellung 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 Spiel­stellung zu erreichen, d.h. die Strategie von B ist, stets die minimal bewertete Spiel­stellung anzusteuern.

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

Bild 4 zeigt einen Spielbaum für vier Züge. Die 16 erreichbaren Spiel­stellungen sind mit ihren Bewertungen markiert. Die Auswertung des Spielbaums zeigt, dass A eine Spiel­stellung 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 Spiel­stellungen stets aus Sicht desjenigen Spielers vorgenommen wird, der gerade am Zug ist. Dieser Spieler berechnet stets das Maximum der aus seiner Sicht bewerteten Folge­stellungen. Diese Werte sind aber gerade die mit -1 multi­plizierten Werte, die sich aus Sicht des Gegners für diese Spiel­stellungen ergeben.

Statt also abwechselnd das Minimum und das Maximum zu bilden, wird stets das Maximum der mit -1 multi­plizierten Werte gebildet; dies führt zum selben Ergebnis. Die Auswertung eval(S) des an einer Spiel­stellung 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 Spiel­stellung S aus Sicht des Spielers, der am Zug ist.

Implementierung

Die folgende rekursive Funktion eval wertet einen Spielbaum beginnend an einer Spiel­stellung 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 ent­sprechenden Spiel­stellung s zurück­gegeben (bewertet aus Sicht des Spielers, der am Zug ist).

Ansonsten werden mit dem Iterator NextMoveIterator(s) alle in der Spiel­stellung s möglichen Spielzüge durchlaufen und die sich daraus ergebenden Folge-Spiel­stellungen t erzeugt. Durch rekursiven Aufruf der Funktion eval werden die an diesen Spiel­stellungen t beginnenden Spielbäume der Tiefe d-1 ausgewertet. Von den mit -1 multi­plizierten 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), move);
    }
    return minimax.getMaxVal();
}

Bestimmen des Spielzugs

Um den optimalen Spielzug zu bestimmen, wird der erste Rekursions­schritt ausgelagert in folgende Methode findMove, die sich denjenigen Zug move merkt, der den Maximalwert liefert. Die Methode greift auf die Attribute config (die aktuelle Spiel­stellung) und searchdepth (dieTiefe des aus­zuwertenden Spielbaums, d.h. die Anzahl der voraus­zuberechnenden Spielzüge) zu.

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. Beispiels­weise 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 ent­sprechende Implementierung entsteht durch eine sehr kleine Abänderung der ursprüng­lichen 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()), move);
    }
    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 unter­schiedliche Zugfolgen zu der gleichen Spiel­stellung führen. D.h. unter­schiedliche Knoten des Spielbaums können gleiche Spiel­stellungen repräsentieren.

 

Weiter mit:   [Literatur]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 25.10.2006   Updated: 24.05.2017
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