我目前正在尝试自学Minimax算法，并尝试在Java中将其应用于井字游戏。然而，我的算法存在一个bug，我无法确定是什么导致的。
以下是完整的源代码（抱歉内容较多！）：
public class TicTacToe {
private static boolean gameEnded = false;
private static boolean player = true;
private static Scanner in = new Scanner(System.in);
private static Board board = new Board();
public static void main(String[] args){
System.out.println(board);
while(!gameEnded){
Position position = null;
if(player){
position = makeMove();
board = new Board(board, position, PlayerSign.Cross);
}else{
board = findBestMove(board);
}
player = !player;
System.out.println(board);
evaluateGame();
}
}
private static Board findBestMove(Board board) {
ArrayList<Position> positions = board.getFreePositions();
Board bestChild = null;
int previous = Integer.MIN_VALUE;
for(Position p : positions){
Board child = new Board(board, p, PlayerSign.Circle);
int current = max(child);
System.out.println("Child Score: " + current);
if(current > previous){
bestChild = child;
previous = current;
}
}
return bestChild;
}
public static int max(Board board){
GameState gameState = board.getGameState();
if(gameState == GameState.CircleWin)
return 1;
else if(gameState == GameState.CrossWin)
return -1;
else if(gameState == GameState.Draw)
return 0;
ArrayList<Position> positions = board.getFreePositions();
int best = Integer.MIN_VALUE;
for(Position p : positions){
Board b = new Board(board, p, PlayerSign.Cross);
int move = min(b);
if(move > best)
best = move;
}
return best;
}
public static int min(Board board){
GameState gameState = board.getGameState();
if(gameState == GameState.CircleWin)
return 1;
else if(gameState == GameState.CrossWin)
return -1;
else if(gameState == GameState.Draw)
return 0;
ArrayList<Position> positions = board.getFreePositions();
int best = Integer.MAX_VALUE;
for(Position p : positions){
Board b = new Board(board, p, PlayerSign.Circle);
int move = max(b);
if(move < best)
best = move;
}
return best;
}
public static void evaluateGame(){
GameState gameState = board.getGameState();
gameEnded = true;
switch(gameState){
case CrossWin :
System.out.println("Game Over! Cross Won!");
break;
case CircleWin :
System.out.println("Game Over! Circle Won!");
break;
case Draw :
System.out.println("Game Over! Game Drawn!");
break;
default : gameEnded = false;
break;
}
}
public static Position makeMove(){
Position position = null;
while(true){
System.out.print("Select column(x-axis). 0, 1 or 2: ");
int column = getColOrRow();
System.out.print("Select row(y-axis). 0, 1 or 2: ");
int row = getColOrRow();
position = new Position(column, row);
if(board.isMarked(position))
System.out.println("Position already marked!");
else break;
}
return position;
}
private static int getColOrRow(){
int ret = -1;
while(true){
try{
ret = Integer.parseInt(in.nextLine());
} catch (NumberFormatException e){}
if(ret < 0 | ret > 2)
System.out.print("\nIllegal input... please re-enter: ");
else break;
}
return ret;
}
}
public enum PlayerSign{
Cross, Circle
}
public enum GameState {
Incomplete, CrossWin, CircleWin, Draw
}
public final class Position {
public final int column;
public final int row;
public Position(int column, int row){
this.column = column;
this.row = row;
}
}
public class Board {
private char[][] board; //e = empty, x = cross, o = circle.
public Board(){
board = new char[3][3];
for(int y = 0; y < 3; y++)
for(int x = 0; x < 3; x++)
board[x][y] = 'e'; //Board initially empty
}
public Board(Board from, Position position, PlayerSign sign){
board = new char[3][3];
for(int y = 0; y < 3; y++)
for(int x = 0; x < 3; x++)
board[x][y] = from.board[x][y];
board[position.column][position.row] = sign==PlayerSign.Cross ? 'x':'o';
}
public ArrayList<Position> getFreePositions(){
ArrayList<Position> retArr = new ArrayList<Position>();
for(int y = 0; y < 3; y++)
for(int x = 0; x < 3; x++)
if(board[x][y] == 'e')
retArr.add(new Position(x, y));
return retArr;
}
public GameState getGameState(){
if(hasWon('x'))
return GameState.CrossWin;
else if(hasWon('o'))
return GameState.CircleWin;
else if(getFreePositions().size() == 0)
return GameState.Draw;
else return GameState.Incomplete;
}
private boolean hasWon(char sign){ //8 ways to win.
if(board[1][1] == sign){
if(board[0][0] == sign && board[2][2] == sign)
return true;
if(board[0][2] == sign && board[2][0] == sign)
return true;
if(board[1][0] == sign && board[1][2] == sign)
return true;
if(board[0][1] == sign && board[2][1] == sign)
return true;
}
if(board[0][0] == sign){
if(board[0][1] == sign && board[0][2] == sign)
return true;
if(board[1][0] == sign && board[2][0] == sign)
return true;
}
if(board[2][2] == sign){
if(board[1][2] == sign && board[0][2] == sign)
return true;
if( board[2][1] == sign && board[2][0] == sign)
return true;
}
return false;
}
public boolean isMarked(Position position){
if(board[position.column][position.row] != 'e')
return true;
return false;
}
public String toString(){
String retString = "\n";
for(int y = 0; y < 3; y++){
for(int x = 0; x < 3; x++){
if(board[x][y] == 'x' || board[x][y] == 'o')
retString += "["+board[x][y]+"]";
else
retString += "[ ]";
}
retString += "\n";
}
return retString;
}
}
以下是运行程序后的输出结果（计算机为圆形）：
[ ][ ][ ]
[ ][ ][ ]
[ ][ ][ ]
Select column(x-axis). 0, 1 or 2: 1
Select row(y-axis). 0, 1 or 2: 1
[ ][ ][ ]
[ ][x][ ]
[ ][ ][ ]
Child Score: 0
Child Score: 0
Child Score: 0
Child Score: 0
Child Score: 0
Child Score: 0
Child Score: 0
Child Score: 0
[o][ ][ ]
[ ][x][ ]
[ ][ ][ ]
Select column(x-axis). 0, 1 or 2: 0
Select row(y-axis). 0, 1 or 2: 1
[o][ ][ ]
[x][x][ ]
[ ][ ][ ]
Child Score: -1
Child Score: 0
Child Score: 0
Child Score: -1
Child Score: -1
Child Score: -1
[o][ ][o]
[x][x][ ]
[ ][ ][ ]
Select column(x-axis). 0, 1 or 2:
如您所见，在第一步之后，计算机认为无论它做出什么移动都可以得到平局（得分=0）。
在第二步中，我在列0行1上打了一个叉。由于某种原因，计算机认为有两种可能的移动方式可以达到平局（得分=0），而只有四种移动方式会输掉（得分=-1）。然后，它会进行错误的移动，以为自己会得到平局。
我最初认为hasWon方法存在问题，但我已经测试了所有8种获得三个连续棋子的方式，它们都返回true。
我怀疑问题存在于findBestMove、max或min方法中的某个地方，但我还没有能够确定具体是什么导致了这个问题。
如果有人能告诉我是什么导致了这个错误，或者提供任何关于如何更好地调试我的递归算法的建议，我将不胜感激。