Chess board representation in Java

Question

I'm currently working on a small chess game written in Java (on GitHub). The board is modeled as a Board object with a 2D array of Piece objects :

public class Board {

  private final int ROWS = 8;
  private final int COLS = 8;

  private Piece[][] board;
  private List<Move> moveList;

  [...]

}

At first, I tried to implement all the board's possible states / legal move generation (isCheck, isCheckMate, isStaleMate, legalMoves...) inside the Board class.

For example :

private List<Move> moves(Color color) {

  List<Move> allMoves = new ArrayList<Move>();

  for (int row = 0; row < ROWS; row++) {
      for (int col = 0; col < COLS; col++) {
            Square src = new Square(row, col);
            Piece piece = getPiece(src);

            if (piece == null || !piece.isColor(color))
                 continue;

             allMoves.addAll(piece.availableMoves(src, this));
       }
  }

  return allMoves;
}

However it ended up being about 300 lines and it was not very easy to read (especially because of the duplication of the board iteration loops).

So I decided to try another approach : I removed all the state evaluation code and replaced it with this method :

 public void accept(BoardVisitor bv) {
    for (int row = 0; row < rows; row++) {
       for (int col = 0; col < cols; col++) {
          bv.visit(board[row][col], new Square(row, col));
       }
    }
 }

I then created a set of classes to "evaluate" the different states :

public class CheckEvaluator implements BoardVisitor {

private Square kingSquare;
private Board board;
private Color color;
private boolean isCheck = false;

public CheckEvaluator(Color color, Board board) {
    this.board = board;
    this.color = color;
}

@Override
public void visit(Piece piece, Square src) {
        isCheck = isCheck || piece.canGoTo(src, kingSquare, board);
}

public boolean getResult() {
    this.kingSquare = board.findKing(color);

    board.accept(this);

    return isCheck;
}
}

I regrouped all these evaluators inside a single class :

public class BoardEvaluator {

private Board board;

public BoardEvaluator(Board board) {
    this.board = board;
}

public boolean isCheck(Color color) {
    CheckEvaluator ce = new CheckEvaluator(color, board);

    return ce.getResult();
}

public boolean isCheckMate(Color color) {
    CheckMateEvaluator cme = new CheckMateEvaluator(color, board);

    return cme.getResult();
}

public boolean isStaleMate() {
    StaleMateEvaluator sme = new StaleMateEvaluator(board);

    return sme.getResult();
}

public List<Move> legalMoves(Color color) {
    LegalMovesEvaluator lme = new LegalMovesEvaluator(color, board);

    return lme.getResult();
}

This version seems clearer and easier to me but I don't have a lot of experience and I'd be very glad to get some feedback about it:

• Do you think this is a valid design?
• Is my BoardVisitor a good (if simple) implementation of the Visitor pattern?

Answer 1

Warning! Arm Chair Quarterbacking in progress. Given that I offer this.

Game Class

Why is this Board.moveList in the Board class? You need a "driver" for a chess game and that would be a Game class. "A game consists of (has) moves" makes more sense.

The Game gives us a conceptual framework for a richer chess game. A Game has players, may have a timer for speed chess, and can keep track of pieces removed from the board; and of course records the moves.

Board Class

The chess board is a data structure. Don't make more of it than it is; nor less.

In the Visitor Pattern the data structure has-a element that has an accept method. That element seems to be a Square. I'm not certain if it's better than the Board being visited, but certainly the point is that we're evaluating the state at that one square? I don't see a big deal in giving a board reference to each square.

OR .. maybe the Pieces are visited. To test if the piece is "inCheck" for example. This perspective makes more sense than a square is in check. Is this why your board is Piece[][] and not Square[][]?

Whether we are visiting the board and iterating the squares; or iterating the board and visiting the squares; or iterating the squares and visiting the pieces may be more than semantics. I vote for whatever best reflects intent, gives me good code expressions, and sensible building blocks.

In any case I agree with @bowmore about refactoring Piece[][] to Square[][].

Pieces

Even given a rich Piece class, I like the idea of using an enumeration for names. This makes for nicer coding and expressability overall (and my pet peeve - it avoids strings). Maybe two enumerations. As in White.Knight and Black.Queen; or Pieces.WhiteKnight, Pieces.BlackQueen And a value to represent an empty square might be nice Pieces.none or Pieces.undefined.

Maybe Piece has a Square reference so it knows where it is. This may have a nice effect on the visit code.

Visitor Pattern

Nice call.

I agree with @MarcoForgerg, the visitors do not need to keep state. Just pass in the needed parameters and forget-about-it when done. And, instead of Singletons perhaps just static.

Nested visitors? Ok, so the board gets "visited" which in turn "visits" each square, which in turn, finally gets to Piece.accept(Evaluator xxxx). Visitors, by definition, understand their visited data structure so I'm thinking board iteration is wrapped in the board visitor, and the square visitor knows to check for an occupying piece and knows what Evaluator(s) to pass to the piece. It feels like nicely layered (code) logic to me. And note how the iteration logic is in the visitors, not the board (data structure). And subsequently all the business logic is in the visitor as well.

SO instead of this

public void accept(BoardVisitor bv) {
    for (Square square : board) {
       bv.visit(square);
    }
}

THIS - Let the Visitor do the walking and talking (decision making). And the decision to evaluate empty squares is delayed as long as possible - push details down. Note that Board, Square, Piece visiting logic is decoupled/layered.

// in Board class
public void accept(BoardVisitor bv) { bv.visit(this));}

// BoardVisitor class
public void visit (Board board) {
    // "board level" logic as needed
    for (Square square in board) {
        square.accept (this.squareVisitor);
    }
}

// Square class
public void accept (SquareVisitor sv) {
    sv.visit(this);
}

// SquareVisitor class
public void visit (Square square) {
   // "square level" logic as needed
   if(!square.isEmpty) {
       // maybe we target Evaluators for the particular piece on the square

       this.evaluator(square); // square has references to its piece and board.
         // maybe the square.piece has "visit"
   }
}

Answer 2

At the moment it seems your board holds 64 (8*8) Pieces :

private Piece[][] board;

It would be more logical to have :

private Square[][] board;

Secondly, you can avoid a lot of nested loops by representing the board with a one dimensional array :

private Square[] board;

Which is simply putting all rows in one big sequence. For the clients of Board this can be perfectly well hidden by converting coordinates to index behind the scenes :

private Square at(int row, int col) {
    return board[row * COLS + col];
}

This, for instance, greatly simplifies the accept method :

public void accept(BoardVisitor bv) {
    for (Square square : board) {
         bv.visit(square);
    }
}

Edit :

The responsibility of the Board class is to keep track of the positions of the pieces on the chess board. In essense this would lead me to this interface :

public interface Board {
    Square positionOf(Piece piece);
    Piece at(Square square);
    void make(Move move);
}

Your current implementation (an array that contains Pieces) would make at() faster than positionOf(). Though other data structures would be possible. (I'm thinking of a bidirectional map of Piece and Square).

You worried about a board keeping 64 square instances around, I worried about creating the same Squares over and over. I'd say both worries would amount to premature optimization. At the moment, I would simply ensure we can address it both ways : make a static factory method on Square :

public static Square valueOf(int col, int row) { return new Square(col, row); }

This allows the board not to worry about whether it is creating new squares or not, and if need be the factory method can later be changed to do a lookup in a cache (an array of Square), rather than creating a new one every time.

For your current implementation I would suggest you simple rename the Piece array from board to positions, just to take away the suggestion that a Board is 64 Pieces.

I think the visitor pattern is overkill (there is no family of classes we want to add behavior to). Extracting the board evaluators out of the Board class is, however, a very good idea. The Iterator pattern will be more than enough. So maybe :

public interface Board {
    Square positionOf(Piece piece);
    Piece at(Square square);
    void make(Move move);
    Iterator<Square> allSquares(); // traverse all Squares of the board
    Iterator<Piece> allPieces(); // traverse all Pieces still on the board.
}