3. Frage zu Min MAx Algorithmus.

Frage zu Min MAx Algorithmus.

  • F

    Hallo. Ich bin dabe ein 4 Gewinnt Spiel zu Programmieren und möchte den Min Max Algorithmus verwenden. Ich habe da zu mal eine Frage :

    Spieler 1 = Max Spieler und Spieler 2 = Min Spieler !

    Wenn nun Spieler 1 an der Reihe ist, ist der Wurzelknoten, des Spielbaums, ein MAX Knoten. Wenn nun aber Spieler 2 an der Reihe ist, ist dann der Wurzelknoten immer noch ein MAX KNoten oder ein MIN Knoten.

    Vielen Dank

    0

  • Nimm besser gleich den Negamax- bzw. "Alpha-Beta-Pruning"-Algorithmus. Dieser ist nicht wirklich komplizierter (nur zwei Schranken mehr: alpha und beta) und du brauchst keine zwei Funktionen zu schreiben, sondern die Vorzeichen drehen sich je Spieler einfach um, d.h. -1000 ist z.B. schlecht für Spieler 1 aber gut für Spieler 2 (da es dann + 1000 entspricht).
    Die Änderungen dafür sind gut auf http://de.wikipedia.org/wiki/Alpha-Beta-Suche beschrieben.

    0
  • F

    Danke für deine Antwort. Ja ich habe mich auch schon mit Alpha - Beta auseinander gesetzt. Wollte aber erst mal den MinMax hinbekommen. Also wäer ich über eine Antwort sehr dankbar

    0
  • M

    Fischkopf2009 schrieb:

    Wenn nun Spieler 1 an der Reihe ist, ist der Wurzelknoten, des Spielbaums, ein MAX Knoten. Wenn nun aber Spieler 2 an der Reihe ist, ist dann der Wurzelknoten immer noch ein MAX KNoten oder ein MIN Knoten.

    Annahme: das ist die Frage. Die Wurzelknoten müssen für beide Spieler gleichartig sein, weil die beiden Spieler in solchen Spielen austauschbar sind. Sonst wäre die Formulierung umständlicher. Es gibt auch keine Max- oder Min-Spieler. Der eine, der an der Reihe ist, spielt auf ein Maximum an Erfolg, und der andere spielt auf ein Minimum des Erfolgs des einen.

    0
  • M

    Und das Minimum des gegnerischen Erfolges ist gleichbedeutend mit dem Maximum des eigenen Erfolges. Das ist der Grundgedanke hinter dem Algorithmus.

    0
  • M

    mngbd schrieb:

    Die Wurzelknoten müssen für beide Spieler gleichartig sein, weil die beiden Spieler in solchen Spielen austauschbar sind. Sonst wäre die Formulierung umständlicher.

    Ich hab nachgeschlagen, weil ich das immer vergesse: die Formulierung, die wir dir vorschlagen, und die zwischen den beiden Spieler keinen Unterschied macht heisst Negamax (siehe Th69). Das ist der Ausdruck, in dem der eigene Erfolg berechnet wird als Negation des gegnerischen Erfolges. Daher kommt das Minus in der Negamax-Formulierung von Wikipedia:

    function integer minimax(node, depth)
    if node is a terminal node or depth <= 0:
        return the heuristic value of node
    alpha = -INFINITY
    for child in node:                       # evaluation is identical for both players 
        alpha = max(alpha, -minimax(child, depth-1))   # <-- hier das Minus
    return alpha

    siehe http://en.wikipedia.org/wiki/Minimax

    Ich empfehle, deine Suchfunktion so zu formulieren, dann lösen sich deine Probleme von selbst.

    0
Anmelden zum Antworten