MiniMax-Suche


Nimmer

Grünschnabel
#1
Hallo zusammen,

momentan muss ich für eine KI die unterschiedliche Spiele spielen soll Suchalgorithmen implementieren.
Beginnen wollte ich mit etwas einfachem und habe mir MiniMax ausgesucht. Die Implementierung ist auch kein Problem, aber dieser Algorithmus funktioniert laut Wikipedia nur für Zwei-Spieler-Nullsummen-Spiele mit perfekten Informationen.

Meine Frage ist jetzt wieso er nicht garantieren kann für "Mehr-Spieler-Spiele" und "nicht Nullsummen-Spiele" optimale Lösungen zu finden.
 

Nimmer

Grünschnabel
#3
Die Rahmenbedingung ist einen general-game-playing-agent zu schreiben.
Also eine KI die in der Lage ist ein Spiel zu spielen, von dem nur bekannt ist, dass es sich um ein endliches perfect-information-game handelt (Die Regeln des Spiels werden zu Begin des Spiels in einer prolog-ähnlichen Sprache an den agent übergeben).

Daher benötige ich verschiedene Suchalgorithmen aus denen ich nach einer Klassifizierung des Spiels auswähle.

Meine erste Wahl ist nur auf MiniMax gefallen weil es eine einfach Sache ist mit der ich beginnen kann. Was ich allerdings nicht verstehe ist warum dieser Algorithmus nur in den genannten Spielarten optimale Lösungen garantiert.



Edit:

Zur Frage warum der Algorithmus nur für Nullsummenspiele optimale Lösungen garantieren kann, habe ich inzwischen die Antwort gefunden (ich poste sie einfach mal, falls irgendwann jemand die selbe Frage hat):
Bei einer MiniMax-Suche geht man davon aus, dass das maximieren der eigenen Rewards die Rewards des Gegners minimiert. Dies ist aber nur in Nullsummenspielen der Fall. In allen anderen Spielen kann das maximieren der eigenen Werte auch den Reward des Gegners erhöhen.
Für Multiplayerspiele bin ich mir noch nicht sicher aber es wird vermutlich auf einen ähnlichen Grund hinauslaufen.
 
Zuletzt bearbeitet:

Neue Beiträge