我目前正在尝试自学 Minimax 算法，并尝试在 java 中的井字游戏中实现它。但是，我的算法中有一个错误，我无法弄清楚是什么原因造成的。
以下是完整的源代码（对不起，文字墙！）：
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:
正如您在第一步之后看到的那样，计算机认为无论它做出什么举动都可以平局（Score = 0）。
在第二步中，我在第 0 列第 1 行打了一个叉。由于某种原因，计算机认为有两个可能的棋步可以达到平局（得分 = 0），只有四个棋步会输（得分 = -1） . 然后它做出了错误的举动，认为它会平局。
我首先认为 hasWon 方法有问题，但是我测试了所有 8 种连续获得三个的方法，它们都返回 true。
我怀疑问题存在于 findBestMove、max 或 min 方法中的某个地方，但我无法准确找出导致它的原因。
如果有人能说出导致错误的原因或就如何更好地调试我的递归算法提供任何建议，我将不胜感激。