Probleme mit Negamax-Algorithmus

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.
 

member42

Aktives Mitglied
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;
}
 

httpdigest

Top Contributor
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.
 

mihe7

Top Contributor
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.
 

member42

Aktives Mitglied
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.
 

mihe7

Top Contributor
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
}
 

member42

Aktives Mitglied
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?
 
X

Xyz1

Gast
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...)
 

member42

Aktives Mitglied
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ß
 

member42

Aktives Mitglied
Hast Du mal ein Beispiel?
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;
        }
 

mrBrown

Super-Moderator
Mitarbeiter
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.
 

mrBrown

Super-Moderator
Mitarbeiter
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.
 

member42

Aktives Mitglied
Vielen Dank. Es scheint jetzt zu funktionieren.
Edit: Durch was für eine Datenstruktur sollte ich das Array den ersetzen?
 
Zuletzt bearbeitet:

member42

Aktives Mitglied
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) {...}
}
 

mrBrown

Super-Moderator
Mitarbeiter
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.
 

member42

Aktives Mitglied
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.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
C Probleme beim Erstellen eines runnable-jar files Allgemeine Java-Themen 1
S Umstellung von File auf Path - Probleme mit Stream Allgemeine Java-Themen 5
C Probleme mit javax.mail.Session Allgemeine Java-Themen 8
M tomcat probleme Allgemeine Java-Themen 1
N Division macht Probleme Allgemeine Java-Themen 14
B Java Reflection Probleme beim wehcselseitigen Referenzieren zweier Klassen/Objekte Allgemeine Java-Themen 14
MarvinsDepression Probleme mit relativem Dateipfad Allgemeine Java-Themen 1
G Geotools Probleme nach PC-Wechsel Allgemeine Java-Themen 6
nibe1501 GUI Probleme Allgemeine Java-Themen 16
C Probleme mit dem WindowBuilder Allgemeine Java-Themen 3
P Selenium . Probleme ein Iron Icon Element anzusprechen Allgemeine Java-Themen 2
B Compiler-Fehler Probleme beim Kompilieren mit Jsoup Allgemeine Java-Themen 8
K VisualVM Profiling Remote Probleme Allgemeine Java-Themen 1
O Leerzeichen und Umlaute im Pfad einer Java Applikation machen Probleme Allgemeine Java-Themen 13
M Probleme bei Eclipse wenn ich entpacke Allgemeine Java-Themen 15
D Regex Probleme Allgemeine Java-Themen 2
M Probleme jar datei. Allgemeine Java-Themen 2
L Vererbung Verständnis Probleme Vererbung Allgemeine Java-Themen 2
Dann07 Probleme mit OpenAL Allgemeine Java-Themen 0
V Threads Probleme beim Aufrufen von Methoden einer anderen Klasse (Threads) Allgemeine Java-Themen 14
V Compiler-Fehler Online Compiler Probleme Allgemeine Java-Themen 4
M Probleme mit BigDecimal Allgemeine Java-Themen 1
T Probleme mit NumberFormat Allgemeine Java-Themen 5
J Probleme exe-Start mit Task Scheduler Allgemeine Java-Themen 1
B Input/Output Probleme beim Ausführen von Shell-Befehlen mit Java Allgemeine Java-Themen 28
J Probleme beim einbinden von Zip4j library Allgemeine Java-Themen 6
F Variablen Palindromzahl (Probleme mit Methode) Allgemeine Java-Themen 9
K Data Konverter - Probleme mit Byte[] Kodierung Allgemeine Java-Themen 3
T Probleme mit dem Pfad zum Propertie file Allgemeine Java-Themen 7
H Swing HashMap zu Tabelle macht mir Probleme Allgemeine Java-Themen 4
Neoline Interpreter-Fehler Probleme mit Arrays.toString Allgemeine Java-Themen 7
F SQLite mit Java / Probleme beim INSERT Befehl Allgemeine Java-Themen 4
J Erste Schritte Probleme mit der Hauptklasse Allgemeine Java-Themen 14
J Tetris Probleme bei Klassen Allgemeine Java-Themen 14
J MinMax VierGewinnt Probleme Allgemeine Java-Themen 22
J Probleme mit CodeCoverage und Lombok Equals Allgemeine Java-Themen 1
S Eclipse Probleme beim Implementieren / Ausführen von jUnit 5-Test Suites Allgemeine Java-Themen 14
R Snake Probleme Allgemeine Java-Themen 2
A Probleme beim Verstehen einer Aufgabenstellung Allgemeine Java-Themen 11
RalleYTN 3D Objekt Translation basierend auf Rotation (Probleme mit Z Rotation) Allgemeine Java-Themen 0
Bluedaishi Druck Probleme mit PDF dateien Allgemeine Java-Themen 4
G Ant Probleme bei einer Installation die Apache ant+ivy verwendet Allgemeine Java-Themen 14
E TableView Probleme Allgemeine Java-Themen 7
perlenfischer1984 Probleme beim Mocken Allgemeine Java-Themen 6
S Kaffemaschine Programmierung Probleme Allgemeine Java-Themen 2
K Threads Runtime und Process Probleme Allgemeine Java-Themen 3
S Probleme mit unterschiedlichen Java-Versionen (Mac OS X 10.11) Allgemeine Java-Themen 0
S Event Handling keyPressed()-Probleme Allgemeine Java-Themen 2
VfL_Freak Große und seltsame Probleme nach Java-Update auf V1.8.0_91 Allgemeine Java-Themen 3
P Probleme mit Grafik (Java) Allgemeine Java-Themen 6
R probleme beim starten von jar unter linux Allgemeine Java-Themen 2
H Probleme mit DAY_OF_WEEK Allgemeine Java-Themen 4
Arif Probleme mit NullPointerException Allgemeine Java-Themen 2
E Probleme mit nextInt() und Exception Allgemeine Java-Themen 35
Streeber Probleme mit AWT-EventQueue: ArrayList Elemente hinzufügen Allgemeine Java-Themen 1
D Performance-Probleme mit Joda-Time Allgemeine Java-Themen 3
M Probleme beim rechnen, bei Zahlen mit führenden Nullen. Allgemeine Java-Themen 7
RalleYTN Probleme mit Encrypting Allgemeine Java-Themen 10
M Probleme mit Schriftarten PDFBox Allgemeine Java-Themen 3
J Probleme mit der Java-Runtime Allgemeine Java-Themen 10
G Probleme mit BufferedWriter und URL Allgemeine Java-Themen 4
S Probleme mit meinem MacBook Pro DRINGEND HILFE erbeten! Allgemeine Java-Themen 17
Androbin Interpreter-Fehler Probleme mit Rekursion - StackOverflowError Allgemeine Java-Themen 8
E JCuda-0.6.5 Probleme beim ausführen der Datei Allgemeine Java-Themen 0
M Runtime.exec() verursacht auf manchen Systemen Probleme - Ursache unklar Allgemeine Java-Themen 2
W JNDI - LDAP - Probleme beim editieren von Usern Allgemeine Java-Themen 0
R DBUnit Performance Probleme Allgemeine Java-Themen 0
S Probleme mit Collection Allgemeine Java-Themen 7
L Probleme mit Jar Allgemeine Java-Themen 6
N Zahlensysteme umrechnen; Probleme beim Umwandeln Allgemeine Java-Themen 4
K OOP OOP Gui Spiel + Vererbungen Probleme durch Nichtwissen!! Allgemeine Java-Themen 1
F Java Native/Shared Library (.so) laden macht Probleme Allgemeine Java-Themen 3
J Synchronized Probleme Allgemeine Java-Themen 7
J Java Progressbar & Download Probleme Allgemeine Java-Themen 10
S Probleme mit dem filechooser Allgemeine Java-Themen 1
J Comperator Probleme Allgemeine Java-Themen 4
A Probleme beim auslesen von Quelltext (HTML) Allgemeine Java-Themen 5
S Probleme mit Webappplikation Allgemeine Java-Themen 5
L Plötzlich Probleme mit der JVM :( Allgemeine Java-Themen 6
S starke performance probleme des forums Allgemeine Java-Themen 10
K Probleme bei Berechnung der Komplexität Allgemeine Java-Themen 7
R JRE Ablaufdatum seit 7u10 - Probleme bei selbst ausgelieferter JRE bekannt? Allgemeine Java-Themen 3
H Reg Exp Probleme Allgemeine Java-Themen 5
M Classpath Probleme bei JAR Generierung Allgemeine Java-Themen 2
S Probleme mit JAVA-Installation Allgemeine Java-Themen 3
D Probleme bei for-Schleife Allgemeine Java-Themen 4
R Probleme mit Javadoc Allgemeine Java-Themen 2
G Gson Probleme Allgemeine Java-Themen 2
P KI für TicTacToe programmieren > Probleme Allgemeine Java-Themen 2
M Google App Engine macht Probleme Allgemeine Java-Themen 4
H Probleme mit finally-Block und close() Allgemeine Java-Themen 4
F 2d array probleme Allgemeine Java-Themen 2
M 3D-Grafik Probleme beim drehen von Objekten Allgemeine Java-Themen 9
T Interface Probleme Allgemeine Java-Themen 8
C Eclipse Probleme bei selbst erstelltem Algorithmus Allgemeine Java-Themen 2
M Probleme mit String in Label übergeben. Allgemeine Java-Themen 6
H MediaManager Fragen/Probleme Allgemeine Java-Themen 6
U Probleme mit Kopiervorgang Allgemeine Java-Themen 3
S Probleme beim Auslesen einer Liste Allgemeine Java-Themen 8
S CardLayout Probleme (Zinsrechner) Allgemeine Java-Themen 4

Ähnliche Java Themen

Neue Themen


Oben