Spiele und adversarielle Suche

Eine Spielsuche beginnt mit einem Zustand: genügend Information, um zu bestimmen, was als Nächstes geschehen kann. Bei Tic-Tac-Toe sind das das Spielfeld und der Spieler am Zug. Das Spielfeld allein ist unvollständig, weil das nächste Zeichen davon abhängt, wer am Zug ist.

Die sechs Bestandteile definieren

Ein Spielmodell enthält:

• Einen Anfangszustand, $S_0$.
• Eine Funktion $\text{Am-Zug}(s)$, die den Spieler nennt, der im Zustand $s$ handelt.
• Die zulässigen Züge, $\text{Aktionen}(s)$.
• Ein Übergangsmodell $\text{Ergebnis}(s,a)$, das den Zustand nach Aktion $a$ angibt.
• Einen Terminaltest $\text{Ist-Terminal}(s)$, der das Spielende erkennt.
• Eine Nutzenfunktion $\text{Nutzen}(s,p)$, die Spieler $p$ in einem Terminalzustand eine numerische Auszahlung zuweist.

Bei Tic-Tac-Toe beginnt das Spiel mit einem leeren 3×3-Feld und X am Zug. Eine Aktion wählt ein leeres Feld. Der Übergang setzt das Zeichen des aktuellen Spielers und wechselt den Spieler am Zug. Das Spiel endet, sobald jemand eine Zeile, Spalte oder Diagonale aus drei Zeichen bildet oder das volle Spielfeld ein Unentschieden ergibt. Bewerte aus Sicht von X einen Sieg mit +1, ein Unentschieden mit 0 und eine Niederlage mit −1. Der Terminaltest muss ausgeführt werden, bevor ein weiteres Zeichen gesetzt wird: Nach einem Sieg geht das Spiel nicht weiter.

Das Spiel anhand getrennter Merkmale einordnen

Diese Merkmale sind unabhängig voneinander. Die Würfel machen Backgammon stochastisch, obwohl das Brett sichtbar ist. Verborgene Karten betreffen die Information, nicht die Frage, ob eine Aktion selbst zufällig ist. In einem Spiel mit verborgener Information denkt ein Spieler über die möglichen Zustände nach, die mit seinen Beobachtungen vereinbar sind. Diese bilden einen Glaubenszustand.

Den Blickwinkel auf die Auszahlung beibehalten

In einem Zwei-Personen-Nullsummenspiel ist der Gewinn des einen der Verlust des anderen. Punktestände mit konstanter Summe verhalten sich genauso: Sieg 1, Niederlage 0 und Unentschieden je ½ ergeben zusammen immer 1. Eine Zahl genügt, um den Gegensatz auszudrücken. Nenne den Spieler, der einen größeren Wert anstrebt, MAX und den Spieler, der einen kleineren Wert anstrebt, MIN. Das sind Rollen; MAX muss nicht immer Weiß oder X sein.

Bei einer gewöhnlichen Suche kann jede Aktion entlang eines Pfads gewählt werden. Ein spielender Agent muss auf Züge reagieren, die er nicht kontrolliert. Seine Lösung ist eine Strategie, die für jede Situation, in die er geraten könnte, festlegt, was zu tun ist. Ein Plan, der nur funktioniert, wenn der Gegner hilfreich antwortet, genügt nicht.

Ein Spielbaum beginnt beim aktuellen Zustand. Jede ausgehende Kante steht für einen zulässigen Zug, und ihr Kind ist der entstehende Zustand. Beschrifte jeden nicht terminalen Knoten mit dem Spieler, der dort handelt. In einem Spiel mit zwei Spielern, die abwechselnd ziehen, wechseln sich MAX- und MIN-Ebenen ab.

Einzelne Züge zählen

Ein Halbzug ist ein Zug eines Spielers. Im Schach umfasst ein vollständiger Zug gewöhnlich einen Zug von Weiß und einen von Schwarz, also zwei Halbzüge. Eine Suche der Tiefe 4, die bei Weiß am Zug beginnt, erreicht Stellungen, nachdem Weiß, Schwarz, Weiß und Schwarz gehandelt haben. Zähle die Kanten von der Wurzel aus, deren Tiefe null ist.

Sei $b$ der Verzweigungsfaktor und $m$ die maximale Tiefe. Ein gleichmäßiger Baum hat $b^d$ Knoten auf der Tiefe $d$ und $b^m$ Blätter. Seine Gesamtzahl an Knoten beträgt:

Für $b>1$ überwiegen die tiefsten Ebenen, was zu exponentiellem Wachstum führt. Bei vier Zügen pro Stellung hat Tiefe 3 insgesamt 64 Blätter und Tiefe 4 insgesamt 256. Ein zusätzlicher Halbzug vervierfacht die Blattzahl, statt sie mit eins zu multiplizieren.

Spiele und Stellungen unterscheiden

Bei Tic-Tac-Toe gibt es höchstens $9!=362.880$ Reihenfolgen, um das Spielfeld zu füllen. Viele Reihenfolgen würden nach einem früheren Sieg fortgesetzt und sind keine vollständigen zulässigen Spiele. Endet jedes Spiel sofort bei einem Sieg, ergeben sich 255.168 vollständige Spiele: 131.184 Siege von X, 77.904 Siege von O und 46.080 Unentschieden. Bei zulässigem Spiel gibt es insgesamt nur 5.478 verschiedene Spielfeldstellungen, einschließlich des leeren Spielfelds.

Der Unterschied entsteht unter anderem durch Zugumstellungen: verschiedene Zugfolgen, die denselben Zustand erreichen. X kann eine Ecke spielen, O die Mitte und X die gegenüberliegende Ecke, oder X kann die beiden Ecken in umgekehrter Reihenfolge spielen. Beide Pfade enden beim selben Spielfeld und demselben Spieler am Zug. Ein Baum behält beide Pfade; ein Spielgraph kann ihren gemeinsamen Zustand einmal speichern. Um Arbeit wiederzuverwenden, müssen vollständige Zustände erkannt werden, nicht nur optisch ähnliche Spielfelder.

Warum eine vollständige Suche scheitert

Schach wird oft mit etwa 35 zulässigen Zügen pro Stellung und einer Partie von 100 Halbzügen modelliert, also 50 Zügen pro Spieler. Das ergibt die ungefähre Größenordnung:

Reale Zweige enden auf unterschiedlichen Tiefen und haben unterschiedliche Anzahlen von Zügen. Doch bereits diese Schätzung erklärt, warum es unpraktikabel ist, einen gesamten Schachspielbaum aufzuzählen. Auf einem leeren 19×19-Go-Brett hat allein der erste Stein 361 mögliche Punkte.

Der Suchbaum ist das, was ein Algorithmus tatsächlich erzeugt. Einfaches Minimax erzeugt bei einem endlichen Spiel, das es bis zum Ende durchsucht, den vollständigen Spielbaum unterhalb des Zustands. Beschneidung, Tiefenbeschränkungen und selektive Simulation erzeugen weniger. Ein Blatt am Suchabbruch kann daher eine nicht beendete Stellung sein, obwohl ein Blatt des vollständigen Spielbaums terminal ist.

Eine Strategie im Baum darstellen

Ein Strategieteilbaum für MAX behält an jedem MAX-Knoten eine ausgewählte Kante und an jedem MIN-Knoten jede zulässige Kante. MAX wählt seine eigene Aktion, muss aber eine Antwort auf jeden gegnerischen Zug bereithalten. Ein einzelner Pfad von der Wurzel zu einem Blatt beschreibt nur einen möglichen Spielverlauf. Er kann nicht zeigen, dass der gewählte Plan auch den anderen Antworten standhält.

Minimax wählt das beste Ergebnis, das MAX gegen einen optimal spielenden Gegner sichern kann. Jeder Nutzen an einem Blatt wird für MAX gemessen. Eine große Zahl begünstigt MAX, auch wenn der bewertete Knoten zu MIN gehört.

Von den Blättern zur Wurzel arbeiten

Gib an einem terminalen Knoten seinen Nutzen zurück. Gib an einem MAX-Knoten den größten Wert seiner Kinder zurück. Gib an einem MIN-Knoten den kleinsten zurück. Fahre fort, bis die Wurzel einen Wert erhält:

Der Wert eines Kindes fasst bereits die optimale Fortsetzung ab diesem Kind zusammen. Deshalb vergleicht ein Elternknoten die zurückgegebenen Werte, statt jedes darunterliegende Blatt erneut zu öffnen. Die Rekursion funktioniert über beliebig viele wechselnde Ebenen.

Eine Entscheidung über zwei Halbzüge nachvollziehen

MAX hat drei Züge, die jeweils zu einem MIN-Knoten führen:

Bilde zuerst das Minimum jeder Zeile. MIN kann dafür sorgen, dass A den Wert 4, B den Wert 2 und C den Wert 5 hat. Dann bildet MAX das Maximum dieser drei Ergebnisse:

Der Minimax-Wert ist 5. Die Minimax-Entscheidung ist der Zug zu C. Das eine ist eine Zahl, die die Stellung beschreibt; das andere ist eine Aktion, die das Programm spielen kann.

Das größte Blatt, 15, liegt unter B, aber MAX kontrolliert nicht die Antwort, die dorthin führt. MIN würde 2 wählen. Der Mittelwert der Blätter von B ist 10, was ebenfalls attraktiv aussieht. Das Mitteln modelliert aber eine zufällige Wahl mit passenden Wahrscheinlichkeiten. Bei optimalem Gegenspiel ist ein Minimum gefragt.

Die Hauptvariante lesen

Die Hauptvariante ist die Zugfolge, die entsteht, wenn die Spieler optimal wählen. Hier spielt MAX nach C und MIN wählt dessen Blatt mit dem Wert 5. Folge in einem tieferen Baum auf jeder Ebene dem gewählten Maximum oder Minimum. Der terminale Nutzen am Ende dieser Variante entspricht dem Wert der Wurzel. Bei mehreren gleichwertigen Zügen kann es mehr als eine optimale Variante geben.

Die Garantie verstehen

Bei einem endlichen deterministischen Zwei-Personen-Nullsummenspiel mit perfekter Information garantiert die Minimax-Strategie mindestens den Wert der Wurzel. Ein optimaler Gegner begrenzt MAX auf diesen Wert. Ein Fehler des Gegners kann ein besseres Ergebnis ermöglichen; 5 ist also eine Untergrenze und keine Vorhersage, dass jedes Spiel mit genau 5 enden muss.

Ein Programm kann Schwächen ausnutzen und diese Untergrenze dabei erhalten. Haben zwei Züge beide den Minimax-Wert 5, kann es denjenigen bevorzugen, der dem Gegner mehr Fehlermöglichkeiten bietet. Wählt es einen Zug mit Minimax-Wert 2, weil dieser eine verlockende 15 enthält, gibt es die Garantie von 5 auf. Entscheidend ist, ob der Zug den besten Wert für den ungünstigsten Fall erhält.

Die Minimax-Definition ist bereits ein rekursives Programm. Eine Wertfunktion nimmt einen Zustand entgegen und gibt eine Zahl zurück. Eine Suchfunktion vergleicht die möglichen ersten Züge und gibt die zu spielende Aktion zurück.

Zugauswahl und Wertberechnung trennen

Der folgende Pseudocode setzt voraus, dass MAX an der Wurzel handelt und die Spieler abwechselnd ziehen:

MINIMAX-SEARCH(s):
    if Is-Terminal(s): return no action
    bestMove = no action
    bestValue = -infinity
    for a in Actions(s):
        value = MIN-VALUE(Result(s, a))
        if value > bestValue:
            bestValue = value
            bestMove = a
    return bestMove

MAX-VALUE(s):
    if Is-Terminal(s): return Utility(s, MAX)
    v = -infinity
    for a in Actions(s):
        v = max(v, MIN-VALUE(Result(s, a)))
    return v

MIN-VALUE(s):
    if Is-Terminal(s): return Utility(s, MAX)
    v = +infinity
    for a in Actions(s):
        v = min(v, MAX-VALUE(Result(s, a)))
    return v

Initialisiere MAX mit minus unendlich, sodass jedes Kind den Wert verbessert; initialisiere MIN mit plus unendlich. Prüfe auf ein Spielende, bevor du Nachfolger erzeugst. Ein volles Tic-Tac-Toe-Feld ohne Gewinnreihe ist ein Unentschieden und keine nicht terminale Stellung, deren bester Zug aus einer leeren Liste gewählt werden muss.

Nachvollziehen, was die Rekursion findet

Betrachte dieses Tic-Tac-Toe-Feld, bei dem X am Zug ist und ein Punkt ein leeres Feld bezeichnet:

X O X
. O .
. . .

O droht mit drei Zeichen in der mittleren Spalte. Spielt X irgendwo anders als auf das untere mittlere Feld, kann O im nächsten Zug gewinnen. Diese Züge haben für X den Wert −1. Der Zug auf das untere mittlere Feld blockiert den unmittelbaren Sieg und ermöglicht bei bestem Spiel ein Unentschieden mit dem Wert 0. Die Wurzel gibt das untere mittlere Feld zurück. Der Algorithmus braucht keine gesonderte Anweisung für diese Drohung: Die terminalen Ergebnisse bestimmen die Werte.

Zeit und Speicher einplanen

Minimax mit Tiefensuche untersucht bei Verzweigungsfaktor $b$ und maximaler Tiefe $m$ insgesamt $O(b^m)$ Knoten. Das Speichern aller erzeugten Geschwister auf jeder aktiven Ebene benötigt $O(bm)$ Speicher. Werden Nachfolger einzeln erzeugt, sinkt der Speicherbedarf der aktiven Suche abgesehen von der Zustandsrepräsentation auf $O(m)$. Die exponentielle Laufzeit ist gewöhnlich das Haupthindernis, nicht der Rekursionsstapel.

Die Bewertungskonvention beibehalten

Im MAX/MIN-Code gibt jeder Aufruf den Nutzen von MAX zurück. Kehre das Vorzeichen nicht allein deshalb um, weil MIN als Nächstes handelt. Negamax verwendet eine andere Konvention: Jeder Wert gilt aus Sicht des aktuellen Spielers, sodass der Wert eines Kindes negiert wird, bevor der Elternknoten maximiert:

Bei einem Spiel, das in weniger als 100 Halbzügen endet, kann der Zeitpunkt berücksichtigt werden, indem ein Sieg von MAX in Tiefe $d$ mit $100-d$, eine Niederlage mit $-100+d$ und ein Unentschieden mit 0 bewertet wird. Schnellere Siege erhalten dann höhere Werte und hinausgezögerte Niederlagen sind weniger negativ. Die strikte Tiefenbeschränkung hält jeden Sieg positiv und jede Niederlage negativ.

Beispielsweise ergeben Siege in den Halbzügen 3 und 7 die Werte 97 und 93, sodass der schnellere Sieg bevorzugt wird. Niederlagen in diesen Tiefen ergeben −97 und −93. Damit ist die spätere Niederlage vorzuziehen, obwohl beide schlechter als ein Unentschieden bleiben.

Ein einzelner Nutzen für MAX funktioniert, wenn die Interessen zweier Spieler strikt entgegengesetzt sind. Bei mehreren Spielern oder sich überschneidenden Interessen verwende einen Nutzenvektor. Für die Spieler A, B und C gibt der Vektor (1, 2, 6) ihre Auszahlungen in dieser Reihenfolge an.

Anhand des Eintrags des aktiven Spielers wählen

Vergleiche an einem Knoten, an dem C handelt, die dritten Einträge der Vektoren seiner Kinder. Gib den gesamten Vektor des von C bevorzugten Kindes zurück. Vergleiche an einem B-Knoten die zweiten Einträge dieser zurückgegebenen Vektoren und an einem A-Knoten die ersten.

Maximiere nicht jeden Eintrag unabhängig. Sind die Ergebnisse (1, 2, 6) und (4, 2, 3) verfügbar, wählt C den Vektor (1, 2, 6). Die Kombination (4, 2, 6) ist kein verfügbares Ergebnis und kann nicht zurückgeführt werden.

Bei drei Spielern rückwärts arbeiten

A zieht zuerst, dann B, dann C. Nach dem linken Zug von A wählt B zwischen zwei C-Knoten:

• Der erste hat die Blätter (1, 2, 6) und (4, 2, 3). C wählt (1, 2, 6).
• Der zweite hat die Blätter (6, 1, 2) und (7, 4, 1). C wählt (6, 1, 2).

B vergleicht die zweiten Einträge 2 und 1, sodass der linke Zweig (1, 2, 6) zurückgibt.

Nach dem rechten Zug von A:

• C wählt (5, 4, 5) statt (2, 5, 4), weil 5 im dritten Eintrag größer als 4 ist.
• C wählt (5, 2, 4) statt (7, 7, 1), weil 4 im dritten Eintrag größer als 1 ist.

B vergleicht die zweiten Einträge 4 und 2, sodass der rechte Zweig (5, 4, 5) zurückgibt. Schließlich vergleicht A die ersten Einträge 1 und 5 und wählt rechts. Die Wurzel erhält den gesamten Vektor (5, 4, 5).

Festlegen, wie Gleichstände aufgelöst werden

Kann C zwischen (2, 3, 4) und (6, 1, 4) wählen, erhält C in beiden Fällen 4. Die spätere Auszahlung von A könnte 2 oder 6 sein. Eine Vorhersage braucht eine Auswahlregel bei Gleichstand oder ein Modell für die Wahl von C. Dass einem anderen Spieler die Wahl gleichgültig ist, muss für den Spieler an der Wurzel nicht folgenlos sein.

Wollen zwei Verfolger beide MAX fangen, hat eine Runde eine MAX-Ebene und für jeden Verfolger eine MIN-Ebene. Bei zwei Verfolgern umfasst eine Runde drei Halbzüge. Dieses Modell unterscheidet sich von drei unabhängigen Spielern, die ihre eigenen Belohnungen verfolgen.

Sich überschneidende Interessen zulassen

In einem Nichtnullsummenspiel können beide Spieler (100, 100) niedrigeren gemeinsamen Auszahlungen vorziehen. Spieler können auch vorübergehend davon profitieren, einen gemeinsamen Führenden anzugreifen. Solches allianzähnliches Verhalten kann aus ihren eigenen Präferenzen folgen und sich ändern, wenn sich die Stellung ändert.

Gewöhnliche Alpha-Beta-Cutoffs beruhen auf entgegengesetzten Interessen und lassen sich nicht direkt auf Nutzenvektoren übertragen. Das paranoide Modell stellt einen Gegensatz zwischen zwei Spielern her und ermöglicht damit Alpha-Beta-Suche. Es kann aber eine koordinierte Feindseligkeit vorhersagen, für die sich die anderen Spieler tatsächlich nicht entscheiden würden.

Alpha-Beta-Beschneidung liefert auf demselben Baum mit denselben Blattwerten denselben Wert der Wurzel wie Minimax. Sie spart Arbeit, indem sie nachweist, dass manche Zweige die Wahl nicht verbessern können. Gleichwertige optimale Züge können in anderer Reihenfolge zurückgegeben werden.

Ein Suchfenster entlang des Pfads weitergeben

Zwei Schranken beschreiben die oberhalb des aktuellen Knotens verfügbaren Möglichkeiten:

• $\alpha$ ist der beste für MAX entlang des Pfads verfügbare Wert: MAX kann bereits mindestens diesen Wert erreichen.
• $\beta$ ist der beste für MIN entlang des Pfads verfügbare Wert: MIN kann den Wert für MAX bereits auf höchstens diesen Wert begrenzen.

Beginne an der Wurzel mit minus und plus unendlich. Jedes rekursive Kind erhält die aktuellen Schranken. Sie sind lokale Argumente und keine globalen Zahlen, die von nicht zusammengehörigen Suchen in benachbarten Teilbäumen geteilt werden.

Behalte an einem MAX-Knoten den größten bisher gesehenen Wert eines Kindes. Brich ab, sobald er Beta erreicht oder übersteigt: MIN weiter oben hat bereits eine Alternative, die höchstens Beta beträgt. Erhöhe andernfalls Alpha, wenn MAX eine Verbesserung findet. Behalte an einem MIN-Knoten den kleinsten bisher gesehenen Wert eines Kindes. Brich ab, sobald er Alpha erreicht oder unterschreitet: MAX weiter oben hat bereits eine mindestens ebenso gute Alternative. Senke andernfalls Beta.

MAX-VALUE(s, alpha, beta):
    if Is-Terminal(s): return Utility(s, MAX)
    v = -infinity
    for a in Actions(s):
        v = max(v, MIN-VALUE(Result(s, a), alpha, beta))
        if v >= beta: return v
        alpha = max(alpha, v)
    return v

MIN-VALUE(s, alpha, beta):
    if Is-Terminal(s): return Utility(s, MAX)
    v = +infinity
    for a in Actions(s):
        v = min(v, MAX-VALUE(Result(s, a), alpha, beta))
        if v <= alpha: return v
        beta = min(beta, v)
    return v

Die Wurzel vergleicht Aktionen und behält Alpha zwischen ihnen bei:

ALPHA-BETA-SEARCH(s):
    if Is-Terminal(s): return no action
    alpha = -infinity
    beta = +infinity
    bestMove = no action
    for a in Actions(s):
        v = MIN-VALUE(Result(s, a), alpha, beta)
        if v > alpha:
            alpha = v
            bestMove = a
    return bestMove

Einen MIN-Cutoff nachvollziehen

Durchsuche die MIN-Zweige A = (4, 9, 6), B = (2, 15, 13) und C = (5, 8, 10) von links nach rechts. A muss alle drei Blätter untersuchen und gibt 4 zurück. Die Wurzel hat nun Alpha 4. Das erste Blatt von B ist 2. Das endgültige Minimum kann nur bei 2 bleiben oder sinken, sodass B nicht besser als A sein kann. Überspringe die beiden übrigen Blätter von B. C untersucht alle drei Blätter und gibt 5 zurück. Die Wurzel wählt C, nachdem sieben von neun Blättern untersucht wurden.

Einen MAX-Cutoff nachvollziehen

Angenommen, ein MIN-Elternknoten hat bereits ein Kind mit dem Wert 3, wodurch Beta auf 3 gesetzt wird. Sein nächstes MAX-Kind findet ein Blatt mit dem Wert 6. Der Wert dieses Kindes beträgt mindestens 6, sodass MIN seine vorhandene 3 bevorzugen wird. Überspringe die übrigen Kinder dieses MAX-Knotens. Die Begründung für den Cutoff beruht auf der Alternative von MIN, obwohl der aktuelle Knoten ein MAX-Knoten ist.

Ein beschnittener MIN-Knoten kann eine obere Schranke zurückgeben; ein beschnittener MAX-Knoten kann eine untere Schranke zurückgeben. Ihre exakten Werte bleiben unbekannt. Der abschließend ermittelte Wert der Wurzel ist für den durchsuchten Baum exakt. Auch Gleichheit erlaubt einen Cutoff, weil ein Zweig, der höchstens gleichziehen kann, den aktuellen Bestwert nicht verbessern kann.

Alpha-Beta spart die meiste Arbeit, wenn starke Züge früh durchsucht werden. Die Werte ändern sich durch die Zugreihenfolge nicht; sie beeinflusst, ab wann die Suche einen Cutoff nachweisen kann.

Zwei Reihenfolgen vergleichen

Bei den drei MIN-Zweigen A = (4, 9, 6), B = (2, 15, 13) und C = (5, 8, 10) werden sieben Blätter untersucht, wenn mit A begonnen wird. Beginne stattdessen mit C. Seine drei Blätter ergeben Alpha 5. A findet dann sofort 4 und bricht ab; B findet sofort 2 und bricht ab. Nur fünf Blätter werden bewertet, und die Antwort bleibt C mit dem Wert 5.

Für einen gleichmäßigen Baum mit perfekter Sortierung beträgt die Blattzahl:

Das entspricht etwa $O(b^{m\mathrm{/}2})$ statt $O(b^m)$ bei Minimax. Der effektive Verzweigungsfaktor sinkt auf etwa $\sqrt{b}$, sodass bei vergleichbarem Aufwand ungefähr die doppelte Tiefe möglich ist. Bei $b=35$ werden mit perfekter Sortierung bis Tiefe 8 insgesamt 3.001.249 Blätter bewertet; gewöhnliches Minimax bis Tiefe 4 hat 1.500.625 Blätter. Der Vergleich betrifft die Größenordnung, nicht eine identische Laufzeit.

Bei der ungünstigsten Reihenfolge kann Alpha-Beta jedes Minimax-Blatt untersuchen. Seine zusätzlichen Schrankenprüfungen verursachen auch dann Mehraufwand, wenn sie keine Blätter einsparen.

Kostengünstige Hinweise für die Sortierung nutzen

Der genaue beste Zug ist vor der Suche unbekannt. Programme verwenden schnelle Schätzungen. Im Schach können sie Schlagzüge, dann Drohungen und dann ruhige Züge ausprobieren. Ein Killerzug hat anderswo auf derselben Suchtiefe einen Cutoff ausgelöst und wird in einer anderen Stellung früh ausprobiert. Diese Hinweise beeinflussen die Effizienz; sie rechtfertigen nicht, die anderen zulässigen Züge zu verwerfen.

Die iterative Vertiefung sucht bis Tiefe 1, dann 2, dann 3 und so weiter. Ein starker Zug aus der vorherigen Iteration wird in der nächsten früh geprüft. Das Ergebnis der tiefsten abgeschlossenen Iteration liegt auch bereit, wenn die Zeit abläuft.

Der Aufwand der wiederholten Arbeit hängt von der Beschneidung ab. Bei unbeschnittener gleichmäßiger Suche mit Verzweigungsfaktor 35 erhöhen alle flacheren Iterationen den Aufwand der letzten Suche um etwa $1\mathrm{/}(35-1)\approx \mathrm{2,9}\mathrm{\%}$. Bei Alpha-Beta mit perfekter Sortierung bewerten die Tiefen 1 bis 7 zusammen 1.677.159 Blätter, etwa 56 % der Anzahl bei Tiefe 8. Eine bessere Sortierung kann den Gesamtprozess trotzdem lohnend machen.

Stellungen mit der Bedeutung ihrer Werte zwischenspeichern

Eine Transpositionstabelle speichert Ergebnisse, die über den vollständigen Spielzustand auffindbar sind. Erreicht eine andere Zugfolge diesen Zustand, kann das Programm einen passenden Eintrag wiederverwenden. Speichere die durchsuchte Tiefe und ob das Ergebnis exakt, eine untere oder eine obere Schranke ist. Ein Eintrag aus einer flachen Suche ersetzt nicht die benötigte Information einer tieferen Suche. Eine Schranke kann ein Fenster verengen oder einen Cutoff rechtfertigen, darf aber nicht als exakter Wert behandelt werden.

Eine Bewertungsfunktion schätzt, wie günstig eine nicht beendete Stellung für MAX ist. Sie ermöglicht eine tiefenbeschränkte Suche: Die Suchfront erhält geschätzte Werte, die durch Minimax oder Alpha-Beta zurückgeführt werden können.

Werte für die Suche nutzbar machen

Eine gute Bewertungsfunktion ist schnell, stimmt mit der Reihenfolge tatsächlicher terminaler Ergebnisse überein und korreliert bei nicht terminalen Stellungen mit dem Erfolg. Terminalzustände selbst sollten ihren exakten Nutzen erhalten. Ein Sieg von MAX muss höher bewertet werden als jede Schätzung für eine nicht terminale Stellung, damit das Sammeln von Figuren nicht attraktiver als ein Sieg werden kann.

Eine Möglichkeit, Bewertung zu betrachten, besteht darin, Stellungen nach gemeinsamen Merkmalen zu gruppieren. Ergibt eine solche Gruppe 72 % Siege, 8 % Unentschieden und 20 % Niederlagen bei den Nutzen 1, ½ und 0, beträgt ihr durchschnittlicher Nutzen:

Diese Deutung hängt davon ab, wie Stellungen und Fortsetzungen ausgewählt wurden. Sie ist eine Schätzung der Ergebnisqualität und kein Beweis für einen erzwungenen Sieg.

Gewichtete Merkmale addieren

Ein verbreiteter Ansatz ist eine gewichtete Summe:

Jedes Merkmal $f_i(s)$ misst eine Eigenschaft der Stellung; jedes Gewicht $w_i$ gibt an, wie viel es beiträgt. Unterschiede zwischen den Seiten halten den Blickwinkel eindeutig. Ein positiver Materialunterschied bedeutet, dass MAX mehr Material hat.

Die traditionellen Schachwerte sind Bauer 1, Springer 3, Läufer 3, Turm 5 und Dame 9. Dem König wird kein Materialwert als schlagbare Figur zugewiesen. Angenommen, MAX ist Weiß. Weiß hat eine Dame, zwei Türme, einen Läufer und sechs Bauern:

Schwarz hat zwei Türme, zwei Springer, einen Läufer und sieben Bauern:

Das Materialmerkmal ist daher $28-26=2$. Hat Weiß 30 zulässige Züge und Schwarz 24, beträgt der Mobilitätsunterschied 6. Mit dem Materialgewicht 1 und dem Mobilitätsgewicht 0,1 ergibt sich:

Diese 2,6 ist ein Merkmalswert und keine Gewinnwahrscheinlichkeit von 260 %. Die Gewichte bestimmen seine Skala.

Wechselwirkungen zwischen Merkmalen berücksichtigen

Eine einfache lineare Summe weist jedem Merkmal einen festen Beitrag unabhängig von den anderen zu. Der tatsächliche Wert im Spiel kann von Kombinationen abhängen: Ein Läuferpaar kann mehr wert sein als die Summe seiner einzelnen Beiträge, und die Bedeutung eines Bauern kann sich im Endspiel ändern. Kombinierte Merkmale, von der Spielphase abhängige Gewichte oder nichtlineare Bewertungsfunktionen können diese Effekte erfassen. Gewichte können nach Ermessen gewählt oder an Ergebnisse aufgezeichneter Partien angepasst werden.

Mehr Merkmale kosten auch Zeit. Eine aufwendige Bewertungsfunktion, die einen zusätzlichen nützlichen Suchhalbzug verhindert, kann die Entscheidung verschlechtern, selbst wenn ihre einzelnen Schätzungen besser werden.

Die Skala an die Rückführungsregel anpassen

Bei deterministischem Minimax erhalten einheitlich angewendete streng monoton steigende Transformationen die Reihenfolge bei der Bildung von Maxima und Minima. Das Quadrieren ausschließlich positiver Werte erhält beispielsweise deren Reihenfolge. Das Quadrieren beliebiger vorzeichenbehafteter Werte tut dies nicht. An Zufallsknoten sind die tatsächlichen Abstände zwischen Nutzenwerten wichtig, weil die Werte gemittelt werden. Ein Wert, der nur zur Einordnung von Stellungen entwickelt wurde, muss kalibriert werden, bevor er den erwarteten Nutzen darstellen kann.

Heuristisches Minimax beendet die Suche, bevor das Spiel endet. Seine Antwort ist für den durchsuchten Baum mit den zugewiesenen Werten an der Suchfront optimal. Es kann im tatsächlichen Spiel trotzdem einen Zug wählen, der zur Niederlage führt, wenn diese Schätzungen das weitere Geschehen nicht erfassen.

Terminalzustände und Suchabbrüche unterscheiden

Ein Terminalzustand hat ein bekanntes Ergebnis. Ein Abbruch wegen der Tiefenbeschränkung lässt das Spiel unvollendet und benötigt eine Schätzung. Prüfe beides in dieser Reihenfolge:

H-MINIMAX(s, d):
    if Is-Terminal(s): return Utility(s, MAX)
    if Is-Cutoff(s, d): return Eval(s)
    if To-Move(s) == MAX:
        return max over a of H-MINIMAX(Result(s, a), d + 1)
    return min over a of H-MINIMAX(Result(s, a), d + 1)

Der Abbruchtest prüft gewöhnlich, ob die Tiefe eine Schranke erreicht hat. Alpha-Beta kann denselben heuristischen Baum beschneiden. Die Beschneidung bleibt bezogen auf diese Werte an der Suchfront exakt; sie macht aus Schätzungen keine tatsächlichen Spielergebnisse.

Unter einer Zeitbeschränkung behält die iterative Vertiefung die Aktion aus der tiefsten abgeschlossenen Iteration. Eine teilweise durchsuchte Wurzel auf größerer Tiefe kann den ersten Zweig bevorzugen, nur weil seine Konkurrenten noch nicht bewertet wurden.

Einen taktischen Abtausch abschließen

Eine ruhige Stellung ist so stabil, dass eine kurze erzwungene Fortsetzung ihre Bewertung wahrscheinlich nicht stark verändert. Die Ruhesuche sucht in unruhigen Stellungen über die normale Tiefe hinaus weiter und folgt dabei gewöhnlich Schlagzügen, bis der Abtausch abgeschlossen ist.

Angenommen, die weiße Dame schlägt genau an der Tiefenbeschränkung einen Bauern. Der Materialwert verbessert sich um 1. Schwarz kann aber im nächsten Halbzug die Dame zurückschlagen. Die Nettoveränderung des Materials ist:

Ein Abbruch nach dem ersten Schlagzug meldet +1; eine kurze Erweiterung um Schlagzüge zeigt −8. Das Problem ist die Bewertung mitten in einem Abtausch, nicht ein Versagen der Rückführungsregel von Minimax.

Hinausgezögerte Verluste erkennen

Der Horizonteffekt tritt auf, wenn ein Programm einen unvermeidbaren Verlust über die Suchtiefe hinauszögert. Ein gefangener Läufer kann nach mehreren Schachgeboten mit Bauern trotzdem verloren gehen. Sieht die Suche die Schachgebote, endet aber vor dem Schlagen des Läufers, kann sie Bauern opfern, um diesen zukünftigen Verlust zu verbergen.

Eine singuläre Erweiterung sucht entlang eines Zugs tiefer, der deutlich besser als seine Alternativen ist. Programme erweitern auch zwingende Schachgebote oder das Zurückschlagen. Erweiterungen investieren zusätzliche Tiefe in ausgewählte Varianten; sie brauchen ein Budget, damit die Suche noch abgeschlossen werden kann.

Vorwärtsbeschneidung, etwa wenn nur die besten wenigen Züge behalten werden, kann den Gewinnzug verwerfen. Ihre Einsparungen bieten nicht die Garantie von Alpha-Beta.

Suche durch exakt gespeichertes Wissen ersetzen

Ein Eröffnungsbuch liefert untersuchte frühe Züge. Endspieldatenbanken arbeiten durch retrograde Analyse von bekannten Ergebnissen aus rückwärts. Schach-Endspieldatenbanken für sieben Figuren schließen die beiden Könige ein und liefern exakte Ergebnisse für die abgedeckten Endspiele. Die Regeln und Zustandsinformationen beim Nachschlagen müssen zum gespielten Spiel passen.

Ein Zufallsknoten stellt ein Zufallsereignis dar. Seine Zweige führen mögliche Ergebnisse und deren Wahrscheinlichkeiten auf, die zusammen 1 ergeben. Kein Spieler wählt den für ihn günstigsten Zweig.

Die zu jedem Knoten gehörende Regel anwenden

Für Ergebnisse $r$ hat ein Zufallsknoten den Wert:

Expectiminimax kombiniert alle vier Regeln. Expectimax verwendet MAX und Zufall, wenn es keinen minimierenden Spieler gibt. Ein Wahrscheinlichkeitsmodell eines zufällig spielenden Gegners kann auch in einem Spiel Zufallszweige liefern, dessen Zugregeln deterministisch sind.

Über Zufall und Gegenspiel rückwärts arbeiten

MAX wählt L oder R. Auf jeden Zug folgen ein Zufallsereignis und dann eine Wahl von MIN.

Nach L ergibt eine faire Münze zwei MIN-Knoten. Ihre Blätter sind (3, 7) und (8, 4). MIN gibt 3 und 4 zurück. Der Zufallsknoten ergibt dann:

Nach R führen die Wahrscheinlichkeiten 0,25 und 0,75 zu MIN-Knoten mit den Blättern (10, 1) und (6, 5). Ihre Werte sind 1 und 5, also:

MAX wählt R, weil 4 größer als 3,5 ist. Würde man zuerst die terminalen Blattwerte mitteln, träte der Zufall an die Stelle der Entscheidung von MIN. Verarbeite jeden Knoten, nachdem seine Kinder ausgewertet wurden.

Die richtigen Wahrscheinlichkeiten zuweisen

Zwei faire Würfel haben 36 gleich wahrscheinliche geordnete Ergebnisse. Beim Backgammon werden umgekehrte Reihenfolgen wie 3-5 und 5-3 zu demselben Wurf zusammengefasst. Das ergibt 21 verschiedene Würfe: sechs Pasche mit je der Wahrscheinlichkeit 1/36 und 15 Würfe ohne Pasch mit je der Wahrscheinlichkeit 1/18. Die Probe lautet:

Würde man allen 21 Würfen die Wahrscheinlichkeit 1/21 geben, würden Pasche zu stark und Würfe ohne Pasch zu schwach gewichtet. Gleich aussehende Zweige müssen nicht gleich wahrscheinlich sein.

Hat jede Entscheidungsstufe $b$ zulässige Züge und ein Zufallsereignis mit $n$ Ergebnissen, kostet die Suche über $m$ solcher Stufen etwa $O(b^m{n}^m)$. Die Tiefenkonvention muss berücksichtigen, wie oft Zufall auftritt. Bei ungefähr 20 zulässigen Zügen und 21 Würfen begrenzen die zusätzlichen Zufallszweige beim Backgammon den vollständigen Vorausblick schnell.

Beispielsweise ergeben zwei Stufen mit jeweils 21 Zufallsergebnissen und 20 Aktionen insgesamt $(21\times 20{)}^2=176.400$ Pfade. Zähle bei der Schätzung dieses Aufwands Zufallsereignisse getrennt von den Halbzügen der Spieler.

Nur bei beschränkten ungesehenen Ergebnissen beschneiden

Ein teilweiser Mittelwert ist keine Minimax-Schranke. Liegen die Nutzen zwischen 0 und 10 und hat das erste von zwei gleich wahrscheinlichen Ergebnissen den Wert 2, liegt der Wert des gesamten Knotens zwischen 1 und 6. Insbesondere gilt:

Hat MAX bereits einen anderen Zug mit dem Wert 7, kann dieser Zufallsknoten ihn nicht übertreffen und das verbleibende Ergebnis kann übersprungen werden. Ohne eine geeignete Schranke für ungesehene Werte könnte ein extremes Ergebnis den Mittelwert noch so stark verändern, dass sich die Wahl umkehrt.

Minimax fragt, welches Ergebnis ein Gegner durchsetzen kann. Expectimax fragt, welcher durchschnittliche Nutzen aus einem Wahrscheinlichkeitsmodell folgt. Ihre Entscheidungen können selbst auf demselben Baum unterschiedlich ausfallen, weil sie unterschiedliches Verhalten darstellen.

Optimales und zufälliges Gegenspiel vergleichen

Bei den MIN-Zweigen A = (4, 9, 6), B = (2, 15, 13) und C = (5, 8, 10) wählt Minimax C mit einer Garantie von 5. Wählt der Gegner stattdessen jede Antwort gleichverteilt, betragen die Erwartungswerte etwa 6,33, 10 und 7,67. Expectimax wählt B.

Unter dem Gleichverteilungsmodell ist das sinnvoll, aber ein geschickter Gegner kann auf B mit 2 antworten. Expectimax nimmt nicht an, dass der Gegner einen Durchschnitt minimiert. Es verwendet die angegebenen Wahrscheinlichkeiten. Bei einem korrekten Modell maximiert es den erwarteten Nutzen; der Schutz für den ungünstigsten Fall ist schwächer als bei Minimax. Im Durchschnitt kann es genauso gut wie Minimax abschneiden, wenn beide denselben Zug empfehlen.

Ein Baum kann Modelle mischen. Der Knoten eines gegnerisch handelnden Agenten bildet ein Minimum, während der Knoten eines zufällig handelnden Agenten einen gewichteten Mittelwert bildet. Verwende die Regel für den Agenten, der an diesem Knoten handelt, statt eine Regel für jede Nicht-MAX-Ebene zu verwenden.

Warum die Reihenfolge allein nicht ausreicht

Angenommen, Zug A ergibt 2 mit Wahrscheinlichkeit 0,6 und 3 mit Wahrscheinlichkeit 0,4. Zug B ergibt 1 mit Wahrscheinlichkeit 0,6 und 4 mit Wahrscheinlichkeit 0,4:

A hat den größeren Erwartungswert. Kubiere nun jeden terminalen Wert. Ihre Rangfolge bleibt gleich, aber die Erwartungswerte werden zu:

B gewinnt nun den Vergleich. Transformierte Ergebnisse zu mitteln ist etwas anderes, als ihren Mittelwert zu transformieren. Das Kubieren verstärkt den Vorteil des hohen Ergebnisses von B so weit, dass sich die Entscheidung ändert.

Entscheidungen mit den richtigen Transformationen erhalten

Eine positive affine Transformation multipliziert jeden Erwartungswert mit derselben positiven Zahl und addiert dieselbe Konstante. Die Anwendung von $10x+5$ ergibt für A den Wert 29 und für B den Wert 27, sodass A bevorzugt bleibt.

Wären A und B MIN-Knoten, wären ihre Werte vor dem Kubieren 2 und 1 und danach 8 und 1. Ihre Reihenfolge bliebe unverändert. Maxima und Minima wählen einen Wert eines Kindes; Mittelwerte kombinieren die Größen mehrerer Werte.

Eine bei Zufall verwendete Bewertungsfunktion sollte daher den angestrebten erwarteten Nutzen auf einer einheitlichen Skala schätzen, etwa die Gewinnwahrscheinlichkeit oder eine positive affine Transformation davon. Ein nichtlinearer Wert zur Rangordnung kann für deterministisches Minimax geeignet sein, bei Zufall aber zu falschen Abwägungen von Risiken führen.

Monte-Carlo-Baumsuche, kurz MCTS, schätzt Züge anhand simulierter Spiele und baut dabei einen Baum auf, der künftige Simulationen steuert. Eine simulierte Fortsetzung bis zum Ende ist ein Playout oder Rollout. Seine Strategie kann zufällige zulässige Züge wählen oder kostengünstiges Wissen nutzen, um ein sinnvolleres Spiel zu erzeugen.

Belege an jedem Knoten speichern

Führe eine Besuchszahl $N(n)$ und eine kumulierte Belohnung $U(n)$. Verwende in einem Zwei-Personen-Spiel mit Sieg und Niederlage die Siege des Spielers, dessen Zug zum Knoten $n$ geführt hat. Ein Unentschieden fügt gewöhnlich einen halben Sieg hinzu. Dann schätzt $U(n)\mathrm{/}N(n)$ die Erfolgsrate dieses Spielers.

Die Wurzel hat keinen eingehenden Zug. Ihre Besuche zählen trotzdem jede Iteration; Siege an der Wurzel können bei Bedarf aus Sicht des Spielers an der Wurzel erfasst werden. Die Werte der Kinder, die die Selektion steuern, müssen einheitlich den Blickwinkel des Spielers verwenden, der den eingehenden Zug gemacht hat.

Die vier Phasen wiederholen

1. Selektion: Folge von der Wurzel aus einer Selektionsstrategie durch vorhandene Kinder, bis ein terminaler Knoten oder ein Knoten mit einem noch nicht ausprobierten Zug erreicht ist.
2. Expansion: Füge bei einem nicht terminalen Knoten ein Kind für einen noch nicht ausprobierten zulässigen Zug hinzu.
3. Simulation: Führe von diesem Kind aus ein Playout bis zu einem terminalen Ergebnis durch.
4. Rückpropagation: Aktualisiere Besuche und Belohnungen für die Knoten auf dem gewählten Pfad.

Erreicht die Selektion einen terminalen Knoten, überspringe Expansion und Simulation. Sein bekanntes Ergebnis kann sofort zurückgeführt werden. Die vorübergehende Fortsetzung eines Playouts muss nicht als neue Baumknoten gespeichert werden: Die gewöhnliche Expansion fügt pro Iteration ein Kind hinzu.

Eine Aktualisierung der Belohnung nachvollziehen

Weiß handelt an der Wurzel. Selektion und Expansion folgen:

• n1, erreicht durch den Zug von Weiß;
• n2, erreicht durch den Zug von Schwarz;
• n3, erreicht durch den Zug von Weiß.

Das Playout endet mit einem Sieg von Schwarz. Erhöhe die Besuche an der Wurzel und an n1, n2 und n3 um jeweils eins. Erhöhe unter diesen drei Kindknoten die Siege nur an n2, weil der eingehende Zug zu n2 von Schwarz stammt. Die Kindknoten von Weiß erhalten keinen zusätzlichen Sieg. Wird an der Wurzel aus Sicht des Wurzelspielers gezählt, bleibt auch die eigene Gewinnsumme der Wurzel unverändert.

Ein Unentschieden würde der Belohnung jedes Kindes 0,5 hinzufügen. Würde man den Sieg von Schwarz an jedem Knoten als Erfolg zählen, würde Weiß Züge wählen, die Schwarz helfen.

Den Baum ungleichmäßig wachsen lassen

Wiederholte Iterationen konzentrieren Simulationen auf erfolgversprechende oder unsichere Zweige. Stark aussehende Züge erhalten tendenziell größere Teilbäume, während in schlechte Züge weniger Arbeit fließt. Die Suche legt nicht für jede Variante eine feste Tiefe fest. Sobald ein zulässiger Zug verfügbar ist, kann sie bei einer Zeitbeschränkung beendet werden und ihre gesammelten Statistiken nutzen.

Die endgültige Aktion ist gewöhnlich der Zug zum meistbesuchten Kind der Wurzel. Ein Zug mit zwei Siegen aus zwei Simulationen hat eine perfekte beobachtete Rate, aber wenig Belege. Ein häufig besuchter Zug wurde im Verlauf der Suche viel gründlicher untersucht.

Die reine Monte-Carlo-Suche weist den Zügen an der Wurzel unabhängige Playouts zu, ohne einen Entscheidungsbaum aufzubauen. Sie kann eine starke Antwort des Gegners wiederholt übersehen, weil das spätere Spiel weiterhin von der Playout-Strategie bestimmt wird. MCTS kann tiefere Entscheidungen verfeinern, während es Belege sammelt, auch wenn es weiterhin dauern kann, eine seltene taktische Widerlegung zu entdecken.

MCTS muss entscheiden, wo eine weitere Simulation am nützlichsten ist. Exploitation besucht erneut Züge, die bereits stark aussehen. Exploration untersucht Züge, für die weniger Belege vorliegen und die sich als besser erweisen könnten. Immer der höchsten beobachteten Gewinnrate zu folgen, kann die Suche auf ein frühes Glücksergebnis festlegen.

Einen UCB1-Wert berechnen

Der Wert der oberen Konfidenzschranke für das Kind $n$ lautet:

Der erste Term ist die beobachtete Gewinnrate. Der zweite ist ein Explorationsbonus. Er wächst, wenn der Elternknoten Besuche sammelt, und schrumpft, wenn das Kind mehr Besuche erhält. Der Logarithmus ist natürlich. Wähle bei der Selektion das Kind mit dem größten Gesamtwert.

Behandle ein unbesuchtes Kind als Kind mit unendlicher Priorität, statt durch null zu dividieren. Jeder zulässige Zug an einem Knoten wird ausprobiert, bevor die Selektion wiederholt besuchte Alternativen bevorzugt. MCTS mit dieser Selektionsregel heißt UCT, auf Bäume angewendete obere Konfidenzschranken.

Drei Kinder vergleichen

Ein Elternknoten hat 50 Besuche. Seine Kinder haben die Gewinn- und Besuchszahlen 21/30, 7/12 und 3/8. Mit $C=\sqrt{2}$ und $\ln 50\approx \mathrm{3,912}$:

Das zweite Kind wird ausgewählt. Seine aktuelle Gewinnrate liegt unter der des ersten Kindes, aber sein Unsicherheitsbonus ist größer. Das dritte wurde noch seltener besucht, doch seine niedrigere Gewinnrate lässt seinen Gesamtwert knapp unter dem des zweiten liegen.

Mit $C=\mathrm{0,5}$ ergeben sich aus denselben Zahlen Gesamtwerte von etwa 0,881, 0,869 und 0,725. Die Selektion bevorzugt nun das erste Kind. Kein Ergebnis hat sich geändert; das Programm hat geändert, wie stark es Unsicherheit belohnt.

Die Explorationskonstante interpretieren

Ein größeres positives $C$ gewichtet Exploration stärker. Setzt du die Konstante auf null, entfällt der Bonus und die Wahl erfolgt allein anhand des beobachteten Mittelwerts. Die Formulierung des Mehrarmigen-Bandit-Problems mit Belohnungen zwischen 0 und 1 begründet $C=\sqrt{2}$ in dieser Form der Gleichung; praktische Spielprogramme stimmen die Konstante ab. Eine Änderung der Belohnungsskala verändert auch das Verhältnis zum Explorationsterm.

Bei jedem Elternknoten erfassen seine Kinder Siege für den Spieler, der dort wählt. Dadurch ist die Maximierung von UCB1 bei beiden Spielern am Zug sinnvoll. Würde man im gesamten Baum nur Siege von Weiß speichern und jeden Wert maximieren, würde Schwarz den Erfolg von Weiß bevorzugen.

Suchpriorität und Zugqualität unterscheiden

UCB1 wählt, wo die nächste Simulation eingesetzt wird. Ein großer Unsicherheitsbonus kann dazu führen, dass sich die Untersuchung eines wenig getesteten Zugs lohnt. Wähle am Ende der Suche das meistbesuchte Kind der Wurzel, nicht das Kind mit dem aktuell höchsten UCB1-Wert. Unter den Bedingungen von UCT für endliche Spiele und bei fortgesetzter Exploration nähert sich eine unbegrenzte Suche dem Minimax-Verhalten; ein endliches Budget lässt weiterhin Unsicherheit durch die Stichprobenziehung.

Ein Suchverfahren muss zur Größe des Zugraums, zur Qualität der verfügbaren Bewertung und zur Art der Unsicherheit im Spiel passen. Dasselbe Zeitbudget kann zu sehr unterschiedlichen Entscheidungen führen, je nachdem, was das Verfahren untersucht.

Taktische Abdeckung und Simulation vergleichen

Alpha-Beta kann innerhalb seiner Suchtiefe eine einzelne taktische Widerlegung finden. MCTS bevorzugt möglicherweise zunächst einen Zug, der die meisten zufälligen Playouts gewinnt, aber gegen eine präzise Antwort verliert. Während der Baum wächst, kann es diese Antwort entdecken, doch bei einem kleinen Simulationsbudget kann sie unentdeckt bleiben. Eine hohe Gewinnrate bei Playouts ist daher keine Garantie für den ungünstigsten Fall.

Verfahren mit wegweisenden Programmen verbinden

1997 nutzte IBMs Deep Blue Alpha-Beta-Suche, Spezialhardware und Schachbewertung, um Weltmeister Garri Kasparow über sechs Partien mit 3½–2½ zu besiegen. Der Erfolg zeigte, wie viel starke Suche und spielspezifische Bewertung zusammen erreichen können.

Bei Go war diese Kombination schwieriger. Ein leeres 19×19-Brett bietet 361 Möglichkeiten, einen Stein zu setzen, und eine Stellung anhand einfacher Merkmale zu beurteilen ist schwierig. MCTS wurde zu einem starken Ansatz, weil es Ergebnisse durch Spielen schätzen und einen selektiven Baum aufbauen konnte, ohne eine handgeschriebene statische Bewertungsfunktion zu benötigen.

AlphaGo kombinierte MCTS mit neuronalen Netzen, die Züge vorschlagen und Stellungen bewerten. Seine Beschreibung in Nature von 2016 ging seinem 4–1-Sieg über Lee Sedol im März 2016 voraus. AlphaZero nutzte später eine Bewertung durch ein neuronales Netz anstelle zufälliger Playouts und erreichte in Schach, Shogi und Go übermenschliche Spielstärke. Diese Programme zeigen, dass ein Suchverfahren unterschiedliche Quellen für Stellungswerte nutzen kann.

Starkes Spiel und das Lösen eines Spiels unterscheiden

Ein Programm kann einen Meister besiegen, ohne den Wert der Anfangsstellung zu beweisen. 2007 stellte Jonathan Schaeffers Team mithilfe von Suche und großen Endspieldatenbanken fest, dass Dame bei perfektem Spiel unentschieden endet. Das Lösen des Spiels bestimmt ein Ergebnis gegen jede mögliche gegnerische Strategie, nicht nur gegen die in Wettkämpfen getesteten Gegner.

Das Verfahren auf das Modell abstimmen

Ziehe in einem stochastischen Spiel während des Durchlaufens des Baums und der Playouts Zufallsergebnisse entsprechend ihren tatsächlichen Wahrscheinlichkeiten. Ein Ereignis mit Wahrscheinlichkeit 0,8 sollte über viele Stichproben etwa viermal so oft auftreten wie eines mit Wahrscheinlichkeit 0,2. So wird derselbe gewichtete Erwartungswert geschätzt, den die explizite Rückführung am Zufallsknoten berechnet.

Jeder Ansatz hängt weiterhin von korrekten Regeln und Zustandsübergängen ab. Tiefenbeschränktes Alpha-Beta hängt von seiner Bewertungsfunktion ab; MCTS hängt von seiner Simulations- oder Bewertungsstrategie und seinem endlichen Stichprobenbudget ab. Einen gegnerisch handelnden Spieler als zufällig zu modellieren, kann kostspielig sein, unabhängig davon, welches Suchverfahren die Antwort dieses Modells berechnet.