Making Good Software

A blog by Alberto G (Alberto Gutierrez)

Written by Alberto Gutierrez

May 16th, 2011 at 3:07 pm

Progamming a chess engine with Java (I) – Finding where a piece can move.

without comments

A few weeks ago, I posted an article describing some Java code which would be able to solve any Sudoku using tree data structures. After this article, I thought it would be nice to continue developing around tree data structures, and that’s when I decided to code a chess engine in Java.

This is the first installment of a series of articles that will describe this chess engine as I am developing it. It will also use, the tree library that I created for the Sudoku resolver. You can find the complete source code in the link provided at the bottom of the article, any feedback on the code will be very much appreaciated.

The Chess Board class

public class ChessBoard {
	private final Squares squares;

	public ChessBoard() {
		this (new Squares());
	}

	public ChessBoard(Squares squares) {
		this.squares = squares;
	}

	public ChessBoard performMovement(Piece piece, Location locationFrom, Location locationTo) {
		Squares copy = squares.copy();
		copy.setContent(SquareContent.EMPTY_SQUARE, locationFrom.getCoordinateX(), locationFrom.getCoordinateY());
		copy.setContent(piece, locationTo.getCoordinateX(), locationTo.getCoordinateY());
		return new ChessBoard(copy);
	}

	public ChessBoard performMovement(PieceOnLocation pieceInBoard, Location locationTo) {
		return performMovement(pieceInBoard.getPiece(), pieceInBoard.getLocation(), locationTo);
	}

	public ChessBoard performMovement(Movement movement) {
		return performMovement(movement.getMovingPiece(), movement.getFrom(), movement.getTo());
	}

	public SquareContent getSquareContent(Location location) {
		return squares.getContent(location.getCoordinateX(), location.getCoordinateY());
	}

	public ChessBoard addPiece(Piece piece, Location location) {
		Squares copy = squares.copy();
		copy.setContent (piece, location.getCoordinateX(), location.getCoordinateY());
		return new ChessBoard(copy);
	}

	public List<PieceOnLocation> getPieces(Color movingColor) {
		List<PieceOnLocation> pieces = new ArrayList<PieceOnLocation>();
		for (Location location : Location.values()) {
			SquareContent content = squares.getContent(location.getCoordinateX(), location.getCoordinateY());
			if (! content.isEmpty()){
				Piece piece = (Piece) content;
				if (piece.getColor() == movingColor) pieces.add(piece.on(location));
			}
		}
		return pieces;
	}

	public List<PieceOnLocation> find(Piece pieceToFind) {
		List<PieceOnLocation> pieces = new ArrayList<PieceOnLocation>();
		for (Location location : Location.values()) {
			SquareContent content = squares.getContent(location.getCoordinateX(), location.getCoordinateY());
			if (! content.isEmpty()){
				Piece piece = (Piece) content;
				if (piece == pieceToFind) pieces.add(piece.on(location));
			}
		}
		return pieces;
	}

	public PieceOnLocation getPieceOnLocation(Location location) {
		return new PieceOnLocation(getSquareContent(location).asPiece(), location);
	}

	public ChessBoard empty(Location location) {
		Squares copy = squares.copy();
		copy.setContent(SquareContent.EMPTY_SQUARE, location.getCoordinateX(), location.getCoordinateY());
		return new ChessBoard(copy);
	}
}

About the Chess Board class is important to notice 3 things:

  1. Is thread safe. All is member variables are private and final, and is immutable, all the “changing operations” create a copy of the object with the new state.
  2. It delegates all the functionality to Squares. Squares is the main class, it contains all the logic for holding SquareContent objects (Pieces and empty squares). It is wrapped by the Board to achieve thread safeness.
  3. It is easy to create and customise a board, we only have to create a new board, and call the method addPiece. (See example below).

Creating a new board with a few pieces.

board = new ChessBoard().
			addPiece(Piece.BLACK_PAWN, Location.C5).
			addPiece(Piece.WHITE_PAWN, Location.D5).
			addPiece(Piece.WHITE_KING, Location.D4);

The Chess Analiser

This class contains the main entry points for all the main logic, in particular, we are interested in the method findReachableLocations and in the default implementation ChessAnaliserImpl.

public interface ChessAnaliser {
	[...]
	public List findReachableLocations(PieceOnLocation pieceOnLocation, ChessBoard board, Movement previousMovement);
}
public class ChessAnaliserImpl implements ChessAnaliser {
@Override
	public List<Location> findReachableLocations(PieceOnLocation pieceOnLocation, ChessBoard board, Movement previousMovement) {
		Piece piece = pieceOnLocation.getPiece();
		List<Location> toReturn = new ArrayList<Location>();

		for (MovementLine movementLine : chessReader.findMovementLines(pieceOnLocation)) {
			if (movementLine.isApplicable (board, previousMovement)){
				List<Location> potentiallyReachablePositions = movementLine.filterPotentiallyReachablePositions (pieceOnLocation.getColor(), board);
				for (Location location : potentiallyReachablePositions) {
					ChessBoard nextPossibleBoard = nextBoard(board, movementLine.getType(), pieceOnLocation, location, previousMovement);
					if (!isInCheck(nextPossibleBoard, piece.getColor())){
						toReturn.add(location);
					}
				}
			}
		}

		return toReturn;
	}
}

Take into consideration:

  1. [Line 07]. The base of any movement is the movement line. The MovementLine class defines the type of movement and the different locations for that movement type that a piece can potentially move to given a starting position. Movement lines don’t take into consideration other pieces in the board.
  2. [Line 08]. The method isApplicable, in the movement line, checks if that movement line is applicable for a given board taking into consideration the previous movement. The clearest example here would be the movement line for a pawn to do an “en passant” movement, this method will check if all the conditions for an en passant movement are true.
  3. [Line 09] The method filterPotentiallyReachablePositions checks from all the possible locations of a movement line, how many are reachable, so if there is a piece that is actually standing in the middle of the board for that movement line, it will filter out all the positions after that piece . (See examples below).
  4. [Lines 11 and 12] For all the potential locations that given piece can move to, it finds what the next board would be, and then it checks wether if the movement would cause the pieces for that color to be in check. This would be an illegal movement, so the location would be discarded.

Tying everything together

The following are real examples to find what the possible locations for the given pieces are:

public class ChessAnaliserImplIntegrationTest {
	private ChessAnaliserImpl testObj;
	private ChessReader chessReader = new ChessReaderImpl();
	private ChessBoard board;

	@BeforeMethod (groups="integration")
	public void setup (){
		testObj = new ChessAnaliserImpl (chessReader);
	}

	@Test (groups="integration")
	public void testFindReachableLocations_forRook_withSameColorObstacles (){
		//GIVEN
		board = new ChessBoard().
			addPiece(Piece.WHITE_ROOK, Location.A1).
			addPiece(Piece.WHITE_QUEEN, Location.A5).
			addPiece(Piece.WHITE_KNIGHT, Location.C1).
			addPiece(Piece.WHITE_KING, Location.C8);

		//WHEN
		List<Location> actualReachablePositions = testObj.findReachableLocations(board.getPieceOnLocation (Location.A1), board, null);

		//THEN
		Assert.assertEquals(actualReachablePositions.size(), 4);
		Assert.assertEquals(actualReachablePositions.get(0), Location.B1);
		Assert.assertEquals(actualReachablePositions.get(1), Location.A2);
		Assert.assertEquals(actualReachablePositions.get(2), Location.A3);
		Assert.assertEquals(actualReachablePositions.get(3), Location.A4);
	}

	@Test (groups="integration")
	public void testFindReachableLocations_forRook_withDifferentColorObstacles (){
		//GIVEN
		board = new ChessBoard().
			addPiece(Piece.WHITE_ROOK, Location.A1).
			addPiece(Piece.BLACK_QUEEN, Location.A5).
			addPiece(Piece.WHITE_KNIGHT, Location.C1).
			addPiece(Piece.WHITE_KING, Location.C8);

		//WHEN
		List<Location> actualReachablePositions = testObj.findReachableLocations(board.getPieceOnLocation (Location.A1), board, null);

		//THEN
		Assert.assertEquals(actualReachablePositions.size(), 5);
		Assert.assertEquals(actualReachablePositions.get(0), Location.B1);
		Assert.assertEquals(actualReachablePositions.get(1), Location.A2);
		Assert.assertEquals(actualReachablePositions.get(2), Location.A3);
		Assert.assertEquals(actualReachablePositions.get(3), Location.A4);
		Assert.assertEquals(actualReachablePositions.get(4), Location.A5);
	}

	@Test (groups="integration")
	public void testFindReachableLocations_forRook_whenCantMove (){
		//GIVEN
		board = new ChessBoard().
			addPiece(Piece.WHITE_KING, Location.D1).
			addPiece(Piece.WHITE_ROOK, Location.C2).
			addPiece(Piece.BLACK_QUEEN, Location.A4).
			addPiece(Piece.WHITE_KNIGHT, Location.C1);

		//WHEN
		List<Location> actualReachablePositions = testObj.findReachableLocations(board.getPieceOnLocation (Location.C2), board, null);

		//THEN
		Assert.assertEquals(actualReachablePositions.size(), 0);
	}

	@Test (groups="integration")
	public void testFindReachableLocations_forPawn_whenInFirstRow (){
		//GIVEN
		board = new ChessBoard().
			addPiece(Piece.BLACK_PAWN, Location.A7).
			addPiece(Piece.BLACK_KING, Location.D4);

		//WHEN
		List<Location> actualReachablePositions = testObj.findReachableLocations(board.getPieceOnLocation (Location.A7), board, null);

		//THEN
		Assert.assertEquals(actualReachablePositions.size(), 2);
		Assert.assertEquals(actualReachablePositions.get(0), Location.A6);
		Assert.assertEquals(actualReachablePositions.get(1), Location.A5);
	}

	@Test (groups="integration")
	public void testFindReachableLocations_forPawn_enPassant (){
		//GIVEN
		board = new ChessBoard().
			addPiece(Piece.BLACK_PAWN, Location.C5).
			addPiece(Piece.WHITE_PAWN, Location.D5).
			addPiece(Piece.WHITE_KING, Location.D4);

		Movement enPassantEnabler = new Movement(Piece.BLACK_PAWN, Location.C7, Location.C5);
		//WHEN
		List<Location> actualReachablePositions = testObj.findReachableLocations(board.getPieceOnLocation (Location.D5), board, enPassantEnabler);

		//THEN
		Assert.assertEquals(actualReachablePositions.size(), 1);
		Assert.assertEquals(actualReachablePositions.get(0), Location.C6);
	}
}

Source code

All the source code can be found in the following SVN URL http://subversion.assembla.com/svn/making-good-software/tags/mgsChess/blog20110515/