我想测试一个通用的极小极大算法，它应该返回场景的最佳可能位置，算法的代码：
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);
}
}
井字棋代码：
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;
}
}
我非常确定检查游戏是否结束的代码正在工作，并且极小极大算法正是它在许多其他程序中的样子，所以我猜想某个地方存在逻辑问题。 失败的测试示例：
X|-|-
-|-|-
-|-|-
AI:
X|-|O
-|-|-
-|-|-
无论如何，这都会导致 AI 在 3 步内失败。
另外：该代码甚至不适用于简单的任务，例如当我减少算法的深度时停止一步获胜，也许这有助于错误搜索。 谢谢
我重写了我的整个代码，现在它可以工作了，我的新极小极大：
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;
}
}
希望这对尝试编写极小极大算法的人有帮助，我也有一个带有二维数组的版本，所以只要问你是否想要它