Nega Scout (Übung 3.1)

Moderator: Einführung in die Künstliche Intelligenz

sunfy
Windoof-User
Windoof-User
Beiträge: 34
Registriert: 22. Jun 2004 18:15

Nega Scout (Übung 3.1)

Beitrag von sunfy »

Hallo,
wir rätseln gerade noch etwas über den NegaScout Algorithmus.
Kann da mal jemand die Grundidee erklären und das Zusammenspiel von FAIL HIGH, FAIL LOW etc. erklären?

Gruß Sunfy

acerberus
Erstie
Erstie
Beiträge: 13
Registriert: 16. Jul 2009 15:08

Re: Nega Scout (Übung 3.1)

Beitrag von acerberus »

Der Negascout geht davon aus, dass der erste gefundene Weg der Beste ist. Im folgenden testet er zuerst (mittels minimal window) nur noch ob, ein anderer Weg besser oder schlechter ist als der bereits gefundene. Tritt im folgenden ein Fail low auf (Wert <= alpha), dann ist dieser Branch schlechter als der bisherige und kann somit gepruned werden. Tritt ein Fail high auf (Wert >= beta), so können wir an der Stelle noch nicht genau sagen, was passiert ist, da wir ja mit einem Minimalen Fenster (beta=alpha+1) gesucht haben (und nicht mit dem echten Beta Wert), daher muss nun dieser Zweig nochmal mit einem größeren Fenster durchsucht werden, um zu bestimmen, wie viel besser der Zweig ist.

Damit Negascout optimal funktioniert muss natürlich die Zugreihenfolge auch sinnvoll sein, da man ansonsten vieles doppelt absuchen würde (vgl. schlechteste Zugreihenfolge).

So, ich hoffe jetzt das war richtig. Ich komme nämlich dauernd mit diesen ganzen Fenstern durcheinander.

Grüße
Arno

marluwie
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 18. Okt 2005 22:33

Re: Nega Scout (Übung 3.1)

Beitrag von marluwie »

Hallo!

Man bekommt doch in der Regel einen Fail High, wenn der gefundene Wert t > a (also t >= b) oder t < beta ist. Das heißt eben, dass wir keinen sicheren beta-Cutoff machen können. Was genau ist aber dann der Vorteil von dem kleineren Fenster, wenn wir sowieso letztendlich alpha und beta entscheiden lassen. Ist das nicht einfach eine Alpha-Beta-Suche mit zusätzlichen Suchen? (Also ich bin mir eigentlich sicher, dass es das nicht ist :wink: )
"You can't change anything by fighting or resisting it. You change something by making it obsolete through superior methods." (Buckminster Fuller)

acerberus
Erstie
Erstie
Beiträge: 13
Registriert: 16. Jul 2009 15:08

Re: Nega Scout (Übung 3.1)

Beitrag von acerberus »

Ok, vergesst einfach alles, was ich über Fail High, Low gesagt habe, das ist einfach falsch glaube ich. Mittlerweile bin ich der Meinung, dass es vom Vorgängerknoten abhängt, ob man bei Fail High oder Fail Low pruned, bzw. eine neue Suche startet (da z.B. in der 3.1 ja nur beta-cutoffs vorkommen). Also keine Ahnung. Ich habe leider auch keine vernünftigen Beispiele im Netz gefunden. Kennt da jemand was?

acerberus
Erstie
Erstie
Beiträge: 13
Registriert: 16. Jul 2009 15:08

Re: Nega Scout (Übung 3.1)

Beitrag von acerberus »

Also, ich habs zwar immer noch nicht geschnallt, aber es scheint zu helfen, den Algorithmus (http://en.wikipedia.org/wiki/Negascout) einfach mal mit nem Beispielbaum durchzuspielen. (Auch wenn man durch das ganze negieren und anpassen der Grenzen ein wenig Wahnsinnig wird).

Benutzeravatar
Arki
Mausschubser
Mausschubser
Beiträge: 62
Registriert: 15. Sep 2004 00:47
Wohnort: Darmstadt
Kontaktdaten:

Re: Nega Scout (Übung 3.1)

Beitrag von Arki »

Also ich kann nur empfehlen sich die Originalarbeit von Reinefeld anzuschauen. Der Algorithmus ist da sehr verständlich erklärt. Hat mir mehr gebracht das entsprechende Kapitel in dem Paper zu lesen als zu versuchen, die zugehörigen Folien im KI-Skript zu verstehen. Allerdings: Der Algorithmus in dem Paper arbeitet in einer kleinen Sache anders als der auf den Folien (vgl. Code, betrifft nur den Rückgabewert an den Vaterknoten in manchen Fällen), ändert aber natürlich nichts an der Korrektheit oder dem prinzipiellen Schema (würd mich aber doch interessieren woher der Algo aus den Folien stammt -_-).

Hier der Link zu dem Paper: http://www.zib.de/reinefeld/bib/83icca.pdf
Der Biber machts richtig: Nagt alles kaputt!

banshee
Nerd
Nerd
Beiträge: 684
Registriert: 22. Okt 2006 18:46

Re: Nega Scout (Übung 3.1)

Beitrag von banshee »

Stimmt der Algorithmus aus der Vorlesung überhaupt? Mal angenommen, er wird auf dem Beispiel auf Folie 75 aufgerufen, dann landet man mit -\(\infty\), +\(\infty\) bei dem ganz linken Max-Knoten auf Tiefe 3. Dieser bekommt dann t = -2 vom ersten Blatt zurück, setzt a = -2 und b = -1. Beim zweiten Durchlauf bekommt er t = -5 vom zweiten Blatt zurück, was ignoriert wird (Fail Low?) und -2 wird nach oben propagiert, was einen falschen Wert für den Knoten zur Folge hat. Mache ich da was falsch oder wo liegt der Fehler?

Benutzeravatar
foo
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 179
Registriert: 22. Okt 2004 17:59

Re: Nega Scout (Übung 3.1)

Beitrag von foo »

banshee hat geschrieben:Stimmt der Algorithmus aus der Vorlesung überhaupt? Mal angenommen, er wird auf dem Beispiel auf Folie 75 aufgerufen, dann landet man mit -\(\infty\), +\(\infty\) bei dem ganz linken Max-Knoten auf Tiefe 3. Dieser bekommt dann t = -2 vom ersten Blatt zurück, setzt a = -2 und b = -1. Beim zweiten Durchlauf bekommt er t = -5 vom zweiten Blatt zurück, was ignoriert wird (Fail Low?) und -2 wird nach oben propagiert, was einen falschen Wert für den Knoten zur Folge hat. Mache ich da was falsch oder wo liegt der Fehler?
Spekulation: Das Beispiel ist nicht als NegaMax formuliert, so wie wir das gemacht haben. Dort wird ja z.B. auch auf zwei aufeinander folgenden Baumstufen 5 gespeichert. Wenn man den Algorithmus genau so wie auf der Folie davor anwenden will, muss man die Blättergewichte negieren (und bekommt dann zwischendrin auch andere Werte/Fenster, aber das korrekte Ergebnis), vgl. Übung 3.1.a.

Antworten

Zurück zu „Einführung in die Künstliche Intelligenz“