1

Just like the title says. A mailbox would allow for better handling of checking "which piece is at a certain square," and I see no real downsides to it besides the need to synchronize it with the bitboards properly.

3
  • Since it is redundant you can just remove it.
    – ferdy
    Jun 7 at 0:51
  • Well, it's not really "redundant" per se. It is useful for finding out what piece is on a given square.
    – AAce3
    Jun 7 at 1:38
  • Not sure if the same idea you're proposing, but DanChess uses an "hybrid" system. Also, I guess you could get more help in this forum (but you'd have to provide more details about your idea).
    – emdio
    Jun 7 at 9:50

2 Answers 2

4

Is it worth it to use a redundant mailbox representation in addition to bitboards?

In my estimation, yes.

Bitboards are nice. But as you mentioned, getting information about what pieces sit on a certain square is a pain. You could look through all of your bitboards and test whether a bit is set at that square, but that becomes costly when you're running said functions millions of times.

So as you recognize, a hybrid approach is likely most optimal. And note this isn't at all a strange idea. Most of the top chess engines use it. For example, here's the relevant code from Stockfish:

class Position {

...

private:
  // Data members
  Piece board[SQUARE_NB];
  Bitboard byTypeBB[PIECE_TYPE_NB];
  Bitboard byColorBB[COLOR_NB];
  int pieceCount[PIECE_NB];
  int castlingRightsMask[SQUARE_NB];
  Square castlingRookSquare[CASTLING_RIGHT_NB];
  Bitboard castlingPath[CASTLING_RIGHT_NB];
  Thread* thisThread;
  StateInfo* st;
  int gamePly;
  Color sideToMove;
  Score psq;
  bool chess960;
};

Where board is defined as a 64-element array of Piece objects. You'll see similar definitions in many other engines as well. And I myself actually use this method, after learning the hard way the inadequacy of bitboards to deal with square-centric information.

Do note however that not all engines use this method. Some use the approach of copying the board before making a move, and since this copying process can be expensive, they can't afford to add a whole 64-element piece array to the position. So they find acceptable workarounds.

So my advice? Go for the hybrid approach, it's likely the easiest, most efficient, and most sustainable approach in the long run for writing a good chess engine. But don't just take my word for it either. Experiment and profile and see what works best for your specfic engine. Half the fun of creating an engine is solving your own problems and adapting ideas to fit your unique needs.

3

Maintaining data structures for representing the game state is not a goal in itself. You do it in order to efficiently retrieve data on which you have to make decisions. This often leads to redundancy in the representation. A good example is the material + positional score based on piece-square tables. If you already maintain some board representation, you could calculate it from there whenever you need it, by just adding the contribution from all 32 pieces. But you need it in every node, and daughter nodes only differ in 3 terms of this sum (moved piece in old and new location and captured piece), so it is far more efficient to maintain this redundant sum on the side, and update it incrementally.

Mailbox-based engines usually maintain a redundant 'piece list', for quickly answering the question 'where is/are my king/.../knights/pawns'. For which you otherwise would have to loop over all board squares. Incremental update only requires changing the location of the moved piece, and possibly marking a piece as captured.

Mailbox boards are also ideal for being updated incrementally, as you only have to alter the occupants of two squares, no matter how large the array is. Whether it pays to maintain a redundant data structure depends on how expensive it is to update it, versus how much time it saves compared to calculating the information it provides from scratch. Identifying the type of the captured piece has to be done often enough that it would really hurt to figure it out from the bitboard representation.

In fact bitboards are a comparatively cumbersome and slow method for obtaining the info that chess engines need. Such as knowing what can capture what (i.e. capture generation). It is much faster to do that by maintaining an attack map, which for each piece records the pieces that can capture it or protect it as a 'set' (i.e. 1 bit per piece, indicating whether it attacks or not). It is not extremely difficult to incrementally update such a data structure, and it saves you the work of generating captures from scratch in every node, and sorting the thus obtained captures in an array. (As you can extract the captures from the attack map directly in the desired order, by assigning the bits properly.)

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.