exponentielle-entscheidungsbaeume

In unserem letzten Beitrag haben wir uns damit beschäftigt, wann wir einen künstlichen Agenten als intelligent wahrnehmen und mit welchen Basis-Methoden spezialisierte intelligente Agenten Probleme lösen können. Eine wichtige Methode ist die Suche nach den jeweils besten Handlungsoptionen. Die Such-Komponente wird dabei umso wichtiger, je komplexer die Problemstellung ist.

Exponentielle Entscheidungsbäume

Bei vielen Problemen wachsen die zu durchsuchenden Entscheidungsbäume exponentiell, was dazu führt, dass sie selbst mit massivster Rechenleistung nicht komplett durchsucht werden können. Ein gutes Beispiel hierfür sind interaktive Spiele wie Isolation, Schach, oder Go, bei denen jeweils nicht nur die eigenen Möglichkeiten, sondern auch alle jeweils möglichen Reaktionen des Gegners in Betracht gezogen werden müssen.

Adversarial Search und Minimax Agenten

Die Suche nach Lösungen für Probleme, bei denen sich zwei Gegner gegenüberstehen, nennt man Adversarial Search. Eine Möglichkeit, diese Probleme zu modellieren, ist die Annahme, dass der Agent und sein Gegner rational handeln und anhand der gleichen Bewertungsmuster agieren und in den selben Situationen die selben Entscheidungen treffen. Jeder Agent versucht dann, seine eigene Gewinnchance zu maximieren und die des Gegners zu minimieren. Die Suche nach der besten Handlungsoption muss also einen ständigen Wechsel von Minimieren und Maximieren durchlaufen, weshalb man auch von Minimax-Agenten spricht.

Diese Rationalisierung hilft zwar bei der Modellierung des Problems, die exponentielle Natur des Entscheidungsbaums führt jedoch in der Regel dazu, dass die beste Handlungsoption nicht mit Brute Force, also durch ein bloßes Ausrollen aller möglichen Entscheidungsbäume gefunden werden kann (Roll-Outs) – insbesondere, wenn für die Entscheidungsfindung zusätzlich ein Zeit-Limit gilt.

Depth Limited Search

Wenn die Suche durch einen Entscheidungsbaum zeitlich limitiert ist, gibt es verschiedene Strategien für das Finden der besten Option innerhalb der zur Verfügung stehenden Zeit. Eine naheliegende Möglichkeit besteht darin, die Such-Tiefe zu limitieren und z.B. nur die nächsten drei Züge inklusive der möglichen Antworten des Gegners komplett durchzurechnen.

Da das Ergebnis jeder möglichen Position allerdings kein Endresultat mit der Antwort „Sieg“ oder „Niederlage“ ist, stellt sich die Frage, wie der Agent die Suchergebnisse beurteilen soll. Bei diesen Ergebnissen handelt es sich jeweils um einen Status des Spielfelds inklusive der Positionen des Agenten und des Gegners. Welcher Status ist der vorteilhafteste und warum?

Situationen richtig einschätzen mit Evaluation Functions

Der Agent benötigt also eine heuristische Funktion, mit der er für den aktuellen Status einer Spielsituation möglichst genau einschätzen kann, wie hoch die Wahrscheinlichkeit für einen Sieg ist. Da das tatsächliche Ergebnis nicht bekannt ist, muss die Evaluierungsfunktion (Evaluation Function) eine Schätzung vornehmen. Diese Schätzung selbst darf wiederum nicht zu rechenintensiv sein, da ansonsten die Einhaltung des Zeitlimits gefährdet wäre.

Je komplexer die Heuristik der Evaluation Function ist, desto weniger Zeit bleibt für das Durchsuchen tieferer Äste des Entscheidungsbaums. Es handelt sich also immer um einen Kompromiss, und das Definieren und Testen einer guten Evaluation Function ist ein sehr wichtiger Teil bei der Entwicklung von Adversarial Search Agenten.

Ein Problem künstlicher Agenten besteht darin, dass sie anders als menschliche Agenten nicht über ihren definierten Horizont hinaus blicken können. So kann es z.B. sein, dass es in einer bestimmten Spielsituation für einen Menschen anhand bestimmter Muster sofort ersichtlich ist, dass ein bestimmter Zug das Spiel bereits entscheidet, auch wenn diese Entscheidung dann noch viele Züge entfernt ist. Der künstliche Agent evaluiert jedoch nur die aktuelle Situation bis zu einem bestimmten Punkt. Dieses Problem wird Horizon Effect genannt.

Dem Horizon Effekt kann begegnet werden, indem die dem menschlichen Agenten durch Erfahrung bekannten Muster in die Evaluierungsfunktion mit einbezogen werden. Dadurch kann diese allerdings wiederum schnell zu komplex werden, so dass die mögliche Such-Tiefe darunter leidet. Dies gilt es je nach Problemstellung abzuwägen.

Quiescent Search – Trendanalyse der Handlungsempfehlungen

Eine weitere Möglichkeit ist die Beobachtung der Handlungsempfehlungen und die Erkennung von Trends während der Steigerung der Such-Tiefe. Dabei wird am Ende jeder Such-Ebene das Ranking der initial zur Verfügung stehenden Handlungsmöglichkeiten anhand der Evaluierungsfunktion festgehalten. Wenn dabei eine oder mehrere Handlungsoptionen bei verschiedenen erreichten Such-Tiefen konsistent als die besten erweisen, so ist die Quiescence (Ruhe, Stille) erreicht und man kann davon ausgehen, dass es sich dabei tatsächlich um gute Optionen handelt.

Allerdings ist auch dieses Vorgehen relativ rechenintensiv und nicht in allen Situationen sinnvoll. Und sofern eine gute funktionierende Evaluation Function vorhanden ist, braucht es diese Strategie eventuell gar nicht. Aber insbesondere zu Beginn eines Spiels sowie kurz vor dem Ende kann Quiescent Search eine gute Strategie sein. Eine weitere Möglichkeit ist die flexible Anpassung der Such-Tiefe mit dem Iterative Deepening.

Such, solange du kannst: Iterative Deepening

Die Zahl der möglichen Handlungs-Optionen des künstlichen Agenten und seines Gegners ändert sich bei vielen Problemstellungen im Verlauf des Spiels. Oft sind kurz vor dem Ende einer Partie nur noch sehr wenige Optionen vorhanden, sodass diese auch in größerer Tiefe innerhalb des Zeitlimits komplett durchsucht werden könnten. Am Anfang stehen dagegen sehr viele verschiedene Optionen zur Verfügung und die Suchtiefe ist durch das Zeitlimit stark limitiert.

Eine weitere mögliche Such-Strategie besteht daher darin, nicht die Such-Tiefe zu limitieren, sondern bei jeder Suche jeweils so tief zu suchen, wie es zeitlich möglich ist. Die Suche läuft also immer weiter, bis ein zeitlicher Schwellenwert erreicht wird. Dieser Schwellenwert muss hoch genug dafür angesetzt sein, dass die Evaluierungsfunktion noch die Ergebnisse bewerten und die beste Handlungsempfehlung zurückgeben kann.

Den Entscheidungsbaum beschneiden mit Alpha-Beta-Pruning

Bisher war allen beschriebenen Such-Strategien gemeinsam, dass pro erreichter Suchtiefe jeweils alle Äste und Knotenpunkte (Nodes) komplett durchsucht wurden. Wenn die Such-Tiefe jedoch größer als 1 ist, ist es möglich, bestimmte Äste des Entscheidungsbaums schon nach kurzer Suche komplett auszuschließen, und so mehr Zeit für eine tiefere Suche in vielversprechenderen Bereichen zu gewinnen.

Der Trick besteht darin, die Ergebnisse der mit der Heuristik der Evaluierungsfunktion bereits bewerteten Äste mit der Minimax-Regel zurück nach oben zu propagieren und mit den Werten des aktuellen Astes zu vergleichen. Da der Such-Agent pro Ebene jeweils abwechselnd minimiert oder maximiert, können z.B. Äste in einer Minimierungs-Ebene, die in der darunter liegenden Maximierungs-Ebene schon ein Element mit einem Wert enthalten, der höher ist, als der niedrigste Wert der Minimierungs-Ebene von der weiteren Suche ausgeschlossen werden.

Alpha-Beta-Pruning

Ein Adversarial Search Agent für Isolation

Die beschriebenen Strategien für die Kombination von Such-Mechanismen und Evaluierungsfunktionen kann man z.B. einsetzen, um eine komplizierte Variante von Isolation zu spielen. Der hier gezeigte intelligente Agent verwendet Alpha-Beta-Pruning mit Iterative Deepening und schafft es auf einem 7×7 Spielfeld in einem Turnier mit Figuren, die sich nur wie Pferde im Schach bewegen dürfen, in 70-80% der Fälle, alle anderen künstlichen Agenten zu schlagen, die diese Strategien nicht oder nicht kombiniert einsetzen. Ein beispielhafter Spielverlauf ist unten dargestellt. Das Spiel-Ergebnis ist zwar kurz, aber um den kompletten Entscheidungsbaum durchzurechnen würde ein normaler aktueller Computer mehrere Hundertausend Jahre benötigen.

Adversarial Search Agent - Isolation


Grafik Alpha-Beta-Pruning: By Jez9999 CC BY-SA 3.0