Java minmax algorithm returning null move and failing to correctly undo moves
Here is the code for my minmax algorithm:
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 is an object that stores a from location, a to location, and a score associated with the board's value after making that move. The line Move move = max(4, true, null); assigns a null value to "move" (I don't understand why) and after the methods are run it leaves the board in a strange state, it seems like the moves are not correctly being undone, but I have checked that functionality repeatedly.
Here is an example of running the code (after commenting out the board.makeMove(move.getFromPoint(), move.getToPoint()); line to prevent a null pointer exception):
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
It leaves only the computer's pieces, removing all of the player's.
Move 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;
}
}
The Board Class is built on a Stack of 2D arrays, here are the move and undo methods:
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;
}
I expect the program to return an optimal Move (the one that leads to the highest scoring board state) and to leave the board as it was before the minmax method was executed. Neither of these are happening, the method returns null and the board is completely changed.
After changing the makeMove() method in the Board class to correctly copy the board I am now getting NullPointerExceptions in that method:
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; }
}
Here is an example of an Object that extends 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;}
}
Let me know if more information would be helpful.
Any help is appreciated.
One issue I can see:
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!!!
}
Your board is using the same reference on each level of the stack.
When you call Piece[][] boardNode = board.peek(); ... board.push(boardNode); Piece[][] boardNode = board.peek(); ... board.push(boardNode); you are really just using the same reference for all your board states and modifying one of them will modify the object which all of them reference.. which I assume is not what you want.
This could be the root of your problem, if there are more issues besides that then update your question.
Update:
It was all still an issue in cloning the 2D array of the board state. You cloned the arrays but not the Piece s in them, thus when you update the position of the piece it is updating for that object that all states of the board reference.
First, make Piece implement Cloneable
public abstract class Piece implements Cloneable {
// ...
@Override
public abstract Piece clone();
Then make all child Pieces actually clone themselves, Eg Pawn does this:
@Override
public Pawn clone() {
return new Pawn(getPoint.x, getPoint.y, color);
}
Then this to clone your 2D array:
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();
}
}
}
This seems to get you on the right track, but now it seems like the opponent is moving the players pieces, or something like that.
Best of luck with the rest!
链接地址: http://www.djcxy.com/p/56392.html