Generating "through" attacks with rotated bitboard

[vladstamate]

Hi all,

I am using rotated bitboards in my engine, and I have stumbled upon a problem. I would like to generate the attacks of a given piece counting for double attacks or attack through. Think of two rooks on the A file file attacking a pawn. Using "conventional" mode I can easily detect the "front" rook attacking the pawn but due to the occupancy bitboard the "back" rook won't attack the pawn since it is blocked by the front rook. However I need way to detect that the back rook also attacks the pawn. Is there such a way?

For example this is the code I am using to generate rook attacks:

Code: Select all

// sq = the square on which the rook I am looking at is situated
kRowOccupancy = (int) (m_kOccupiedSquares >> shiftRank[sq]) & 255;
kRankOccupancy = (int) (m_kOccupiedSquares90R >> shiftFile[sq]) & 255;
kAttacks = g_kRankAttacks[sq][kRankOccupancy] | g_kRowAttacks[sq][kRowOccupancy];

The problem I am trying to overcome is that my rotated occupancy bitboards (such as m_kOccupiedSquares90R) are updated incrementally upon makeMove (and restored when unMakeMove happens).

The solution I am looking at is, remove any rooks, except the one that I am looking at and use that occupancy information to lookup into the (precomputed) g_kRankAttacks and g_kRowAttacks. However generating rotated occupancy is not free.

Has anyone a good solution for through attacks generation using (rotated) bitboards? A similar solution should apply to all sliding pieces.

Thanks in advance,
Vlad.

[BubbaTough]

I do this for sliding pieces by detecting when the behind rook hits the in front rook, and then grabbing the in front rook's moves in that direction.

-Sam

[vladstamate]

Thank you for your answer Sam.

I am doing something like this now:

a) generate rowAttacks
b) friendlyPieces = rowAttacks OR (friendly rooks AND queens)
c) generate rowattacks2 for the friendlyPieces
d) attacks = rowAttacks OR rowAttacks2

That works fine for all sliding pieces. The only thing it does not work for is when I have 3 sliding pieces in the same direction, which (barring any weird promotions) can only happen if I have 2 rooks and a queen in the same line.

I am trying to find a solution that works fast.

Regards,
Vlad.

[Gerd Isenberg]

Thank you for your answer Sam.

I am doing something like this now:

a) generate rowAttacks
b) friendlyPieces = rowAttacks OR (friendly rooks AND queens)
c) generate rowattacks2 for the friendlyPieces
d) attacks = rowAttacks OR rowAttacks2

That works fine for all sliding pieces. The only thing it does not work for is when I have 3 sliding pieces in the same direction, which (barring any weird promotions) can only happen if I have 2 rooks and a queen in the same line.

I am trying to find a solution that works fast.

Regards,
Vlad.

This is an advantage of Magic Bitboards:

Code: Select all

U64 xrayRookAttacks(U64 occ, U64 blockers, enumSquare rookSq) {
   U64 attacks = rookAttacks(occ, rookSq);
   blockers &= attacks;
   return attacks ^ rookAttacks(occ ^ blockers, rookSq);
}

or Kindergarten Bitboards or Obstruction Difference:

Code: Select all

U64 xrayRankAttacks(U64 occ, U64 blockers, enumSquare rookSq) {
   U64 attacks = rankAttacks(occ, rookSq);
   blockers &= attacks;
   return attacks ^ rankAttacks(occ ^ blockers, rookSq);
}

One may simpler remove some pieces from the occupancy.

[BubbaTough]

Well Gerd, if I ever have time to right things again from scratch again I might invest the time to switch. It seems magic is a little better. For now though, I am stuck with rotated.

Vlad, I guess how you want to do it depends a little on how you are using it. Are you trying to write a SEE function? If so its worth spending some time setting up some efficient loops to do this. I can try to help, though doubtless others are better at it. Are you using it for mobility or king threat bonuses in your eval function? If so I would do it a bit differently (I personally don't bother in eval worrying about 3 in a row cases much to the regret of those in love with the infamous Alekhine's gun).

-Sam

[vladstamate]

Hi,

I am actually for now just trying to get correct king safety evaluation as well as mobility for sliding pieces to count attacking through a fellow sliding piece. Following your idea I managed to get that working so I am happy for now. It is a lot of code, like I pointed above though. However like you I am stuck with rotated bitboards and it would require a substantial work to switch to magic bitboards.

My next effort will be in trying to fix the SEE using this technique.

Regards,
Vlad.

[Desperado]

Hi Vlad,

just a question about your data structures.

1. I think that you already have masks at hand,like filemask,rankmask,
diagmask,antimask ? do you ? (excluding square in question)

a. are the masks easy to split in lower and upper part ?
b. or can you invest 4k mem to add such lo and hi masks ?

example: Rd4

msk_lo: d1,d2,d3
msk_hi: d5,d6,d7,d8

Michael

[Gerd Isenberg]

Well Gerd, if I ever have time to right things again from scratch again I might invest the time to switch. It seems magic is a little better. For now though, I am stuck with rotated.

Hi Sam,
Rotated is still competitive and fast. Specially if you can utilize the same occupancy multiple times, it is faster than the multiplicative alternatives.

For X-rays it is about the algorithm, whether one use the intersection of attacks (say per line) with the desired blockers (e.g. same friendly or opponent sliders), to bitscan those blockers (up to two per line), and to perform up to two further rotated lookups - or the alternative to remove the blockers (temporarily) from the occupancy, and to perform one lookup from the original square as well.

If the X-ray algorithm is applied with one line, one may think about the second algorithm as well for rotated, to flip/rotate the intersection according to the appropriate rotated bitboard, and to xor only one bitboard, to remove the blockers for this particular line-direction.

Obviously, the superior algorithm is much simpler with non-rotated approaches. No rotated discrimination intended

Cheers,
Gerd

[Desperado]

Obviously, the superior algorithm is much simpler with non-rotated approaches. No rotated discrimination intended

Cheers,
Gerd

Hi again,

i think so too, and maybe it is not necessary to write everything from scratch. Maybe you can easily make a buildup with Obstruction difference
approach. I think most data is already there, and adding only _one_ additionally function (lineattack()) is not much work. Done in 5 minutes.
Nothing to loose in my opinion.

And if you see that you can profit, who knows ?!, you can replace rotated step by step, write from scratch, or simple use it as buildup.
(as optimal case maybe combine both, because of the weakest point OD has,
the reverse isolation, which you may change to advantage because you have reversed bitboards at hand and you may simply need forword isolation, who knows?)


cheers

[Gerd Isenberg]

Hi again,

i think so too, and maybe it is not necessary to write everything from scratch. Maybe you can easily make a buildup with Obstruction difference
approach. I think most data is already there, and adding only _one_ additionally function (lineattack()) is not much work. Done in 5 minutes.
Nothing to loose in my opinion.

And if you see that you can profit, who knows ?!, you can replace rotated step by step, write from scratch, or simple use it as buildup.
(as optimal case maybe combine both, because of the weakest point OD has,
the reverse isolation, which you may change to advantage because you have reversed bitboards at hand and you may simply need forword isolation, who knows?)


cheers

Of course that is possible. But the computational costs of OD and register pressure is greater than rotated lookups. If you had spend effort to implement rotated, you will likely choose algorithms to take advantage of them in the sense to avoid temporarily changes of the occupancy per node. Changing those aspects is much more work than replacing the pure attack-getter api. It is more error-prone for very little gain, if any.