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?

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; 

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];
}

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;
   }