2014-04-06

Hyperbola Quintessence for rooks along ranks

Hyperbola Quintessence is a quick and simple alternative to Magic Bitboards, but it does not work for rooks or queens moving along ranks (assuming LERF mapping).  It applies the o^(o-2r) trick to generate attacks in positive ray direction (for rooks, east or north).  The attacks in negative ray direction are generated by applying the same trick to the bit-reversed board.

There is no fast (i.e. branchless) way to reverse bits, but in many cases (attacks along a diagonal or along a file), the relevant bits are in separate bytes.  In those cases, the relevant bits can be reversed by a simple byte swap, which is sufficient.

In the case of a rook moving along a rank, the relevant bits are all in the same byte.  The same trick can't be exploited here because the byte swap will have no effect on the relative order of the bits.

I'm new to the world of computer chess, so I don't know what people have been falling back to.  I guess look-up tables are an okay solution, with 8 * 256 entries covering all combinations of rook position on the rank and presence of other pieces on the rank.

In any case, here's a way to apply Hyperbola Quintessence in the rook-along-rank case.  The crux is that we don't need to be able to reverse all the bits of bitboard but only the relevant ones.  Since there are as many bits in the byte (representing the rank) as there are bytes in the board, we can map the bits to their own consecutive bytes and swap the bytes as usual.

Here are the steps (dots are zeros):
  1. Mask the occupancy and the piece position to keep only the relevant rank.
  2. Map the relevant rank of the occupancy and the piece position to the a1-h8 diagonal:
    occupancy         piece
    . . . . . . . .   . . . . . . . . 
    . . . . . . . .   . . . . . . . . 
    . . . . . . . .   . . . . . . . . 
    . . . . . . . .   . . . . . . . . 
    0 0 1 0 0 1 1 0   0 0 1 0 0 0 0 0 
    . . . . . . . .   . . . . . . . . 
    . . . . . . . .   . . . . . . . . 
    . . . . . . . .   . . . . . . . . 
    
    >> rank_index * 8
    
    occupancy         piece
    . . . . . . . .   . . . . . . . . 
    . . . . . . . .   . . . . . . . . 
    . . . . . . . .   . . . . . . . . 
    . . . . . . . .   . . . . . . . . 
    . . . . . . . .   . . . . . . . . 
    . . . . . . . .   . . . . . . . . 
    . . . . . . . .   . . . . . . . . 
    0 0 1 0 0 1 1 0   0 0 1 0 0 0 0 0 
    
    * 0x0101010101010101
    
    occupancy         piece
    0 0 1 0 0 1 1 0   0 0 1 0 0 0 0 0  
    0 0 1 0 0 1 1 0   0 0 1 0 0 0 0 0  
    0 0 1 0 0 1 1 0   0 0 1 0 0 0 0 0  
    0 0 1 0 0 1 1 0   0 0 1 0 0 0 0 0  
    0 0 1 0 0 1 1 0   0 0 1 0 0 0 0 0  
    0 0 1 0 0 1 1 0   0 0 1 0 0 0 0 0  
    0 0 1 0 0 1 1 0   0 0 1 0 0 0 0 0  
    0 0 1 0 0 1 1 0   0 0 1 0 0 0 0 0 
     
    & 0x8040201008040201
    
    occupancy         piece
    . . . . . . . 0    . . . . . . . 0 
    . . . . . . 1 .    . . . . . . 0 . 
    . . . . . 1 . .    . . . . . 0 . . 
    . . . . 0 . . .    . . . . 0 . . . 
    . . . 0 . . . .    . . . 0 . . . . 
    . . 1 . . . . .    . . 1 . . . . . 
    . 0 . . . . . .    . 0 . . . . . . 
    0 . . . . . . .    0 . . . . . . . 
  3. Apply Hyperbola Quintessence to get the attacks along the rank as if it were the a1-h8 diagonal.
  4. Map the attacks back onto the relevant rank:
    attacks
    . . . . . . . 0
    . . . . . . 0 .
    . . . . . 1 . .
    . . . . 1 . . .
    . . . 1 . . . .
    . . 0 . . . . .
    . 1 . . . . . .
    1 . . . . . . .
    
    * 0x0101010101010101
    
    attacks
    1 1 0 1 1 1 0 0
    1 1 0 1 1 1 0 0
    1 1 0 1 1 1 0 0
    1 1 0 1 1 1 0 0
    1 1 0 1 1 1 0 0
    1 1 0 1 1 1 0 0
    1 1 0 1 1 1 0 0
    1 1 0 1 1 1 0 0
    
    / 0x0100000000000000
    
    attacks
    . . . . . . . .
    . . . . . . . .
    . . . . . . . .
    . . . . . . . .
    . . . . . . . .
    . . . . . . . .
    . . . . . . . .
    1 1 0 1 1 1 0 0
    
    << rank_index * 8
    
    attacks
    . . . . . . . .
    . . . . . . . .
    . . . . . . . .
    . . . . . . . .
    1 1 0 1 1 1 0 0
    . . . . . . . .
    . . . . . . . .
    . . . . . . . .
Note, this only works one rook at a time.

2 comments:

  1. when you multiply with 0x0101010101010101 to fill all the other bits for the file, for some reason it does't work when there is already a bit set on the same fie. Some weird structures start appearing. What is the reason?
    take this bitboard

    . . . . . . . .
    . . . . 1 . . .
    . . . . . . . .
    . . . . . . . .
    . . . . 1 . . .
    . . . . . . . .
    . . . . . . . .
    . . . . . . . .

    piece on e4 and occupancy on top.
    after shifting, it looks like this

    . . . . . . . .
    . . . . . . . .
    . . . . . . . .
    . . . . . . . .
    . . . . 1 . . .
    . . . . . . . .
    . . . . . . . .
    . . . . 1 . . .

    After multiplying with 0x0101010101010101

    you get
    . . . . . 1 . .
    . . . . . 1 . .
    . . . . . 1 . .
    . . . . . 1 . .
    . . . . . 1 . .
    . . . . 1 . . .
    . . . . 1 . . .
    . . . . 1 . . .

    which is definately not what is intended, help me

    ReplyDelete
  2. How I rectified it is by doing
    occupancy&= get_rank_mask(square);

    ReplyDelete