Problem
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;
}
Solution
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).
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.
-
I’m confused on why you sometimes call
super.getSquare()and other times just callgetSquare(). Since you are implementing type-specific behavior, shouldn’t you be callinggetSquare()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;
}