Wie wird das Alpha Beta Pruning Algorithmus angezeigt?
Aktualisierungen
Update 1
Ich habe versucht dies (2. Zeile): Ich habe die Farbe der Knoten als erste Anweisung in der alphabetischen Funktion hinzugefügt. Ich bekomme dieses Ergebnis :
Grüne Knoten sind besuchte Knoten. Es sieht so aus, dass der Algorithmus die Knoten richtig wirft, oder? Aber wie gebe ich korrekte Werte in Knoten aus - muss ich das auch tun? Minimum der Kinderwerte, Maximum der Kinderwerte (ausgenommen abgeschnittene Äste).
Update 2
Ich habe versucht, Alpha und Beta an die Baumknoten auszugeben und habe kein korrektes Ergebnis erhalten. Dies ist Code (Zeilen 18 und 31 wurden hinzugefügt). Dies ist das Ergebnis des Codes:
Auf diesem Bild zeige ich seltsame Orte:
Erster Pfeil: warum Minimum von 7 und 6 ist 5? Zweiter Pfeil: warum maximal 4, 3 und 2 ist 5? Seltsam. Deshalb denke ich, dass es jetzt richtig funktioniert.
Alte Frage
Es war einmal eine ähnliche Frage, die ich hier gestellt habe. Es war wie: "Warum bekomme ich diesen Fehler?". Lets rollback und erstellt neue. Diese Frage wird lauten: "Wie wird das Beta-Pruning-Algorithmus-Ergebnis angezeigt?"
Ich habe Pseudocode dieses Algorithmus im Wiki gefunden. Es kann hier gefunden werden.
Meine Realisierung ist unten (es ist auf JavaScript, aber ich denke nicht, dass, um diese Frage zu beantworten, Sie JS oder Java oder C ++ usw. kennen müssen). Die Frage ist, wie man das Ergebnis dieses Algorithmus auf das Diagramm (Baumstruktur) ausgibt. Beim Start habe ich diese Baumstruktur:
HINWEIS: Ich habe eine Baumstruktur (eine Menge verknüpfte node s), auf der ich den Alpha-Beta-Bereinigungsalgorithmus verwenden werde, und ich habe eine andere Baumstruktur (um Ergebnisse anzuzeigen, lasst uns anrufen es "Graph"). Die Knoten des Baumes, die ich zum Anzeigen des Graphen verwende, sind mit Knoten verbunden, die ich benutze, um das Ergebnis des Algorithmus zu finden.
Also, Code des Alpha-Beta-Schnittalgorithmus ist unten. Können Sie bitte klarstellen, was und wo ich ausgeben muss, um Prozess / Ergebnisse des Algorithmus korrekt anzuzeigen?
Meine Annahme ist Alpha und Beta auszugeben, aber ich denke, es ist falsch. Ich habe es versucht, aber es funktioniert nicht.
Ich möchte Schnitte anzeigen und alle Knoten im Baum mit korrekten Werten füllen.
Das ist meine Erkenntnis von Minimax mit Alpha-Beta-Beschneidung:
%Vor%1 Antwort
Warum speichern Sie nicht einfach die tatsächlich besuchten Knoten und färben Sie diese Knoten rot. Dann sehen Sie, welche Knoten im Vergleich zum gesamten Baum ausgewertet wurden. ZB
Nach einer langen Diskussion in den Kommentaren denke ich, dass ich dies jetzt beleuchten kann. Wenn das Alpha-Beta um den Baum herumläuft, hat es drei Werte. Wenn es auf einem bestimmten Knoten arbeitet, hat es die Alpha- und Beta-Werte, die von seinem Elternknoten dorthin geleitet wurden, und dann hat es den besten bisher gefundenen Wert . Wenn es einen Wert außerhalb des Alpha-Beta-Fensters findet, wird es sofort gelöscht, da es weiß, dass dieser Knoten unabhängig von seinem Wert keine optimale Bewegung ist. Für einige Knoten berechnet Alpha Beta also niemals den "wahren Wert" des Knotens.
Wenn Sie also gebeten werden, das "Ergebnis" von Alpha Beta anzuzeigen, dachte ich fälschlicherweise, dass Sie das Alpha-Beta-Fenster meinten, da der "wahre Wert" niemals unbedingt bewertet wird.
Sie müssten separaten Code schreiben, um die "wahren Knotenwerte" auszudrucken. Ich denke, dass der Minimax-Algorithmus das für Sie tun wird.
Beachten Sie auch beim manuellen Vergleichen, dass bei Verwendung eines "Satzes" von Knoten der Listeniterator nicht garantiert, dass die Knoten in einer vorhersagbaren Reihenfolge zurückgegeben werden. Wenn Sie also innerhalb der Knoten Sätze und keine Listen verwenden Vielleicht finden Sie, dass es schwierig ist, mit der Hand zu folgen. Listen-Iteratoren geben die Anzeigenreihenfolge zurück. Setze Iteratoren haben keinen vorhersagbaren Iterator.
Tags und Links algorithm search artificial-intelligence minimax alpha-beta-pruning