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

coffee drinker · 12. Jan 2023

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 · 12. Jan 2023

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.

coffee drinker · 12. Jan 2023

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. 🙁

coffee drinker · 13. Jan 2023

Hab es endlich geschafft. 😵 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. 😱

KonradN · 13. Jan 2023

coffee drinker hat gesagt.:
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.

coffee drinker hat gesagt.:
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.

coffee drinker · 13. Jan 2023

KonradN hat gesagt.:
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 · 13. Jan 2023

coffee drinker hat gesagt.:
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...

Aber die Methode prüft ja nur, ob jemand gewonnen hat. Die Gewichtung erfolgt doch dann im eigentlichen Algorithmus welche ja die Tiefe kennt.

coffee drinker · 13. Jan 2023

KonradN hat gesagt.:
Aber die Methode prüft ja nur, ob jemand gewonnen hat. Die Gewichtung erfolgt doch dann im eigentlichen Algorithmus welche ja die Tiefe kennt.

Laut ChatGpt soll die Methode evaluate(...) die Gewichtung vornehmen. 😉

KonradN · 14. Jan 2023

coffee drinker hat gesagt.:
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).

coffee drinker · 14. Jan 2023

KonradN hat gesagt.:
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 · 14. Jan 2023

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.

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

coffee drinker

Mitglied

KonradN

Super-Moderator

coffee drinker

Mitglied

coffee drinker

Mitglied

KonradN

Super-Moderator

coffee drinker

Mitglied

KonradN

Super-Moderator

coffee drinker

Mitglied

KonradN

Super-Moderator

coffee drinker

Mitglied

KonradN

Super-Moderator

Aktuelle Jobs

Neue Themen

Ähnliche Themen