Seite 1 von 1

Definition von NegaMax

Verfasst: 6. Jul 2018 14:49
von Jannis
Hallo,

wie ist die Definition von NegaMax auf Folie 28 von dem Adversarial Search Foliensatz (http://www.ke.tu-darmstadt.de/lehre/ss1 ... arial.pdf) zu verstehen? Kann es sein, dass die Definition unvollständig ist?

Als Beispiel:
- Angenommen ich hab nur einen Baum mit dem Wurzelknoten (MAX) und den Blättern 1, 2, 3. Dann würde mir diese Definition von NEGAMAX -1 als Maximum von -1, -2, -3 zurückliefern. Dabei will man ja die Äquivalenz zu MINIMAX, also sollte die Rückgabe 3 sein.

Es reicht allerdings nicht, beispielsweise den Fall UTILITY(n) zu negieren, da sonst ein Baum mit drei Ebenen (MAX, MIN, negative Blattknoten) ebenfalls falsche Ergebnisse liefert.

In dem Pseudocode auf Wikipedia (https://en.wikipedia.org/wiki/Negamax) wird dieses Problem z.B. so behandelt, dass die Utility der Blattknoten negiert wird, je nachdem ob gerade MIN oder MAX am Zug ist.

Viele Grüße,
Jannis

Update:
Ich denke man soll "Assume that evaluations in all nodes (and leaves) are always from the point of view of the player that is to move" so deuten, dass UTILITY(n) je nach aktuellem Spieler mal positive und mal negative Werte liefert. Dann wäre es aber vermutlich sauberer noch den jeweiligen Spieler als Argument der Utility-Funktion aufzunehmen (oder es zumindest explizit auf der Folie zu erwähnen), da man das ansonsten leicht falsch verstehen kann.

Re: Definition von NegaMax

Verfasst: 6. Jul 2018 15:00
von Tobias Joppen
Hallo,

das im Update ist genau der Punkt. Und ja, könnte man vielleicht deutlicher darstellen.

Liebe Grüße,
Tobias