Alpha Beta Cut/de: Difference between revisions

From Qt Wiki
Jump to navigation Jump to search
No edit summary
 
No edit summary
Line 1: Line 1:
Bei der Minimax-Suche tritt durch Alpha- bzw- Beta-Abschneidung ein Effekt ein, der als eine Erweiterung der [http://qt.io/groups/qt_german/wiki/Kurzschluss-Auswertung Kurzschluss Auswertung] Boolescher Ausdrücke aufgefasst werden kann:


==Boolsche Ausdrücke==
* '''a <span class="caps">AND</span> b''' -&gt; wenn '''a falsch''' ist, beeinflusst der Wert von b das Gesamtergebnis nicht. Es ist '''falsch'''.
* '''a OR b''' -&gt; 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:<br /> (entsprechend der [http://de.wikipedia.org/wiki/Alpha-Beta-Suche Wikipedia-Grafik des Artikels] ''[de.wikipedia.org]'')<br />
<div class="cpp-qt geshi">
# <div class="de1">max<span class="br0">(</span> min<span class="br0">(</span> max<span class="br0">(</span><span class="nu0">4</span><span class="sy0">,</span> <span class="nu0">12</span><span class="sy0">,</span> <span class="nu0">7</span><span class="br0">)</span><span class="sy0">,</span> max<span class="br0">(</span><span class="nu0">10</span><span class="sy0">,</span> <span class="nu0">5</span><span class="sy0">,</span> <span class="nu0">6</span><span class="br0">)</span><span class="sy0">,</span> max<span class="br0">(</span><span class="nu0">1</span><span class="sy0">,</span> x<span class="sy0">,</span> y<span class="br0">)</span><span class="br0">)</span><span class="br0">)</span></div>
</div>
<br /> 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

Revision as of 13:56, 25 February 2015

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