Probleme mit Negamax-Algorithmus

Bitte aktiviere JavaScript!
Hallo,

um eine Schachaufgabe zu lösen(Weiß ist am Zug und muss mattsetzen) verwende ich den Negamax-Algorithmus.

Java:
private int suchTiefe = 3;
private Zug besterZug;
....

private int negaMax(int spieler, int tiefe) { // Weiß 1 , Schwarz -1


    if(tiefe == 0 || überprüfePatt() || überprüfeMatt()) { // Suchtiefe erreciht oder keine Züge mehr
        return zugBewerten(spieler);
    }


    int maxWert = Integer.MIN_VALUE;
    ArrayList<Zug> züge = generiereZüge(spieler);


    for(Zug z: züge) {

        macheZug(z);
        int wert = -negaMax(-spieler, tiefe - 1);
        macheZugRückgängig(z);

        if(wert > maxWert) {
            maxWert = wert;

            if(tiefe == suchTiefe) {
               besterZug = z;
            }
        }

    }
    return maxWert;
}

...

negaMax(1, suchTiefe);
System.out.println(besterZug.toString());
Wenn es z.B ein Matt in 3 ist und die Suchtiefe auch 3 ist, wird der erste Zug(der zum Matt führt) richtig ausgegeben. Bei der selben Aufgabe, aber z.B mit einer Suchtiefe von 4 oder 5 wird ein falscher Zug zurückgegeben.

Woran könnte das liegen?

Danke im vorraus.
 
A

Anzeige




Vielleicht hilft dir unser Kurs hier weiter —> (hier klicken)
Ich habe jetzt versucht bei der Bewertungsfunktion die Tiefe zu berücksichtigen, aber es wird bei größerer Suchtiefe immer noch ein falscher Zug zurückgegeben.
Java:
/*
 Je schneller Matt gefunden wird, desto größer der Rückgabewert
 */

private int zugBewerten(int spieler, int tiefe) {

if (spieler == 1) {  // Weiß
    if (überprüfeMatt()) return 100 * tiefe;
    if (überprüfePatt()) return 0 ;
    return 10; // Weder Matt noch Patt
  
}else if(spieler == -1) { // Schwarz
    if (überprüfeMatt()) return 0;
    if (überprüfePatt()) return 100 * tiefe;
    return 10; // Weder Matt noch Patt
}

   return 0;
}
 
Der Negamax-Algorithmus ist hier ja auch nicht das, wo die eigentliche Musik spielt. Die Musik spielt in der verwendeten Heuristik. Genauso wie Minmax dient Negamax ja nur dazu, die durch die Heuristik berechneten Ergebnisse einfach nach oben zu propagieren, zusätzlich unter Zuhilfenahme der Symmetrie, dass, wenn ein Zug für Spieler A gut ist, ist er für Spieler B in exakt gleichem Maße schlecht.
Der "Baum" entsteht hier implizit durch die Rekursion. Auf Datenstruktur-Ebene wird der Baum durch das Generieren und das Backtracken von Zügen basierend auf vorherigen Zügen traversiert.
 
Nehmen wir mal Spieler 1 (weiß) mit einer Suchtiefe von 1 an (negaMax(1,1)). Es wird ein möglicher Zug ausgeführt und anschließend wird negaMax rekursiv aufgerufen, diesmal mit dem Gegenspieler (schwarz), also negaMax(-1,0). Damit wird der Zug aus Sicht des Gegenspielers bewertet. Das Ergebnis dieses Aufrufs wird daher invertiert.

Die Bewertungsfunktion muss also das Ergebnis für den jeweiligen Spieler angeben. Es reicht z. B. nicht, zu überprüfen, ob ein Matt besteht, denn die Frage ist ja, wer mattgesetzt wurde. Nehmen wir mal an, der weiße Spieler wäre mattgesetzt. Dann ist die Bewertung für den weißen Spieler schlecht (z. B. -100) und im gleichen Maße für den schwarzen gut (+100). Genau umgekehrt verhält es sich, wenn der schwarze Spieler mattgesetzt würde.
 
Die Bewertungsfunktion muss also das Ergebnis für den jeweiligen Spieler angeben. Es reicht z. B. nicht, zu überprüfen, ob ein Matt besteht, denn die Frage ist ja, wer mattgesetzt wurde.
Ich verstehe nicht ganz was du damit meinst. Dafür habe ich in der Bewertungsfunktion die Unterscheidung zwischen den beiden Spielern. Jenachdem welcher Spieler am Zug ist, wird ein anderer Wert zurückgegeben.
 
Sorry, mein Fehler. Hatte nicht berücksichtigt, dass die Bewertungsfunktion nicht nur bei Tiefe 0 sondern auch dann aufgerufen wird, sobald z. B. ein Matt entstanden ist. Dadurch verhält sich sogar noch etwas anders: ein Spieler führt einen Zug aus und sollte im rekursiven Aufruf (Gegenspieler) dieser Zug zu einem Matt geführt haben, dann wäre das für den Gegenspieler (= aktueller Spieler im rekursiven Aufruf) schlecht. Es sollte also genügen, wenn die Bewertungsfunktion den Wert unabhängig vom Spieler (wohl aber von der Tiefe) zurückgibt - und zwar negativ.

Wenn ich mich jetzt nicht vertan habe:
Java:
// Zug wurde "gegen" den Spieler ausgeführt, für den die Methode aufgerufen wird
private int zugBewerten(int tiefe) {
    if (überprüfeMatt()) return -100 - tiefe;
    if (überprüfePatt()) return -10 - tiefe;
    return 0; // Weder Matt noch Patt
}
 
Deine Bewertungsfunktion funktioniert mit einer Suchtiefe von 3(und Matt in 3) genau wie meine. Nur bei einer Tiefe von 4 oder mehr nicht.
Vermutlich liegt es gar nicht an der Bewertungsfunktion, sondern an überprüfePatt() oder überprüfeMatt() das dann nicht rechzeitig abgebrochen wird. So wie das für mich aussieht, sind die Bewertungsfunktionen recht ähnlich, bei mir wird nur noch nch dem Spieler unterschieden. Oder liege ich da jetzt komplett falsch?
 
Ich habe auf diese Seite mal geschaut: https://www.chessprogramming.org/Negamax .

Java:
import java.util.List;

public class CN {

    int negaMax(int depth) {
        if (depth == 0) {
            return evaluate();
        }
        int max = Integer.MIN_VALUE;
        for (Move m : moves(depth)) { /* ??? */
            int score = -negaMax(depth - 1);
            if (score > max) {
                max = score;
            }
        }
        return max;
    }

    private int evaluate() {
        int score, materialWeight = 0, numWhitePieces = 0, numBlackPieces = 0, who2move = 0;
        return score = materialWeight * (numWhitePieces - numBlackPieces) * who2move;
    }

    private Iterable<Move> moves(int depth) {
        return List.of(new Move(), new Move(), new Move());
    }

}

class Move { }
Bei den drei Fragezeichen und moves bin ich mir unsicher...
Aber an sich ist der Algorithmus ja nicht schwer...

Die Bewertungsfunktion... keine Ahnung. :D (Doch... etwas.. aber das geht in Richtung schwarze Magie...)
 
Jetzt wird der erste Zug auch bei einer Suchtiefe von 4 oder 5 anscheinend richtig ausgegeben. Nur die drauf folgenden Bewertungen sind nicht mehr richtig(Die Züge update ich im Brett).

Suchtiefe 4:
1. Bewertung 103 Weiß
2. Bewertung 13 Schwarz
3. Bewertung 13 Weiß
 
Passende Stellenanzeigen aus deiner Region:

Neue Themen

Oben