Answers.Body: <p>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.</p>
  <p>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.</p>
  <p>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.</p>
  <p>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.)</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-07-02T13:03:37.907Z
Answers.LastActivityDate: 2022-07-02T13:03:37.907Z
Answers.UserDisplayName: H.G.Muller
Answers.Body: <blockquote>
  <p>Is it worth it to use a redundant mailbox representation in addition
  to bitboards?</p>
  </blockquote>
  <p>In my estimation, yes.</p>
  <p>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.</p>
  <p>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, <a href="https://github.com/official-stockfish/Stockfish/blob/master/src/position.h#L189" rel="nofollow noreferrer">here's the relevant code from Stockfish</a>:</p>
  <pre><code>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;
  };
  </code></pre>
  <p>Where <code>board</code> is defined as a 64-element array of <code>Piece</code> 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.</p>
  <p>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.</p>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-06-07T15:01:00.613Z
Answers.LastActivityDate: 2022-06-07T15:01:00.613Z
Answers.UserDisplayName: Chris
Body: <p>Just like the title says. A mailbox would allow for better handling of checking &quot;which piece is at a certain square,&quot; and I see no real downsides to it besides the need to synchronize it with the bitboards properly.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-06-07T00:51:19.113Z
Comments.Text: Since it is redundant you can just remove it.
Comments.UserDisplayName: ferdy
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-06-07T01:38:58.320Z
Comments.Text: Well, it's not really "redundant" per se. It is useful for finding out what piece is on a given square.
Comments.UserDisplayName: AAce3
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-06-07T09:50:52.223Z
Comments.Text: Not sure if the same idea you're proposing, but [DanChess](https://www.chessprogramming.org/DanChess) uses an "hybrid" system.
  Also, I guess you could get more help in [this forum](http://talkchess.com/forum3/viewforum.php?f=7&sid=ad192b734adef5de8ff5c29b4dd39709) (but you'd have to provide more details about your idea).
Comments.UserDisplayName: emdio
Tags: <engines>
Title: Is it worth it to use a redundant mailbox representation in addition to bitboards?
ThreadText: # Is it worth it to use a redundant mailbox representation in addition to bitboards?
  
  (Asked by: username_0 on 2022-06-06)
  
  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.
  
  **Tags:** engines
  
  > **Comments:**
  > **username_1**: Since it is redundant you can just remove it.  
  > **username_0**: Well, it's not really "redundant" per se. It is useful for finding out what piece is on a given square.  
  > **username_2**: Not sure if the same idea you're proposing, but [DanChess](https://www.chessprogramming.org/DanChess) uses an "hybrid" system. Also, I guess you could get more help in [this forum](http://talkchess.com/forum3/viewforum.php?f=7&sid=ad192b734adef5de8ff5c29b4dd39709) (but you'd have to provide more details about your idea).  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_4 on 2022-06-07. Score: 4 | Accepted answer
  
  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.
  
  
  ---
  
  ### Answer by username_3 on 2022-07-02. Score: 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.)
  
  
  ---
  
  