Not logged inCSS-Forum
Forum CSS-Online Help Search Login
CSS-Shop Impressum Datenschutz
Up Topic Hauptforen / Schachprogrammierung / Erläuterungen zum Suchalgorithmus
- - By Lothar Jung Date 2021-07-09 11:26 Edited 2021-07-09 11:38
Wikipedia-Beitrag zur Alpha-Beta-Suche:

https://de.wikipedia.org/wiki/Alpha-Beta-Suche?wprov=sfti1

Der Alpha-Beta-Algorithmus
Maria Hartmann 19. Mai 2017:

http://www.inf.fu-berlin.de/lehre/SS17/PSThInf/notes/03_alphabeta.pdf
Parent - - By Wolfram Bernhardt Date 2021-07-10 10:04
Hi!

Da möchte ich direkt über einen Punkt sprechen, über den ich neulich gestolpert bin. Es geht um den Ausgangwert für das Maximum des Zugwertes in der aktuellen Suchtiefe. Die Negamax-Suche ist in der Wikipedia wie folgt angegeben:

Code:

int miniMax(int spieler, int tiefe,
             int alpha, int beta) {
    if (tiefe == 0 or keineZuegeMehr(spieler))
       return bewerten(spieler);
    int maxWert = alpha;
    Zugliste = generiereMoeglicheZuege(spieler);
    for each (Zug in Zugliste) {
       fuehreZugAus(Zug);
       int wert = -miniMax(-spieler, tiefe-1,
                           -beta, -maxWert);
       macheZugRueckgaengig(Zug);
       if (wert > maxWert) {
          maxWert = wert;
          if (tiefe == gewuenschteTiefe)
             gespeicherterZug = Zug;
          if (maxWert >= beta)
             break;
       }
    }
    return maxWert;
}


Mir geht es um die 5. Zeile:  int maxWert = alpha;

In vielen anderen Implementierungsbeispielen wird hier aber dies verwendet: maxWert = -99999 .

Meiner Meinung nach ist das schon ein wichtiger Unterschied und ich frage mich, was richtig ist. Oder ob es egal ist (was ich eher nicht glaube).

Weiß da jemand etwas zu?

Viele Grüße
      Wolfram
Parent - By Lothar Jung Date 2021-07-10 10:34 Edited 2021-07-10 10:36
Hallo Wolfram,

gutes Beispiel für eine MiniMax-Funktion.

An diese Funktion werden 4 Werte übergeben.
Einer davon ist alpha.
Alpha wird an die Variable int maxWert übergeben.
Danach wird die Anzahl der möglichen Züge an die Zugliste übergeben.
Danach wird die Suchschleife ausgeführt.
Die Schleife wird verlassen, wenn der maxWert >= beta ist.
Die Funktion gibt den maxWert zurück.

Die Anzahl der Schleifendurchläufe hängt von der Anzahl der Züge in der Zugliste ab: „for each (Zug in Zugliste)“.

Ich kann nur diese Funktion kommentieren, da mir andere Algorithmen mit maxWert=-99999 nicht vorliegen.

Just my two cents.

Lothar
Parent - By Thomas Plaschke Date 2021-07-10 11:04
Ich weiß nix!

… halte aber maxwert=alpha auch für verdächtig, weil damit der negierte beta-Wert der tiefe-1 zum Vergleich wert > maxwert genommen wird. Das könnte bessere Züge der aktuellen Suchtiefe ausblenden, glaube ich.

In anderen Veröffentlichungen wird tatsächlich -unendlich zugewiesen (, um sicherzustellen, dass maxwert in der aktuellen Tiefe ermittelt wird(?), wodurch alle Züge der aktuelle Tiefe einbezogen werden).

Viele Grüße
Th. Plaschke
Parent - By Lothar Jung Date 2021-07-10 11:52
Hier ist ein anderes Beispiel, das auch keinen Maximalwert vorsieht:

function AlphaBeta(node, depth, alpha, beta, maximizingPlayer)
  if depth = 0 or node is a terminal node then
    return the heuristic value of node
  end if
  if maximizingPlayer then
    v := visits MAXVALUE
    for each child of node do
      v := max(v, alphabeta(child, depth -1, alpha, beta, FALSE))
      alpha := max(alpha, v)
      if beta ≤ alpha then
        break(beta-cutoff)
      end if
    end for
    return v
  else
    v := visits MINVALUE
    for each child of node do State v := max(v, alphabeta(child, depth -1, alpha,beta, TRUE))
      beta := min(beta, v)
      if beta ≤ alpha then
        break(alpha-cutoff)
      end if
    end for
  return v
end if
end function
Parent - - By Jörg Oster Date 2021-07-10 12:10
maxWert übernimmt hier die Rolle von alpha.
Deshalb wird zu Beginn maxWert der Wert von alpha zugeteilt.
Siehe auch der nachfolgende rekursive Aufruf von miniMax() mit -maxWert anstatt -alpha.

In den meisten Implementierungen ist es aber so, dass man beide Werte getrennt voneinander beibehält.
Dann wird maxWert erstmal auf den schlechtestmöglichen Wert initialisiert (-unendlich).
Wenn der Wert eines Zuges größer als maxWert ist, wird dieser aktualisiert.
Ist der Wert auch größer als alpha, wird auch alpha aktualisiert.
Parent - By Lothar Jung Date 2021-07-10 12:25
Danke Jörg,

Also beides geht. Fragt sich nur welche Variante schneller ist.

Lothar
Parent - - By Jörg Oster Date 2021-07-10 12:27
Ergänzend dazu, müsst ihr euch darüber im Klaren sein,
dass das ganze ja seinen Ursprung an der Wurzelposition (root position) hat.
Und von da wird die Suche ja mit alpha = -unendlich und beta = unendlich gestartet!
Parent - - By Wolfram Bernhardt Date 2021-07-10 13:46
Hi Jörg!

Klar, an der Wurzelposition startet man mit Maximalwerten.

Ich bin aber weiterhin nicht sicher. Man will in der Praxis schon die Variante, in der man nicht dauernd zwischen minimierendem und maximierendem Spiel unterscheiden wil, also negamax.

Hier gibt es den Algorithmus auch beschrieben und man sieht, dass alpha, beta und der value der aktuellen Stufe als drei getrennte Werte gehalten werden und alpha und value sind nicht dasselbe.

https://en.wikipedia.org/wiki/Negamax#Negamax_with_alpha_beta_pruning

Es könnte aber sein, dass es auch nicht schadet... bisher kommt mir die Initialisierung von value = alpha aber doch irgendwie eigenartig vor...
Up Topic Hauptforen / Schachprogrammierung / Erläuterungen zum Suchalgorithmus

Powered by mwForum 2.29.3 © 1999-2014 Markus Wichitill