Diskussion:Alpha-Beta-Suche

Dieser Artikel war am 7. Dezember 2016 der Artikel des Tages.

Aus Wikipedia:Kandidaten für exzellente Artikel:

Alpha-Beta-Suche, 19. September

• Dafür: Sieht gut aus. -- Dishayloo [ +] 15:42, 19. Sep 2004 (CEST)
• neutral: Im Pseudocode war IMHO eine kleine Korrektur nötig, nämlich bei den Vergleichen if (wert >= schwelle) return ... Es ist hier besser, nicht schwelle, sondern wert zurückzugeben. Kommt vielleicht daher, dass im Russell-Norvig-Buch in der ersten Ausgabe die erste Codeversion verwendet wurde, das führt aber dann dazu, dass alle Knoten auf einer Ebene, unterhalb denen das Pruning zugeschlagen hat, denselben Wert haben.
• contra:
  • Noch einige Rechtschreibfehler.
  • Die Tabelle nennt eine Rechenzeit, sagt aber nicht, auf welchem System die Messungen durchgeführt wurden.
    • System wurde bewusst weggelassen, weil es für den Vergleich keine Rolle spielt und nur ablenkt --Sgop 16:31, 20. Sep 2004 (CEST)
  • Die Implementierung ist Pseudo-Pseudocode, also Pseudocode, der unnötig kompliziert nach einer echten Programmiersprache aussieht: Entweder Beispiele in einer richtigen Programmiersprache machen, oder richtigen Pseudocode verwenden (der kann dann auch Umlaute).
    • Bis auf vergessene Strichpunkte (schon korrigiert) ist das valides ANSI-C, oder? --Sgop 16:31, 20. Sep 2004 (CEST)
  • Alpha-Beta-Cut - dieser Name ist mir unbekannt (was nix heißen muss), ich stoße (z.B. im Standard-Lehrbuch von Russell und Norvig) auf die Bezeichnung "pruning".
    • Als Bezeichnung für den Algorithmus ist mir der Ausdruck auch unbekannt, das ist ein Relikt aus der Ur-Version des Artikels --Sgop 16:31, 20. Sep 2004 (CEST)
  • Keine Literatur. Keine geschichtlichen Anmerkungen, keine Informationen zu den an der Entwicklung beteiligten Personen.
  • Kein Hinweis auf die Möglichkeit der Optimierung mit Transpositionstafeln.
  • Soweit ich weiß, werden Varianten der Alpha-Beta-Suche (in Kombination mit Endspielbibliotheken) bei allen wichtigen Schachprogrammen verwendet - das sollte zumindest erwähnt werden.
  • Bei der Quiescent-Suche sollte das Horizontproblem erwähnt und vielleicht anhand eines Beispielts gezeigt werden - würde das Ganze wesentlich verständlicher machen.
  • --zeno 19:11, 19. Sep 2004 (CEST)
    • Manche diser Punkte wären gut auf der Seite Diskussion:Alpha-Beta-Suche aufgehoben --Sgop 16:31, 20. Sep 2004 (CEST)
      • Nach Abschluss der Abstimmung, sollte die Diskussion auf die Diskussionsseite des Artikels übertragen werden. Passiert also. -- Dishayloo [ +] 17:42, 23. Sep 2004 (CEST)
• neutral: dafür, weil selbst das erste Kapitel als kompletter Logik- und Mathematikversager verstanden habe, wodurch entgegen meiner Selbsteinschätzung mein Beta-Wert unterschritten wurde. Beim Knoten Alghoritmus allerdings musste ich die Suche nach Verstehen abbrechen. Schade, vielleicht wird's ja noch verständlicher. Wegen o.g. Unfähigkeit möchte ich aber auch nicht mit contra stimmen, insgesamt ne coole Geschichte. Brummfuss 19:37, 19. Sep 2004 (CEST)
• contra: Der Artikel verdient höchstens die Note gut. --Sgop 12:16, 24. Sep 2004 (CEST) (Autor des Artikels)

Zu den Bearbeitungen des Quellcodes

Bevor im in den Beispielimplementierungen noch 10mal zwischen "return wert" und "return alpha" bzw. "return beta" hin- und hergewechselt wird, wollte ich nur anmerken: Es macht für den Algorithmus und dessen Ergebnis absolut keinen Unterschied, ob es nun so oder so heisst.--Sgop 19:12, 14. Dez 2005 (CET)

Lesenswert-Diskussion

Die Alpha-Beta-Suche, auch Alpha-Beta-Cut genannt, ist eine optimierte Variante des Minimax-Suchverfahrens, also eines Algorithmus zur Bestimmung eines optimalen Zuges bei Spielen mit zwei gegnerischen Parteien. Während der Suche werden zwei Werte Alpha und Beta aktualisiert, die angeben, welches Ergebnis die Spieler bei optimaler Spielweise erzielen können. Mit Hilfe dieser Werte kann entschieden werden, welche Teile des Suchbaumes nicht untersucht werden müssen, weil sie das Ergebnis der Problemlösung nicht beeinflussen können.

•  Pro Antifaschist 666 21:01, 27. Feb 2006 (CET)
•  Pro Thornard, ^Diskussion, 00:11, 28. Feb 2006 (CET)
•  Pro Cottbus 05:30, 28. Feb 2006 (CET)
•  Pro Akkandi 09:51, 04. Mär 2006 (CET) Einfach hilfreich und interessant auch für nicht technisch- versierte Leser

Anglizismen

Der Artikel strotzt vor Anglizismen. Ich kann mir kaum vorstellen, dass man das nicht übersetzen kann. Hat jemand da Ahnung. Stern 23:21, 6. Mär 2006 (CET)

Hallo Stern, welche Anglizismen meinst du? Ich finde nur „Cutoff“, welches als Anglizismus verwendet wird. Alles andere sind ja quasi Lemmata (hier Fachwörter), dessen Übersetzung ich nicht für Sinnvoll halte, und desser Erklärung ja Aufgabe des Artikels ist. --Thornard, ^Diskussion, 23:30, 6. Mär 2006 (CET)

Die meinte ich. Ich habe die Erfahrung gemacht, dass man für beinahe alle derartige Begriffe eine deutsche Entsprechung findet, die man bei geringer Verbreitung zumindest in Klammern nennen kann. Stern 00:45, 7. Mär 2006 (CET)

Begriffswahl

Das Adjektiv "wertlos" kann IMHO nicht gesteigert werden.

Eine Frage

Müsste if(wert >= beta) return beta; nicht folgendermaßen aussehen: if(wert >= beta) return wert; ???

Falsch wäre es nicht, aber unnötig. Es geht ja darum das alpha/beta Fenster zu verkleinern. Einen Wert grösser als beta zurückzuliefern hat für die nächste Rekursion (=die nächste Baumtiefe) denselben Effekt, wie beta selbst. Zum Beweis: diesen Rückgabewert bekommt die Min-Funktion geliefert.... und was macht die Min-Funktion damit? Sie macht die beiden Tests if(wert<=alhpa) und if(wert<beta). Ob nun der Wert gleich beta, oder eben grösser als beta ist, macht bei diesen beiden Tests keinen Unterschied. --Sgop 20:36, 23. Jan. 2008 (CET)

Anstatt am Ende, falls kein Schnitt erfolgte, alpha (bzw. beta) zurückzuliefern, sollte man besser den Wert des besten gefundenen Zuges zurückliefern. Zurückliefern von alpha (bzw. beta) ist verwirrend, obwohl, glaube ich, im Grunde nicht falsch, führt aber zu seltsamen Effekten. Z.B. werden Züge gleich gut bewertet, wobei eigentlich der zuerst bewertete die richtige Bewertung bekommt und spätere auf dieses Bewertung künstlich "angehoben" werden. (siehe auch Russel/Norvig, 2. Auflage)

Es wird bereits der beste Zug geliefert: das liegt (zB in Funktion Max()) an dem Ausdruck "if (wert > alpha) alpha = wert;". Alpha wird also in der Schleife ständig an den besten Zug angepasst. Folglich wird am Ende der Funktion auch der Wert des besten Zuges zurückgeliefert und nicht der ursprüngliche alpha-Eingangswert. Oder habe ich dich falsch verstanden? --Sgop 09:57, 12. Okt. 2008 (CEST)

Angenommen, das Fenster ist (10,20). Es kann doch trotzdem sein, dass die Kindknoten nur Werte <10 zurückliefern. In diesem Fall sollte man das Maximum der Kindknoten (z.B. 7) zurückgeben, anstatt alpha (=10).

Warum? Ein Spieler, der maximiert bekommt so 10 zurück. Das ist doch vollkommen richtig: Immerhin wurde der Alpha-Wert durch einen Knoten vom Wert 10 gesetzt, was besagt, dass alle Knoten unter 10 irrelevant sind. Sind alle anderen Knoten < 10, ist der zuerst gefundene Knoten der beste. --KEBA 09:58, 24. Mai 2009 (CEST)

minimieren != mindestens

»Ähnlich verhält es sich beim minimierenden Knoten mit dem 3-Alpha-Cutoff. Obwohl dieser Teilbaum erst teilweise ausgewertet wurde, ist klar, dass der maximierende Wurzelknoten diese Variante niemals wählen würde, weil der minimierende Knoten mindestens das Ergebnis 3 erzwingen könnte, während aus dem mittleren Teilbaum das Ergebnis 12 sichergestellt ist.«

Ich würde behaupten, dass ein minimierender Knoten maximal ein bestimmtes Ergebnis erzielen könnte, daher würde ich mindestens mit höchstens ersetzen und den letzten Nebensatz streichen, dessen Sinn will sich mir nicht wirklich erschließen. --KEBA 10:14, 24. Mai 2009 (CEST)

Optimierungen von alpha-beta

Im Artikel steht: "Die einfache (nicht optimierte) Alpha-Beta-Suche liefert exakt dasselbe Ergebnis wie die Minimax-Suche."

Dieser Satz ist irreführend. Von den hier vorgeschlagenen Optimierungen liefern nur Null-Move und die Ruhesuche abweichende Ergebnisse. Diese beiden Erweiterungen sollten aber gar nicht als Optimierungen aufgeführt werden.

- Die Ruhesuche ist eine für viele Spiele notwendige bzw. sinnvolle Erweiterung mit radikal reduzierten Zuglisten sowohl von der Alpha-beta-Suche als auch der mimimax-Suche.

- Die Nullmove-Suche ermöglicht einen spekulativen Cut, der z.B. bei Schach oft hilfreich ist, der aber letztlich wie alle anderen spekulativen Cuts ("Ach jetzt habe ich schon soviel Material verloren, dies verfolge ich nun nicht tiefer!") zu behandeln ist, die hilfreich oder auch nicht sein können und mit der alpha-beta-Methode (den durch sie definierten Cuts) aber sicher nichts zu tun haben.

Ich würde auf beide Erweiterungen hinweisen, vielleicht zusammen mit Hinweisen auf Tablebases und Hashtabellen und ggf. weiteres. Ich würde sie aber sicher nicht als 'Optimierungen von alpha-beta' bezeichnen. Dann könnte der oben kritisierte Satz auch geändert werden auf:

"Die Alpha-Beta-Suche liefert, auch mit allen Optimierungen, exakt dasselbe Ergebnis wie die Minimax-Suche."

Benno, 7.9.2009 (nicht signierter Beitrag von 89.27.201.94 (Diskussion | Beiträge) 22:56, 7. Sep. 2009 (CEST))

Verbesserungsvorschlag

Hallo, ich finde den Artikel eigentlich sehr gut, aber ich habe einen kleinen Verbesserungsvorschlag: Man könnte noch zu diesem Pseudocode eine Hauptfunktion hinzufügen, in der dann beschrieben ist, wie man mit der Alpha-Beta-Suche dann tatsächlich den besten Zug findet, der jetzige Pseudocode beschreibt ja erst die Bewertung für die Züge. Bis jetzt muss man sich noch ziemlich etwas selbst überlegen, z.B. was man jetzt für Startwerte von Alpha und Beta nimmt und da kann man natürlich schnell versehentlich etwas verwechseln, wenn man sich nicht auskennt (und ich denke vor allem solche Leute, die sich nicht im Voraus schon gut mit Alpha-Beta-Suche auskennen, lesen diesen Artikel), also denke ich, dass es um der Vollständigkeit willen schon Sinn macht, das hinzuzufügen. Meinetwegen kann ich das auch versuchen, ich hab halt noch nie etwas geschrieben und bin auch nicht so der Pseudocode-Spezialist, drum wollte ich das mal zuerst hier vorschlagen, bevor ich wild auf eigene Faust drauflosschreibe. -- Lykos42 23:00, 14. Feb. 2010 (CET)

Hallo, ich habe auch einen Verbesserungsvorschlag. Man sollte in der Grafik die blaue 10 (zweite Zeile im Baum) schwarz färben, da bei den anderen blauen Zahlen und Pfeilen immer die eingefärbt wurden, die sich lokal durchgesetzt haben. -- TheSlater 15:04, 15.04.2015 (CET)

Implementierung schwer verständlich

Ich kann mich dem Vorredner Lykos42 nur anschließen. Ohne die Hauptfunktion ist das schwer zu verstehen. Im im Pseudo-Code von "Minimax-Algorithmus" (http://de.wikipedia.org/wiki/Minimax-Algorithmus#Pseudocode) steht ja eine Hauptfunktion. Insbesondere gibt Max ja an die Hauptfunktion auch nur

     return alpha;

zurück. Das ist aber ein Wert wie -33 und keine Zugnummer. Daher müsste man in die globale Liste der möglichen Züge jeweils den Wert einschreiben und die Hauptfunktion die Liste nochmal durchgehen, bis er alpha findet. Oder, eleganter, wie im Pseudo-Code von "Minimax-Algorithmus" (http://de.wikipedia.org/wiki/Minimax-Algorithmus#Pseudocode) die globale Var doNext noch in Max setzen. Also

  doNext := ZugNummer (WertVonWhileZuegeUebrigVariable)

Würde ein Aufruf in der Hauptfunktion funktionieren mit:

  Dummy := Max (3,-9999,9999)
  ZieheDenZug doNext

?

Also, lieber Lykos42, ich wäre dankbar für die Ergänzung der Hauptfunktion. Ich gehöre zu solchen Leuten, die sich nicht im Voraus schon gut mit Alpha-Beta-Suche auskennen. ;-) (Ich beziehe mich hiermit auf den Abschnitt: Implementierung.) (nicht signierter Beitrag von 79.223.64.19 (Diskussion) 12:27, 9. Okt. 2011 (CEST))

Fehler in der Implementierung

In der Implementierung gibt es zwei subtile Fehler mit großer Auswirkung:

In der Max-Funktion:

if (wert >= beta)

sollte sein:

if (wert > beta)

In der Min-Funktion:

if (wert <= alpha)

sollte sein:

if (wert < alpha)

Ansonsten wirkt sich eine höhere Suchtiefe nicht auf bessere Suchergebnisse aus. Möge es ein Admin editieren. Ich rühre keinen Artikel mehr an, wird sowieso alles rückgängig gemacht. (nicht signierter Beitrag von 82.113.106.36 (Diskussion) 23:15, 5. Apr. 2012 (CEST))

// 03. April 2013 //

nachdem ich grade in min() und max() herumgefuhrwerkt habe stelle ich fest, daß ein kommentar hilfreich wäre:

in min() und max() steht der spieler selbstverständlich fest und gehört nicht in die argumentenliste; insbesondere dann, wenn sinn u zweck der pseudoschnipsel das hervorheben von gemeinsamkeiten und unterschieden ist ... (nicht signierter Beitrag von 87.149.182.236 (Diskussion) 00:53, 3. Apr. 2013 (CEST))

Ergänzung?

Hallo,

ich persönlich habe relativ lange benötigt, um die Alpha-Beta-Suche zu verstehen. Daher habe ich ein Mini-Tutorial (pdf) geschrieben, was ich hier hochgeladen habe: http://www.sendspace.com/file/scdahp . Die Ausführung vom Tutorial ist sicherlich grottig.

Vielleicht hilft es aber trotzdem jemandem direkt oder inspiriert Leute, um das ganze noch besser zu erklären?!

-- Christian (nicht signierter Beitrag von Gebbissimo (Diskussion | Beiträge) 20:55, 12. Jun. 2012 (CEST))

Fehler im Pseudocode

Hallo zusammen,

meiner Meinung nach ist in dem Pseudocode noch ein Fehler enthalten:

int maxWert = alpha;

sollte heißen:

int maxWert = -unendlich;

und

int minWert = beta;

sollte heißen:

int minWert = +unendlich;

Ich habe den Fehler selbst entdeckt beim Schreiben eines Schachspiels für Lehrzwecke. Ohne die Änderung wird der Suchbaum viel zu stark beschnitten und es kommen unsinnige Züge zustande die ohne alpha-beta-pruning, also nur mit Minimax, nicht zustande kommen.

Zusätzlich wird in der aktuellen ct-Zeitschrift der Algorithmus vorgestellt mit der richtigen Initialisierung der Min/Max-Werte. (nicht signierter Beitrag von 46.115.125.4 (Diskussion) 16:02, 28. Apr. 2014 (CEST))

Du musst beachten, dass der Code mit alpha = -unendlich und beta = +unendlich initialisiert werden.

Dass alpha und beta im Laufe des Algorithmusses Züge beschneiden, ist ja Sinn und Zweck des Codes. Könntest du ein einfaches Beispiel bringen, in dem es zu falschen Ergebnissen führen würde? --Eulenspiegel1 (Diskussion) 22:58, 28. Apr. 2014 (CEST)

Bei der alpha-beta Suche gibt es keine einfachen Beispiele. Auch mit der Änderung wird der Suchbaum beschnitten. Zusätzlich besitze ich das Buch "Computers, Chess, and Cognition" in dem der Algorithmus auch anders als hier bei Wikipedia beschrieben wird. Ich habe jetzt zwei vertrauenswürdige Quellen genannt, das muß doch reichen. (nicht signierter Beitrag von 89.204.137.31 (Diskussion) 19:05, 1. Mai 2014 (CEST))

Könntest du eine vollständige Quellenangabe liefern? Das heißt beim Buch bitte auch Autor, ISBN und Seitenzahl. Bei der Zeitschrift die Ausgabe und Seitenzahl. --Eulenspiegel1 (Diskussion) 16:44, 2. Mai 2014 (CEST)

Zeitschrift: c't magazin für computertechnik Nr. 10 vom 22.04.2014, Ab Seite 176 Artikel "Denkmaschine - Brettspiel-KI selbst programmieren", Auf Seite 180 c#-Funktion mit Alpha-Beta-Suche. Buch: "Computers, Chess, and Cognition" von T. Antony Marsland und Jonathan Schaeffer, 1990 Springer Verlag, ISBN 0-387-97415-6. Ab Seite 133 Artikel "Tree Searching Algorithms" von H.Kaindl, auf Seite 138 Beschreibung des Algorithmus. (nicht signierter Beitrag von 89.204.139.64 (Diskussion) 10:58, 3. Mai 2014 (CEST))

In diesem Code darf maxWert nicht mit -unendlich initialisiert werden.

maxWert ist hier ein Ersatz für alpha und wird dementsprechend auch der Rekursion übergeben. Wenn er mit -unendlich initialisiert werden würde, dann ginge der alpha-Wert bei der Rekursion verloren. Das liefert zwar kein falsches Ergebnis, aber die Effizienz des Algorithmus leidet wohl stark darunter, weil das ein viel zu grosses alpha-beta Fenster übergeben wird.

Dass maxWert auch als Ergebnis zurückgeliefert wird (return maxWert), ist auch ok, weil es für die Vergleiche des Aufrufers keine Rolle spielt, ob der Wert gleich oder kleiner alpha ist (siehe: if minWert <= alpha).

Man könnte maxWert gleich -unendlich setzen, wenn man alpha statt maxWert in der Zugschleife verwendet. Das wird auch im Code der englisch-sprachigen Seite so gemacht und meines Wissens auch in echten Schachprogrammen. Das wäre m.M. nach verständlicher. --82.135.89.96 11:39, 10. Jan. 2015 (CET)