MiniMax国际象棋算法返回坏棋

Question

我对我的象棋游戏的最小极大算法的实现有问题。它的大部分似乎都起作用了，但它要么从来没有做出好的动作，要么对它们的评估（基于两个玩家的活动棋子的分数）出了问题。例如，如果我设置了check（例如，傻瓜的伴侣），ai会做一些随机的事情，而不是杀死国王。我真的找不出我做错了什么。

评估电路板的类StandardBoardEvaluator在经过一些测试后似乎可以工作，因此问题很可能出现在MiniMax实现中的某个地方。这个游戏是由一个类棋盘组成的，它有和我自己的类方块的8x8对象的2D数组，它本身有一个棋子的引用（可以是空的，或者任何典型的棋子）。在算法中，我不断地在搜索中创建新的Board实例，这就是为什么我在Board和Square中创建这些“深度克隆”构造函数的原因，所以这似乎不是问题。像这样：

public Board(Board originalBoard) {
        this.turnIsWhite = originalBoard.getTurnIsWhite();
        winner = null;
        squares = new Square[8][8];

        for (int rank=0; rank<squares.length; rank++) {
            for(int file=0; file<squares[rank].length; file++) {
                squares[rank][file] = new Square(originalBoard.getSquare(posStringFromFileRank(rank, file)));
            }
        }
    }

public Square(Square originalSquare) {
        this.pos = new String(originalSquare.getPos());
        this.piece = originalSquare.getPiece();
    }

我有一个典型的命令类，MovePiece，用于移动碎片。这将使用另一个类MoveCheck来检查move命令是否合法。MovePiece返回一个布尔值，表示移动是否合法。这两个类都经过了大量的测试，并且正在工作，所以我不认为问题出在这些类内部。

以下是算法：

public class MiniMax implements MoveStrategy{
    BoardEveluator bV;
    MoveGenerator mGen;
    int depth;

    public MiniMax(int depth){
        bV = new StandardBoardEvaluator();
        mGen = new MoveGenerator();
        this.depth = depth;
    }

    @Override
    public MovePiece execute(Board board) {
        MovePiece bestMove = null;
        int lowestValue = Integer.MAX_VALUE;
        int highestValue = Integer.MIN_VALUE;
        int currentValue = 0;

        String color = (board.getTurnIsWhite() ? "white" : "black");
        System.out.println(color + " is evaluation best move with MiniMax depth " + depth);
        List<MovePiece> allPossibleMoves = mGen.getLegalMoves(board, board.getTurnIsWhite());

        for (MovePiece mp : allPossibleMoves){
            Board tempBoard = new Board(board);
            mp.setBoard(tempBoard);
            if (mp.execute()){
                currentValue = tempBoard.getTurnIsWhite() ? min(tempBoard, depth -1) : max(tempBoard, depth -1);
                if (board.getTurnIsWhite() && currentValue >= highestValue){
                    highestValue = currentValue;
                    bestMove = mp;
                }
                else if (!board.getTurnIsWhite() && currentValue <= lowestValue){
                    lowestValue = currentValue;
                    bestMove = mp;
                }
                mp.unexecute();
            }
        }
        return bestMove;
    }



    int min (Board board, int depth){
        if (depth == 0 || board.getWinner() != null){
            return bV.eveluate(board);
        }
        int lowestValue = Integer.MAX_VALUE;
        List<MovePiece> legalMoves = mGen.getLegalMoves(board, board.getTurnIsWhite());
        for (MovePiece mp : legalMoves){
            Board tempBoard = new Board(board);
            mp.setBoard(tempBoard);
            if (mp.execute()){
                int currentValue = max(tempBoard, depth - 1);
                if (currentValue <= lowestValue){
                    lowestValue = currentValue;
                }
                mp.unexecute();
            }

        }
        return lowestValue;
    }
    int max (Board board, int depth){
        if (depth == 0 || board.getWinner() != null){
            return bV.eveluate(board);
        }
        int highestValue = Integer.MIN_VALUE;
        List<MovePiece> legalMoves = mGen.getLegalMoves(board, board.getTurnIsWhite());
        for (MovePiece mp : legalMoves){
            Board tempBoard = new Board(board);
            mp.setBoard(tempBoard);
            if (mp.execute()){
                int currentValue = min(tempBoard, depth - 1);
                if (currentValue >= highestValue){
                    highestValue = currentValue;
                }
                mp.unexecute();
            }
        }
        return highestValue;
    }

和evalutor类

public class StandardBoardEvaluator implements BoardEveluator {
    private int scorePlayer(Board board, boolean isWhite){
        return pieceValue(board, isWhite) + mobolity(isWhite, board);
    }
    private int mobolity(boolean isWhite, Board board){
        return (int) (board.getActiveSquares(isWhite).size() * 1.5);
    }
    private static int pieceValue(Board board, boolean isWhite){
        int piceValueScore = 0;
        for (Square square : board.getActiveSquares(isWhite)){
            piceValueScore += square.getPiece().getPieceValue();
        }
        return piceValueScore;
    }
    @Override
    public int eveluate(Board board) {
        return scorePlayer(board, true) - scorePlayer(board, false);
    }
}

private Square from;
    private Square to;
    private Board board;
    private MoveCheck mCheck;
    private RulesCheck rCheck;
    private boolean done = false;
    private Piece killed;

    public MovePiece(Board board, String from, String to) {
        this.board = board;
        this.from = board.getSquare(from);
        this.to = board.getSquare(to);
        mCheck = new MoveCheck();
    }
    public MovePiece(Board board, Square from, Square to) {
        this.board = board;
        this.from = from;
        this.to = to;
        mCheck = new MoveCheck();
        rCheck = new RulesCheck(board);
    }
    public void setBoard(Board board) {
        this.board = board;
    }
    public Board getBoard() {
        return board;
    }

    public Square getFrom() {
        return from;
    }
    public Square getTo() {
        return to;
    }
    public void setFrom(Square from) {
        this.from = from;
    }
    public void setTo(Square to) {
        this.to = to;
    }
    public void setFrom(String from) {
        this.from = board.getSquare(from);
    }
    public void setTo(String to) {
        this.to = board.getSquare(to);
    }
    @Override
    public boolean execute() {
        rCheck = new RulesCheck(board);
        if (done) {
            board.movePiece(from, to);
            return true;
        }
        else if (mCheck.isLegal(board, from, to)){
            if (to.getPiece() != null) {
                killed = to.getPiece();
                rCheck.winCheck(killed);
            }
            board.setGameOutput("Moved " + from.pieceToString() + " at " + from.getPos() + " - to " + to.getPos() + "(" + to.pieceToString() + ")");
            board.movePiece(from, to);
            rCheck.checkPromotion(to);
            done = true;
            return true;
        }
        return false;
    }

    @Override
    public void unexecute() {
        if (to.getPiece().getClass() == Pawn.class)
            ((Pawn) to.getPiece()).decreaseMoves();
        board.movePiece(to, from);
        if (killed != null) {
            to.setPiece(killed);
        }

    }

MoveCheck类只查看移动是否合法（路径清晰、目标是敌人或空的等等），不认为它与我的问题相关，因为代码已经测试并可以工作。

piece值在抽象类piece的子类（所有类型的pieces）中声明为int。一个卒100分，主教和骑士300分，鲁克500分，皇后900分，国王10000分。

如果有人能帮我解决这个问题，我将永远感激！请让我知道，如果您需要执行一些其他代码，我没有显示。

Answer 1

您还没有共享MovePiece实现和主游戏循环，但我在minimax.execute方法中发现了两个可能的问题：

currentValue = tempBoard.getTurnIsWhite() ? min(tempBoard, depth -1) : max(tempBoard, depth -1)

根据上面的代码，您假设MinMax播放器将始终是黑色的，因为它为白色计算min而为黑色计算max。对于一个通用算法，这是一个错误的假设，不知道它是否适用于您。

第二件事是在调用mp.execute()并赋值bestmove=mp之后，调用mp.unexecute()，因此有效地调用bestmove.unexecute()，因为变量指向同一个对象。

请考虑上面的建议，如果它不能解决问题，请分享上面的实现部分。