Alpha Beta Cut/de: Difference between revisions
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''' -> 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:<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])
- 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.