Should I use object references or integral values to store pieces in a chess board?

Question

just a general question regarding a checkers project. I built a class hierarchy for the game pieces (that could be extended for chess etc). The hierarchy looks something like

interface GamePiece() {...}
class EmptySquare implements GamePiece {...}
class Pawn implements GamePiece extends EmptySquare {...}
class Queen implements GamePiece extends EmptySquare {...} 

I store an object reference in the board[][] array. In the tree search that array is cloned for each recursion (not with doMove() ... call recursion ... undoMove()). I store object refs for the game pieces so I can do something like this for generating the list of moves:

for(sq:Squares) 
    sq.getPossibleMoves()
    possibleMoves.addAll(sq.possibleMoves)

I'm not sure how much space this array of references takes up and if that is any good way to it from a performance point of view. It works nicely logically though. Would you do it like that or sacrifice the nicer code for a more compact game board array and the use switch() to call subroutines for each piece to make the move list?

Answer 1

Most modern chess engines use redundant methods of storing the board. For example, my own engine uses bitboards (64-bit integer for each possible piece type - see http://chessprogramming.wikispaces.com/Bitboards) as the primary board representation, but also makes use of a one-dimensional array of integers. In this array, empty squares are represented by 0, while the white pieces are represented by integers 1 through 6 for pawn, knight, bishop, rook, queen and king. Black pieces are the white pieces multiplied by -1, so the white pawn is 1, black bishop is -3 and so on.

This redundant representation comes at a cost when making moves, as there is more to update, but it pays off elsewhere in the program. For example, we can easily answer questions such as "what piece is on f4?" (array) or "which black pawns are attacking white pieces?" (bitboards).

To more directly answer the question - go with the array and switch statement if you're looking for pure performance, which is the case for most chess engine authors. At an early stage of developing my engine, I used a similar inheritance scheme, with a Piece interface implemented by classes like WhitePawn and Bishop. This worked fine, but was awfully slow, and I eventually went through the effort of replacing the scheme with the integer array, and eventually adding the bitboards. There is a lot of messy code involved behind the scenes, but it's all abstracted away neatly enough and the benefits are many.

I highly recommend reading articles that take your interest on the chess programming wiki (http://chessprogramming.wikispaces.com/), as I found it to be an invaluable resource in every phase of development. Many concepts are also directly applicable to other board games, especially checkers!

Answer 2

Here's how I would move pieces around:

private void playChess() {

    Board board = new Board();
    board.makeSquares();
    System.out.println(board);
    Square startingSquare = board.getSquare(3, 1);  //   0<=x<=7, 0<=y<=7  (file, rank)
    Square endingSquare = board.getSquare(3, 4);  //illegal move
    ChessPiece pawn = startingSquare.getPiece();  //assumes a pawn is at that square...
    System.out.println(pawn.toString());
    try {
        board.movePiece(startingSquare, endingSquare);
    } catch (IllegalMove ex) {
        System.out.println(ex);  //pawns can only move two spaces, so it's an illegal move
    }
    System.out.println(board);
}

The important thing is to only allow the board to move pieces, I think, but have the logic for movement into the pieces. The knight would be the most difficult, followed by the pawn (because the pawn can move twice at first, and en passant). I would have the pawn throw an error to the square, and then to the board, to catch the illegal move in the driver.

Some code:

https://github.com/THUFIR/StackOverflow/tree/0001chess_boar

Answer 3

It depends on what you want to do.

Do you have an AI or not? If not, then it hardly matters. About all modern devices have more than enough memory to handle 32 pieces on 64 fields, no matter how you represent them. Here you should make the code the way it looks/feels best for you.

If you do have an AI that you want to do quite good then you will need the most effective data structure behind the whole thing. It doesn't matter so much whether you use referenced objects or an int as ID but it matters much more what kind of data structure you are using.

I would probably use multiple data structures in combination. On the one hand you need to be able to do a quick look-up if a field is occupied and what unit occupies it. For this it is best to use a 2D-array. On the other hand you need a data structure where you only have the units of each player in it, so you don't have to iterate over all 64 fields just to find the two remaining pieces. Here something like a linked list would do just fine.

I'd probably use reference types, just because they make programming so much easier.