Zitat:
Nein, wenn ich Brute-Force schreibe, meine ich nicht Minimax.
OK. Minimax ist halt ein definierter Algorithmus, bruteforce ist eine Klasse von Algorithmen, zu der eben auch Minimax gehört.
Im Schach ist aber Minimax der klassische bruteforce-Algorithmus.
Wenn du dies anders siehst, zeige die Differenz doch bitte an einem ganz konkreten Beispiel, einem konkreten kleinen Suchbaum.Ob der originäre alphabeta-Algorithmus auch ein bruteforce-Algorithmus ist, mag man diskutieren wollen, wenn man sich über die Eigenschaften dieses Algorithmus einig geworden ist.
Zitat:
Brute-Force durchsucht den Variantenbaum bis zu einer gewissen Tiefe vollständig. Eine Bewertungsfunktion für jede untersuchte Stellung dient dabei zur Entscheidungsfindung für den besten Zug.
Die Bewertungsfunktion bewertet die Blätter des Suchbaumes, die inneren Knoten werden aber durch den minimax-Mechanisus mit Werten versehen. Vermutlich meintest du das.
Minimax schlägt dir halt hat keine Schnitte vor. (nur zur Klarstellung, da sind wir uns wohl einig)
Zitat:
Alpha-Beta untersucht den Variantenbaum nicht vollständig, sondern schneidet - mathematisch korrekt - auf der Basis der Bewertungsfunktion Blätter oder Zweige des Suchbaums ab.
Auf der Basis der auf Blätter angewandten Bewertungsfunktion und der gemäß alphabeta nach innen übertragenen Knotenwerte. Ja
(was hier 'mathematisch korrekt' bedeutet, müsste aber ggf. noch genauer gesagt werden)
Aber
Zitat:
Alpha-Beta auf der Basis der von mir beschriebenen Bewertungsfunktion durchsucht den Variantenbaum auch vollständig, weil keine Schnitte auftreten können
stimmt sicher nicht.
Auch gemäß 'deiner' Bewertungsfunktion mit den Werten -1,0,+1 schneidet alphabeta ganz erheblich!Beispiel:Der vollständige Suchbaum sei folgender:
Code:
Zug_1 Antwort_1_1 w=0
Antwort_1_2 w=0
Antwort_1_3 w=0
Zug_2 Antwort_2_1 w=-1
Antwort_2_2 w=0
Antwort_2_3 w=1
Zug_3 Antwort_3_1 w=0
Antwort_3_2 w=0
Antwort_3_3 w=0
Das soll bedeuten: Der Anziehende hat 3 Züge zur Auswahl, jeder bietet dem Gegner 3 Antwortzüge mit den angegebenen Bewertungen.
Der Anziehende soll bei +1 gewinnen und -1 unbedingt zu verhindern versuchen, der Antwortende umgekehrt.
minimax ermittelt dann für die Gruppen der Antwortzüge die Minimalwerte und erkennt für
Zug_1 den Wert 0
Zug_2 den Wert -1
Zug_3 den Wert 0
und entscheidet sich für Zug_1 mit dem Wert 0 (könnte auch Zug_3 nehmen, der gleich gut ist.)
Dann wird alphabeta den Baum folgendermaßen abarbeiten:
Code:
Zug_1 Antwort_1_1 w=0
Antwort_1_2 w=0
Antwort_1_3 w=0 -> Zug_1 bekommt also den Wert 0
Zug_2 Antwort_2_1 w=-1 -> Cut, Zug_2 ist bereits als schlechter als Zug_1 erkannt und bekommt den Wert -1
Zug_3 Antwort_3_1 w=0 -> Cut, Zug_3 kann also nicht besser sein als Zug_1 und bekommt den Wert 0
Auch alphabeta entscheidet sich dann für Zug_1 mit dem Wert 0
Du siehst, es wurden zwei Zuglisten
ohne Informationsverlust abgeschnitten, es wurden 4 Antwortzüge nicht weiterverfolgt.
Und bei Bewertungen, die diverse Zwischenwerte liefern, sieht das genauso aus, wie man sich leicht überzeugen kann.
Hast du dir inzwischen meinen Denkanstoß angesehen und erkannt, dass hier ohne Betrachtung der weiteren Antwortzüge z2 verworfen werden kann, und dass dadurch sicher nichts Spekulatives hineingekommen ist? Das
ist ein alphabeta-Cut.
Und darum würde ich mir so wünschen, dass du dieses Beispiel mal durchdenkst.
Du bist ja lange im Computerschach aktiv.
Nein, ich will immer noch nicht recht glauben, dass du mir nicht zustimmen magst, sicher wie ich mich fühle.
Und ich hoffe immer noch, dass sich nur irgendwelche Missverständnisse in das Gespräch geschlichen haben.
Ich hatte mir halt nicht vorstellen können, und mag es mir auch jetzt nicht vorstellen, dass du nun so lange und sogar in der schachbezogenen Programmierung aktiv bist, ohne die Wirkung des alphabeta-Algorithmus verstanden zu haben.
Falls du tatsächlich der Meinung bist, dass bei einer anderen Bewertungsfunktion alphabeta ein anderes Ergebnis liefern kann als minimax (oder bruteforce, wie du es lieber nennst), dann gib doch bitte ein ganz konkretes Beispiel, einen Suchbaum mit Blattbewertungen, an dem man das durchspielen kann, nach minimax (bzw. bruteforce) und alphabeta.Ich denke, anhand eines solchen Beispiels würde man den Kern der Meinungsverscheidenheit oder das Missverständnis konkretisieren und die Lage dann auch klären können.
Benno
)
CSS-Shop