Alpha-Beta Pruning Sonderfall?

Ich versuche den Alpha-Beta-Schnittalgorithmus zu verstehen, aber es gibt einen speziellen Fall, den ich nicht verstehe.Alpha-Beta Pruning Sonderfall?

Gegeben this tree, this soll die Lösung sein. Was ich nicht verstehe, ist, warum die rot markierten Knoten den Wert 19 haben sollen. Anscheinend ist das ein "Spezialfall" und der Wert im unteren roten Knoten ist 19, weil 3 (0) 3 ist der aktuelle Wert für Alpha). Was dann dazu führt, dass der obige Knoten ebenfalls den Wert 19 hat.

Das ergibt für mich keinen Sinn, denn das würde darauf hindeuten, dass es im rechten Teilbaum ein Blatt mit dem Wert 19 gab. Ist das einfach falsch und beide Knoten sollten den Wert 10 haben?

Quelle

2017-08-19 user8488823

Ich habe versucht, die Bilder direkt einfügen, aber anscheinend brauche ich mindestens 10 Ruf? Da dieser Fall ein Tippfehler zu sein scheint, gibt es eine andere Sache, über die ich mir nicht ganz sicher bin. Ich habe gefunden [dieses Tool] (http://proof.github.io/minimax/#tree=KCgoMTcsMiwxMCKsKDEsMTksNykpLCgoMTcsMTksMTApLCgyMCw4LDExKSksKCgxMCw5LDMpLCgyNCw0LDE0KSkp), die die richtige Lösung zu geben scheint, aber ich verstehe nicht, warum der Beta-Wert im rechten Teilbaum ist 19, sollte es nicht 10 sein? – user8488823

Ob dieser Knoten den Wert 19 (der Wert von Alpha) oder 10 (der größte Wert unter den Kindern) erhält, hängt von Varianten ab, die in verschiedenen Alpha-Beta-Algorithmen existieren. Wenn der maximierte Wert kleiner als Alpha ist, weisen einige Algorithmen den Wert von Alpha zu, während andere diesen kleineren Wert zuweisen (der somit außerhalb des Alpha-Beta-Fensters liegt). Ähnliches passiert mit der Beta.

Welche Methode auch immer verwendet wird, beeinflusst nicht die Wahl der besten Bewegung. Das Alpha-Beta-Fenster zeigt an, dass jeder Wert, der unterhalb von diesem außerhalb des Alpha-Beta-Fensters aufsteigt, nicht von Bedeutung sein kann. Es ist bereits eine bessere Variante bekannt.

In diesem Fall läuft die beste Variante über den mittleren Kindknoten des Stammes. Der maximierende Spieler kann sicher sein, dass mindestens 19 erreicht werden können. Wenn man der dritten Option entweder 10 oder 19 zuweist, kommt man zu der gleichen Schlussfolgerung: Es ist kein besserer Zug als wir bereits haben.

Quelle

2017-08-19 21:43:15 trincot

Das macht Sinn, danke. Es erscheint mir jedoch etwas kontraintuitiv, da, wenn 19 dem Knoten zugewiesen wird, der Baum selbst keinen Sinn mehr macht, da dieser Knoten kein Kind hat, das den Wert 19 enthält. Ich nehme an, das bedeutet auch, dass Wenn ein Minimierungsknoten einen Beta-Wert von 10 und Kinder die Werte 15 und 20 haben, wird der Beta-Wert von 10 dem Knoten selbst zugewiesen, da es der kleinste verfügbare Wert zwischen dem Beta-Wert und den Werten seiner Kinder ist? – user8488823

In der Tat, das wäre der Fall für Beta. – trincot

Alpha-Beta Pruning Sonderfall?

Antwort

Verwandte Themen