Definition von NegaMax

Moderator: Einführung in die Künstliche Intelligenz

Jannis
Mausschubser
Mausschubser
Beiträge: 63
Registriert: 15. Apr 2015 17:10

Definition von NegaMax

Beitrag von Jannis » 6. Jul 2018 14:49

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.

Tobias Joppen
Mausschubser
Mausschubser
Beiträge: 43
Registriert: 20. Feb 2017 15:08

Re: Definition von NegaMax

Beitrag von Tobias Joppen » 6. Jul 2018 15:00

Hallo,

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

Liebe Grüße,
Tobias

Antworten

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