Beschneidung des Alpha-Betas ist ein Suchalgorithmus, der sich bemüht, die Anzahl gegen Knoten zu reduzieren, die durch den minimax Algorithmus in seinem Suchbaum bewertet werden. Es ist ein Adversarial-Suchalgorithmus verwendet allgemein für das Maschinenspielen von Zwei-Spieler-Spielen (Tic-tac-toe, Schach, Gehen Sie usw.). Es hört völlig auf, eine Bewegung zu bewerten, als mindestens eine Möglichkeit gefunden worden ist, dass das die Bewegung beweist, um schlechter zu sein, als eine vorher untersuchte Bewegung. Solche Bewegungen brauchen weiter nicht bewertet zu werden. Wenn angewandt, auf einen Standard minimax Baum gibt es dieselbe Bewegung zurück, wie minimax würde, aber weg Zweige beschneiden, die die Endentscheidung nicht vielleicht beeinflussen können.

Geschichte

Allen Newell und Herbert Simon, der verwendet hat, was John McCarthy eine "Annäherung" 1958 nennt, haben geschrieben, dass Alpha-Beta "scheint, verschiedene Male wiedererfunden worden zu sein". Arthur Samuel hatte eine frühe Version und Richards, Hirsch, Levine und/oder Edwards gefundenes Alpha-Beta unabhängig in den Vereinigten Staaten. McCarthy hat ähnliche Ideen während der Dartmouth Konferenz 1956 vorgeschlagen und hat es zu einer Gruppe seiner Studenten einschließlich Alan Kotoks an MIT 1961 vorgeschlagen. Alexander Brudno hat unabhängig den Algorithmus des Alpha-Betas entdeckt, seine Ergebnisse 1963 veröffentlichend. Donald Knuth und Ronald W. Moore haben den Algorithmus 1975 raffiniert, und Judea Pearl hat seinen optimality 1982 bewiesen.

Verbesserungen über naiven minimax

Der Vorteil der Beschneidung des Alpha-Betas liegt in der Tatsache, dass Zweige des Suchbaums beseitigt werden können. Auf diese Weise kann die Suchzeit auf den 'viel versprechenderen' Subbaum beschränkt werden, und eine tiefere Suche kann in derselben Zeit durchgeführt werden. Wie sein Vorgänger gehört es dem Zweig und der gebundenen Klasse von Algorithmen. Die Optimierung reduziert die wirksame Tiefe auf ein bisschen mehr als halb mehr als das von einfachem minimax, wenn die Knoten in einer optimalen oder nahen optimalen Ordnung (beste Wahl für die Seite auf der Bewegung bestellt zuerst an jedem Knoten) bewertet werden.

Mit (durchschnittlich oder unveränderlich) sich verzweigender Faktor von b und eine Suchtiefe von d Falten ist die maximale Zahl von Blatt-Knotenpositionen bewertet (wenn die Bewegung, die bestellt, ist) O (b*b*...*b) = O (b) - dasselbe als eine einfache Minimax-Suche. Wenn die Bewegung, die für die Suche bestellt, optimal ist (das Meinen, dass die besten Bewegungen immer zuerst gesucht werden), ist die Zahl von bewerteten Blatt-Knotenpositionen über O (b*1*b*1*...*b) für die sonderbare Tiefe und O (b*1*b*1*...*1) für sogar die Tiefe, oder. Im letzten Fall, wo die Falte einer Suche sogar ist, wird der wirksame sich verzweigende Faktor auf seine Quadratwurzel, oder gleichwertig reduziert, die Suche kann zweimal so tief mit demselben Betrag der Berechnung gehen. Die Erklärung von b*1*b*1* besteht... darin, dass Bewegungen ganzen ersten Spielers studiert werden müssen, um die beste zu finden, aber für jeden ist nur die Bewegung des besten zweiten Spielers erforderlich, um alle außer dem ersten (und am besten) die erste Spieler-Bewegung zu widerlegen - stellt Alpha-Beta sicher, dass die keine anderen zweiten Spieler-Bewegungen betrachtet werden müssen. Wenn Knoten aufs Geratewohl, bestellt werden

die durchschnittliche Zahl von bewerteten Knoten ist grob

.

Normalerweise während des Alpha-Betas werden die Subbäume von irgendeinem ein erster Spieler-Vorteil provisorisch beherrscht (wenn sich vieler erster Spieler bewegt, sind gut, und an jeder Suchtiefe hat die erste Bewegung vom ersten Spieler überprüft ist entsprechend, aber alle zweiten Spieler-Antworten sind erforderlich zu versuchen, eine Widerlegung zu finden), oder umgekehrt. Dieser Vorteil kann Seiten oft während der Suche schalten, wenn die Bewegung, die bestellt, falsch ist, jedes Mal zu Wirkungslosigkeit führend. Da die Zahl von Positionen Abnahmen exponential jede Bewegung näher die aktuelle Position gesucht hat, lohnt es sich, beträchtliche Anstrengung für das Sortieren früher Bewegungen auszugeben. Eine verbesserte Sorte an jeder Tiefe wird die Gesamtzahl von gesuchten Positionen exponential reduzieren, aber alle Positionen an Tiefen in der Nähe vom Wurzelknoten sortierend, ist relativ preiswert, weil es so wenige von ihnen gibt. In der Praxis wird die Bewegung, die bestellt, häufig durch die Ergebnisse von früheren, kleineren Suchen, solcher als durch das wiederholende Vertiefen bestimmt.

Der Algorithmus erhält zwei Werte, Alpha und Beta aufrecht, die die maximale Kerbe vertreten, dass der Maximierungsspieler und die minimale Kerbe versichert wird, deren der Minderungsspieler beziehungsweise versichert wird. Am Anfang ist Alpha negative Unendlichkeit, und Beta ist positive Unendlichkeit. Als die Recursion-Fortschritte wird das "Fenster" kleiner. Wenn Beta weniger wird als Alpha, bedeutet es, dass die aktuelle Position das Ergebnis des besten Spieles durch beide Spieler nicht sein kann und folglich weiter nicht erforscht zu werden braucht.

Zusätzlich kann dieser Algorithmus trivial modifiziert werden, um eine komplette Hauptschwankung zusätzlich zur Kerbe zurückzugeben. Einige aggressivere Algorithmen wie MTD (f) erlauben solch eine Modifizierung nicht leicht.

Pseudocode

fungieren Sie alphabeta (Knoten, Tiefe, α, β, Spieler)

wenn Tiefe = 0 oder Knoten ein Endknoten ist

geben Sie den heuristischen Wert des Knotens zurück

wenn Spieler = MaxPlayer

für jedes Kind des Knotens

α: = max (α, alphabeta (Kind, Tiefe 1, α, β, nicht (Spieler)))

wenn β  α\

Brechung (* Beta-Abkürzung *)

geben Sie α\zurück

sonst

für jedes Kind des Knotens

β: = Minute (β, alphabeta (Kind, Tiefe 1, α, β, nicht (Spieler)))

wenn β  α\

Brechung (* Abkürzung von Alpha *)

geben Sie β zurück

(* Initiale rufen *)

alphabeta (Ursprung, Tiefe, - Unendlichkeit, +infinity, MaxPlayer)

Heuristische Verbesserungen

Weitere Verbesserung kann erreicht werden, ohne Genauigkeit, durch das Verwenden des Befehlens die Heuristik zu opfern, Teile des Baums zu suchen, die wahrscheinlich Abkürzungen des Alpha-Betas früh zwingen werden. Zum Beispiel, im Schach, können Bewegungen, die Stücke nehmen, untersucht werden vor Bewegungen, die nicht, oder Bewegungen tun, die hoch in früher gezählt haben, geht durch die Spielbaum-Analyse kann vor anderen bewertet werden. Ein anderer üblich, und sehr preiswert, heuristisch ist der heuristische Mörder, wo die letzte Bewegung, die eine Beta-Abkürzung an demselben Niveau in der Baumsuche verursacht hat, immer zuerst untersucht wird. Diese Idee kann in eine Reihe von Widerlegungstischen verallgemeinert werden.

Suche des Alpha-Betas kann noch schneller durch das Betrachten nur eines schmalen Suchfensters (allgemein als bestimmt durch die Spekulation gestützt auf der Erfahrung) gemacht werden. Das ist als Ehrgeiz-Suche bekannt. Im äußersten Fall wird die Suche mit dem Alpha und gleichen Beta durchgeführt; eine Technik, die als Nullfenster-Suche, Suche des ungültigen Fensters oder Pfadfinder-Suche bekannt ist. Das ist für Suchen des Gewinns/Verlustes in der Nähe vom Ende eines Spiels besonders nützlich, wo die Extratiefe, die vom schmalen Fenster und einer einfachen Einschätzungsfunktion des Gewinns/Verlustes gewonnen ist, zu einem abschließenden Ergebnis führen kann. Wenn eine Ehrgeiz-Suche scheitert, ist es aufrichtig, um zu entdecken, ob es hoch gescheitert hat (der hohe Rand des Fensters war zu niedrig), oder niedrig (war der niedrigere Rand des Fensters zu hoch). Das gibt Information darüber, welche Fensterwerte in einer Forschung der Position nützlich sein könnten.

Andere Algorithmen

Fortgeschrittenere Algorithmen, die noch schneller sind, während sie noch im Stande sind, den genauen Minimax-Wert zu schätzen, sind wie PFADFINDER, Negascout und MTD-f bekannt.

Da der minimax Algorithmus und seine Varianten von Natur aus Tiefe zuerst sind, wird eine Strategie wie das wiederholende Vertiefen gewöhnlich in Verbindung mit dem Alpha-Beta verwendet, so dass eine vernünftig gute Bewegung zurückgegeben werden kann, selbst wenn der Algorithmus unterbrochen wird, bevor es Ausführung beendet hat. Ein anderer Vorteil, das wiederholende Vertiefen zu verwenden, besteht darin, dass Suchen an seichteren Tiefen Bewegung bestellende Hinweise geben, die helfen können, Abkürzungen für höhere Tiefe-Suchen viel früher zu erzeugen, als sonst möglich sein würde.

Algorithmen wie SSS * verwenden andererseits die beste erste Strategie. Das kann sie zeiteffizienter, aber normalerweise an schweren Kosten in der Raumleistungsfähigkeit potenziell machen.

Siehe auch

• Beschneidung (des Algorithmus)
• Zweig und gebundener
• Minimax
• Kombinatorische Optimierung
• Negamax
• Umstellungstisch
• Judea Pearl, Heuristik, Addison-Wesley, 1984

Außenverbindungen

http://www.emunix.emich.edu/~evett/AI/AlphaBeta_movie/sld001.htm http://sern.ucalgary.ca/courses/CPSC/533/W99/presentations/L1_5B_McCullough_Melnyk/ http://sern.ucalgary.ca/courses/CPSC/533/W99/presentations/L2_5B_Lima_Neitz/search.html http://www.maths.nott.ac.uk/personal/anw/G13GAM/alphabet.html

• http://chess.verhelst.org/search.html

http://www.frayn.net/beowulf/index.html http://hal.inria.fr/docs/00/12/15/16/PDF/RR-6062.pdf

• Minimax (mit oder ohne Beschneidung des Alpha-Betas) Algorithmus-Vergegenwärtigung - das Spielbaumlösen (Java Applet), für das Gleichgewicht oder die aus dem Gleichgewicht Bäume
• Die Demonstration/Zeichentrickfilm des minimax Spiels sucht Algorithmus mit der Beschneidung des Alpha-Betas (html5, Leinwand, javascript, css verwendend)

,