Minimax Algorithmus auch für Spiele mit mehr als 2 Spielern?
-
Hallo,
bei meinem aktuellen Projekt handelt es sich um eine Art Brettspiel, das komplett "offen" ist, nach der Initialisierung keine Zufälle enthält und bei dem abwechselnd gezogen wird. Der minimax-Algorithmus eignet sich also in dieser Hinsicht sehr gut. Allerdings ist die Spielerzahl variabel und liegt zwischen 2-4. Meiner Meinung nach müsste es trotzdem möglich sein den minimax-Algorithmus zu benutzen, allerdings ist bei dem Algorithmus immer nur von 2 Spielern die Rede. Bevor ich jetzt noch viel an der Implementierung arbeite, um dann zu merken dass es nicht geht, frage ich euch!MfG
-
Mit dem normalen minimax würde das bedeuten, das der Computer während er die gute Stellung für sich sucht, die Gesamtsituation aller Gegner in der Summe möglichst schlecht zu machen. Es wird dann sozusagen der "Angriff" gewählt der den meisten Schaden macht, egal gegen wen er sich richtet. Eigentlich sollte man ja aber auch darauf achten, das nicht einer der Gegner superstark wird, während man die anderen fertigmacht.
Bye, TGGC (Wähle deine Helden)
-
Stimmt, daher dachte ich man könnte die Anzahl Felder (worum es in dem Spiel geht) quadratisch wichten. Z.B.:
E = Anzahl eigener Felder
G1 = Anzahl Felder des 1. Gegners
....P = E² - (G1² + G2² + G3² + G4²)
und dann noch ggf. Bonuspunkte wenn man einen Gegner komplett beseitigt. Was mir allerdings z.Zt mehr sorgen bereitet ist die Rechenzeit: Es gibt für einen Spieler locker so um 40 Zugmöglichkeiten, die möglichen Züge zu berechnen ist kein Ding, den Zug auszuführen ist aber nicht so simpel... gibt es gute Alternativen? Es ist nicht unbedingt erforderlich eine KI zu entwickeln die unschlagbar ist, relativ leistungsstark sollte sie schon sein (ja, ich weiß, ohne das Spiel zu kennen wird es schwierig was sinniges dazu zu sagen, einige Stichworte zum Googlen reichen mir schon)
-
Also ich kenn dein Spiel nicht, und auch nicht die Zahlen, die du quadrierst. Und es dürfte ohnehin recht schwer werden, durch bloßes Hinschauen alle möglichen Probleme zu erkennen.
Um den Spielbaum wirst du aber vermutlich bei minmax nicht umhinkommen, aber vielleicht kannst du mit einem Bounding-Verfahren die Anzahl der Äste einschränken.
Bye, TGGC (Keine Macht den Dummen)
