Sliding move generation using magic bitboard

Question

This is a question regarding the big picture of how to validate a sliding piece move in chess using magic bitboards. Just to clarify, I am not asking how magic bitboards work internally.

Now, some more details about the question. I'm writing chess board representation using bitboard and I want to validate sliding piece moves using magic bitboards. Can somebody list the main steps of how to achieve that? As an example consider the following board position:

Assume we have all magic bitboard functions and data structures initialised and ready to use. So using only the function signatures for magic bitboards, can you list the steps (pseudo code or any language) to validate a given move for the white rook on g3?

Rettke

Answer 1

It's good that we can assume magic bitboard functions are available, but in general bitboard move generation functions can accept any technique that produces a bitboard that gives the possible squares to move to. Say RookMoves is such a function, then you would populate the move list as follows:

UInt64 pieceBitboard = Bitboard[SideToMove | Piece.Rook];
UInt64 targetBitboard = ~Bitboard[SideToMove | Piece.All];

while (pieceBitboard != 0) {
   Int32 from = Bit.Pop(ref pieceBitboard);
   UInt64 moveBitboard = targetBitboard & RookMoves(from, OccupiedBitboard);

   while (moveBitboard != 0) {
       Int32 to = Bit.Pop(ref moveBitboard);
       moveList[index++] = Move.Create(this, from, to);
   }
}

where Bit.Pop(ref x) returns the least significant bit in x while simultaneously "popping" (removing) it from x.

To validate a move (I'm interpreting this as confirming move validity), you would either check to see if the move is in the move list, or perform the move and see whether it leaves you in check. Of course, you might need to check whether it obeys the movement rules for the piece but that is trivial.

if ((RookRays[move.From] & Bit.At[move.To]) == 0)
   return false;

Int32 side = SideToMove;
position.Make(move);
Boolean valid = position.InCheck(side);
position.Unmake(move);

return valid; 

Biancabiancha

Thanks very much Zong Zheng Li, that answers my question. Although I am taking a simpler approach (chessprogramming.wikispaces.com/Classical+Approach) at the moment, I will return to magic boards as soon as I get my head round the overall process, including search and evaluation. – Rettke

@Rettke Yes, in my own engine I also use the classical approach as it was easy to implement as a temporary component. I found it to be fast enough (perft(6) in 2 seconds) that the gains from switching to magic generation is pretty much insignificant, so I just kept it. – Biancabiancha

That's very helpful as it adds more meaning to what I'm currently implementing. On a side note, as I hit further roadblocks, I will be posting questions on SO with the tag 'chess'. Looking forward to more assistance :) – Rettke

@ZongZhengLi Perft (6) in 2 seconds? Can you help me? See my question here: chess.stackexchange.com/questions/15705/…. – Mihe

Answer 2

Simply put, magic bitboards are an efficient way to take a position and obtain the legal moves for a sliding piece.

First, you need to find some magic numbers. Some of the code you write to find the magic numbers will also be re-used when you use the magic numbers.

To start off, you need to write 5 functions. These don't need to be particularly fast, because you will only use them when looking for magic numbers and once at program startup before you use your magic numbers. You can use any old technique in these functions.

uint64_t blockermask_rook   (int square);
uint64_t blockermask_bishop (int square);
uint64_t moveboard_rook     (int square, uint64_t blockerboard);
uint64_t moveboard_bishop   (int square, uint64_t blockerboard);
uint64_t blockerboard       (int index, uint64_t blockermask);

So you may be asking yourself, da f%q are a blocker mask, move board, and blocker board? Well, I just made the terms up, but here's what I mean by them:

/* Example, Rook on e4:
 *  
 *    The blocker mask        A blocker board         The move board
 *    0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0 
 *    0 0 0 0 1 0 0 0         0 0 0 0 1 0 0 0         0 0 0 0 0 0 0 0 
 *    0 0 0 0 1 0 0 0         0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0 
 *    0 0 0 0 1 0 0 0         0 0 0 0 1 0 0 0         0 0 0 0 1 0 0 0 
 *    0 1 1 1 0 1 1 0         0 1 1 0 0 0 0 0         0 0 1 1 0 1 1 1 
 *    0 0 0 0 1 0 0 0         0 0 0 0 0 0 0 0         0 0 0 0 1 0 0 0 
 *    0 0 0 0 1 0 0 0         0 0 0 0 1 0 0 0         0 0 0 0 1 0 0 0 
 *    0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0         0 0 0 0 0 0 0 0 
 */

The blocker mask is all of the squares that can be occupied and block your piece from moving further. The edge squares don't need to be a part of that, because your piece can't move further past that square anyway. The number of 1's in this bitboard determine how large of a lookup table you need for this piece & square combination. In this case, there are 10 ones, so there are 2^10 (1024) possible permutations of pieces that can block an e4 rook.

The blocker board is one of these permutations. In this example, there are pieces on b4, c4, e2, e5, and e7. These are enemy and friendly pieces. A blocker board is always a subset of the blocker mask (it needn't show pieces on other squares (e.g., blockers = occupancy & blockermask;)).

The move board is the resulting available moves for your piece, for a given blocker board. This includes possible captures for your piece. Note that it also includes capturing your own pieces (but you can just AND it with a NOT of your own piece locations to remove those).

So, basically you need to generate the blocker mask on all squares, for both the rook and bishop. And you also need to generate all possible blocker boards on each square, for both the rook and bishop. As you generate the blocker boards, you should also generate the resulting move boards. Store all of this stuff in arrays for later use.

Now that you have that done, for each square/piece combo you try random 64 bit numbers and see if they're magic. You'll know if they're magic by using the magic formula, return ((blockerboard*magic) >> (64-bits));, which will create a magical index from 0..2^bits (0..1024 in the case of the e4 rook). For a certain piece/square, if two blocker boards ever generate the same magical index but these two blocker boards have different move boards, then this is a muggle number, and you should try a new one.

Once you get that down, you'll have 64 magic rook numbers and 64 magic bishop numbers. To use them, at program startup you will initialize all of the blocker masks, blocker boards, and move boards. And now your program can efficiently look up move boards for bishops and rooks on any square (and thus also queens). The code for that will look something like this:

/* Retrieves the move board for the given square and occupancy board. */
uint64_t magic_move_rook  (int8_t square, uint64_t occupancy)
{
    /* Remove occupants that aren't in the blocker mask for this square. */
    occupancy &= Rook.blockmask[square];
    /* Calculate the magic move index. */
    int index = (occupancy*Rook.magic[square]) >> (64-Rook.bits[square]);
    /* Return the pre-calculated move board. */
    return Rook.moveboard[square][index];
}

Strained

This was a fantastic answer, certainly made things a lot clearer for me. The only thing I struggle with now is what index actually is and why it correctly points to the right spot in the moveboard array. Do you have anywhere I can go for a clearer understanding of this? I have checked all the usual places i.e. chessprogramming wiki, various blog posts etc. – Peery

It's magic, man. Seriously though, I had it all figured out when I wrote the answer last summer, and now I'm struggling to recall. So the index returned by the magic formula is always an integer less than the total number of blockerboards (BB). Each BB has a corresponding moveboard (MB). When searching for magics, you're calculating each MB with a slow algorithm and storing the MB at the index calculated by the candidate magic number. At engine startup, the MBs are recalculated with the slow algorithm and then they are just stored at the index calculated by your preprogrammed good magics. – Strained

Also, while you may have 1024 BBs, each of which has a corresponding MB, you may end up storing less than 1024 MBs. Eg., for two different BBs that have the same MB, the magic could calculate two different indices or it could calculate the same index for both. As long as the MBs are the same, it's ok for the index to collide. So to directly answer your question, it's just luck/probability that we found a number that happens to calculate unique indices for unique MBs. We then purposefully store the MBs at the correct indices at engine startup using the magic formula and our known magics. – Strained

I realize I'm writing a comment three years after you posted your answer. But I wanted to say thanks. I referred to your very clear explanation while converting my chess engine from mailbox board representation to bitboards. See madchess.net/2018/10/28/madchess-3-0-beta-build-39-bitboards. – Daman

Cool blog, Erik. Thanks for the shoutout! – Strained

@Strained This answer has helped me, and will keep helping other people who look-up magic bitboards! – Tonisha

Thank you for your detailed answer. Each sentence in the answer is very valuable information. – Galumph

Answer 3

Haha never heard of 'magic bitboard'. Google it and it is exactly what I expected. Although I dont see any magic about it. Anyways to answer your question, you need to generate the available move bit position of the currently selected piece. Not sure what else is needed.

As for psuedo code something like so I guess:

Positions KingChessPiece::getMovablePositions(){
   (x,y) = current bit position in the bitboard
   availablePosition = [ (x+1,y),(x-1,y),(x,y+1),(x,y-1) ]
   for each position in availablePosition
      if p_i is occupied then remove it from list

   return availablePosition
   }

I mean there is nothing hard about this, you just need to make sure you get and set position in a way compatible to the internal structure you are using.

EDIT:

example of a queen:

Position QueenChessPiece::getMovablePosition(){
     (x,y) = queens current position
      availablePosition = []; //empty list
     //check diagonal positions
     //move top left diagonal 
     availablePosition.concat( this.generateAvailablePosition(x,y,-1,1);
     //move top right diagonal 
     availablePosition.concat( this.generateAvailablePosition(x,y,1,1);
     //move bottom right diagonal 
     availablePosition.concat( this.generateAvailablePosition(x,y,1,-1);
     //move bottom left diagonal 
     availablePosition.concat( this.generateAvailablePosition(x,y,-1,-1);

    //move straight up 
    availablePosition.concat( this.generateAvailablePosition(x,y,0,1) )
    //move straight down 
    availablePosition.concat( this.generateAvailablePosition(x,y,0,-1) )

    //move left 
    availablePosition.concat( this.generateAvailablePosition(x,y,-1,0) )
    //move right
    availablePosition.concat( this.generateAvailablePosition(x,y,1,0) )

  return availablePosition;
}
Position QueenChess::generateAvailablePosition(x,y,dx,dy){
  availPosition = [];
  while( !isSpaceOccupied(x + dx , y + dy)) 
    availPosition.add( position(x + dx ,y + dy) );
    x += dx;
    y += dy;
  endWhile
  return availPosition;
   }

Lamberto

Thanks for your reply. This is okay for a king but what about rook? It is not straightforward for sliding pieces, i.e. rook, bishop and queen. A blocker blocks the square it occupies as well as any square afterwards in the move's direction. – Rettke

No, magic bitboards generate the attack maps only once before move generation. When it comes to the generation it is just a table lookup. This is a naive implementation that doesn't employ bitboard advantages at all. – Biancabiancha

It pre-generates attack maps? Can you explain – Lamberto

Basic summary: occupancy bits for a specific piece on a specific square can be multiplied against a "magic" number, and then shifted, to obtain an index in a pre-initialized attack table. – Biancabiancha

So the lookup table basically pregenerates move position for each piece at position (x,y)? – Lamberto

Yes, it generates a bitboard containing the squares the piece can move to. As you can see, it takes some cleverness to to do this for sliding pieces that can be blocked. – Biancabiancha

Look at here for magic bitboards: chessprogramming.wikispaces.com/Magic+Bitboards – Thaxton