Alpha Beta Cut/de

This article may require cleanup to meet the Qt Wiki's quality standards. Reason: Auto-imported from ExpressionEngine. Please improve this article if you can. Remove the {{cleanup}} tag and add this page to Updated pages list after it's clean.

Bei der Minimax-Suche tritt durch Alpha- bzw- Beta-Abschneidung ein Effekt ein, der als eine Erweiterung der Kurzschluss Auswertung Boolescher Ausdrücke aufgefasst werden kann:

Boolsche Ausdrücke

• a AND b -> wenn a falsch ist, beeinflusst der Wert von b das Gesamtergebnis nicht. Es ist falsch.
• a OR b -> wenn a wahr ist, beeinflusst der Wert von b das Gesamtergebnis nicht. Es ist wahr.

Alpha-Beta-Abschneidung

Um das Prinzip zu verstehen, genügt es, wenn wir uns Alpha-Abschneidungen näher ansehen:
(entsprechend der Wikipedia-Grafik des Artikels [de.wikipedia.org])

1. max( min( max(4, 12, 7), max(10, 5, 6), max(1, x, y)))

nicht alle Werte müssen evaluiert werden, wenn man hinreichende Indizien hat. Klar wird der Effekt, wenn man anstelle der Fragezeichen nicht Zahlen, sondern Ausdrücke einsetzt: Deren Evaluierung (und die damit verbrauchten Ressourcen) ist gar nicht nötig, weil die Entscheidung auch so schon feststeht. Dieser Effekt wurde in der Programmierung von Schach-Software erst recht spät entdeckt und änderte die Meinung über die prinzipielle Brauchbarkeit dieser durchgreifend: Vorher war alles Spaß und die Schachspieler hatten allen Grund die Programme auszulachen, plötzlich aber wurden sie das Fürchten gelehrt, denn durch die Reduktion des Rechenaufwandes konnten Suchtiefen plötzlich erreicht werden, die für die meisten menschlichen Schachspielern unerreichbar waren.

Weblinks

• http://de.wikipedia.org/wiki/Alpha-Beta-Suche
• http://en.wikipedia.org/wiki/Alpha-beta_pruning