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