Probleme mit Negamax-Algorithmus

M

member42

Aktives Mitglied
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.
 
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.
 
mihe7 hat gesagt.:
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.
Zum Vergrößern anklicken....
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. 😀 (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ß
 
mihe7 hat gesagt.:
Hast Du mal ein Beispiel?
Zum Vergrößern anklicken....
Irgendwie kann ich das was ich im vorherigen Post meinte nicht mehr rekonstruieren, weil ich einiges im Programm verändert habe. (Es funktioniert aber immer noch nicht) Ich verwende jetzt auch eine Brettkopie, vorher hatte ich die Züge auf dem Brett ja direkt geändert. Ist meine negaMax Methode von der Logik her soweit richtig?

Java: 
private int negaMax(int spieler, int tiefe) { // Weiß 1 , Schwarz -1
           
            int maxWert = Integer.MIN_VALUE;           
            ArrayList<Zug> züge = generiereZüge(kopie, spieler);                      
           
            if(tiefe == 0 || züge.size() == 0) { // Keine Züge mehr                                            
                brettAusgeben(kopie);
                aufrufe++;
                return bewerten(kopie,  tiefe); // Hier wird dann Patt und Matt überprüft
            }
          
            for(Zug z: züge) {
         
                kopie = kopiereBrett(brett);
                kopie[z.vonX][z.vonY] = 0; // altes Feld
                kopie[z.nachX][z.nachY] = z.figur; // neues Feld
                              
                int wert = -negaMax(-spieler, tiefe - 1);
                                           
                if(wert > maxWert) {
                    maxWert = wert;

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

            }
            return maxWert;
        }
 
Das du die Kopie nicht weiter gibst und in negaMax immer eine neue Kopie von Brett anlegst, sieht auf den ersten Blick falsch aus. Vielleicht passiert da aber auch irgendwo Magie, die hier nicht sichtbar ist.
 
Statt irgendwelche Instanzvariablen zu benutzen, kannst du das Brett einfach als Parameter weiter geben.
Die Signatur müsste dann grob so sein: int negaMax(int spieler, int tiefe, int[][] brett) (wobei du das Array noch durch eine sinnvolle Datenstruktur ersetzen solltest). Überall, wo du das aktuelle Brett brauchst, benutzt du dann das Argument.

In der Schliefe kopierst du dann das übergebene Brett, führst auf der Kopie den Zug durch, und gibst die Kopie an den Rekursiven Aufruf weiter.
 
Vielen Dank. Es scheint jetzt zu funktionieren.
Edit: Durch was für eine Datenstruktur sollte ich das Array den ersetzen?
 
Zuletzt bearbeitet:
Habe nochmal ne Frage zu der Bewertungsfunktion beim Negamaxalgorithmus, da ich mir noch ziemlich unsicher bin..
Kann ich in der Bewertungsfunktion zwischen schwarzen und weißen Spieler unterscheiden und bei welchem der Spieler muss ich dann negative Werte zurückgeben?
Java: 
private int bewerten(int b[][], int spieler, int tiefe) {
if (spieler == weiß) {...}
if (spieler == schwarz) {...}
}
 
Du solltest das immer aus Sicht von weiß zurückgeben. Wenn weiß am Zug und Matt ist (also weiß schwarz matt setzt) positive Werte, wenn Schwarz am Zug ist negative Werte.
 
Da ich das mit der Bewertung beim negamax verwirrend finde habe ich jetzt stattdessen Minmax ausprobiert. Die Laufzeit vom minmax ist nur deutlich höher. Woran liegt das? ich dachte eigentlich das beide ungefähr gleich von der Laufzeit wären.
 

Aktuelle Jobs

Neue Themen

Ähnliche Themen

negamax-Algorithmus für Tic-Tac-Toe spielt manchmal falsch
Antworten: 10
Negamax-Algorithmus
Antworten: 7
Negamax Evaluierung
Antworten: 8
NegaMax für TicTacToe in JS gewinnt nicht...
Antworten: 11
Probleme mit Algorithmus
Antworten: 3

Zurück
Oben