Die Alpha-Beta-Suche (auch Alpha-Beta-Cut oder Alpha-Beta-Pruning genannt) ist eine optimierte Variante des Minimax-Suchverfahrens, 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. Die einfache (nicht optimierte) Alpha-Beta-Suche liefert exakt dasselbe Ergebnis wie die Minimax-Suche. Der Minimax-Algorithmus analysiert den vollständigen Suchbaum. Dabei werden aber auch Knoten betrachtet, die in das Ergebnis (die Wahl des Zweiges an der Wurzel) nicht einfließen. Die Alpha-Beta-Suche versucht, möglichst viele dieser Knoten zu ignorieren. Ein anschauliches Beispiel für die Funktionsweise ist ein Zweipersonenspiel, bei dem der erste Spieler eine von mehreren Taschen auswählt und von seinem Gegenspieler den Gegenstand mit dem geringstem Wert aus dieser Tasche erhält. – Zum Artikel …
from Die Artikel des Tages der Wikipedia http://ift.tt/2g7mhgl
0 comments:
Post a Comment