Java minmax алгоритм, возвращающий нулевой ход и не в состоянии правильно отменить ходы
Вот код для моего алгоритма 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); присваивает нулевое значение "движению" (я не понимаю, почему), и после запуска методов оно оставляет доску в странном состоянии, похоже, что ходы неправильно отменяются, но я неоднократно проверял эту функциональность.
Вот пример запуска кода (после комментирования 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
Он оставляет только кусочки компьютера, удаляя все части игрока.
Переместить класс:
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;
}
}
Класс Board построен на стеке двухмерных массивов, вот методы перемещения и отмены:
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;
}
Я ожидаю, что программа вернет оптимальное движение (то, которое приводит к самому высокому состоянию игрового поля) и оставит игровое поле таким, каким оно было до того, как был выполнен метод minmax. Ничего из этого не происходит, метод возвращает ноль, и доска полностью заменена.
После изменения метода makeMove() в классе Board для правильного копирования платы я теперь получаю исключения NullPointerException в этом методе:
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;}
}
Дайте мне знать, будет ли полезной дополнительная информация.
Любая помощь приветствуется.
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); вы на самом деле просто используете одну и ту же ссылку для всех состояний вашей доски, и модификация одного из них изменит объект, на который они все ссылаются.. который, я полагаю, не тот, который вы хотите.
Это может быть причиной вашей проблемы, если помимо этого есть другие проблемы, обновите свой вопрос.
Обновить:
Это все еще оставалось проблемой при клонировании двумерного массива состояния платы. Вы клонировали массивы, но не Pieces в них, таким образом, когда вы обновляете позицию фигуры, она обновляется для того объекта, на который ссылаются все состояния доски.
Во-первых, заставить Piece реализовать Cloneable
public abstract class Piece implements Cloneable {
// ...
@Override
public abstract Piece clone();
Тогда сделай все детское Pieces на самом деле клонировать себя, например Pawn Является ли это:
@Override
public Pawn clone() {
return new Pawn(getPoint.x, getPoint.y, color);
}
Затем это клонировать ваш 2D-массив:
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();
}
}
}
Похоже, что вы на правильном пути, но теперь похоже, что противник двигает фигуры игроков или что-то в этом роде.
Желаем удачи с остальными!