5
\$\begingroup\$

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?
\$\endgroup\$
  • \$\begingroup\$ at a first glance it looks nice to me. just two things: 1. according to Java naming conventions your static final members should be COLS and ROWS and 2. bv.visit(board[row][col], new Square(col, row)); looks confusing to me. You should consider reordering the parameters and always use row or colas first parameter \$\endgroup\$ – Marco Forberg Jun 18 '13 at 6:57
  • \$\begingroup\$ Thank you very much for your comment! I've edited my post to take your remarks into account. How about the fact that a new evaluator is created each time one of the BoardEvaluator method is called? Should I try to implement some kind of singleton pattern? (only one instance for each board/color couple...) \$\endgroup\$ – ouzned Jun 18 '13 at 8:08
  • \$\begingroup\$ I wonder if your Evaluators have to be stateful at all. If it would suffice to pass board and color to the evaluation method you could implement them as singletons \$\endgroup\$ – Marco Forberg Jun 18 '13 at 8:20
  • \$\begingroup\$ Yeah I'll pass the board to getResult() and use the Evaluators as singletons. Thanks \$\endgroup\$ – ouzned Jun 18 '13 at 16:12
4
\$\begingroup\$

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"
   }
}
\$\endgroup\$
  • \$\begingroup\$ Your points are very interesting! The moveList should indeed belong to the Game object. Concerning the Piece[][], please read my answer to @bowmore above. As for the visitor, I agree that it has a knowledge of the entity it visits (in the sense that it knows the entity exists) but I think it shouldn't understand the entity's internal representation. As a result the visitor can't know how to iterate over the board pieces, hence the iteration inside the Board class. Your nested visitor example is quite interesting but don't you think in this case we only visit the board as a "whole"? \$\endgroup\$ – ouzned Jun 18 '13 at 18:27
  • \$\begingroup\$ (1) Ah, I see your rational for Piece[][]. If a Piece has a position property then maybe no need for Square at all? (2) Client code (Board class, Evaluators) manipulating things in terms of chess is the holy grail of OO here and as long as higher level code does not obfuscate what's going on then fine. (3)Re: Iterator vs. visitor. Iterator, good idea. But not mutually exclusive. Iterator abstracts looping thru a pile of stuff. Visitor decouples logic code, allowing you to "swap out" different visitor behavior on each iteration. \$\endgroup\$ – radarbob Jun 19 '13 at 13:19
2
\$\begingroup\$

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.
}
\$\endgroup\$
  • \$\begingroup\$ Thanks for your answer! I agree that storing the Piece objects into a flat array simplifies the accept method. However I think the board doesn't really need to generate and keep 68 square objects just for the sake of setting a Piece on a Square. The way I see it, Square objects are only used to communicate position throughout the application instead of using basic integers. Aside from that, I don't see the benefits of changing the Piece[] into a Square[]. (btw, a Piece[][] doesn't mean that the board contains 64 pieces, only that it contains 64 placeholders that may or may not contain one) \$\endgroup\$ – ouzned Jun 18 '13 at 17:03
  • \$\begingroup\$ I understand that the name doesn't imply that there are 64 pieces, it just suggests it when you read the code, so readability could be improved there. Secondly, while unwilling to have the board keep 64 squares around, you are willing to create 64 new ones whenever a visitor passes through all coordinates... \$\endgroup\$ – bowmore Jun 18 '13 at 20:24
  • \$\begingroup\$ Well, I prefer to create Square objects that are quickly discarded rather than keeping them around for the entire duration of the game. Another reason behind this is that putting pieces on Squares would force me to create duplicates when copying the Board. Right now, I only have to clone the array as the Pieces are stateless. \$\endgroup\$ – ouzned Jun 18 '13 at 20:49
  • \$\begingroup\$ I never said to make Squares mutable. \$\endgroup\$ – bowmore Jun 18 '13 at 22:58
  • \$\begingroup\$ Sorry I thought that was what you meant. Would you then create a copy of the square only when a piece is moved on the board? \$\endgroup\$ – ouzned Jun 18 '13 at 23:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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