Fastest way to generate moves of multiple pieces

[Pradu]

I'm currently experimenting with some stuff that requires the generation of moves of multiple pieces simultaneusly.

Right now I'm doing something like:

Code: Select all

//Fillled attacks - initial place included
U64 Rfill(U64 pieces, U64 occ)
{
   occ=~(occ&~pieces);
   return fillUpOccluded(pieces,occ<<8)|fillDownOccluded(pieces,occ>>8)
         |fillRightOccluded(pieces,occ>>1)|fillLeftOccluded(pieces,occ<<1);
}

U64 Bfill(U64 pieces, U64 occ)
{
   occ=~(occ&~pieces);
   return fillUpLeftOccluded(pieces,occ<<9)|fillDownRightOccluded(pieces,occ>>9)
         |fillUpRightOccluded(pieces,occ<<7)|fillDownLeftOccluded(pieces,occ>>7);
}

U64 Qfill(U64 pieces, U64 occ)
{
   occ=~(occ&~pieces);
   return fillUpOccluded(pieces,occ<<8)|fillDownOccluded(pieces,occ>>8)
         |fillRightOccluded(pieces,occ>>1)|fillLeftOccluded(pieces,occ<<1)
         |fillUpLeftOccluded(pieces,occ<<9)|fillDownRightOccluded(pieces,occ>>9)
         |fillUpRightOccluded(pieces,occ<<7)|fillDownLeftOccluded(pieces,occ>>7);
}

U64 Nfill(U64 pieces)
{
   return
      pieces |
      //left 2 up 1
      ( (pieces<< 6) & C64(0x3F3F3F3F3F3F3F3F) ) |
      //right 2 up 1
      ( (pieces<<10) & C64(0xFCFCFCFCFCFCFCFC) ) |
      //left 1 up 2
      ( (pieces<<15) & C64(0x7F7F7F7F7F7F7F7F) ) |
      //right 1 up 2
      ( (pieces<<17) & C64(0xFEFEFEFEFEFEFEFE) ) |
      //left 2 down 1
      ( (pieces>> 6) & C64(0xFCFCFCFCFCFCFCFC) ) |
      //right 2 down 1
      ( (pieces>>10) & C64(0x3F3F3F3F3F3F3F3F) ) |
      //left 1 down 2
      ( (pieces>>15) & C64(0xFEFEFEFEFEFEFEFE) ) |
      //right 1 down 2
      ( (pieces>>17) & C64(0x7F7F7F7F7F7F7F7F) ) ;
}

U64 Kfill(U64 pieces)
{
   pieces |= (pieces << 8) | (pieces >> 8);
   return ((pieces<<1)&0xFEFEFEFEFEFEFEFE) | ((pieces>>1)&0x7F7F7F7F7F7F7F7F);
}

where

Code: Select all

U64 fillUpOccluded(U64 g, U64 p)
{
   g |= p & (g << 8);
   p &=     (p << 8);
   g |= p & (g << 16);
   p &=     (p << 16);
   return g |= p & (g << 32);
}

U64 fillDownOccluded(U64 g, U64 p)
{
   g |= p & (g >> 8);
   p &=     (p >> 8);
   g |= p & (g >> 16);
   p &=     (p >> 16);
   return g |= p & (g >> 32);
}

U64 fillLeftOccluded(U64 g, U64 p)
{
   p &= C64(0xFEFEFEFEFEFEFEFE);
   g |= p & (g << 1);
   p &=     (p << 1);
   g |= p & (g << 2);
   p &=     (p << 2);
   return g |= p & (g << 4);
}

U64 fillRightOccluded(U64 g, U64 p)
{
   p &= C64(0x7F7F7F7F7F7F7F7F);
   g |= p & (g >> 1);
   p &=     (p >> 1);
   g |= p & (g >> 2);
   p &=     (p >> 2);
   return g |= p & (g >> 4);
}

U64 fillUpLeftOccluded(U64 g, U64 p)
{
   p &= C64(0xFEFEFEFEFEFEFEFE);
   g |= p & (g <<  9);
   p &=     (p <<  9);
   g |= p & (g << 18);
   p &=     (p << 18);
   return g |= p & (g << 36);
}

U64 fillUpRightOccluded(U64 g, U64 p)
{
   p &= C64(0x7F7F7F7F7F7F7F7F);
   g |= p & (g <<  7);
   p &=     (p <<  7);
   g |= p & (g << 14);
   p &=     (p << 14);
   return g |= p & (g << 28);
}

U64 fillDownLeftOccluded(U64 g, U64 p)
{
   p &= C64(0xFEFEFEFEFEFEFEFE);
   g |= p & (g >>  7);
   p &=     (p >>  7);
   g |= p & (g >> 14);
   p &=     (p >> 14);
   return g |= p & (g >> 28);
}

U64 fillDownRightOccluded(U64 g, U64 p)
{
   p &= C64(0x7F7F7F7F7F7F7F7F);
   g |= p & (g >>  9);
   p &=     (p >>  9);
   g |= p & (g >> 18);
   p &=     (p >> 18);
   return g |= p & (g >> 36);
}

Is there a faster way to generate move bitboards for multiple pieces? (Espically for the slider pieces)

[smcracraft]

I use Bmagic and Rmagic to generate the moves
"in parallel" from your Magic code. Fits right in.

Sure, Bmagic and Rmagic are for parallel generation
of destinationsquares from a single given unique origination
square.

Are you trying to provide multiple origination squares
instead of the single origination square?

I don't understand how what you want is any
different than what you have given the chess
world already and why you'd need to go further.

Sounds like you are trying to beat yourself!

Stuart

[Pradu]

I use Bmagic and Rmagic to generate the moves
"in parallel" from your Magic code. Fits right in.

Sure, Bmagic and Rmagic are for parallel generation
of destinationsquares from a single given unique origination
square.

Are you trying to provide multiple origination squares
instead of the single origination square?

I don't understand how what you want is any
different than what you have given the chess
world already and why you'd need to go further.

Sounds like you are trying to beat yourself!

Stuart

The above code I ripped off and adapted from one of Gerd's postings, not trying to do anything new . And generating moves of multiple pieces could be really interesting. For example it could be used to implement "future mobility" or things like a flood-fill based kingsafety. I was just wondering if there was a quicker way than these fills for generating moves of multiple pieces so that I can use it in some tests I'm doing on future mobility.

[Dann Corbit]

You can also have a table lookup for either 1 or 2 knights. The list size grows (64*63+64)=4096 entries instead of 64.

Just make a perfect hash for the 4096 different bit patterns and use that for an index. You still have to account for 3 or more knights, so you may have to peel knights off the list by twos.

[Zach Wegner]

That won't work for floodfilling. Imagine trying to get the set of squares knights can reach in 3 moves. That's a lot of pulling off and hashing.

But anyways Pradu, those look about as fast as possible based on what I know.