Navigation überspringen ([Alt] + [0])

Sitemap | english Version

>> Ressourcen > Theses > Reif, Gerald: M[..] > 05. Spielbäume

• Über uns
  • Mitarbeiter
  • Aktuelles
  • ... mehr über uns
  • Kontaktinformationen
• Lehre
  • Offene Projekte
  • Lehrveranstaltungen
  • LV-Unterlagen
  • Abschlussarbeiten
• Forschung
  • Forschungsbereiche
  • Projekte
  • Publikationen
  • Partner

• TU Graz
• TUGRAZonline
• Impressum

5. Spielbäume

Spielbäume und die dazugehörenden Algorithmen ermöglichen es, Computern eine bestimmte Art von Strategiespielen zu spielen. Bei den Spielen handelt es sich um Zweipersonenspiele, bei denen beide Spieler vollständig wissen, welche Züge gemacht wurden und welche noch möglich sind. Beispiele dafür sind Spiele wie Dame und Schach. Kartenspiele oder Backgammon bei denen der Zufall eine Rolle spielt, gehören nicht dazu [Nilsson1982].

Die aktuelle Brettsituation, die möglichen Züge und die daraus folgenden neuen Brettsituationen werden mit Hilfe eines Spielbaumes repräsentiert. Abbildung  5.1 zeigt einen Spielbaum, bei dem die Spieler bei jedem Zug zwischen zwei möglichen Zügen wählen können. Die Nodes in einem Spielbaum repräsentieren die Brettsituationen, die Links stehen für die erlaubten Züge, die zu neuen Brettsituationen führen [Winston1993].

Abbildung 5.1: Beispiel eines Spielbaumes. Nodes repräsentieren Brettsituationen, Links gültige Züge.

Für ein komplexes Spiel ist es jedoch nicht möglich, den vollständigen Spielbaum aufzubauen. Für Schach wären dazu $10^{120}$ Nodes notwendig [Nilsson1982]. Darum baut man den Baum nur bis zu einer vertretbaren Ebene auf und bewertet anschießend die entstandenen Brettsituationen.

Um bewerten zu können, ob eine Brettsituation gut oder schlecht für einen Spieler ist, wird ein Situation-Analyzer benötigt. Der Situation-Analyzer gibt abhängig von der Brettsituation einen Zahlenwert zurück. Vom Absolutbetrag des Zahlenwerts hängt es ab, wie gut eine bestimmte Situation ist. Hohe Zahlenwerte stehen dabei für eine günstige Brettsituation. Das Vorzeichen des Zahlenwerts drückt aus für welchen der beiden Spieler die Situation günstig ist. Ein Spieler hat somit das Ziel den Zahlenwert zu maximieren, der Maximierer, der andere ihn zu minimieren, der Minimierer. Daraus ergibt sich auch der Name des MiniMax-Algorithmus, der nun vorgestellt werden soll.

5.1 MiniMax Algorithmus

Der MiniMax Algorithmus baut einen Spielbaum bis zu einer bestimmten Ebene auf und ordnet jedem Blatt^5.1 mit Hilfe des Situation-Analyzer einen Zahlenwert zu (siehe Abbildung  5.2 oben). Bei der abgebildeten Situation ist der Maximierer am Zug. Beim nächsten Zug ist der Minimierer an der Reihe, usw. Welche Person in welcher Ebene am Zug ist, ist rechts vom Baum angegeben.

Abbildung 5.2: Bestimmung des bestmöglichen Zuges mit Hilfe des MiniMax-Algorithmus. [Winston1993]

Der Maximierer hat das Ziel zu der Brettsituation mit der höchsten erreichbaren Bewertung zu gelangen. Der höchste Wert, der einem Blatt zugeordnet wurde, ist 8 im rechten Teilbaum. Entscheidet sich der Maximierer für diesen Teilbaum, so gibt er den Minimierer im nächsten Schritt die Möglichkeit sich zwischen den Werten -1 und 8 zu entscheiden. Dieser wird sich für die Brettsituation mit der Bewertung -1 entscheiden. Der Maximierer hat durch seinen Zug erreicht, daß er bei einer für ihn ungünstigen Brettsituation landet. Hätte er sich für den linken Teilbaum entschieden, hätte der Minimierer nur eine Auswahl zwischen Situationen, die mit 2 oder 7 bewertet wurden. Die beste Bewertung die der Maximierer somit nach zwei Zügen erreichen kann, ist die 2.

Der MiniMax Algorithmus beginnt seine Analyse eine Ebene über den Blättern. Befindet er sich in einer Minimierer Ebene, ordnet er dem Knoten das Minimum der Bewertungen seiner Kinder zu, bzw. in einer Maximierer Ebene das Maximum. Nachdem er dies für allen Knoten dieser Ebene erledigt hat, nimmt er diese Bewertung eine Ebene höher vor, wie in Abbildung  5.2 mitte und unten gezeigt wird. Der dem Root-Knoten zugeordnete Wert entspricht der Bewertung der Brettsituation, die der Spieler schlechtesten falls erreichen kann. Der schlechteste Fall tritt dann ein, wenn der Gegner die Brettsituationen gleich bewertet und bei der Auswahl seiner Zügen keinen Fehler macht. Der Algorithmus ist in Abbildung 5.1 dargestellt.

Da der Situations Analyzer eine sehr rechenaufwendige Aufgabe darstellt, sollte man sich überlegen, ob er überhaupt für jedes Blatt aufgerufen werden muß. Der Alpha-Beta Algorithmus, der im nächsten Abschnitt behandelt wird, zeigt, das dies nicht nötig ist. [Winston1993]

5.2 Alpha-Beta-Algorithmus

Der Alpha-Beta-Algorithmus ist eine Verbesserung von MiniMax. Durch ihn ist es nicht mehr notwendig, für jedes Blatt eine Bewertung durchzuführen, es muß nicht einmal der vollständige Suchbaum aufgebaut werden. Welche Äste im Baum nicht aufgebaut werden müssen, soll mit Hilfe von Abbildung  5.4 erklärt werden.

Abbildung 5.4: Beim Alpha-Beta Algorithmus werden nur jene Teile des Baumes aufgebaut, in denen noch die Möglichkeit besteht, einen besseren Zug, als die bisher bekannten, zu finden. [Winston1993]

In Abbildung  5.4 oben wurde der linke Teilbaum bereits aufgebaut und die Blätter bewertet. In der Minimierer-Ebene kann man schon erkennen, daß die beste Brettsituation, die der Minimierer erreichen kann, die Situation mit der Bewertung 2 ist. Diese Beobachtung ist beim Knoten mit ,,=2'' vermerkt. Eine Ebene darüber weiß der Maximierer nun, daß die niedrigste Bewertung, die er erreichen kann, die 2 ist. Dies ist beim Knoten mit $\ge$2 vermerkt, siehe Abbildung  5.4 mitte.

Im nächsten Schritt wird begonnen den rechten Teilbaum aufzubauen. Sobald das erste Blatt bewertet ist, weiß der Minimierer, daß er zumindest zu einer Brettsituation kommen kann die mit -1 bewertet wurde. Beim Knoten wird diese Information mit $\le$-1 vermerkt. Siehe Abbildung  5.4 unten. Der Maximierer eine Ebene höher kann daraus schließen, daß die höchste Bewertung die er mit diesem Teilbaum erreichen kann, die -1 ist. Nun ist bei diesem Knoten aber schon vermerkt, daß es einen Teilbaum gibt, mit dem der Maximierer zur Bewertung 2 gelangt. Es macht also keinen Sinn diesen Teilbaum weiter aufzubauen.

Durch den Alpha-Beta Algorithmus werden nur jene Teile des Baumes aufgebaut, in denen die Möglichkeit besteht einen besseren Zug zu finden, als den Besten der zur Zeit bekannt ist. Das Prinzip das dahinter steckt lautet: Wenn man feststellt, daß ein Zug schlecht ist, schaue nicht nach, wie schlecht er wirklich ist. [Winston1993]

Bei der Implementierung des Algorithmus werden zwei Hilfsvariablen, alpha und beta, eingeführt. Diese Variablen haben folgende Eigenschaften:

• Die Bewertung eines Knoten kann nicht niederer als $\alpha$ und nicht höher als $\beta$ werden.
• Während der Abarbeitung des Algorithmus können sich die Werte für $\alpha$ und $\beta$ ändern, jedoch wird der Wert für $\alpha$ nie sinken, der für $\beta$ nie steigen.
• Der $\alpha$-Wert eines Knoten ist nie niederer, als der $\alpha$ Wert seiner Vorgänger.
• Der $\beta$-Wert eines Knoten ist nie höher, als der $\beta$ Wert seiner Vorgänger.
• Wenn ein Knoten auf einer Minimierer Ebene das letzte mal besucht wurde, entspricht seine Bewertung dem $\alpha$ Wert des Knotens.
• Wenn ein Knoten auf einer Maximierer Ebene das letzte mal besucht wurde, entspricht seine Bewertung dem $\beta$ Wert des Knotens.

Der Algorithmus ist in Abbildung 5.2 dargestellt. Der Aufruf der Funktion erfolgt mit $\mbox{\emph{minimax-ab}}(Startknoten, -\infty, +\infty)$.

Bei den meisten Brettspielen haben die Spieler nicht beliebig lange Zeit, sich für einen bestimmten Zug zu entscheiden. Sie müssen innerhalb einer vorgegebenen Zeit einen Zug durchführen. Dies stellt die beiden bisher vorgestellten Algorithmen vor ein Problem. Es muß beim Start des Algorithmus festgelegt werden, bis zu welcher Tiefe der Baum aufgebaut werden soll. Unterschätzt man die Zeit für die Analyse und baut zuviele Ebenen des Spielbaumes auf, so ist der Algorithmus in der zur verfügungstehenden Zeit noch nicht fertig abgearbeitet. Der Computer verliert das Spiel, da er die Zeit überschreitet. Überschätzt man die Zeit für die Analyse, so geht Rechenzeit ,,verloren'', in der man vielleicht einen besseren Zug hätte finden können. Um dieses Problem zu lösen und zu jeder Zeit über den bestmöglichen, bekannten Zug bescheid zu wissen, verwendet man daher die Technik des Progressiv Deepening. [Winston1993]

5.3 Progressiv Deepening

Um über den bestmöglichen Zug zu jeder Zeit bescheid zu wissen, analysiert man beim Progressiv Deepening den Baum nach dem Aufbau jeder Ebene mit dem MiniMax-Algorithmus; zuerst Ebene 1, dann Ebene 2, usw. Nach dem Ablauf der zur Verfügung stehenden Zeit, wird die Berechnung in der untersten Ebene abgebrochen. Der bestmögliche bekannte Zug ist somit der, der sich aus der Analyse der vorletzten Ebene ergeben hat. Dies ist die letzte Ebene die fertig analysiert wurde. [Winston1993]

Auf den ersten Blick erscheint diese Vorgangsweise sehr zeitaufwendig. Doch die nachfolgende Analyse wird zeigen, daß sich der Mehraufwand für Progressiv Deepening in Grenzen hält. Bei der Analyse wird davon ausgegangen, daß der Situation-Analyzer für jeden Knoten die größten Kosten bei der Bewertung des Baumes verursacht. Daher kann man die Analyse auf die Betrachtung der Anzahl der Knoten beschränken. Gegeben ist ein Spielbaum mit dem Branching-Faktor $b$ und der Tiefe $d$. In der untersten Ebene besitzt der Baum somit $b^d$ Knoten. Die Anzahl der Knoten im gesamten Baum bis zur vorletzten Ebene $d-1$ kann mit folgender Formel berechnet werden:

$$b^0+b^1+\ldots+b^{d-1}=\frac{b^d-1}{b-1}$$ (5.1)

Bildet man das Verhältnis der Knoten in der letzten Baumebene zu allen Knoten im Baum darüber so erhält man:

$$\frac{b^d(b-1)}{b^d-1}\approx b-1$$ (5.2)

Betrachtet man einen Baum mit dem Branching-Faktor $b=16$, so sagt Gleichung (5.2) aus, daß der Aufwand den Baum bis zur vorletzten Ebene zu bewerten um $\frac{1}{15}$ geringer ist, als die letzte Ebene zu bewerten. Der für das Progressiv Deepening zusätzlich notwendige Aufwand hält sich somit in Grenzen. [Winston1993]