Verstehen Minimax mit Alpha-Beta-Beschneidung

Question

Sorry für das Bild, es ist direkt aus meinen Notizen.

Ich habe gelesen, über Minimax-Bäume und Daten Alpha für den letzten Tag Beschneiden und ein wenig in der Vorbereitung für mein Projekt. Was ist eine Implementierung für Othello in c.

Ich habe eine Menge Ressourcen darüber gelesen, und ich weiß, dass es viel gefragt wird. Bevor ich meine Bewertungsfunktionen starte, möchte ich dies vollständig verstehen.

In dem angehängten Bild kann ich nicht herausfinden, was die Funktion Min_Node(pos) und Max_Node(pos) genau tun würde, würde jede Eingabe sehr geschätzt werden.

Wenn jemand irgendwelche Tipps oder Dinge hat, auf die ich achten sollte, wenn ich diese und meine Bewertungsfunktion für Othello implementiere, bin ich bereit, jede Hilfe zu nehmen, die ich finden kann.

Answer 1

Ich gelang es herauszufinden, was max und min Knoten war, in diesem Fall Max_Node(pos) überprüft, ob dies der Spieler ist, und es gibt wahr, weil dies maximiert werden sollte und Min_Node(pos) prüft, ob es der Gegner ist, wenn wahr, dann sollte es minimiert werden.

Answer 2

Der Minimax-Algorithmus, der auch here beschrieben wird, muss Bewegungen des optimalen Werts finden, die die aktuelle Position im Spielbaum betreffen. Die Position besteht aus der Board-Konfiguration und dem aktuellen Spieler (bei einigen Spielen kann nur über die Board-Konfiguration entschieden werden). Normalerweise wird der Wert der Züge rekursiv definiert; Für ein Board in der Eding-Position (welches ein Blatt des Spielbaums ist) lautet der Wert 1, wenn Spieler Eins gewonnen hat, -1, wenn Spieler Zwei gewonnen hat und 0 für ein Ziehungsspiel. Der Wert einer Bewegung wird bestimmt, indem diese Verschiebung ausgeführt und der Wert rekursiv ausgewertet wird. Dann wird ein Zug mit Maximum (für Spieler eins) oder Minimum (für Spieler zwei) gewählt; Bei der rekursiven Auswertung ist der Wert der maximale (oder minimale) Wert aller Blätter des Wurzelverzeichnisses an der aktuellen Position. Dies sind offenbar die in der ursprünglichen Frage genannten Funktionen.

Alpha-Beta-Beschneidung, wie beschrieben here, ist eine Verfeinerung dieses Ansatzes. Da die optimalen Werte bekannt sind (sie sind 1 oder -1), kann die Auswertung gestoppt werden, sobald eine Bewegung mit dem gewünschten Wert gefunden wird.

Dieser Ansatz ist unabhängig vom eigentlichen Spiel. Ich schlage jedoch einen ersten Schritt vor, in dem ein einfacheres Spiel (z. B. Tic-Tac-Toe) als Spielzeugbeispiel verwendet wird, das leichter zu debuggen ist.