Negamax Evaluierung

[toaopeter]

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.

// 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;
    }

 

[mihe7]

Der Computer bleibt "dumm".

Ja, ja, jetzt wäre es wieder der Computer

Aber was mache ich bei NegaMax?

Einfach im Fall des Gewinnes 1 zurückgeben.

 

[toaopeter]

Das habe ich schon erfolglos versucht.
Vermutlich dann doch ein Fehler im Algorithmus... hmh...

 

[mihe7]

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

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.

 

[toaopeter]

Hm. Das funktioniert leider auch nicht. Sorry.
Aber es hat auf jeden Fall mit dem Alpha-Beta Cut zu tun.
Wenn ich

// if (alpha >= beta) break;

auskommentiere, dann läuft der Algorithmus einwandfrei.
Eben ohne Alpha-Beta :-/

 

[mihe7]

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.

 

[toaopeter]

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

Aber auch Beta wird im rekursiven Aufruf negativ übergeben.

 

[mihe7]

Moment, ich probier mal kurz was.

 

[mihe7]

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.