Java minmax 算法返回空着法且未能正确撤消着法

Question

这是我的 minmax 算法的代码：

private static void minmax(){
    Move move = max(4, true, null);
    //System.out.println(move);
    board.makeMove(move.getFromPoint(), move.getToPoint());
}

private static Move max(int depth, boolean player, Move passedMove){
    if(depth == 0) return passedMove.setScore(board.boardVal());
    Move max = new Move(Integer.MIN_VALUE);
    for(int i = 0; i < board.getMoves(player).size(); i++){
        Move move = board.getMoves(player).get(i);
        board.makeMove(move.getFromPoint(), move.getToPoint());
        //System.out.println(board);
        Move scoreMove = min(depth - 1, !player, move);
        board.undo();
        if(scoreMove.getScore() > max.getScore()) max = new Move(move.getFromPoint(), move.getToPoint(), scoreMove.getScore());
    }
    return max;
}

private static Move min(int depth, boolean player, Move passedMove){
    if(depth == 0) return passedMove.setScore(-board.boardVal());
    Move min = new Move(Integer.MAX_VALUE);
    for(int i = 0; i < board.getMoves(player).size(); i++){
        Move move = board.getMoves(player).get(i);
        board.makeMove(move.getFromPoint(), move.getToPoint());
        //System.out.println(board);
        Move scoreMove = max(depth - 1, !player, move);
        board.undo();
        if(scoreMove.getScore() < min.getScore()) min = new Move(move.getFromPoint(), move.getToPoint(), scoreMove.getScore());
    }
    return min;
}

移动是一个对象，它存储从位置、到位置以及移动后与棋盘值相关联的分数。 Move move = max(4, true, null); 行为 "move" 分配了一个空值（我不明白为什么）并且在方法运行之后它使棋盘处于一种奇怪的状态，看起来这些动作是未正确撤消，但我已反复检查该功能。

这里是运行代码的示例（在注释掉 board.makeMove(move.getFromPoint(), move.getToPoint()); 行以防止空指针异常之后）：

8 [R] [N] [B] [Q] [K] [B] [N] [R] 
7 [P] [P] [P] [P] [P] [P] [P] [P] 
6 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] 
5 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] 
4 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] 
3 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] 
2 [P] [P] [P] [P] [P] [P] [P] [P] 
1 [R] [N] [B] [Q] [K] [B] [N] [R] 
   a   b   c   d   e   f   g   h

a2,a4
8 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] 
7 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] 
6 [ ] [ ] [ ] [ ] [ ] [ ] [N] [ ] 
5 [ ] [ ] [N] [ ] [ ] [ ] [R] [K] 
4 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] 
3 [ ] [ ] [ ] [ ] [ ] [ ] [B] [B] 
2 [ ] [P] [ ] [ ] [ ] [ ] [ ] [ ] 
1 [P] [ ] [R] [P] [P] [P] [P] [P] 
   a   b   c   d   e   f   g   h

它只留下电脑的部分，移除所有玩家的部分。

移动Class:

public class Move {
    private Point fromPoint;
    private Point toPoint;
    private int score;

    public Move(Point fromPoint, Point toPoint, int score){
        this.fromPoint = fromPoint;
        this.toPoint = toPoint;
        this.score = score;
    }

    public Move(Point fromPoint, Point toPoint){
        this(fromPoint, toPoint, 0);
    }

    public Move(int score){
        this(null, null, score);
    }

    public Point getFromPoint() {
        return fromPoint;
    }

    public Point getToPoint() {
        return toPoint;
    }

    public int getScore() {
        return score;
    }

    public Move setScore(int score){
        this.score = score;
        return this;
    }

    @Override
    public String toString(){
        return "(" + fromPoint.y + ", " + fromPoint.x + ")" + " (" + toPoint.y + ", " + toPoint.x + ") " + score;
    }
}

棋盘Class建立在二维数组Stack之上，这里是移动和撤消方法：

public void makeMove(Point fromPoint, Point toPoint){
    Piece[][] boardNode = new Piece[board.peek().length][];
    for(int i = 0; i < boardNode.length; i++){ //this was changed
        boardNode[i] = board.peek()[i].clone();
    }
    boardNode[fromPoint.y][fromPoint.x].setPoint(toPoint);
    boardNode[toPoint.y][toPoint.x] = boardNode[fromPoint.y][fromPoint.x];
    boardNode[fromPoint.y][fromPoint.x] = null;
    board.push(boardNode);
}

public void undo(){
    board.pop();
}

public ArrayList<Move> getMoves(boolean color){
    ArrayList<Move> moves = new ArrayList<>();
    for(Piece[] row : board.peek()){
        for(Piece piece : row){
            if(piece != null) {
                for (Point point : piece.moves()) {
                    if (piece.getColor() == color && straightLine(piece.getPoint(), point) && (board.peek()[point.y][point.x] == null || board.peek()[point.y][point.x].getColor() != color)) moves.add(new Move(piece.getPoint(), point));
                }
            }
        }
    }
    return moves;
}

我希望程序 return 一个最佳移动（导致得分最高的棋盘状态的那个）并使棋盘保持在执行 minmax 方法之前的状态。这些都没有发生，方法 return 无效，并且板已完全更改。

更改板中的 makeMove() 方法 class 以正确复制板后，我现在在该方法中收到 NullPointerExceptions：

8 [R] [N] [B] [Q] [K] [B] [N] [R] 
7 [P] [P] [P] [P] [P] [P] [P] [P] 
6 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] 
5 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] 
4 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] 
3 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] 
2 [P] [P] [P] [P] [P] [P] [P] [P] 
1 [R] [N] [B] [Q] [K] [B] [N] [R] 
   a   b   c   d   e   f   g   h

a2,a4
Exception in thread "main" java.lang.NullPointerException
    at Board.makeMove(Board.java:45)
    at ChessMain.min(ChessMain.java:87)
    at ChessMain.max(ChessMain.java:75)
    at ChessMain.min(ChessMain.java:89)
    at ChessMain.max(ChessMain.java:75)
    at ChessMain.minmax(ChessMain.java:63)
    at ChessMain.play(ChessMain.java:58)
    at ChessMain.main(ChessMain.java:15)

...

public abstract class Piece {
    private boolean color;
    private Point getPoint;

    public Piece(int x, int y, boolean color){
        this.color = color;
        getPoint = new Point(x, y);
    }

    abstract int getValue();

    public String toString(){
        return "";
    }

    public void setPoint(Point point){
        this.getPoint = point;
    }

    public Point getPoint(){ return getPoint; }

    public boolean takable(Point point){ return containsPoint(moves(), point); }

    private static boolean containsPoint(ArrayList<Point> list, Point point){
        for(Point listPoint: list){
            if(listPoint.x == point.x && listPoint.y == point.y) return  true;
        }
        return false;
    }

    abstract ArrayList<Point> moves();

    public boolean getColor(){ return color; }
}

这里是一个扩展 Piece 的对象的例子：

import java.util.ArrayList;

public class Bishop extends Piece{

    public Bishop(int x, int y, boolean color) {
        super(x, y, color);
    }

    public ArrayList<Point> moves(){
        ArrayList<Point> possibleMoves = new ArrayList<>();
        int x = 1;
        while(getPoint().x + x <= 7 && getPoint().y + x <= 7){
            possibleMoves.add(new Point(getPoint().x + x, getPoint().y + x));
            x++;
        }
        x = 1;
        while(getPoint().x - x >= 0 && getPoint().y + x <= 7){
            possibleMoves.add(new Point(getPoint().x - x, getPoint().y + x));
            x++;
        }
        x = 1;
        while(getPoint().x - x >= 0 && getPoint().y - x >= 0){
            possibleMoves.add(new Point(getPoint().x - x, getPoint().y - x));
            x++;
        }
        x = 1;
        while(getPoint().x + x <= 7 && getPoint().y - x >= 0){
            possibleMoves.add(new Point(getPoint().x + x, getPoint().y - x));
            x++;
        }
        return possibleMoves;
    }

    @Override
    public String toString(){ return "B"; }

    public int getValue(){ return 3;}
}

如果更多信息有帮助，请告诉我。

感谢任何帮助。

Answer 1

我能看到的一个问题：

public void makeMove(Point fromPoint, Point toPoint){
    Piece[][] boardNode = board.peek(); // WARNING!!!
    // Instead, make a copy of the previous board state
    // so  you don't change all board states when you want to change one.
    boardNode[fromPoint.y][fromPoint.x].setPoint(toPoint);
    boardNode[toPoint.y][toPoint.x] = boardNode[fromPoint.y][fromPoint.x];
    boardNode[fromPoint.y][fromPoint.x] = null;
    board.push(boardNode); // WARNING!!!
}

您的 board 在堆栈的每一层使用相同的引用。

当您调用 Piece[][] boardNode = board.peek(); ... board.push(boardNode); 时，您实际上只是对所有棋盘状态使用相同的引用，修改其中一个将修改所有引用的 object.. 我认为是不是你想要的。

这可能是您问题的根源，如果除此之外还有其他问题，请更新您的问题。

更新：

克隆棋盘状态的二维数组仍然是个问题。您克隆了数组而不是其中的 Pieces，因此当您更新棋子的位置时，它正在更新棋盘所有状态的 object。

首先，制作Piece工具Cloneable

public abstract class Piece implements Cloneable {
    // ...
    @Override
    public abstract Piece clone();

然后让所有 child Pieces 实际上克隆自己，例如 Pawn 这样做：

@Override
public Pawn clone() {
    return new Pawn(getPoint.x, getPoint.y, color);
}

然后克隆您的二维数组：

public void makeMove(Point fromPoint, Point toPoint) {
    final Piece[][] prevBoard = board.peek();
    final int width = prevBoard.length;
    Piece[][] boardNode = new Piece[width][];
    for (int i = 0; i < width; i++) {
        final int height = prevBoard[i].length;
        boardNode[i] = new Piece[height];
        for (int j = 0; j < height; j++) {
            Piece p = prevBoard[i][j];
            if (p == null) {
                boardNode[i][j] = null;
            } else {
                boardNode[i][j] = p.clone();
            }
        }
    }

这似乎让你走上了正确的轨道，但现在看起来对手正在移动玩家的棋子，或者类似的东西。

祝大家一切顺利！

Java minmax 算法返回空着法且未能正确撤消着法

Java minmax algorithm returning null move and failing to correctly undo moves

java

algorithm

chess

minmax