Negamax Evaluierung

T

toaopeter

Mitglied
Hallo liebe Java-Freunde,

ich sehe mir gerade den NegaMax Algorithmus an.
Mein Problem ist, dass ich irgendwie nicht klar komme.
Der Computer bleibt "dumm".
(MiniMax geht einwandfrei. Die korrekte Evaluierungsfunktion für NegaMax kapiere ich nicht.)

Hier am Beispiel TicTacToe.

Die Evaluierungsfunktion für MiniMax ist einfach. "player" ist entweder 1 oder -1.

Java:
// Evaluierungsfunktion für MiniMax. Aber was mache ich bei NegaMax?
int evaluate(int player) {
        if ((isWin()))
            return -player;
        else return 0;
    }


// Hier der NegaMax Algorithmus - - hoffentlich ohne Fehler!
    int negaMax(int player, int depth, int alpha, int beta) {
        if (depth == 0 || isGameOver()) return evaluate(player);
        List<Integer> availableMoves = getAvailableMoves();
        if (availableMoves.isEmpty()) return 0;
        for (int move : availableMoves) {
            doMove(move);
            int score = -negaMax(-player, depth - 1, -beta, -alpha);
            undoMove();
            if (score > alpha) {
                alpha = score;
                if (depth == maxDepth) {
                    listOfMoves.add(move);
                    listOfScores.add(score);
                }
                if (alpha >= beta) break;
            }
        }
        return alpha;
    }
 
T

toaopeter

Mitglied
Das habe ich schon erfolglos versucht. :(
Vermutlich dann doch ein Fehler im Algorithmus... hmh...
 
mihe7

mihe7

Top Contributor
Das Prinzip ist ja relativ einfach:

Die Bewertung erfolgt immer aus Sicht des jeweiligen Spielers, so dass eine positive Bewertung sich in einer positiven Zahl niederschlägt. Diese Bewertung wrid bei Negamax vom anderen Spieler in genau umgekehrter Richtung wahrgenommen. Sprich: was für den Gegner positiv ist, ist für mich negativ und umgekehrt.

Negamax funktioniert nun einfach so, dass bewertet wird, wie sich ein gegenwärtiger Zug in der Zukunft auswirkt. Dazu wird das Spiel "gedanklich" eine gewisse Anzahl an Runden weitergespielt.

Interessant ist in dem Zusammenhang insbesondere alpha, der den Wert des besten Zugs des Spielers darstellt, der in einer gegebenen Situation bislang ausgeführt wurde. Sofern kein Zug stattgefunden hat, entspricht er - negativ - dem besten Wert des Gegenspielers.

Das beta dient als Abbruchbedingung (sprich: wenn ich für einen Spieler einen "winning move" festgestellt habe, braucht mich der Rest nicht mehr zu interessieren). Daher darfst Du beta im rekursiven Aufruf nicht negativ übergeben.

int score = -negaMax(-player, depth - 1, -beta, -alpha);
Muss also
Java:
int score = -negaMax(-player, depth - 1, beta, -alpha);
sein.

Beim initialen Aufruf sollten depth und maxDepth der Zahl freier Felder entsprechen, alpha müsste 0 und beta 1 sein.
 
T

toaopeter

Mitglied
Hm. Das funktioniert leider auch nicht. Sorry.
Aber es hat auf jeden Fall mit dem Alpha-Beta Cut zu tun.
Wenn ich
Code:
// if (alpha >= beta) break;
auskommentiere, dann läuft der Algorithmus einwandfrei.
Eben ohne Alpha-Beta :-/
 
mihe7

mihe7

Top Contributor
Das gibt irgendwie keinen Sinn: score kann nur -1, 0 oder 1 sein. Damit kann alpha max. 1 werden. Wenn Du immer 1 für beta übergibst, wird die Schleife beendet, wenn kein besserer Zug gefunden werden kann.
 
T

toaopeter

Mitglied
OK. Wenn ich im Initialaufruf Alpha -1 und Beta +1 verwende, dann geht es.

Aber auch Beta wird im rekursiven Aufruf negativ übergeben.
 
mihe7

mihe7

Top Contributor
OMG: Dein negaMax-Aufruf vertauscht alpha und beta.

Nachtrag: außerdem hängt es davon ab, wie Du isWin() implementiert hast. Dann musst Du tatsächlich -player zurückgeben, weil der vermutlich am Ende von doMove wechselt.
 
Zuletzt bearbeitet:
Ähnliche Java Themen
  Titel Forum Antworten Datum
A Negamax-Algorithmus Spiele- und Multimedia-Programmierung 7

Ähnliche Java Themen

Anzeige

Neue Themen


Oben