Übung 02 - Minimax Algorithmus: Spielfeld bewerten

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

Danke

LG

[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

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

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.

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
Jetzt ist es nicht mehr so einfach.

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