Übung 3 Aufgabe 3c Minimal Window Erweiterung

[sunshine127]

Hallo,

ich habe eine Frage zu der Lösung der Aufgabe.

Zunächst ruft man NegaScout mit [-infinity,+infinity] an jeder Kante des linken Zweiges des Baumes auf, bis man zum Wert -2 kommt. Aus Sicht von MAX ist 2 > -infinity, d.h. der Wert links unten wird überschrieben. Damit muss MAX >= 2 sein, also setzt man alpha = 2 und beta = alpha + 1 = 3 und ruft NegaScout auf den rechten Teilbaum mit [2,3] auf. Da 5 nicht in diesem Intervall liegt und 5 > 3 = beta gilt, muss der Unterbaum erneut durchsucht werden, dieses mal mit dem Intervall [5,+infinity]. Da der Wert nun genau 5 ist, muss MAX >= 5 sein und man setzt alpha = 5.

Müsste dann nicht aber beta = alpha + 1 = 6 gelten und der Algo dann mit dem Intervall [5,6] aufgerufen werden statt mit [4,5], so wie es in der Lösung steht? Man weiß ja bereits, dass MAX >= 5 sein muss, also macht es meiner Meinung nach keinen Sinn, wieder Werte kleiner als 5 zu betrachten.

Habe ich hier etwas falsch verstanden oder ist die Lösung nicht korrekt?

Viele Grüße

[Tobias Joppen]

Du befindest dich in dem linken Kindknoten der Wurzel, richtig?
Hier bekommst du (Min Spieler) vom Max Spieler eine 5 zurück.
Einfach gesprochen interessiert es den Min Spieler, ob es Werte kleiner 5 gibt, oder nicht.
Größer ist egal (weil sonst der 5er Arm gespielt werden würde), aber kleiner als 5 ist interessant. Daher ist [4,5] zumindest intuitiv deutlich richtiger als [5,6].

Die Formel beta=alpha+1 ist korrekt, aber die Frage ist, ob die 5 alpha oder beta ist. In einem Min Knoten ist es eben beta (weil wie oben beschrieben interessant ist, ein kleineren Wert zu finden) und in einem Max Knoten ist es alpha. Damit kommt man auch hier auf [4,5] als Intervall.

In den Folien ist das in der Regel in der negierten Formulierung beschrieben und daher etwas schwer nachzuvollziehen für den AlphaBeta Fall - aber man kommt durch das invertieren auf die gleichen Ergebnisse.

Ich hoffe das hat geholfen