java - Tic Tac Toe 的 Minimax 算法中的错误

Question

我目前正在尝试自学 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:   

正如您在第一步之后看到的那样，计算机认为无论它走什么步都可以平局(得分 = 0)。

在第二步，我在第 0 列，第 1 行打了一个叉。出于某种原因，计算机随后认为有两种可能的走法可以达到平局(分数 = 0)并且只有四步可以失败(分数 = -1).然后它认为它会平局而做出错误的移动。

我一开始以为是hasWon方法有问题，后来测试了8种连成三的方法，都返回true。

我怀疑问题存在于 findBestMove、max 或 min 方法中的某处，但我无法弄清楚到底是什么导致了它。

如果有人能告诉我导致该错误的原因或就如何更好地调试我的递归算法提出任何建议，我将不胜感激。

Answer 1

在我看来，您混淆了 min 和 max 的部分内容。目前，您的max 返回人类 可能采取的最差可能移动(对他而言)的值，而不是计算机可能采取的最佳移动的值。同样，min 返回计算机可能采取的最差着法的值，而不是对手的最佳着法。

通过在 min 和 max 中切换 PlayerSigns 来解决这个问题，findBestMove 应该调用 min，而不是 最大。