Diskussion:Minimax-Algorithmus

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.

Wer ein einfaches Beispiel (5 Streichhölzer, man darf eines oder zwei wegnehmen) hinzufügen und erläutern möchte, darf meine selbst erstellte Grafik frei verwenden und verändern. Möchte den Artikel nicht selbst ändern, habe zu wenig Erfahrung damit...

Bildbeschriftung hier hinzufügen

(nicht signierter Beitrag von R1234r (Diskussion | Beiträge) 22:03, 5. Jul 2012 (CEST))

"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)

Hallo Algorithmus!

In welchem Teil des Artikels wird eigentlich der Minimax-Algorithmus beschrieben? Was ist das überhaupt?

Zunächst erfahre ich wozu man den MMA verwenden kann, dann erfahre ich etwas über Nullsummenspiele und daß der MMA da nicht so gut sein kann. Aber wie geht der MMA? Was ist die Grundidee und wie wird diese Idee umgesetzt?

Dann erfahre ich einige Feinheiten zu Berwertungsfunktionen, aber nicht wo ich die im MMA brauche, zumal ich immer noch nicht weiß, was der MMA überhaupt ist!

Im "Suchbaum-Beispiel" , gemeint ist wahrscheinlich ein Suchbaumbeispiel, erfahre ich etwas über die Spieler A und B, aber nicht wer wer ist, was sie wie und warum machen, woran ich das in der Graphik erkenne und was das Ganze mit dem MMA zu tun hat.

Schließlich wird mein Wissen noch um einige geistvolle "Anmerkungen" und Nachbetrachtungen bereichert, die mangels Kernbetrachtung zwangsläufig gegenstandslos sind. Das weitgehend unkommentierte Listing in einer Phantasieprogrammiersprache ist als Einführung und Beschreibung des Algorithmus völlig unbrauchbar.

Der Artikel ist nur etwas für Leute, die bereits an anderer Stelle erfahren haben, was der MMA ist und soviel Erfahrung damit haben, daß sie den durchaus banalen Ausführungen des Artikeln folgen können und wollen. Also Thema verfehlt! Es wird nicht einmal gesagt, wo ich mich denn über den MMA informieren kann (Quellenangabe!?) um danach zu überprüfen, was das ganze Drumrumgelaber mit dem Thema zu tun hat.

Analoges Beispiel: Messer: damit kann man schneiden. Harte Sachen kann man nicht mit Messern schneiden. Für Papier können andere Werkzeuge sinnvoller sein. Man kann damit auch werfen und sich damit verletzen. Bild Einwegrasierer. Es gibt scharfe und stumpfe, große und kleine Messer und einige werden in Solingen gemacht... Aber was ist ein Messer? Wie sieht es aus? Wie benutzt man es? Wer hat es wann erfunden?

CBa--79.206.247.14 19:01, 16. Sep. 2010 (CEST)

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

Fehler im Pseudocode?(erledigt)

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

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)

Immer noch schwer verständlich

Ich finde einige Aspekte im Pseudo Code immer noch schwer verständlich

1. so heißt es

   if restTiefe = gewünschte suchTiefe (1)

beim Aufruf steht aber

   dummy := maxWert ( gewünschte suchTiefe )

und im Kopf der function

   function maxWert ( restTiefe )

daher müsste "gewünschte suchTiefe" doch als globale Variable abgelegt werden, damit (1) funktioniert, oder? Oder ist gemeint "if restTiefe = 0" ?

2. Auch in der Zeile

  doNext := nummer des Zuges

Die Var "nummer des Zuges" taucht hier das erste Mal auf; sollte daher nicht statt

  für alle möglichen Züge begin

besser stehen

  für <nummer des Zuges> gehe alle möglichen Züge durch begin 

3. Die Bewertungsfunktion wird in Min und in Max aufgerufen. Wenn man beide Male die gleiche Funktion "Bewertungsfunktion" verwendet, muss dann nicht der Wert in Min mit -1 multipliziert werden? Sonst sollte stehen "BewertungsfunktionFuerMax" und "BewertungsfunktionFuerMin", oder ?

Vielen Dank! (nicht signierter Beitrag von 79.223.64.19 (Diskussion) 12:02, 9. Okt. 2011 (CEST))

Suchbaum-Beispiel :

Weder Text noch Graphik sind nachvollziehbar und konsistent.

170.133.12.82 16:32, 23. Jun. 2023 (CEST)

Liebe IP! Muss ich leider voll zustimmen. Ich habe mal eine Überarbeitung versucht.--Lefschetz (Diskussion) 10:58, 24. Jun. 2023 (CEST)

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! ;-)

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)

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)

Welche blauen Pfeile ?

" ...und die blauen Pfeile den gewählten Zug."

Ich sehe nur einen blauen Pfeil

Völlig richtig. Jetzt besser? --Lefschetz (Diskussion) 11:00, 24. Jun. 2023 (CEST)

170.133.12.82 16:23, 23. Jun. 2023 (CEST)

Vielleicht Literatur (?)

Jörg Bewersdorff:

Glück Logik und Bluff. Mathematik im Spiel.

Braunschweig/Wiesbaden 2001.

170.133.12.82 16:27, 23. Jun. 2023 (CEST)

Danke. Vorschlag aufgegriffen. --Lefschetz (Diskussion) 11:01, 24. Jun. 2023 (CEST)