Answers.Body: <p>This is a very deep subject, but here's a few basic thoughts that might get you going.</p>
  
  <p>A bitboard consists of 64 bits. If you designate one corner of the board as the most-significant bit and the opposite corner as the least-significant bit, you can store a bitboard in a single 64-bit integer.</p>
  
  <p>For example, suppose A1 is the LSB and H8 is the MSB. We will fill up the 64-bit integer moving left-to-right (A-to-H) and then down-to-up (1-to-8). Your sample turns into:</p>
  
  <pre><code>0000000000000000000000000100000000100000000000000010000001000000
  </code></pre>
  
  <p>and this 64-bit integer represents the possible "landing" locations of a knight located at A6. In C this could be stored like:</p>
  
  <pre><code>long long knight_a6 = 0x4020002040;
  </code></pre>
  
  <p>We can do this for <em>every</em> possible location of the knight, in the same order that we filled out the bitboard (left-to-right, down-to-up). In other words:</p>
  
  <pre><code>A1: 0000000000100000010000000000000000000000000000000000000000000000
  A2: &lt;bitboard for a knight at A2&gt;
  ...
  B1: &lt;bitboard for a knight at B1&gt;
  ...
  H8: &lt;bitboard for a knight at H8&gt;
  </code></pre>
  
  <p>This will take up 64 entries * 64 bits each = 512 bytes of space. Now we can determine the possible landing locations of a knight at <em>any</em> location, just by looking at the corresponding entry in the table. In C it could look something like this:</p>
  
  <pre><code>long long knight[64] = { 0x0020400000000000,
                           &lt;bitboard for a knight at A2&gt;,
                           ... };
  long long knight_a6 = knight[40]; /* A6 = index 40 */
  </code></pre>
  
  <p>These are all static bitboards: they're just there for your convenience when programming. But you'll probably also want some active bitboards that represent the state of the game. For example, you'll probably want a bitboard that represents where all the pieces are. At the start of the game ranks 1, 2, 7, and 8 are full, so the bitboard looks like this:</p>
  
  <pre><code>1111111111111111000000000000000000000000000000001111111111111111
  </code></pre>
  
  <p>Or in C:</p>
  
  <pre><code>long long game = 0xFFFF00000000FFFF;
  </code></pre>
  
  <p>So what can you <em>do</em> with bitboards? Well, for starters you can determine if a piece (say, a knight at A6) is attacking another piece. To do this you perform a logical AND between the game bitboard and the static bitboard for the attacking piece. Let's say the game looks like this:</p>
  
  <pre><code>00000000
  00k00000
  N0000000
  00000000
  00000000
  00000000
  00000000
  000000K0
  </code></pre>
  
  <p>The white king is on G1, the white knight is on A6, and the black king is on C7. The game bitboard would look like this:</p>
  
  <pre><code>0000001000000000000000000000000000000000100000000010000000000000
  </code></pre>
  
  <p>Let's see if the white knight is putting the black king in check. First, we look up the white knight's "landing" bitboard as described earlier.</p>
  
  <pre><code>0000000000000000000000000100000000100000000000000010000001000000
  </code></pre>
  
  <p>Now we AND that bitboard together with our game bitboard.</p>
  
  <pre><code>    0000001000000000000000000000000000000000100000000010000000000000
  AND 0000000000000000000000000100000000100000000000000010000001000000
      ----------------------------------------------------------------
      0000000000000000000000000000000000000000000000000010000000000000
  </code></pre>
  
  <p>The result is <strong>not</strong> all-zeroes, so the selected piece is attacking <em>something</em>. Here's it is in C:</p>
  
  <pre><code>long long game = 0x200000000802000;
  long long attacker = knight[40]; /* A6 = index 40 */
  if (game &amp; attacker != 0)
  {
    /* The knight at A6 is attacking something! */
  }
  </code></pre>
  
  <p>The next step is to see what he's attacking. There are multiple ways to do this: you could see where the 1 appeared in the ANDed bitboard and find the corresponding square, or you could keep a bitboard for every different type of piece. Let's leave it at that for now though.</p>
  
  <p>Next let's see how pieces can be moved. We'll remove the black king from the board for simplicity.</p>
  
  <pre><code>00000000
  00000000
  N0000000
  00000000
  00000000
  00000000
  00000000
  000000K0
  
  Bitboard: 0000001000000000000000000000000000000000100000000000000000000000
  </code></pre>
  
  <p>Looking at the knight's landing bitboard we can see there are four one's, so four possible moves. Let's take the first one - so we'll erase all the other zeroes in the bitboard for now.</p>
  
  <pre><code>0000000000000000000000000100000000000000000000000000000000000000
  </code></pre>
  
  <p>To move the knight, we erase him from the game bitboard, and then AND the game bitboard with the knight's move bitboard.</p>
  
  <pre><code>       0000001000000000000000000000000000000000100000000000000000000000
  ERASE  0000000000000000000000000000000000000000100000000000000000000000
         ----------------------------------------------------------------
         0000001000000000000000000000000000000000000000000000000000000000
  OR     0000000000000000000000000100000000000000000000000000000000000000
         ----------------------------------------------------------------
         0000001000000000000000000100000000000000000000000000000000000000
  </code></pre>
  
  <p>The new gameboard looks like this:</p>
  
  <pre><code>00000000
  00000000
  00000000
  00000000
  0N000000
  00000000
  00000000
  000000K0
  </code></pre>
  
  <p>Now, there are a <strong>lot</strong> of things brushed over in this answer:</p>
  
  <ol><li>How do you track what kind of piece is at each location?</li>
  <li>How do you distinguish between white and black?</li>
  <li>How do you distinguish between captures and normal moves?</li>
  <li>How do you determine which squares are "shielded" behind another piece?</li>
  <li>How do you handle pawns, which move in a different way than they capture?</li>
  <li>How do you handle the initial pawn move and capture en passant?</li>
  </ol>
  
  <p>Not all bitboards are the same, either. What if we filled out the bitboard in a fancier order than just going left-to-right, bottom-to-top? Maybe there's some other way to assign squares to bits that makes certain checks or moves faster. The way we've written it is just the simplest to picture.</p>
  
  <p>Again, this is a very deep subject, but hopefully this at least explained some of the basics about how bitboards are used.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-03-04T02:16:48.667Z
Answers.Text: I think you avoided the question. I think the question was how to represent a move, not how to apply one. If you want a legal move neighbor generator, not legal state generator, you need a way to represent a move. The most efficient way isn't an intuitive simple bitboard manipulation.
Answers.UserDisplayName: Harrichael
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2015-07-13T19:58:48.600Z
Answers.LastActivityDate: 2019-09-21T17:46:23.250Z
Answers.LastEditDate: 2019-09-21T17:46:23.250Z
Answers.UserDisplayName: intx13
Answers.Body: <p>Smallchess berated me but didn't understand my post. I can't put a comment yet, so I will detail my example with more step by step explanations in this new post :</p>
  
  <p>bmna6 contains 4 bits at 1, for the squares b4, c5, c7, b8
  bg1 contains one bit at 1, for square g1. If you put b := bmna6 OR bg1, you obtain a bitmap b with 5 bits, which is different from bmna6. So g1 is not attacked by the Na6.</p>
  
  <p>If the king is on c7 instead, then bmna6 == (bmna6 OR bc7), so the king is in check.</p>
  
  <p>You can do a AND and compare to 0, but afaIk the processing time to compare an unsigned int to zero is the same (on x64/x86 at least) as the processing time to compare to a positive unsigned int, and the OR and AND binary operators also have similar processing times. So the two methods are the same for processing time.
   One advantage of doing a OR instead of a AND is that the resulting bitboard can be used again, for calculating paths to checks (ie to determine how a rook can give check in 2 moves, or a knight in 3 moves.. this can be very useful, for instance if coding a chess problem solver, or a SPG solver, etc..). While we already know the result of the AND in case of check, it's the bitboard giving the square where the check happens, which is bc7 in the second exemple, so no new information generated : we already know where the king is.</p>
  
  <p>On the other hand, let's say that instead of wanting to test if the Na6 gives check, you want to test if it's able to capture something. Then you will use a AND between bmna6 and the bitboard of all the black pieces. It will give us a very useful bitboard : the list of squares where the Na6 can capture something. That is what Glorfindel's explanations actually show (but it's best suited for testing non specific captures, not checks, unless you play a fancy feeric variant where black has several kings or where black s pieces are undetermined, one of them possibly being the king).</p>
  
  <p>Also, just to clarify, to check if a king in g1 is attacked by a knight on a6, with bmna6 being the predefined bitboard mask of the possible landing squares of a N on a6 and with bsqg1 being the bit map with a 1 only for square g1, you do a OR of bmna6 and bsg1, and if it's equal to bmna6(which isn't the case) then the king is in check by that knight.
   Obv it's more complex for long range pieces.</p>
  
  <p>To generate and store moves, you need to define a chessboard class and a move class, with the infos that interest you for whatever your purpose is (usually the chessboard stores at least whose turn it is to play. You can for instance have him store the list of legal moves, have a method chessboard.play(move) which will both update the board, update the player whose turn it is, update the list of legal moves.. possibly keep an history of previous moves as well.. UP to you, really depends on what you want to do. You won't code exactly the same way wether you want to code an engine, a mere replayer, or a problem solver who also solves serial-movers..</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-11-08T19:05:43.677Z
Answers.Text: Please consider merging your accounts. See https://chess.stackexchange.com/help/merging-accounts
Answers.UserDisplayName: Herb
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2017-11-08T18:50:18.133Z
Answers.LastActivityDate: 2019-09-21T13:50:23.587Z
Answers.LastEditDate: 2019-09-21T13:50:23.587Z
Answers.UserDisplayName: Emphyrio
Answers.Body: <p>My last chess engine used bitboards to store position information. It represented moves as a vector of simple move structures that looks something like this: </p>
  
  <pre><code>struct move_info {
      char move[2];        //origin and destination squares (0 - 63)
      bool side;           //side moving LIGHT=0 or DARK=1
  
      char piece;          //king=0, queens=2,rooks=4,bishops=6,pawns=8
      char captured_piece; //king=0, queens=2,rooks=4,bishops=6,pawns=8
      bool capture;        //is this move a capture
  
      bool canCastle_off[4];
      bool isCastle[4];
  
      bool passant_capture;   //is this move a capture using en passant
      char enPassant;         //if the pawn is pushed two places, set en passant square, along with the square the pawn is on for capture porpoises
  
      bool promotion;
      char promotion_piece;
  };
  </code></pre>
  
  <p>Then to make the move it would take the move info in a node of the moves vector and update all bitboards. Essentially this means there is a 'position' represented by bitboards, and a list of moves that effect that position. Note that this engine was written when I was a much less experienced programmer. </p>
  
  <p>I'm currently working on a new chess engine which will have a class named 'Position' which carries all needed information for a single position in bitboards. Then, I'll create a linked list of positions for the game tree. I think this will be more efficient then having a list of 'moves'.</p>
  
  <p>Hope this helps a bit, if it does and you want more detail, shout out :)  </p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-27T21:38:24.177Z
Answers.Text: Since this post I've finished my bitboard engine and got it to rank #45 on CCRL. This answer is a good one though, I'll upvote it for the future readers.
Answers.UserDisplayName: AndrewGrant
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-27T22:07:59.317Z
Answers.Text: That is quite an achievement, nice job! I'm am realising now though that storing a list of moves with minimal information is more efficient for the alpha-beta algorithm in which certain 'branches' won't be searched.
Answers.UserDisplayName: Tony Oreglia
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-28T19:05:23.583Z
Answers.Text: https://github.com/AndyGrant/Ethereal/blob/master/src/movegen.c
Answers.UserDisplayName: AndrewGrant
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-27T21:29:36.987Z
Answers.LastActivityDate: 2017-12-27T21:29:36.987Z
Answers.UserDisplayName: Tony Oreglia
Body: <p>I understand how to find all valid moves for all pieces on the board. For example I know that a certain knight can hit all of the 1's in this board</p>
  
  <pre><code>01000000
  00100000
  N0000000
  00100000
  01000000
  00000000
  00000000
  00000000
  </code></pre>
  
  <p>How do I store these as individual moves, how do I apply them to my BitBoards, how do I take back the move?</p>
  
  <p>I've already written an engine before, but I did not use bitboards.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-06-14T15:44:48.883Z
Comments.Text: For anyone simply wanting an implementation, see [python-chess](https://python-chess.readthedocs.io/en/latest/), which uses bitboards internally and does fancy tricks with bitwise operators to actually move pieces.
Comments.UserDisplayName: Jackson H
Tags: <programming><bitboard>
Title: Representing Moves found via BitBoards, applying them, and removing them
ThreadText: # Representing Moves found via BitBoards, applying them, and removing them
  
  (Asked by: username_0 on 2015-07-11)
  
  I understand how to find all valid moves for all pieces on the board. For example I know that a certain knight can hit all of the 1's in this board
  
  ```
  01000000
  00100000
  N0000000
  00100000
  01000000
  00000000
  00000000
  00000000
  
  ```
  
  How do I store these as individual moves, how do I apply them to my BitBoards, how do I take back the move?
  
  I've already written an engine before, but I did not use bitboards.
  
  **Tags:** programming, bitboard
  
  > **Comments:**
  > **username_1**: For anyone simply wanting an implementation, see [python-chess](https://python-chess.readthedocs.io/en/latest/), which uses bitboards internally and does fancy tricks with bitwise operators to actually move pieces.  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_6 on 2017-12-27. Score: 5 | Accepted answer
  
  My last chess engine used bitboards to store position information. It represented moves as a vector of simple move structures that looks something like this:
  
  ```
  struct move_info {
      char move[2];        //origin and destination squares (0 - 63)
      bool side;           //side moving LIGHT=0 or DARK=1
  
      char piece;          //king=0, queens=2,rooks=4,bishops=6,pawns=8
      char captured_piece; //king=0, queens=2,rooks=4,bishops=6,pawns=8
      bool capture;        //is this move a capture
  
      bool canCastle_off[4];
      bool isCastle[4];
  
      bool passant_capture;   //is this move a capture using en passant
      char enPassant;         //if the pawn is pushed two places, set en passant square, along with the square the pawn is on for capture porpoises
  
      bool promotion;
      char promotion_piece;
  };
  
  ```
  
  Then to make the move it would take the move info in a node of the moves vector and update all bitboards. Essentially this means there is a 'position' represented by bitboards, and a list of moves that effect that position. Note that this engine was written when I was a much less experienced programmer.
  
  I'm currently working on a new chess engine which will have a class named 'Position' which carries all needed information for a single position in bitboards. Then, I'll create a linked list of positions for the game tree. I think this will be more efficient then having a list of 'moves'.
  
  Hope this helps a bit, if it does and you want more detail, shout out :)
  
  > **Comments:**
  > **username_0**: Since this post I've finished my bitboard engine and got it to rank #45 on CCRL. This answer is a good one though, I'll upvote it for the future readers.  
  > **username_6**: That is quite an achievement, nice job! I'm am realising now though that storing a list of moves with minimal information is more efficient for the alpha-beta algorithm in which certain 'branches' won't be searched.  
  > **username_0**: https://github.com/AndyGrant/Ethereal/blob/master/src/movegen.c  
  
  ---
  
  ### Answer by username_2 on 2015-07-13. Score: 8
  
  This is a very deep subject, but here's a few basic thoughts that might get you going.
  
  A bitboard consists of 64 bits. If you designate one corner of the board as the most-significant bit and the opposite corner as the least-significant bit, you can store a bitboard in a single 64-bit integer.
  
  For example, suppose A1 is the LSB and H8 is the MSB. We will fill up the 64-bit integer moving left-to-right (A-to-H) and then down-to-up (1-to-8). Your sample turns into:
  
  ```
  0000000000000000000000000100000000100000000000000010000001000000
  
  ```
  
  and this 64-bit integer represents the possible "landing" locations of a knight located at A6. In C this could be stored like:
  
  ```
  long long knight_a6 = 0x4020002040;
  
  ```
  
  We can do this for *every* possible location of the knight, in the same order that we filled out the bitboard (left-to-right, down-to-up). In other words:
  
  ```
  A1: 0000000000100000010000000000000000000000000000000000000000000000
  A2: <bitboard for a knight at A2>
  ...
  B1: <bitboard for a knight at B1>
  ...
  H8: <bitboard for a knight at H8>
  
  ```
  
  This will take up 64 entries \* 64 bits each = 512 bytes of space. Now we can determine the possible landing locations of a knight at *any* location, just by looking at the corresponding entry in the table. In C it could look something like this:
  
  ```
  long long knight[64] = { 0x0020400000000000,
                           <bitboard for a knight at A2>,
                           ... };
  long long knight_a6 = knight[40]; /* A6 = index 40 */
  
  ```
  
  These are all static bitboards: they're just there for your convenience when programming. But you'll probably also want some active bitboards that represent the state of the game. For example, you'll probably want a bitboard that represents where all the pieces are. At the start of the game ranks 1, 2, 7, and 8 are full, so the bitboard looks like this:
  
  ```
  1111111111111111000000000000000000000000000000001111111111111111
  
  ```
  
  Or in C:
  
  ```
  long long game = 0xFFFF00000000FFFF;
  
  ```
  
  So what can you *do* with bitboards? Well, for starters you can determine if a piece (say, a knight at A6) is attacking another piece. To do this you perform a logical AND between the game bitboard and the static bitboard for the attacking piece. Let's say the game looks like this:
  
  ```
  00000000
  00k00000
  N0000000
  00000000
  00000000
  00000000
  00000000
  000000K0
  
  ```
  
  The white king is on G1, the white knight is on A6, and the black king is on C7. The game bitboard would look like this:
  
  ```
  0000001000000000000000000000000000000000100000000010000000000000
  
  ```
  
  Let's see if the white knight is putting the black king in check. First, we look up the white knight's "landing" bitboard as described earlier.
  
  ```
  0000000000000000000000000100000000100000000000000010000001000000
  
  ```
  
  Now we AND that bitboard together with our game bitboard.
  
  ```
      0000001000000000000000000000000000000000100000000010000000000000
  AND 0000000000000000000000000100000000100000000000000010000001000000
      ----------------------------------------------------------------
      0000000000000000000000000000000000000000000000000010000000000000
  
  ```
  
  The result is **not** all-zeroes, so the selected piece is attacking *something*. Here's it is in C:
  
  ```
  long long game = 0x200000000802000;
  long long attacker = knight[40]; /* A6 = index 40 */
  if (game & attacker != 0)
  {
    /* The knight at A6 is attacking something! */
  }
  
  ```
  
  The next step is to see what he's attacking. There are multiple ways to do this: you could see where the 1 appeared in the ANDed bitboard and find the corresponding square, or you could keep a bitboard for every different type of piece. Let's leave it at that for now though.
  
  Next let's see how pieces can be moved. We'll remove the black king from the board for simplicity.
  
  ```
  00000000
  00000000
  N0000000
  00000000
  00000000
  00000000
  00000000
  000000K0
  
  Bitboard: 0000001000000000000000000000000000000000100000000000000000000000
  
  ```
  
  Looking at the knight's landing bitboard we can see there are four one's, so four possible moves. Let's take the first one - so we'll erase all the other zeroes in the bitboard for now.
  
  ```
  0000000000000000000000000100000000000000000000000000000000000000
  
  ```
  
  To move the knight, we erase him from the game bitboard, and then AND the game bitboard with the knight's move bitboard.
  
  ```
         0000001000000000000000000000000000000000100000000000000000000000
  ERASE  0000000000000000000000000000000000000000100000000000000000000000
         ----------------------------------------------------------------
         0000001000000000000000000000000000000000000000000000000000000000
  OR     0000000000000000000000000100000000000000000000000000000000000000
         ----------------------------------------------------------------
         0000001000000000000000000100000000000000000000000000000000000000
  
  ```
  
  The new gameboard looks like this:
  
  ```
  00000000
  00000000
  00000000
  00000000
  0N000000
  00000000
  00000000
  000000K0
  
  ```
  
  Now, there are a **lot** of things brushed over in this answer:
  
  1. How do you track what kind of piece is at each location?
  2. How do you distinguish between white and black?
  3. How do you distinguish between captures and normal moves?
  4. How do you determine which squares are "shielded" behind another piece?
  5. How do you handle pawns, which move in a different way than they capture?
  6. How do you handle the initial pawn move and capture en passant?
  
  Not all bitboards are the same, either. What if we filled out the bitboard in a fancier order than just going left-to-right, bottom-to-top? Maybe there's some other way to assign squares to bits that makes certain checks or moves faster. The way we've written it is just the simplest to picture.
  
  Again, this is a very deep subject, but hopefully this at least explained some of the basics about how bitboards are used.
  
  > **Comments:**
  > **username_3**: I think you avoided the question. I think the question was how to represent a move, not how to apply one. If you want a legal move neighbor generator, not legal state generator, you need a way to represent a move. The most efficient way isn't an intuitive simple bitboard manipulation.  
  
  ---
  
  ### Answer by username_4 on 2017-11-08. Score: 1
  
  Smallchess berated me but didn't understand my post. I can't put a comment yet, so I will detail my example with more step by step explanations in this new post :
  
  bmna6 contains 4 bits at 1, for the squares b4, c5, c7, b8
  bg1 contains one bit at 1, for square g1. If you put b := bmna6 OR bg1, you obtain a bitmap b with 5 bits, which is different from bmna6. So g1 is not attacked by the Na6.
  
  If the king is on c7 instead, then bmna6 == (bmna6 OR bc7), so the king is in check.
  
  You can do a AND and compare to 0, but afaIk the processing time to compare an unsigned int to zero is the same (on x64/x86 at least) as the processing time to compare to a positive unsigned int, and the OR and AND binary operators also have similar processing times. So the two methods are the same for processing time.
  One advantage of doing a OR instead of a AND is that the resulting bitboard can be used again, for calculating paths to checks (ie to determine how a rook can give check in 2 moves, or a knight in 3 moves.. this can be very useful, for instance if coding a chess problem solver, or a SPG solver, etc..). While we already know the result of the AND in case of check, it's the bitboard giving the square where the check happens, which is bc7 in the second exemple, so no new information generated : we already know where the king is.
  
  On the other hand, let's say that instead of wanting to test if the Na6 gives check, you want to test if it's able to capture something. Then you will use a AND between bmna6 and the bitboard of all the black pieces. It will give us a very useful bitboard : the list of squares where the Na6 can capture something. That is what Glorfindel's explanations actually show (but it's best suited for testing non specific captures, not checks, unless you play a fancy feeric variant where black has several kings or where black s pieces are undetermined, one of them possibly being the king).
  
  Also, just to clarify, to check if a king in g1 is attacked by a knight on a6, with bmna6 being the predefined bitboard mask of the possible landing squares of a N on a6 and with bsqg1 being the bit map with a 1 only for square g1, you do a OR of bmna6 and bsg1, and if it's equal to bmna6(which isn't the case) then the king is in check by that knight.
  Obv it's more complex for long range pieces.
  
  To generate and store moves, you need to define a chessboard class and a move class, with the infos that interest you for whatever your purpose is (usually the chessboard stores at least whose turn it is to play. You can for instance have him store the list of legal moves, have a method chessboard.play(move) which will both update the board, update the player whose turn it is, update the list of legal moves.. possibly keep an history of previous moves as well.. UP to you, really depends on what you want to do. You won't code exactly the same way wether you want to code an engine, a mere replayer, or a problem solver who also solves serial-movers..
  
  > **Comments:**
  > **username_5**: Please consider merging your accounts. See https://chess.stackexchange.com/help/merging-accounts  
  
  ---
  
  