Generating possible Chess moves

Question

Here is the solution to generating possible moves and keeping the king safe. If someone is willing to look it over and come with some suggestion to perhaps improve it, I would appreciate it.

Full source code is at GitHub

King:

@Override
public Collection<Square> generatePossibleMoves() {
    possibleMoves.clear();
    List<Square> moves = new ArrayList<>();
    int[][] offsets = {
        {1, 0},
        {0, 1},
        {-1, 0},
        {0, -1},
        {1, 1},
        {-1, 1},
        {-1, -1},
        {1, -1}
    };
    for (int[] o : offsets) {
        Square square = super.getSquare().neighbour(o[0], o[1]);
        if (square != null && (square.getPiece() == null || isOpponent(square.getPiece()))) {
            moves.add(square);
        }
    }
    possibleMoves.addAll(moves);
    if (getSquare().isSelected()) {
        Piece[] pieces = {
            PieceType.PAWN.create(getPieceColor()),
            PieceType.ROOK.create(getPieceColor()),
            PieceType.BISHOP.create(getPieceColor()),
            PieceType.KNIGHT.create(getPieceColor()),
            PieceType.QUEEN.create(getPieceColor()),
            PieceType.KING.create(getPieceColor())};
        Piece oldKing = this;
        getSquare().removePiece();
        for (Square kingMove : moves) {
            if (kingMove.isEmpty()) {
                for (Piece piece : pieces) {
                    piece.putPieceOnSquareFirstTime(kingMove);
                    piece.generatePossibleMoves();
                    for (Square enemy : piece.getPossibleMoves()) {
                        if (!enemy.isEmpty() && enemy.getPiece().isOpponent(piece) && enemy.getPiece().getTypeNumber() == piece.getTypeNumber()) {
                            enemy.setBackground(Color.BLUE);
                            possibleMoves.remove(kingMove);
                            break;
                        }
                    }
                }
                kingMove.removePiece();
            } else if (isOpponent(kingMove.getPiece())) {
                Piece oldPiece = kingMove.getPiece();
                for (Piece piece : pieces) {
                    kingMove.removePiece();
                    piece.putPieceOnSquareFirstTime(kingMove);
                    piece.generatePossibleMoves();
                    for (Square square1 : piece.getPossibleMoves()) {
                        if (!square1.isEmpty() && square1.getPiece().isOpponent(piece) && square1.getPiece().getTypeNumber() == piece.getTypeNumber()) {
                            possibleMoves.remove(kingMove);
                            break;
                        }
                    }
                }
                kingMove.removePiece();
                oldPiece.putPieceOnSquareFirstTime(kingMove);
            }
        }
        oldKing.putPieceOnSquareFirstTime(getSquare());
    }
    return possibleMoves;
}

Bishop

@Override
public Collection<Square> generatePossibleMoves() {
    int row = super.getSquare().ROW;
    int column = super.getSquare().COLUMN;
    possibleMoves.clear();
    //all possible moves in the down positive diagonal
    for (int j = column + 1, i = row + 1; j < Board.SIZE && i < Board.SIZE; j++, i++) {
        Square square = super.getSquare().getBoardSquare(i, j);
        if (square.getPiece() == null) {
            possibleMoves.add(square);
        } else if (isOpponent(square.getPiece())) {
            possibleMoves.add(square);
            break;
        } else {
            break;
        }
    }
    //all possible moves in the up positive diagonal
    for (int j = column - 1, i = row + 1; j > -1 && i < Board.SIZE; j--, i++) {
        Square square = super.getSquare().getBoardSquare(i, j);
        if (square.getPiece() == null) {
            possibleMoves.add(square);
        } else if (isOpponent(square.getPiece())) {
            possibleMoves.add(square);
            break;
        } else {
            break;
        }
    }
    //all possible moves in the up negative diagonal
    for (int j = column - 1, i = row - 1; j > -1 && i > -1; j--, i--) {
        Square square = super.getSquare().getBoardSquare(i, j);
        if (square.getPiece() == null) {
            possibleMoves.add(square);
        } else if (isOpponent(square.getPiece())) {
            possibleMoves.add(square);
            break;
        } else {
            break;
        }
    }
    //all possible moves in the down negative diagonal
    for (int j = column + 1, i = row - 1; j < Board.SIZE && i > -1; j++, i--) {
        Square square = super.getSquare().getBoardSquare(i, j);
        if (square.getPiece() == null) {
            possibleMoves.add(square);
        } else if (isOpponent(square.getPiece())) {
            possibleMoves.add(square);
            break;
        } else {
            break;
        }
    }
    return possibleMoves;
}

Knight

@Override
public Collection<Square> generatePossibleMoves() {
    possibleMoves.clear();
    int[][] offsets = {
        {-2, 1},
        {-1, 2},
        {1, 2},
        {2, 1},
        {2, -1},
        {1, -2},
        {-1, -2},
        {-2, -1}
    };
    for (int[] o : offsets) {
        Square square = super.getSquare().neighbour(o[0], o[1]);
        if (square != null && (square.getPiece() == null || isOpponent(square.getPiece()))) {
            possibleMoves.add(square);
        }
    }
    return possibleMoves;
}

Rook

@Override
public Collection<Square> generatePossibleMoves() {
    int row = super.getSquare().ROW;
    int column = super.getSquare().COLUMN;
    possibleMoves.clear();
    //all possible moves in the up
    for (int i = row + 1; i < Board.SIZE; i++) {
        Square square = super.getSquare().getBoardSquare(i, column);
        if (square.getPiece() == null) {
            possibleMoves.add(square);
        } else if (isOpponent(square.getPiece())) {
            possibleMoves.add(square);
            break;
        } else {
            break;
        }
    }
    //all possible moves in the down
    for (int i = row - 1; i > -1; i--) {
        Square square = super.getSquare().getBoardSquare(i, column);
        if (square.getPiece() == null) {
            possibleMoves.add(square);
        } else if (isOpponent(square.getPiece())) {
            possibleMoves.add(square);
            break;
        } else {
            break;
        }
    }
    //all possible moves to the right
    for (int i = column + 1; i < Board.SIZE; i++) {
        Square square = super.getSquare().getBoardSquare(row, i);
        if (square.getPiece() == null) {
            possibleMoves.add(square);
        } else if (isOpponent(square.getPiece())) {
            possibleMoves.add(square);
            break;
        } else {
            break;
        }
    }
    //all possible moves to the left
    for (int i = column - 1; i > -1; i--) {
        Square square = super.getSquare().getBoardSquare(row, i);
        if (square.getPiece() == null) {
            possibleMoves.add(square);
        } else if (isOpponent(square.getPiece())) {
            possibleMoves.add(square);
            break;
        } else {
            break;
        }
    }
    return possibleMoves;
}

Queen

Moves exactly like the Rook and Bishop so why not reuse?

@Override
public Collection<Square> generatePossibleMoves() {
    possibleMoves.clear();
    Piece[] pieces = {
        PieceType.ROOK.create(getPieceColor()),
        PieceType.BISHOP.create(getPieceColor())
    };
    for (Piece piece : pieces) {
        piece.setSquare(getSquare());
        possibleMoves.addAll(piece.generatePossibleMoves());
    }
    return possibleMoves;
}

Pawn

@Override
public Collection<Square> generatePossibleMoves() {
    possibleMoves.clear();
    boolean color = super.isWhite();
    int dx = color ? -1 : 1;

    Square ahead = super.getSquare().neighbour(dx, 0);
    if (ahead.getPiece() == null) {
        possibleMoves.add(ahead);
        if (super.getSquare().ROW == 6 && color) {
            Square aheadsecond = super.getSquare().neighbour(dx - 1, 0);
            if (aheadsecond.getPiece() == null) {
                possibleMoves.add(aheadsecond);
            }
        } else if (super.getSquare().ROW == 1 && !color) {
            Square aheadsecond = super.getSquare().neighbour(dx + 1, 0);
            if (aheadsecond.getPiece() == null) {
                possibleMoves.add(aheadsecond);
            }
        }
    }
    Square aheadLeft = super.getSquare().neighbour(dx, -1);
    if (aheadLeft != null && aheadLeft.getPiece() != null && isOpponent(aheadLeft.getPiece())) {
        possibleMoves.add(aheadLeft);
    }
    Square aheadRight = super.getSquare().neighbour(dx, 1);
    if (aheadRight != null && aheadRight.getPiece() != null && isOpponent(aheadRight.getPiece())) {
        possibleMoves.add(aheadRight);
    }
    return possibleMoves;
}

Been thinking perhaps a class MoveList where all kind of moves are added where you could have MoveType but I would like to see if already existing code could be used. — jetersen, Commented Jun 10, 2014 at 11:56
Welcome to Code Review! I find your code is interesting but your question confusing. What exactly is your question? Also, have you read our help center page so that you're sure Code Review is the right place to ask? — Simon Forsberg, Commented Jun 10, 2014 at 12:10

Guy Schalnat · Accepted Answer · 2014-06-27 05:53:28Z

It's a good start. Now comes reality.

The moves you missed are castling, en passant, and promoting a pawn. Also, you can't move a piece out of the way that is pinned to your king (in some cases, you can move it as long as it continues to block the check). If the king is already in check, the only legal moves are ones that removes the check (block, capture the checking piece, run away). If double check, then both checks must be resolved (which means the king has to run away, possibly capturing one of the checking pieces, if possible).

I also agree with JosephP's idea of a MoveType class, although your offsets arrays may be enough (with an added flag for one time move, move until blocked, move if capture, move if no capture, move if en passant, etc.). Let the base Piece class do most of the moves and let the individual pieces just tell the base class what directions the piece can move. I'd let the board do the validity testing for the king being in danger, as well as remembering what square (if any) en passant is possible for. Castling involves checking various squares for opponents checks and emptyness, as well as the rook and king remembering if they have moved before (which can also be used for a pawn moving two squares).

Thanks for your input. I excluded castling, en passant, and promotion for now but your right about checking if it is blocking for the king. MoveType is the option for me I think. Also thanks for meaning how you would go about checking for the different moves. — jetersen, Commented Jun 27, 2014 at 15:32
You're welcome. I mentioned pawn promotion because I think it becomes the hardest to do if you are using inheritance for each piece type (which may or may not be the best pattern to use here, so think about both using inheritance and leaving it at a base Piece class with a data table that defines the different moves). — Guy Schalnat, Commented Jun 27, 2014 at 19:44

toto2 · Accepted Answer · 2014-06-27 13:11:29Z

There is some standard algorithm to optimize moves in games called MinMax. You should also look more specifically on the web for chess related versions of this algorithm. There are books on the subject and I'm sure there are many blogs, tutorials, online classes, etc.

Basically, you generate all your possible moves and you don't care if the piece you move gets taken or not. The next step is to generate all possible moves for your opponent, for each configuration you generated previously. If you move your king and your opponent can take it, you'll see it at that second step.

MinMax is more complicated than that: you have to estimate some score for every move in order to find your best (Max) move, and, inversely, find your opponent's best move (Min). And you'll generally do more than one iteration my_move/your_move (depth), but not too much because the complexity increases exponentially with depth.

MinMax is for AI. Which is not what this is doing. Eventually it will be added but for now focus is around user input. — jetersen, Commented Jun 27, 2014 at 15:25
Using a simplified version of MinMax is nonetheless the simplest option for your problem, in my opinion. — toto2, Commented Jun 27, 2014 at 17:08

aghast · Accepted Answer · 2017-12-29 17:33:50Z

I'm confused on why you sometimes call super.getSquare() and other times just call getSquare(). Since you are implementing type-specific behavior, shouldn't you be calling getSquare() all the time?
You can facilitate castling and pawn double-stepping if you add a "never moved" indicator at the parent level, or specifically to kings, rooks, and pawns.
I'd suggest subclassing black and white pawns. There's no sense checking your color every time. Just build two offset tables.
Some of your code seems awkward. There are places where you have what seems like too many variables. There are other places where you don't loop when you obviously could. I think you need to make a pass and just "clean up" the functions. I suspect that you'll find some common routines when you do.
Creating a new Rook and Bishop on each iteration for evaluating Queen moves seems horribly inefficient. I'd suggest you device a strategy for dealing with "zoomy" pieces, and just maintain a custom offsets table.
As a performance enhancement, you might consider tracking threats to squares, and changes to squares. You could then use this information to avoid recomputing possible moves for pieces where nothing has changed. Basically, a pieces possible moves only change when (1) it moves, (2) a blocking piece moves, (3) a same-colored piece moves into blocking position.

For points 4 and 5, consider this code:

public Collection<Square> generatePossibleMoves() {
    int row = super.getSquare().ROW;
    int column = super.getSquare().COLUMN;
    possibleMoves.clear();
    //all possible moves in the up
    for (int i = row + 1; i < Board.SIZE; i++) {
        Square square = super.getSquare().getBoardSquare(i, column);
        if (square.getPiece() == null) {
            possibleMoves.add(square);
        } else if (isOpponent(square.getPiece())) {
            possibleMoves.add(square);
            break;
        } else {
            break;
        }
    }

Now consider this:

public Collection<Square> generatePossibleMoves() {
    int[][] offsets = { ... };

    possibleMoves.clear();
    Square curr_sq = getSquare();

    for (int[] o : offsets) {
        Square cand_sq = curr_sq;

        for (int i = 1; i < Board.SIZE; ++i) {
            cand_sq = cand_sq.neighbour(o[0], o[1]);

            if (cand_sq == null) break; // Out of bounds

            Piece other = cand_sq.getPiece();

            if (other == null) { // No other piece?
                possibleMoves.add(cand_sq);
            }
            else { // Square is occupied
                if (isOpponent(other)) { // Can capture enemy
                    possibleMoves.add(cand_sq);
                }

                break; // Can't go farther in this direction.
            }
        }
    }

This code loops over the offsets (I copied it from your King method). And it "zooms" in each direction - repeatedly adding the same offset to the 'candidate square'. So instead of writing four different loops for moves in each direction, I can use this same method for any "zoomy" piece, including the Queen. All I need is the right offsets table, which can be a piece of class data.

In fact, if you allow the "zoom limit" to be a class constant instead of using Board.SIZE, you could use the same code for all the pieces, with the "zoom limit" being 1 for kings, knights, and pawns.

Going further, kings, rooks and pawns have special movement options (castling, first double-move) that is only available when the piece has never moved. So you could add this:

    if (neverMoved) {
        possibleMoves.addAll(generateSpecialMoves());
    }

    return possibleMoves;
}

Finally, if you subclass BlackPawn and WhitePawn you can store dedicated offset tables for them, and add support for forward and en passant captures. (Note: I'm waving my hands pretty hard in the en passant section, since I haven't looked at the rest of your code.)

public Collection<Square> generatePossibleMoves() {
    super.generatePossibleMoves();

    Square curr_sq = getSquare();
    Square cand_sq;

    int[][] capture_offsets = {{ FWD_OFFSET, -1}, {FWD_OFFSET, +1}};

    for (int[] o: capture_offsets) {
        cand_sq = curr_sq.neighbour(o[0], o[1]);
        if (cand_sq != null && cand_sq.getPiece() != null && isOpponent(cand_sq.getPiece())) {
            possibleMoves.add(cand_sq);
        }
    }

    int[][] en_passant_offsets = { {0, -1}, {0, +1}};

    Piece ptml = Board.piece_that_moved_last();

    if (ptml.isPawn() && isOpponent(ptml) && ptml.justDoubleMoved()) {
        for (int[] o: en_passant_offsets) {
            cand_sq = curr_sq.neighbour(o[0], o[1]);
            if (cand_sq == ptml.getSquare()) {
                possibleMoves.add(cand_sq);
            }
        }
    }

    return possibleMoves;
}

I appreciate you writing and thanks for the review. If I had to rewrite it today, it would look at lot different :) I would properly not pick Java as my language of choice. Perhaps Kotlin :) — jetersen, Commented Jan 6, 2018 at 0:07

Stack Exchange Network

Generating possible Chess moves

King:

Bishop

Knight

Rook

Queen

Pawn

3 Answers 3

Your Answer

Not the answer you're looking for? Browse other questions tagged
java
chess
or ask your own question.

Hot Network Questions

Generating possible Chess moves

King:

Bishop

Knight

Rook

Queen

Pawn

3 Answers 3

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged javachess or ask your own question.

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
java
chess
or ask your own question.