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)

Inhaltsverzeichnis 1 Weitere Suchstrategien 2 Fehler im Pseudocode? 2.1 Fehler 1 2.2 Fehler 2

[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?

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