Effiziente Impl. von Minimax

Hallo!

Ich würde gerne den Minimax Algorithmus für ein Brettspiel (eine Variante von Reversi) implementieren.
Zur Zeit habe ich so ziemlich die Variante implementiert, die auf Wikipedia als Pseudocode gegeben ist:
http://de.wikipedia.org/wiki/Minimax-Algorithmus

Ich habe das ganze nur auf mehr als 2 Spieler insofern erweitert, dass alle gegnerischen Spieler als MIN-Spieler aufgefasst werden.

Allerdings ist das ganze ja rekursiv und macht bei mir ab einer Tiefe von 10 schon extreme Zeitschwierigkeiten.

Wie implementiert man MINIMAX am effizientesten? Überall finde ich nur diese rekursive Methode, im Buch von Russell/Norvig steht netterweise dabei, dass die Zeitkosten völlig impraktikabel seinen aber es wird nirgendwo gesasgt, wie es besser geht.

Das Alpha-Beta-Pruning ist noch nicht implementiert muss aber auf jeden Fall folgen! Also muss meine Implementierung damit irgendwie verträglich sein.

Ich hoffe ihr könnt mir helfen, es ist wichtig

Opex

knivil

völlig impraktikabel seinen aber es wird nirgendwo gesasgt, wie es besser geht

Tja, vielleicht geht es nicht besser. Du kannst vielleicht hier und da etwas schrauben, aber aus der Komplexitaetsklasse kannst du nicht ausbrechen.

Tja, vielleicht geht es nicht besser.

aber sicher bist du dir auch nicht? irgendwie iterativ und mitm stack oder sowas?
Irgendwas muss doch "praktikabel" sein, wenn man sich überhaupt mit dem Thema beschäftigt.

alpha-beta minimiert den Zeitaufwand in der Praxis doch erheblich. Implementiere den Algorithmus doch einfach mal.

Eine iterative Lösung mit eigenem Stack bringt bestimmt nicht viel. Wenn überhaupt. Aber die Bewertungsfunktion ist auch ein guter Ansatzpunkt für Optimierungen.

Hmmm...okay, das klingt ja so, als wüsstet ihr auch nichts besseres.

Ich wollte das Alpha-Beta-Pruning nur nicht implementieren, weil ich sicher sein wollte vorher schon aufm richtigen Dampfer zu sein.

Opex schrieb:

Hmmm...okay, das klingt ja so, als wüsstet ihr auch nichts besseres.

Ich wollte das Alpha-Beta-Pruning nur nicht implementieren, weil ich sicher sein wollte vorher schon aufm richtigen Dampfer zu sein.

Min-Max und alpha-beta haben wegen der Baumstruktur des Suchraums im schlechtesten Fall eine exponentielle Laufzeit. Daran kann man nichts, was die Komplexitätsklasse betrifft, optimieren. Trotzdem ist alpha-beta in der Praxis DEUTLICH besser und wie gesagt wirken sich auch Verbesserungen in der Bewertungsfunktion aus.

Die beiden Algorithmen gehören quasi zum "Grundwortschatz" der Informatik. In einem Forum auf eine entscheidende Verbesserung zu hoffen ist ... naja, naiv?

Nichts für ungut!!!

Hallo Armin,

es mag naiv sein, wenn man weiß, dass die rekursive Implementierung in der besten Komplexitätsklasse für dieses Problem ist.
Ob mans glaubt oder nicht, aber rekursive Funktionen haben halt desöfteren die Eigenschaft deutlich langsamer zu sein, als ihre iterativen Partner.

Man wird doch wohl fragen dürfen, ob es eine schnellere (iterative) Variante gibt.

Übrigens habe ich das Pruning gerade implementiert.Es scheint zu funktionieren und beschleunigt die Geschichte doch spürbar.
Ist zwar nett, aber so ganz zufrieden bin ich noch immer nicht Aber jetzt weiß ich wenigstens, dass ich keine total blöde Implementierung gewählt habe.