Minimax Algorithmus in Tic Tac Toe

H

HerrInfo

Aktives Mitglied
Hallo zusammen,

ich bin gerade dabei, mich in dem Bereich Algorithmik etwas weiterzubilden und stoße dabei auf folgenden Fehler:
Mein Negamax Algorithmus liefert immer -1 zurück.
Hat jemand von euch eine Idee, woran es liegt?
Hier seht ihr noch meinen entsprechenden Code ausschnitt.

Java: 
package Game_ai;

import java.util.ArrayList;
import java.util.List;
import GUI.GUI;
import static GUI.GUI.*;
import GUI.Winner;
import org.jetbrains.annotations.NotNull;

import static java.lang.Thread.*;


public class Game {

    public static void main(String[] args) throws InterruptedException {
        new Game();
    }
    GUI frame;


    final  int NUM_ACTIONS = 9;
    final int[] board = new int[NUM_ACTIONS];
    int movesRemaining = NUM_ACTIONS;
    int AIMOVE;
    boolean gameEnded = false;
    int move;
    Game() throws InterruptedException {
        frame = new GUI();

        while (!gameEnded) {
            sleep(10);
            if (frame.newButtonClicked) {

                phaseint2darrayzuarray(spiel);
                frame.newButtonClicked = false;
                ausgeben(board);

                switch (whowon(board)){
                    case 'X':
                        xgewonnen = true;
                        System.out.println("X Gewonnen \n Herzlichen Glückwunsch");
                        winner = "Winner: X \n Herzlichen Glückwunsch";
                        new Winner();
                        break;
                    case 'O':
                        ogewonnen = true;
                        System.out.println("O Gewonnen \n Herzlichen Glückwunsch");
                        winner = "Winner: O \n Herzlichen Glückwunsch";
                        new Winner();
                        break;
                    case 'D':



                }
                    phaseint2darrayzuarray(spiel);
                    try {
                        sleep(100);
                    } catch (InterruptedException e) {
                        throw new RuntimeException(e);
                    }
                    aimove(board,2);
                    try {
                        sleep(100);
                    } catch (InterruptedException e) {
                        throw new RuntimeException(e);
                    }
                    if (whowon(board) == 'O'){
                        ogewonnen = true;
                        System.out.println("O Gewonnen \n Herzlichen Glückwunsch");
                        winner = "Winner: O \n Herzlichen Glückwunsch";
                        new Winner();
                    }

                movesRemaining--;
                }
            }
    }
    public void aimove(int[]board, int player){
        AIMOVE = negamax(board, player)[1];
        if (AIMOVE == -1) {
            //throw new RuntimeException("T");
            System.err.println("Random Move");
            dorandomComputerMove();
        } else {
            board[AIMOVE] = 2;
        }
        phasearrayzu2darray(board);
        frame.doupdate();
    }
    public int[] negamax(int @NotNull [] board, int player) {
        move = -1;
        //List of all valid moves
        List<Integer> validMoves = new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            if (board[i] == 0)
                validMoves.add(i);
        }
        //Abbruchbedingung
        int winner = eval(board);
        if (winner != -10 || validMoves.size() < 1)
            return (new int[]{winner, move});
        int bestmovepoints;
        // for Computer
        if (player == 1) {
            bestmovepoints = Integer.MIN_VALUE;
            for (int i = 0; i < validMoves.size(); i++) {
                int[] tmpState = new int[9];
                System.arraycopy(board, 0, tmpState, 0, board.length);
                tmpState[validMoves.get(i)] = 2;

                int val = negamax(tmpState, 2)[0];
                if (val > bestmovepoints) {
                    bestmovepoints = val;
                    move = validMoves.get(i);
                }
            }
        }//Human
        else {
            bestmovepoints = Integer.MAX_VALUE;
            for(int i = 0; i < validMoves.size(); i++) {
                int[] tmpState = new int[9];
                System.arraycopy(board, 0, tmpState, 0, board.length);
                tmpState[validMoves.get(i)] = player;
                int val = negamax(tmpState, 1)[0];
                if(val < bestmovepoints) {
                    bestmovepoints = val;
                    move = validMoves.get(i);
                }
            }
        }
        return (new int[] { bestmovepoints, move });
    }



    private boolean isWinner(int @NotNull [] state, int player)
    {
        return (state[0] == state[1] && state[1] == state[2] && state[0] == player) // horizontal
                || (state[3] == state[4] && state[4] == state[5] && state[3] == player)
                || (state[6] == state[7] && state[7] == state[8] && state[6] == player)
                || (state[0] == state[3] && state[3] == state[6] && state[0] == player) // vertical
                || (state[1] == state[4] && state[4] == state[7] && state[1] == player)
                || (state[2] == state[5] && state[5] == state[8] && state[2] == player)
                || (state[0] == state[4] && state[4] == state[8] && state[0] == player) // diagonal
                || (state[2] == state[4] && state[4] == state[6] && state[2] == player);
    }


    private int eval(int[] state)
    {
        if(isWinner(state, 1))
            return 1;
        else if(isWinner(state, 2))
            return -1;
        else if (movesRemaining <1)
            return 0;
        else
            return -10;
    }


    public void ausgeben(int @NotNull [] daten) {

            for (int j = 0; j < daten.length; j++) {
                System.out.println(daten[j] + "\t");
            }
            System.out.println();
            System.out.println();
            System.out.println();
        }



    private char whowon(int[] board){
         int winner = eval(board);
        return switch (winner) {
            case 1 -> 'X';
            case -1 -> 'O';
            case 0 -> 'D';
            default -> 'f';

        };
    }
    private void phaseint2darrayzuarray(int [] @NotNull [] arr){
        int lauf = 0;
        for (int[] ints : arr) {
            for (int j = 0; j < arr.length; j++) {
                this.board[lauf] = ints[j];
                lauf++;
            }
        }
    }

    private void phasearrayzu2darray(int @NotNull [] arr){
        spiel[0][0] = arr[0];
        spiel[0][1] = arr[1];
        spiel[0][2] = arr[2];
        spiel[1][0] = arr[3];
        spiel[1][1] = arr[4];
        spiel[1][2] = arr[5];
        spiel[2][0] = arr[6];
        spiel[2][1] = arr[7];
        spiel[2][2] = arr[8];
    }

    private void dorandomComputerMove() {
        try {
            int zufallszahl1 = (int) (Math.random() * 9);
            if (ismovelegit(zufallszahl1)) {
                board[zufallszahl1] = 2;
            }else {
                dorandomComputerMove();
            }
            phasearrayzu2darray(board);
                frame.doupdate();
        } catch (StackOverflowError ignored) {
        }
    }
    private boolean ismovelegit(int zahl1){
        return board[zahl1] != 1 && board[zahl1] != 2;
    }
}
 
Hallo,

dein Code ist sehr unübersichtlich! Dennoch ist mir ein Problem aufgefallen:

Du hat nur eine Variable int move;. Innerhalb von negamax rufst du rekursiv negamax auf. Dabei wird der Inhalt von move überschrieben. Dein move ist deshalb nicht in einem konsistenten Zustand.
 
Vielen Dank. Heißt, ich füge eine neue Variable ein, oder? Woran liegt es denn das mein Code so unübersichtlich ist und wie kann ich dies ändern. Vielen Dank im Voraus und auch nochmal vielen Dank für die schnelle Antwort.
 
Ich habe das jetzt mal verändert und noch ein paar andere Kleinigkeiten vorgenommen, aber der oben beschriebene Fehler tritt leider immer noch auf.

Hier seht ihr nochmal meinen aktualisierten Code:
Java: 
package Game_ai;

import java.util.ArrayList;
import java.util.List;
import GUI.GUI;
import static GUI.GUI.*;
import GUI.Winner;
import org.jetbrains.annotations.NotNull;

import static java.lang.Thread.*;


public class Game {

    public static void main(String[] args) throws InterruptedException {
        new Game();
    }
    GUI frame;


    final  int NUM_ACTIONS = 9;
    final int[] board = new int[NUM_ACTIONS];
    int movesRemaining = NUM_ACTIONS;
    int AIMOVE;
    boolean gameEnded = false;
    Game() throws InterruptedException {
        frame = new GUI();

        while (!gameEnded) {
            sleep(10);
            if (frame.newButtonClicked) {

                phaseint2darrayzuarray(spiel);
                frame.newButtonClicked = false;
                ausgeben(board);

                switch (whowon(board)){
                    case 'X':
                        xgewonnen = true;
                        System.out.println("X Gewonnen \n Herzlichen Glückwunsch");
                        winner = "Winner: X \n Herzlichen Glückwunsch";
                        new Winner();
                        break;
                    case 'O':
                        ogewonnen = true;
                        System.out.println("O Gewonnen \n Herzlichen Glückwunsch");
                        winner = "Winner: O \n Herzlichen Glückwunsch";
                        new Winner();
                        break;
                    case 'D':



                }
                    phaseint2darrayzuarray(spiel);
                    aimove(board,2);
                    if (whowon(board) == 'O'){
                        ogewonnen = true;
                        System.out.println("O Gewonnen \n Herzlichen Glückwunsch");
                        winner = "Winner: O \n Herzlichen Glückwunsch";
                        new Winner();
                    }

                movesRemaining--;
                }
            }
    }
    public void aimove(int[]board, int player){
        AIMOVE = negamax(board, player)[1];
        if (AIMOVE == -1) {
            //throw new RuntimeException("T");
            System.err.println("Random Move");
            dorandomComputerMove();
        } else {
            board[AIMOVE] = 2;
        }
        phasearrayzu2darray(board);
        frame.doupdate();
    }
    public int[] negamax(int @NotNull [] board, int player) {
        int move = -1;
        //List of all valid moves
        List<Integer> validMoves = new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            if (board[i] == 0) {
                validMoves.add(i);
            }
        }
        //Abbruchbedingung
        int winner = eval(board);
        if (winner == 0 || validMoves.size() < 1)
            return (new int[]{winner, move});
        int bestmovepoints;
        // for Computer
        if (player == 1) {
            bestmovepoints = Integer.MIN_VALUE;
            for (int i = 0; i < validMoves.size(); i++) {
                int[] tmpState = new int[9];
                System.arraycopy(board, 0, tmpState, 0, board.length);
                tmpState[validMoves.get(i)] = 2;

                int val = negamax(tmpState, 2)[0];
                if (val > bestmovepoints) {
                    bestmovepoints = val;
                    move = validMoves.get(i);
                }
            }
        }//Human
        else {
            bestmovepoints = Integer.MAX_VALUE;
            for(int i = 0; i < validMoves.size(); i++) {
                int[] tmpState = new int[9];
                System.arraycopy(board, 0, tmpState, 0, board.length);
                tmpState[validMoves.get(i)] = player;
                int val = negamax(tmpState, 1)[0];
                if(val < bestmovepoints) {
                    bestmovepoints = val;
                    move = validMoves.get(i);
                }
            }
        }
        return (new int[] { bestmovepoints, move });
    }



    private boolean isWinner(int @NotNull [] state, int player)
    {
        return (state[0] == state[1] && state[1] == state[2] && state[0] == player) // horizontal
                || (state[3] == state[4] && state[4] == state[5] && state[3] == player)
                || (state[6] == state[7] && state[7] == state[8] && state[6] == player)
                || (state[0] == state[3] && state[3] == state[6] && state[0] == player) // vertical
                || (state[1] == state[4] && state[4] == state[7] && state[1] == player)
                || (state[2] == state[5] && state[5] == state[8] && state[2] == player)
                || (state[0] == state[4] && state[4] == state[8] && state[0] == player) // diagonal
                || (state[2] == state[4] && state[4] == state[6] && state[2] == player);
    }


    private int eval(int[] state) // fehler vermutlich hier
    {
        if(isWinner(state, 1))
            return 1;
        else if(isWinner(state, 2))
            return -1;
        else if (movesRemaining <1)
            return 0;
        else
            return -10;
    }


    public void ausgeben(int @NotNull [] daten) {

            for (int j = 0; j < daten.length; j++) {
                System.out.println(daten[j] + "\t");
            }
            System.out.println();
            System.out.println();
            System.out.println();
        }



    private char whowon(int[] board){
         int winner = eval(board);
        return switch (winner) {
            case 1 -> 'X';
            case -1 -> 'O';
            case 0 -> 'D';
            default -> 'f';

        };
    }
    private void phaseint2darrayzuarray(int [] @NotNull [] arr){
        int lauf = 0;
        for (int[] ints : arr) {
            for (int j = 0; j < arr.length; j++) {
                this.board[lauf] = ints[j];
                lauf++;
            }
        }
    }

    private void phasearrayzu2darray(int @NotNull [] arr){
        spiel[0][0] = arr[0];
        spiel[0][1] = arr[1];
        spiel[0][2] = arr[2];
        spiel[1][0] = arr[3];
        spiel[1][1] = arr[4];
        spiel[1][2] = arr[5];
        spiel[2][0] = arr[6];
        spiel[2][1] = arr[7];
        spiel[2][2] = arr[8];
    }

    private void dorandomComputerMove() {
        try {
            int zufallszahl1 = (int) (Math.random() * 9);
            if (ismovelegit(zufallszahl1)) {
                board[zufallszahl1] = 2;
            }else {
                dorandomComputerMove();
            }
            phasearrayzu2darray(board);
                frame.doupdate();
        } catch (StackOverflowError ignored) {
        }
    }
    private boolean ismovelegit(int zahl1){
        return board[zahl1] != 1 && board[zahl1] != 2;
    }
}
 

Aktuelle Jobs

Neue Themen

Ähnliche Themen

Facharbeit: Tic Tac Toe mit Minimax
Antworten: 1
negamax-Algorithmus für Tic-Tac-Toe spielt manchmal falsch
Antworten: 10
Tic Tac Toe Wer hat gewonnen?
Antworten: 4
Tic-Tac-Toe : Computer-AI erstellen?
Antworten: 7
BlueJ Tic Tac Toe öffnen?
Antworten: 6

Zurück
Oben