negamax-Algorithmus für Tic-Tac-Toe spielt manchmal falsch

Spieler A soll immer zufällig wählen, und Spieler B negamax:

Java:
import java.util.Random;

public class TicTacToeAI {
    public int evaluate(int[] b) {
        for (int i = 0; i < 3; i++) {
            int j;
            for (j = 0; j < 2; j++) {
                int idx1 = 3 * i + j;
                int idx2 = 3 * i + j + 1;
                if (b[idx1] == 0 || b[idx2] == 0 || b[idx1] != b[idx2]) {
                    break;
                }
            }
            if (j == 2) {
                return b[3 * i];
            }

            for (j = 0; j < 2; j++) {
                int idx1 = j * 3 + i;
                int idx2 = (j + 1) * 3 + i;
                if (b[idx1] == 0 || b[idx2] == 0 || b[idx1] != b[idx2]) {
                    break;
                }
            }
            if (j == 2) {
                return b[i];
            }

            for (j = 0; j < 2; j++) {
                if (i == 2) {
                    break;
                }
                int idx1 = j * 4 - i * (j - 1) * 2;
                int idx2 = (j + 1) * 3 + j + 1 - i * j * 2;
                if (b[idx1] == 0 || b[idx2] == 0 || b[idx1] != b[idx2]) {
                    break;
                }
            }
            if (j == 2) {
                return b[4];
            }
        }
        return 0;
    }

    public int negamax(int depth, int player, int[] board) {
        if (depth == 0) {
            return evaluate(board);
        }
        int bestValue = Integer.MIN_VALUE;
        for (int i = 0; i < 9; i++) {
            if (board[i] == 0) {
                board[i] = player;
                int value = -negamax(depth - 1, -player, board);
                board[i] = 0;
                bestValue = Math.max(bestValue, value);
            }
        }
        return bestValue;
    }

    public void simulateRandomA() {
        int[] board = new int[9];
        for (int i = 0; i < 9; i += 2) {
            int move = new Random().nextInt(9);
            while (board[move] != 0) {
                move = new Random().nextInt(9);
            }
            board[move] = -1;
            printBoard(board);
            int best = -1;
            int best_nm = Integer.MAX_VALUE;
            for (int j = 0; j < 9; j++) {
                if (board[j] == 0) {
                    board[j] = +1;
                    int nm = negamax(9 - i - 4, -1, board);
                    // Weshalb "- 4" ?
                    board[j] = 0;
                    if (best_nm > nm) {
                        best = j;
                        best_nm = nm;
                    }
                }
            }
            if (best != -1) {
                board[best] = +1;
                printBoard(board);
            }
        }
    }

    private int number = 1;

    public void printBoard(int[] board) {
        System.out.println("Number: " + number++);
        for (int i = 0; i < 9; i++) {
            if (board[i] == -1) {
                System.out.print("a ");
            }
            if (board[i] == +1) {
                System.out.print("b ");
            }
            if (board[i] == 0) {
                System.out.print("_ ");
            }
            if ((i + 1) % 3 == 0) {
                System.out.println();
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        new TicTacToeAI().simulateRandomA();
    }
}

Aber etwas stimmt nicht, zum Beispiel sollte er hier:

Code:
Number: 1
_ _ _
a _ _
_ _ _

Number: 2
b _ _
a _ _
_ _ _

Number: 3
b _ _
a _ a
_ _ _

Number: 4
b _ b
a _ a
_ _ _

Number: 5
b _ b
a a a
_ _ _

Number: 6
b b b
a a a
_ _ _

Number: 7
b b b
a a a
a _ _

Number: 8
b b b
a a a
a b _

Number: 9
b b b
a a a
a b a

im vierten Zug die Mitte besetzen (sonst hätte Spieler A ja sofort gewonnen)...

Habt ihr eine Idee?

Anmerkung: Ich habe nicht Chat gpt danach gefragt.
 

KonradN

Super-Moderator
Mitarbeiter
Deine evaluate Methode sieht so nicht korrekt aus. Aber da diese auch schlicht zu unleserlich ist, macht es kaum Sinn, diese zu kontrollieren.

Aber in der ersten Schleife prüfst Du bei i=0 und j von 0-2 die Paare: 0,1; 1,2 und 2,3

Wenn die Feld-Ids
0 1 2
3 4 5
6 7 8
sind, dann stelle ich mir die Frage, wozu du die Felder mit den ids 2 und 3 vergleichst.

Die Gedankengänge von Dir, was Du wo prüfen willst müsstest Du einmal erläutern. Dann kann man da gerne etwas herleiten und schauen, ob man da auf Deine Formeln kommt. Sprich: genau das, was wir vor Kurzem schon einmal in einem Thread gemacht haben, wo Du für die Diagonalen die unleserlichen Formeln aus Zeile 33 / 34 bekommen hast.
 
Ok, hier noch mal etwas weniger verklausuliert:

Java:
import java.util.Random;

public class TicTacToeAI {
    public int evaluate(int[] b) {
        if (
                        b[0] == -1 && b[1] == -1 && b[2] == -1 ||
                        b[3] == -1 && b[4] == -1 && b[5] == -1 ||
                        b[6] == -1 && b[7] == -1 && b[8] == -1 ||
                        b[0] == -1 && b[3] == -1 && b[6] == -1 ||
                        b[1] == -1 && b[4] == -1 && b[7] == -1 ||
                        b[2] == -1 && b[5] == -1 && b[8] == -1 ||
                        b[0] == -1 && b[4] == -1 && b[8] == -1 ||
                        b[2] == -1 && b[4] == -1 && b[6] == -1
        ) {
            return -1;
        }
        if (
                        b[0] == 1 && b[1] == 1 && b[2] == 1 ||
                        b[3] == 1 && b[4] == 1 && b[5] == 1 ||
                        b[6] == 1 && b[7] == 1 && b[8] == 1 ||
                        b[0] == 1 && b[3] == 1 && b[6] == 1 ||
                        b[1] == 1 && b[4] == 1 && b[7] == 1 ||
                        b[2] == 1 && b[5] == 1 && b[8] == 1 ||
                        b[0] == 1 && b[4] == 1 && b[8] == 1 ||
                        b[2] == 1 && b[4] == 1 && b[6] == 1
        ) {
            return 1;
        }
        return 0;
    }

    public int negamax(int depth, int player, int[] board) {
        if (depth == 0) {
            return evaluate(board);
        }
        int bestValue = Integer.MIN_VALUE;
        for (int i = 0; i < 9; i++) {
            if (board[i] == 0) {
                board[i] = player;
                int value = -negamax(depth - 1, -player, board);
                board[i] = 0;
                bestValue = Math.max(bestValue, value);
            }
        }
        return bestValue;
    }

    public void simulateRandomA() {
        int[] board = new int[9];
        for (int i = 0; i < 9; i += 2) {
            int move = new Random().nextInt(9);
            while (board[move] != 0) {
                move = new Random().nextInt(9);
            }
            board[move] = -1;
            printBoard(board);
            int best = -1;
            int best_nm = Integer.MAX_VALUE;
            for (int j = 0; j < 9; j++) {
                if (board[j] == 0) {
                    board[j] = +1;
                    int nm = negamax(9 - i - 2, -1, board);
                    board[j] = 0;
                    if (best_nm > nm) {
                        best = j;
                        best_nm = nm;
                    }
                }
            }
            if (best != -1) {
                board[best] = +1;
                printBoard(board);
            }
        }
    }

    private int number = 1;

    public void printBoard(int[] board) {
        System.out.println("Number: " + number++);
        for (int i = 0; i < 9; i++) {
            if (board[i] == -1) {
                System.out.print("a ");
            }
            if (board[i] == +1) {
                System.out.print("b ");
            }
            if (board[i] == 0) {
                System.out.print("_ ");
            }
            if ((i + 1) % 3 == 0) {
                System.out.println();
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        new TicTacToeAI().simulateRandomA();
    }
}

Aber er spielt leider immer noch falsch:

Code:
Number: 1
_ _ _
_ _ _
_ _ a

Number: 2
b _ _
_ _ _
_ _ a

Number: 3
b _ _
_ _ a
_ _ a

Number: 4
b b _
_ _ a
_ _ a

Number: 5
b b _
_ _ a
a _ a

Number: 6
b b b
_ _ a
a _ a

Number: 7
b b b
_ _ a
a a a

Number: 8
b b b
b _ a
a a a

Number: 9
b b b
b a a
a a a

Der vierte Spielzug wird wieder falsch gewählt. :(
 
Hab es endlich geschafft. o_O Jetzt gewinnt meistens das o (Spieler 2, negamax) oder es wird unentschieden gespielt:

Java:
import java.util.Random;

public class TicTacToeAI {
    public int evaluate(int depth, int player, int[] b) {
        if (b[0] == -1 && b[1] == -1 && b[2] == -1 ||
                b[3] == -1 && b[4] == -1 && b[5] == -1 ||
                b[6] == -1 && b[7] == -1 && b[8] == -1 ||
                b[0] == -1 && b[3] == -1 && b[6] == -1 ||
                b[1] == -1 && b[4] == -1 && b[7] == -1 ||
                b[2] == -1 && b[5] == -1 && b[8] == -1 ||
                b[0] == -1 && b[4] == -1 && b[8] == -1 ||
                b[2] == -1 && b[4] == -1 && b[6] == -1
        ) {
            return -1 * player * depth;
        }
        if (b[0] == 1 && b[1] == 1 && b[2] == 1 ||
                b[3] == 1 && b[4] == 1 && b[5] == 1 ||
                b[6] == 1 && b[7] == 1 && b[8] == 1 ||
                b[0] == 1 && b[3] == 1 && b[6] == 1 ||
                b[1] == 1 && b[4] == 1 && b[7] == 1 ||
                b[2] == 1 && b[5] == 1 && b[8] == 1 ||
                b[0] == 1 && b[4] == 1 && b[8] == 1 ||
                b[2] == 1 && b[4] == 1 && b[6] == 1
        ) {
            return player * depth;
        }
        return 0;
    }

    public int negamax(int depth, int player, int[] board) {
        int e = evaluate(depth, player, board);
        if (depth == 0 || e != 0) {
            return e;
        }
        int bestValue = Integer.MIN_VALUE;
        for (int i = 0; i < 9; i++) {
            if (board[i] == 0) {
                board[i] = player;
                int value = -negamax(depth - 1, -player, board);
                board[i] = 0;
                bestValue = Math.max(bestValue, value);
            }
        }
        return bestValue;
    }

    public void simulateRandomA() {
        int[] board = new int[9];
        for (int i = 0; i < 9; i += 2) {
            int move = new Random().nextInt(9);
            while (board[move] != 0) {
                move = new Random().nextInt(9);
            }
            board[move] = -1;
            printBoard(board);
            int best = -1;
            int best_nm = Integer.MAX_VALUE;
            for (int j = 0; j < 9; j++) {
                if (board[j] == 0) {
                    board[j] = +1;
                    int nm = negamax(9 - i - 2, -1, board);
                    board[j] = 0;
                    if (best_nm > nm) {
                        best = j;
                        best_nm = nm;
                    }
                }
            }
            if (best != -1) {
                board[best] = +1;
                printBoard(board);
            }
        }
    }

    private int number = 1;

    public void printBoard(int[] board) {
        System.out.println("Number: " + number++);
        for (int i = 0; i < 9; i++) {
            if (board[i] == -1) {
                System.out.print("x ");
            }
            if (board[i] == +1) {
                System.out.print("o ");
            }
            if (board[i] == 0) {
                System.out.print("_ ");
            }
            if ((i + 1) % 3 == 0) {
                System.out.println();
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        new TicTacToeAI().simulateRandomA();
    }
}

Es lag daran, dass evaluate natürlich auch int depth, int player braucht, um eine valide Aussage treffen zu können, und dass bei e != 0 natürlich auch abgebrochen werden muss.

Danke an alle Helfenden. :eek:
 

KonradN

Super-Moderator
Mitarbeiter
Es lag daran, dass evaluate natürlich auch int depth, int player braucht, um eine valide Aussage treffen zu können,
Nein, das bezweifle ich. Es muss ja nur eine Stellung geprüft werden. Diese Prüfung muss der Algorithmus aber nach jedem Zug, den er macht, anstoßen und nicht nur, wenn alle Felder belegt sind.

und dass bei e != 0 natürlich auch abgebrochen werden muss.
Genau, nach jeder Prüfung, bei der das Ergebnis ist, dass ein Spieler gewonnen hat, muss der Algorithmus keine weiter folgenden Züge machen.
 
Es muss ja nur eine Stellung geprüft werden. Diese Prüfung muss der Algorithmus aber nach jedem Zug, den er macht, anstoßen und nicht nur, wenn alle Felder belegt sind.
Also das int depth braucht die Methode, um eine Gewichtung der Evaluation vorzunehmen... Sprich: Ein früher Sieg ist mehr wert als ein späterer...

So hätte ich das zumindest gedacht - und ich habe den Code schrittweise erweitert und nach jeder Änderung geprüft, ob es dann funktioniert.
 

KonradN

Super-Moderator
Mitarbeiter
Laut ChatGpt soll die Methode evaluate(...) die Gewichtung vornehmen. ;)
Das ist ein tolles Argument. Ich finde es sehr interessant, weil so eine Entwcklung von jemandem vorher gesagt (und befürchtet) wurde.

Das muss man aber nicht weiter thematisieren. Ich freue mich, dass Du mit Deinem Algorithmus zufrieden bist und werde verzichten, da tiefer drauf ein zu gehen, was ich daran alles verändern würde (incl. dem wieso).
 
Das ist ein tolles Argument. Ich finde es sehr interessant, weil so eine Entwcklung von jemandem vorher gesagt (und befürchtet) wurde.

Das muss man aber nicht weiter thematisieren. Ich freue mich, dass Du mit Deinem Algorithmus zufrieden bist und werde verzichten, da tiefer drauf ein zu gehen, was ich daran alles verändern würde (incl. dem wieso).
Möchtest du darüber reden, was dich weshalb daran stört?

Der Code erfüllt meine Anforderungen, ist effizient, gut strukturiert und enthält keine Anti-Pattern... Es würde genügen, wenn man einfach sagt, ist ok so.

Deshalb verstehe ich deine negative Abwertung nicht, bzw. nicht ganz...
 

KonradN

Super-Moderator
Mitarbeiter
Nein Tobias, wir hatten in der Vergangenheit oft genug das Vergnügen, über Clean Code zu reden und gebracht hat es eigentlich nie etwas. Daher erspare ich mir die Zeit.

Und wie gesagt: ich freue mich, dass du zufrieden bist.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
laxla123 Eigenschaften eines Algorithmus (determiniert vs.. deterministisch) Java Basics - Anfänger-Themen 2
C Gewinnspiel erstellen mit Algorithmus Java Basics - Anfänger-Themen 3
H Minimax Algorithmus in Tic Tac Toe Java Basics - Anfänger-Themen 3
M Minimax-Algorithmus für Vier gewinnt Java Basics - Anfänger-Themen 11
ohneInformatik; Trockentest Algorithmus, mathematischen Zusammenhang angeben Java Basics - Anfänger-Themen 3
M Minimax-Algorithmus Java Basics - Anfänger-Themen 17
mervanpolat Binary Search Algorithmus ausführen Java Basics - Anfänger-Themen 1
J Rekursiver Algorithmus Java Basics - Anfänger-Themen 9
M monte carlo Algorithmus für 4 gewinnt Java Basics - Anfänger-Themen 12
izoards Sortier Algorithmus für Bounding Box Elememte Links nach Rechts und von Oben nach Unten Java Basics - Anfänger-Themen 33
S Algorithmus entwicklen, der zu einem gegebenen Datum die Jahreszeit ermittelt Java Basics - Anfänger-Themen 13
rosima26 Merge-Algorithmus Java Basics - Anfänger-Themen 53
C Ein Algorithmus soll schneller werden Java Basics - Anfänger-Themen 24
D Dijkstra Algorithmus Hilfe!! Java Basics - Anfänger-Themen 9
U Den Kuchen aufteilen - aber wie? (Rebalancing-Algorithmus) Java Basics - Anfänger-Themen 14
s_1895 Pseudocode Naiver Algorithmus Java Basics - Anfänger-Themen 17
H String verschlüsseln - eigener Algorithmus Java Basics - Anfänger-Themen 104
T Algorithmus für Index mit min-Wert Java Basics - Anfänger-Themen 2
Düsseldorf2002 Testen meines Algorithmus Java Basics - Anfänger-Themen 1
D Primzahlen Rechner nach Eratostenes von Kyrene Algorithmus Java Basics - Anfänger-Themen 2
KogoroMori21 Frage zum Euklidischen Algorithmus Java Basics - Anfänger-Themen 11
S Algorithmus java searchAll IKey Java Basics - Anfänger-Themen 4
S Algorithmus Datensätze einfügen wenn... Java Basics - Anfänger-Themen 26
KogoroMori21 MergeSort Algorithmus Java Basics - Anfänger-Themen 2
KogoroMori21 Textdatei einlesen im Array (Selection Sort Algorithmus) Java Basics - Anfänger-Themen 3
fendix Compiler-Fehler Algorithmus zur Bestimmung von Primzahlen Java Basics - Anfänger-Themen 7
S Algorithmus (reelle Zahl <65536 von dezimal zu dual) max. 10 Nachkommastellen Java Basics - Anfänger-Themen 4
G Algorithmus Graphen Java Basics - Anfänger-Themen 10
D Input/Output fehlerhafter Algorithmus zum Ersetzen von Array-Werten nach logischem Schema Java Basics - Anfänger-Themen 1
N Selection Algorithmus: Methode wird nicht erkannt (BlueJ) Java Basics - Anfänger-Themen 3
U Meinung zum Dijkstra Algorithmus Java Basics - Anfänger-Themen 6
U Dijkstra Algorithmus Laufzeit Java Basics - Anfänger-Themen 3
L Math.exp also eigenen Algorithmus Java Basics - Anfänger-Themen 2
Kirby.exe Algorithmus entwickeln Java Basics - Anfänger-Themen 37
M Algorithmus Max-Heap? Java Basics - Anfänger-Themen 3
I Labyrinth auf der Basis eines rekursiven Algorithmus Java Basics - Anfänger-Themen 27
CptK Best Practice Algorithmus nach jedem Schritt zum Visualisieren pausieren Java Basics - Anfänger-Themen 3
A Algorithmus effizienter machen Java Basics - Anfänger-Themen 1
V Algorithmus zur fortlaufenden Berechnung des duechscjnt Java Basics - Anfänger-Themen 1
M Dijkstra Algorithmus in Graphen auf mehrere verschiedene Knoten anwenden lassen Java Basics - Anfänger-Themen 11
O Labyrinth Algorithmus Java Basics - Anfänger-Themen 3
G Quicksort Algorithmus Java Basics - Anfänger-Themen 12
S Binäre-Suche Algorithmus Java Basics - Anfänger-Themen 1
D Algorithmus in Pseudocode mit log2(n) Operationen erstellen Java Basics - Anfänger-Themen 3
C Laufzeit eines Sortier-Algorithmus ermitteln Java Basics - Anfänger-Themen 4
H aufgabe java luhn algorithmus Java Basics - Anfänger-Themen 10
A Datenstruktur für Savings Algorithmus und Planung von kleinen Programmierprojekten Java Basics - Anfänger-Themen 1
J Algorithmus für eine Reihe implementieren Java Basics - Anfänger-Themen 2
S Dijkstra Algorithmus funktioniert nicht Java Basics - Anfänger-Themen 4
N Denksportaufgabe durch Algorithmus lösen Java Basics - Anfänger-Themen 2
S Problem mit einem rekursivem FloodFill Algorithmus Java Basics - Anfänger-Themen 62
B Algorithmus Square und Multiply Java Basics - Anfänger-Themen 3
J Algorithmus - Strings auf eigene Reihenfolge miteinander vergleichen Java Basics - Anfänger-Themen 4
D Frage Boyer-Moore Algorithmus Java Basics - Anfänger-Themen 7
M Komplexität Algorithmus Java Basics - Anfänger-Themen 8
H Zeichen im algorithmus Java Basics - Anfänger-Themen 4
B Code Verständnisfragen - FLoyd Warshall Algorithmus Java Basics - Anfänger-Themen 1
B Algorithmus zum entmischen einer Zahlenfolge Java Basics - Anfänger-Themen 15
X Minimax-Algorithmus über alle Kanten möglich? - Kanten darstellen Java Basics - Anfänger-Themen 1
T Algorithmus zur Überprüfung eines binären Suchbaums Java Basics - Anfänger-Themen 2
K Best Practice Algorithmus für Berechnung von Zahlenreihenfolge Java Basics - Anfänger-Themen 12
M Simpler Algorithmus läuft extrem langsam. Java Basics - Anfänger-Themen 3
K Erste Schritte Brute Force Algorithmus Java Basics - Anfänger-Themen 2
L Frage zu BubbleSort Algorithmus Java Basics - Anfänger-Themen 2
B gibt es ein Stundenplan-Algorithmus? Java Basics - Anfänger-Themen 11
O Algorithmus-Problem Java Basics - Anfänger-Themen 5
P Euklidischer Algorithmus Java Basics - Anfänger-Themen 9
L Greates Commong Dividend - euklidischer Algorithmus, modulos not positive Java Basics - Anfänger-Themen 5
J Euklidischer Algorithmus Java Basics - Anfänger-Themen 1
S Quicksort Algorithmus Java Basics - Anfänger-Themen 2
S GraphNode --- Dijkstra Algorithmus : NullPointerException Java Basics - Anfänger-Themen 1
B Rekursive Algorithmus schreiben Java Basics - Anfänger-Themen 8
V Algorithmus in einer Methode ausführen Java Basics - Anfänger-Themen 3
M Implementierung des Knuth-Morris-Pratt-Algorithmus Java Basics - Anfänger-Themen 0
M Dijkstras Algorithmus Java Basics - Anfänger-Themen 5
S Zusammenhang Datenstruktur/Algorithmus Java Basics - Anfänger-Themen 1
M Simulation - Algorithmus Java Basics - Anfänger-Themen 3
F Erste Schritte Hilfe beim Algorithmus finden Java Basics - Anfänger-Themen 8
D Algorithmus für Punkte auf einem Kreis Java Basics - Anfänger-Themen 0
D Algorithmus zu gegebener Laufzeit implementieren Java Basics - Anfänger-Themen 1
B Doppelte Werte aus Array entfernen ohne Import - Algorithmus Java Basics - Anfänger-Themen 5
C Ideen für einen Algorithmus Java Basics - Anfänger-Themen 1
F Best Practice Algorithmus optimieren - Binaeruhr Java Basics - Anfänger-Themen 2
S Euklid Algorithmus zur Berechnung des GGTs Java Basics - Anfänger-Themen 2
L Welcher Algorithmus ist das ? Java Basics - Anfänger-Themen 9
J Rekursiver Horner-Schema-Algorithmus - Verstehe ich ihn richtig? Java Basics - Anfänger-Themen 2
O Java Zufalls-Verteil-Algorithmus Java Basics - Anfänger-Themen 3
P ganz simpler algorithmus Java Basics - Anfänger-Themen 3
C Sortieren ohne Algorithmus Java Basics - Anfänger-Themen 8
J Algorithmus: Grad von floating zu Grad/Minute/Sekunde Java Basics - Anfänger-Themen 3
A Text Verschriebung/Algorithmus(?) Java Basics - Anfänger-Themen 8
R Rekursionsformel für Laufzeit von Algorithmus Java Basics - Anfänger-Themen 3
E Algorithmus für kart. Produkt: als int [] Feld repräsentiert Java Basics - Anfänger-Themen 10
U Peterson Algorithmus Java Basics - Anfänger-Themen 13
algebraiker Collections Bräuchte Hilfe bei dem Algorithmus - LinkedHashMap Java Basics - Anfänger-Themen 2
S A* Path Algorithmus in Java schon vorhanden Java Basics - Anfänger-Themen 3
S Bubble Sort Algorithmus Java Basics - Anfänger-Themen 3
N Unerklärlich: Rekursiver Algorithmus gibt falschen Datentyp zurück... Java Basics - Anfänger-Themen 4
S Algorithmus (Programmablaufplan) Java Basics - Anfänger-Themen 11
S Algorithmus für Spielbaum Java Basics - Anfänger-Themen 5

Ähnliche Java Themen

Neue Themen


Oben