Alpha Beta Cut/de

This article is nominated for deletion. Reason: Not related to the Qt Project in any way (past or present). The content just references to wikipedia, emphasizes the importance of the alpha beta cut (with informal language) and explains the concept just a little bit. The page is not relevant to any other page in this wiki and, hence, it is not clear how it relates to the Qt content in this wiki. Please raise your support/opposition to this nomination in the article's discussion page.

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