Gegnersuche und Spieltheorie

Die Gegnersuche ist die Untersuchung von Entscheidungsfindungen in kompetitiven Umgebungen, bei denen ein Akteur in einem Spielbaum Züge gegen einen Gegner wählen muss, der versucht, das entgegengesetzte Ergebnis zu erzielen.

Definition

Die Gegnersuche berechnet einen Zug für einen Spieler, indem sie einen Spielbaum erkundet, in dem die Spieler abwechselnd Züge ausführen, wobei das Minimax-Prinzip (jeder Spieler optimiert unter der Annahme, dass der Gegner optimal spielt) zusammen mit Pruning und heuristischer Bewertung verwendet wird, um mit großen Bäumen umzugehen.

Scope

Dieses Thema behandelt die Suche in Zwei-Spieler-, Nullsummen-, Vollinformationsspielen: die Minimax-Entscheidungsregel, die Alpha-Beta-Pruning, die es Minimax ermöglicht, nachweislich irrelevante Zweige zu überspringen, Bewertungsfunktionen und tiefenbegrenzte Suche für Spiele, die zu groß sind, um exakt gelöst zu werden, und Monte-Carlo-Baumsuche für Spiele mit sehr großen Verzweigungsfaktoren. Es wird behandelt, wie Spielbäume modelliert werden und wie rechnerische Grenzen heuristische Abschneidungen erzwingen. Es behandelt nicht die allgemeine spieltheoretische Gleichgewichtsanalyse von Multi-Agenten-Anreizen, die unter Multi-Agenten-Systemen behandelt wird.

Core questions

• Wie bestimmt die Minimax-Regel einen optimalen Zug gegen einen optimalen Gegner?
• Wie eliminiert die Alpha-Beta-Pruning Zweige, ohne den Minimax-Wert zu beeinflussen?
• Wie werden Bewertungsfunktionen verwendet, um die Suche in großen Spielen bei einer festen Tiefe abzuschneiden?
• Wann ist die Monte-Carlo-Baumsuche der tiefenbegrenzten Minimax-Suche vorzuziehen?

Key concepts

• Spielbaum
• Minimax-Wert
• Alpha-Beta-Pruning
• Bewertungsfunktion (heuristisch)
• tiefenbegrenzte Suche und der Horizont-Effekt
• Nullsummen-Vollinformationsspiele
• Monte-Carlo-Baumsuche
• Zugreihenfolge

Key theories

Minimax-Entscheidungsregel

In einem Zwei-Spieler-Nullsummenspiel wählt jeder Spieler den Zug, der sein eigenes minimal garantiertes Ergebnis maximiert; die Weitergabe dieser Max-/Min-Werte im Spielbaum ergibt den optimalen Zug an der Wurzel.

Alpha-Beta-Pruning

Durch die Verfolgung der besten Werte, die den maximierenden und minimierenden Spielern bereits garantiert sind, beweist die Alpha-Beta-Suche, dass bestimmte Teilbäume die endgültige Entscheidung nicht beeinflussen können, und überspringt diese, wobei der exakte Minimax-Wert zurückgegeben wird, während im besten Fall die erreichbare Tiefe in einer bestimmten Zeit ungefähr verdoppelt wird.

Monte-Carlo-Baumsuche

Wenn die Verzweigungsfaktoren für eine erschöpfende Vorausschau zu groß sind, erstellt die Monte-Carlo-Baumsuche einen asymmetrischen Baum, der durch randomisierte Rollouts und eine Auswahlregel, die Exploration und Exploitation ausbalanciert, geleitet wird, eine Methode, die das Computerspiel in Spielen wie Go transformiert hat.

Clinical relevance

Die Gegnersuche hat wegweisende KI-Systeme hervorgebracht, von Schach-Engines, die Alpha-Beta-Suche verwenden, bis hin zu Go-Programmen, die auf Monte-Carlo-Baumsuche basieren, und dieselben Techniken beeinflussen die automatisierte Verhandlung, Sicherheitsspiele und jede Umgebung, die als Wettbewerb zwischen optimierenden Parteien modelliert wird.

History

Shannons Arbeit von 1950 formulierte Computerschach als Minimax-Suche mit einer Bewertungsfunktion, und von Neumanns Minimax-Theorem lieferte die spieltheoretische Grundlage. Die Alpha-Beta-Pruning wurde in den 1950er-60er Jahren entwickelt und von Knuth und Moore (1975) rigoros analysiert. Die Monte-Carlo-Baumsuche, die in den 2000er Jahren formalisiert wurde, führte zum nächsten Sprung in der Spielstärke, insbesondere im Go.

Key figures

• Claude E. Shannon
• John von Neumann
• Arthur Samuel
• Donald E. Knuth
• Ronald W. Moore

Seminal works

• shannon1950
• knuth1975
• browne2012

Frequently asked questions

Ändert die Alpha-Beta-Pruning den Zug, den Minimax wählen würde?

Nein. Die Alpha-Beta-Pruning liefert genau den gleichen Wert und Zug wie die vollständige Minimax-Suche; sie vermeidet lediglich die Erkundung von Zweigen, die nachweislich das Ergebnis nicht beeinflussen können. Ihr Vorteil ist die Geschwindigkeit, und bei guter Zugreihenfolge kann sie in der gleichen Zeit ungefähr doppelt so tief suchen.

Warum sollte man in Spielen wie Go die Monte-Carlo-Baumsuche anstelle von Minimax verwenden?

Go hat einen enormen Verzweigungsfaktor und es fehlt eine einfache, genaue Bewertungsfunktion, so dass die tiefenbegrenzte Minimax-Suche ineffektiv ist. Die Monte-Carlo-Baumsuche schätzt stattdessen die Zugqualität durch viele randomisierte Spielzüge und lässt den Baum selektiv in vielversprechende Richtungen wachsen, was in solchen Spielen wesentlich besser skaliert.