javaartificial-intelligenceminimax

Why is my minimax algorithm not outputting the best move


i wanted to test out a universal minimax algorithm, that should return the best possible position for a scenario, the code for the algorithm:

import java.util.ArrayList;

public class AI<E> {
    public int go = 0;
   protected int minimax(ArrayList<E> position, int depth, int alpha, int beta, boolean maximizingPlayer) {
    if (depth == 0 || isGameOver(position)) {
        return evaluatePosition(position);
    }

    if (maximizingPlayer) {
        int maxEval = Integer.MIN_VALUE;
        for (ArrayList<E> child : getChildren(position, maximizingPlayer)) {
            int eval = minimax(child, depth - 1, alpha, beta, false);
            maxEval = Math.max(maxEval, eval);
            alpha = Math.max(alpha, eval);
            if (beta <= alpha) {
                break;
            }
        }
        return maxEval;
    } else {
        int minEval = Integer.MAX_VALUE;
        for (ArrayList<E> child : getChildren(position, maximizingPlayer)) {
            int eval = minimax(child, depth - 1, alpha, beta, true);
            minEval = Math.min(minEval, eval);
            beta = Math.min(beta, eval);
            if (beta <= alpha) {
                break;
            }
        }
        return minEval;
    }
}


    protected boolean isGameOver(ArrayList<E> position) {
        return false;
    }

    protected int evaluatePosition(ArrayList<E> position) {
        return 0;
    }

    protected ArrayList<ArrayList<E>> getChildren(ArrayList<E> position, boolean player) {
        return new ArrayList<>();
    }

    public static <T> void copyArrayList(ArrayList<T> source, ArrayList<T> destination) {
        //destination.clear();
        destination.addAll(source);
    }
}

The TicTacToe Code:

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Scanner;

public class TicTacToe extends AI<Character> {
    private final char EMPTY = ' ';
    private final char PLAYER_X = 'X';
    private final char PLAYER_O = 'O';
    private final int SIZE = 3;
    private char currentPlayer = PLAYER_X;
    private ArrayList<Character> board = new ArrayList<>(SIZE * SIZE);
    private Scanner scanner = new Scanner(System.in);
    Random random = new Random();
    public TicTacToe() {
        super();
        initializeBoard();

        while (true) {
            printBoard();

            if (currentPlayer == PLAYER_X) {
                playerMove(currentPlayer);
            } else {
                botMove(currentPlayer);
            }

            if (checkWinner(board, currentPlayer)) {
                printBoard();
                System.out.println("Player " + currentPlayer + " wins!");
                break;
            }

            if (checkDraw(board)) {
                printBoard();
                System.out.println("The game is a draw!");
                break;
            }

            currentPlayer = (currentPlayer == PLAYER_X) ? PLAYER_O : PLAYER_X;
        }
    }

    public static void main(String[] args) {
        new TicTacToe();
    }

    private void initializeBoard() {
        for (int i = 0; i < SIZE * SIZE; i++) {
            board.add(EMPTY);
        }
    }

    private void printBoard() {
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                System.out.print(board.get(i * SIZE + j));
                if (j < SIZE - 1) System.out.print("|");
            }
            System.out.println();
            if (i < SIZE - 1) System.out.println("-----");
        }
    }

    private void playerMove(char player) {
        while (true) {
            System.out.println("Enter the row (0, 1, 2) and column (0, 1, 2) for player " + player + ": ");
            int row = scanner.nextInt();
            int col = scanner.nextInt();
            int index = row * SIZE + col;
            if (row >= 0 && row < SIZE && col >= 0 && col < SIZE && board.get(index) == EMPTY) {
                board.set(index, player);
                break;
            } else {
                System.out.println("This spot is already taken or out of bounds, try again.");
            }
        }
    }

    private void botMove(char player) {
        int max = Integer.MIN_VALUE;
        int pos = -1;
        ArrayList<ArrayList<Character>> children = getChildren(board,false); //andern so das true/ false andert welches zeichen gesetzt wird
        for (int i = 0; i < children.size(); i++) {
            int depth = 10;
            int alpha = Integer.MIN_VALUE;
            int beta = Integer.MAX_VALUE;
            boolean maximizingPlayer = true;

            int result = minimax(children.get(i), depth, alpha, beta, maximizingPlayer);
            if (result > max) {
                max = result;
                pos = i;
            }
        }
        if (pos != -1) {
            board = children.get(pos);
        } else {
            // Fallback to random move if no valid move is found by minimax
      System.out.println("random");
            while (true) {
                int row = random.nextInt(SIZE);
                int col = random.nextInt(SIZE);
                int index = row * SIZE + col;
                if (board.get(index) == EMPTY) {
                    board.set(index, player);
                    break;
                }
            }
        }
    }

    private boolean checkWinner(ArrayList<Character> board, char player) {
    // Überprüfen der horizontalen und vertikalen Reihen
    for (int i = 0; i < SIZE; i++) {
        // Horizontale Überprüfung
        if (board.get(i * SIZE) == player && board.get(i * SIZE + 1) == player && board.get(i * SIZE + 2) == player) {
            return true;
        }
        // Vertikale Überprüfung
        if (board.get(i) == player && board.get(SIZE + i) == player && board.get(2 * SIZE + i) == player) {
            return true;
        }
    }
    // Diagonale Überprüfung (links oben nach rechts unten)
    if (board.get(0) == player && board.get(4) == player && board.get(8) == player) {
        return true;
    }
    // Diagonale Überprüfung (rechts oben nach links unten)
    if (board.get(2) == player && board.get(4) == player && board.get(6) == player) {
        return true;
    }
    return false;
}




    private boolean checkDraw(ArrayList<Character> pos) {
        return pos.stream().noneMatch(spot -> spot == EMPTY);
    }

    @Override
    protected boolean isGameOver(ArrayList<Character> position) {
        return checkDraw(position) || checkWinner(position, PLAYER_X) || checkWinner(position, PLAYER_O);
    }

     @Override
    protected int evaluatePosition(ArrayList<Character> position) {
    char otherPlayer = currentPlayer == PLAYER_X ? PLAYER_O : PLAYER_X;
        if (checkWinner(position, currentPlayer)) { // hier waren probleme, nicht vergessen!!!  
            return 100000;  
        } else if (checkWinner(position, otherPlayer)) {
            return -100000;  //math.min
        } else {
            return 0;
        }
    }
  @Override
protected ArrayList<ArrayList<Character>> getChildren(ArrayList<Character> position, boolean player) {
    ArrayList<ArrayList<Character>> children = new ArrayList<>();
    char currentPlayer = player ? PLAYER_X : PLAYER_O;
    char otherPlayer = currentPlayer == PLAYER_X ? PLAYER_O : PLAYER_X;

    for (int i = 0; i < SIZE * SIZE; i++) {
        if (position.get(i) == EMPTY) {
            ArrayList<Character> child = new ArrayList<>(position);
            child.set(i, currentPlayer);
            children.add(child);
        }
    }
    return children;
}

}

I'm pretty sure that the code for checking if the game is over is working, and the minimax algorithm is exactly how it looks like in many other programms, so i guess there is a logic problem somewhere. A Test Example for it's failure:

X|-|- 
-|-|-
-|-|-
AI:
X|-|O 
-|-|-
-|-|-

This leads to a loss for the AI in 3 moves no matter what.

Also: The code doesnt work for even simple tasks like stopping a win in 1 move when i decrease the depth of the algorithm, maybe that helps with the error search. Thanks


Solution

  • i rewrote my entire code, now it works, my new minimax:

    protected int minimax(ArrayList<E> position, int depth, int alpha, int beta, boolean maximizingPlayer) {
        if (depth == 0 || isGameOver(position)) {
            return evaluatePosition(position);
        }
    
        if (maximizingPlayer) {
            int maxEval = Integer.MIN_VALUE;
            for (ArrayList<E> child : getChildren(position)) {
                int eval = minimax(child, depth - 1, alpha, beta, false);
                maxEval = Math.max(maxEval, eval);
                alpha = Math.max(alpha, eval);
                if (beta <= alpha) {
                    break;
                }
            }
            return maxEval;
        } else {
            int minEval = Integer.MAX_VALUE;
            for (ArrayList<E> child : getChildren(position)) {
                int eval = minimax(child, depth - 1, alpha, beta, true);
                minEval = Math.min(minEval, eval);
                beta = Math.min(beta, eval);
                if (beta <= alpha) {
                    break;
                }
            }
            return minEval;
        }
    }
    

    Hope this helps someone trying to program a minimax algorithm, i also have a version with a 2D Array, so just ask if you want it