Representing Moves found via BitBoards, applying them, and removing them

Question

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.

Answer 1

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 :)

Answer 2

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.

Answer 3

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..