Frage zu AlphaBeta Pruning ...

joe75

Hallo Leute,

eine kleine Frage zu folgendem, in pseudo-code dargegestelltem alphabeta algorithmus (wird z.B. bie Brettspielen zur Suche des besten Zuges benutzt):

int AlphaBeta(int tiefe, int alpha, int beta) {
   if (tiefe == 0) return Bewerten();
   GeneriereMoeglicheZuege();
   while (ZuegeUebrig()) {
     FuehreNaechstenZugAus();
     wert = -AlphaBeta(tiefe-1, -beta, -alpha);
     MacheZugRueckgaengig();
     if (wert >= beta) return beta;
     if (wert > alpha) alpha = wert;
   }
   return alpha;
}

Meine Frage hierbei lautet wie folgt:
Der Algorithmus gibt nur einen Wert (bestmoegliche Brettbewertung bei bestem Spiel des Gegners) zurueck.
Wie kann man aber nun den besten Zug (besser waere noch der ganze Trace, der bis zu der entsprechenden Brettposition an den Blaettern fuehrt) sich abspeichern oder merken!?

Vielen Dank.

Gruss

volkard

joe75 schrieb:

Der Algorithmus gibt nur einen Wert (bestmoegliche Brettbewertung bei bestem Spiel des Gegners) zurueck.

Wie kann man aber nun den besten Zug[/quote]
indem du auf der obersten ebene eine andere funktion nimmst, die dir (auch?) den zug zurückliefert.

(besser waere noch der ganze Trace, der bis zu der entsprechenden Brettposition an den Blaettern fuehrt) sich abspeichern oder merken!?

das müßte ganz einfach gehen mit pair<zug,wert> besteZuege[maxlevel]; nebst vor jedem return ein if(wert>besteZuege[level].wert){besteZiege[level].wert=wert; besteZuiege[level].zug=zug}; oder so.

joe75

ich haette noch eine frage zu obigem algorithmus und waere sehr dankbar wenn mir jemand den knoten den ich in meinen gehirnzellen habe irgendwie aufkriegen koennte:

zu meinem bereits geposteten algorithmus (siehe oben) schaue man sich auf der folgenden URL einen beispiel-baum an, der mit obigem algorithmus durchlaufen wird:

[url]
http://lexikon.freenet.de/Alpha-Beta-Suche
[/url]

Was ich hier nicht verstehe ist die tatsache dass im ersten schritt auf unterster ebene (bei blatt 1 links unten) der rueckgabewert 10 ist und im dazugehoerigen eltern-knoten darueber ploetzlich beta angepasst wird, obwohl der algorithmus doch auf der eltern-ebene abfragt ob der wert der vom kind stammt groessergleich beta ist (dann wird beta an aufrufstelle zurueckgeliefert) oder groesser alpha ist (dann wird alpha(!!) angepasst !!

ferner ist mir nicht klar wieso im algorithmus steht
wert = -AlphaBeta(...)

aber die 10 immer als positiver Wert hochgereicht wird!?

Ein paar gedankliche Tipps waeren sehr nett.

Gruss

volkard

vielleicht weil du NegaMax im code hast und MiniMax auf dem bildchen?

joe75

ok du hast recht ...
im prinzip liefern beide das gleiche ergebnis zurueck aber die skizze fuer negamax duerfte dann ein bischen anders aussehen.

vielen dank.

gruss