Diskussion:Minimax-Algorithmus
aus Wikipedia, der freien Enzyklopädie
Hm. Dieser Artikel ist etwas ungenau, und beschreibt überhaupt nicht, wie Minimax überhaupt funktioniert, obwohl dies denkbar einfach ist. Außerdem wird mittels Minimax weder für Reversi (Othello), noch für Schach oder gar Go eine optimale Lösung gefunden.
"Hier kann heute noch nicht schon von der Anfangsstellung aus eine optimale Strategie berechnet werden."
- "Noch nicht" ist etwas schmeichelhaft - es wird nie möglich sein! Rechner werden nicht sooo schnell werden, um den kompletten Spielbaum von Go aufzuspannen, nicht in diesem Universum ...
--zeno 19:19, 7. Jun 2003 (CEST)
- Habe das Beispiel erläutert, so dass der Algorithmus wenigstens einmal kurz erklärt wird. Ist das OK so?
- --Rubik-wuerfel 01:24, 22. Jun. 2007 (CEST)
Inhaltsverzeichnis |
[Bearbeiten] Weitere Suchstrategien
Gibt es bereits Artikel ueber andere Suchtechniken? Ich denke da an Alpha-Beta, Principal Variation Search, Forward Pruning, Quiescent Search und solche Dinge.
stw am 23. nagut 24.11.2004
[Bearbeiten] Fehler im Pseudocode?(erledigt)
[Bearbeiten] Fehler 1
Es geht mir um folgende Stelle des Pseudocodes:
if zugWert > ermittelt then begin
ermittelt := zugWert
doNext := nummer des Zuges /* für das Hauptprogramm */
end
Soweit ich das richtig verstanden habe, werden nur die Stellungen der maximalsten Tiefe bewertet und dann jeweils die maximalste bzw. minimalste Bewertung dem Mutterknoten zugeschrieben. Die Variable doNext ist hierbei eine globale Variable, das bedeutet sie verändert sich auch, wenn innerhalb der Rekursion maxWert aufgerufen wird. Beispiel: Angenommen es gibt 3 Züge, der erste wird mit 100, der zweite mit 150 und der dritte mit 50 bewertet. Beim zweiten Durchlauf wird die Variable doNext auf den Zug gesetzt, der mit 150 bewertet wurde. Nun besteht aber das Problem, dass zwischen dem 2. und dem 3. Zug noch weitere Rekursionen folgen, die doNext verändern. Da am Ende jedoch die Zahl 50 nicht größer ist als 150 wird doNext nicht mehr neu gesetzt und doNext besitzt einen Wert, der irgendwann mal in der Rekursion aufgetreten ist. Berichtigt mich bitte, wenn ICH falsch liege, ansonsten sollte das geändert werden, bei meinem Programm kam jedenfalls nach dem genannten Pseudecode nichts gutes bei raus!
Lösungvorschlag, wenn maxTiefe eine globale Variable wäre, könnte man bei der Funktion maxWert dann folgendes schreiben:
if zugWert > ermittelt then begin
ermittelt := zugWert
if restTiefe = maxTiefe then doNext := nummer des Zuges /* für das Hauptprogramm */
end
[Bearbeiten] Fehler 2
kann es sein, dass die Rekursion im Pseudocode nicht korrekt ist? die maxWert-Funktion ruft minwert der Kinder auf und umgekehrt?!
--Lollipop 18:43, 17. Jun 2006 (CEST)
Das ist ja gerade der Hauptbestandteil des minimax-Algorithmus. Die Funktionen minWert und maxWert rufen sich gegenseitig auf, bis eine bestimmte Tiefe erreicht ist und dann wird dieser letzte Knoten bewertet. Die Bewertungen der anderen Knoten erfolgt dann einfach durch die Auswahl der größten bzw. kleinsten Bewertung des Mutterknotens.
Krasno 21:32, 18. Jun 2006 (CEST)
[Bearbeiten] Abgrenzung "alternate moves" - "simultaneous moves"
Die o.g. Abgrenzung ist noch ziemlich ungenau: der Pseudocode bezieht sich nur auf Spiele mit abwechselnden Zügen, wie z.B. Schach. Das Applet allerdings ist der allgemeinere (durch Von Neumann vorgeschlagene) Minimax-Algorithmus für Spiele mit gleichzeitigen Zügen wie z.B. Schnick-Schnack-Schnuck (Roshambo).
Beim englischen Artikel ist das schöner gemacht. Dafür gibt's hier den schöneren Pseudocode! ;-)
[Bearbeiten] Strategie dominiert
Welchen Nutzen kann man aus der Erkenntnis ziehen, wenn eine Strategie über die andere Strategie dominiert? Sind bei Zweipersonenspielen Gleichgewichtsstrategien immer das Beste, was die 2 Spieler erreichen können? Diese dinge kann ich aus dem Text nicht entnehmen, obwohl sie wichtig sind. --Flow2 18:48, 17. Feb. 2007 (CET)
[Bearbeiten] Iterative Tiefensuche
Handelt es sich bei der iterativen Tiefensuche nicht einfach um eine Breitensuche?
- Nein. Bei der iterativen Tiefensuchen werden - im Gegensatz zur Breitensuche - die oberen Ebenen tatsaechlich mehrfach durchsucht. Von der Laufzeit her faellt das (in der O-Notation) aber nicht ins Gewicht, da man eine exponentielle Steigerung der Knoten mit steigender Tiefe hat. Der grosse Vorteil der iterativen Tiefensuche gegenueber der Breitensuche ist, das erstere den Speicher viel sparsamer verwaltet. Breitensuche hat einen exponentiellen Speicherbedarf in der erreichten Tiefe, Tiefensuche und iterative Tiefensuche nur linearen. Lars 21:48, 27. Mai 2007 (CEST)
