Übung 02 - Minimax Algorithmus: Spielfeld bewerten

robtothein
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 1. Aug 2014 13:33

Übung 02 - Minimax Algorithmus: Spielfeld bewerten

Beitrag von robtothein »

Hallo,
bei dem Minimax-Algorithmus gibt es ja eine Funktion "bewerten", welche das aktuelle Spielfeld bewerten soll. Laut wiki gilt:
Je besser die Brettstellung für den maximierenden Spieler ist, desto größer ist der Rückgabewert der Bewertungsfunktion (Funktion bewerten()). Je besser sie für den minimierenden Spieler ist, desto kleiner ist der Rückgabewert.
Ich habe einige verschiedene Bewertungen durchprobiert, aber leider hat keine optimal funktioniert. Ich konnte meistens gewinnen.
Könnte mir bitte jemand einen kleinen Hinweis bzw. Denkanstoß geben, für wen wann ein Spielfeld besser/schlechter geeignet ist? :cry:

Danke

LG
VG,
robtothein

headhumper
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 118
Registriert: 13. Aug 2009 21:25

Re: Übung 02 - Minimax Algorithmus: Spielfeld bewerten

Beitrag von headhumper »

Ich glaube es wäre besser, wenn man für das Spiel eine angepasste KI nehmen würde, und nicht den generischen Minimax-Algorithmus. Der passt zwar für "viele" Spiele irgendwie, aber ist dann natürlich für keins optimal.

Bei uns gewinnt die Minimax AI in 98-99% der Fälle gegen die Zufalls-KI, als Mensch ist es jedoch trivial die Minimax-KI zu schlagen :cry:

leonidglanz
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 126
Registriert: 29. Apr 2015 08:35

Re: Übung 02 - Minimax Algorithmus: Spielfeld bewerten

Beitrag von leonidglanz »

Hallo zusammen,
sind Sie sich sicher, dass es einfach ist gegen die MINIMAX-KI zu gewinnen oder haben Sie vielleicht eine nicht so angepasste Bewertungsfunktion beim MINIMAX-Algorithmus.
Bei kleinen Feldern sollte die MINIMAX-KI nämlich den Spielbaum komplett durchlaufen und somit schwer zu schlagen sein, da Sie mehrere Züge im Voraus berechnet.

MfG,
Leonid Glanz

headhumper
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 118
Registriert: 13. Aug 2009 21:25

Re: Übung 02 - Minimax Algorithmus: Spielfeld bewerten

Beitrag von headhumper »

leonidglanz hat geschrieben:sind Sie sich sicher, dass es einfach ist gegen die MINIMAX-KI zu gewinnen oder haben Sie vielleicht eine nicht so angepasste Bewertungsfunktion beim MINIMAX-Algorithmus.
Bei uns ist die Bewertungsfunktion = Differenz der eingenommenen Spielfelder.
leonidglanz hat geschrieben:Bei kleinen Feldern sollte die MINIMAX-KI nämlich den Spielbaum komplett durchlaufen und somit schwer zu schlagen sein, da Sie mehrere Züge im Voraus berechnet.
Naja, bei Minimax wird ja durchaus eine Annahme darüber gemacht, wie der Gegner spielt. Die KI plant zu lange voraus und nutzt nicht immer die Möglichkeit ein Kästchen zu schließen. Wenn sie es macht, wird im nächsten Zug zu einem Kästchen mit zwei Wänden eine dritte hinzugefügt, was natürlich auch nicht optimal ist, da dann der andere Spieler wieder dran ist und das Kästchen einfach einnehmen kann.

Gegen die "Zufalls-KI" kann Minimax so zuverlässig gewinnen, aber eben nicht gegen einen Menschen, der dieses extrem simple Muster durchschaut.

Edit: So... Nochmal genau hingeschaut und einen kleinen Vorzeichenfehler gefunden :oops:
Jetzt ist es nicht mehr so einfach.

BluBlu
Erstie
Erstie
Beiträge: 19
Registriert: 17. Sep 2015 09:50

Re: Übung 02 - Minimax Algorithmus: Spielfeld bewerten

Beitrag von BluBlu »

Bin zwar nur Student, aber: Wenn das Spielfeld klein genug ist, um den Suchbaum komplett durchlaufen zu können, sollte die MiniMax KI immer das bestmögliche Ergebnis erzielen. Spielt der Spieler anders als es die KI "erwartet", führt das höchsten zu einem noch besseren Ergebnis für die KI. Beispielsweise sollte die KI bei einem 2x2 großen Feld immer mit mindestens 3:1 gewinnen, wenn sie den ersten Strich setzen darf (wobei nicht gefordert ist, dass die Implementierung dort schnell genug zum Durchlaufen des kompletten Suchbaums in vernünftiger Zeit ist).

Bei größeren Spielfeldern kann es natürlich durchaus sein, dass die KI langfristige Strategien des Spielers nicht durchschauen kann, hier ist eine reine MiniMax KI mit "dummer" Bewertungsfunktion dann nicht mehr der optimale Ansatz.

Antworten

Zurück zu „Archiv“