# Computer Chess Club Archives

## Messages

### Subject: Re: Natural move generation with bitboards (was Re:significant math)

Author: Alessandro Damiani

Date: 00:24:24 11/22/02

Go up one level in this thread

```On November 22, 2002 at 02:49:05, Alessandro Damiani wrote:

>On November 21, 2002 at 19:17:46, Steffan Westcott wrote:
>
>>On November 21, 2002 at 15:23:55, Alessandro Damiani wrote:
>>
>>>On November 21, 2002 at 06:47:24, Steffan Westcott wrote:
>>>
>>>>On November 21, 2002 at 05:55:59, Alessandro Damiani wrote:
>>>>
>>>>>And for sliding pieces? The distance between the from- and the to-square is not
>>>>>fixed. In the worst case, for each to-square there are 7 from-squares for one
>>>>>direction. Do you keep one bitboard for each distance in one direction, ordered
>>>>>from 1 to 7? Just my first thought.
>>>>
>>>>No, just one bitboard is used to store all possible destination squares for,
>>>>say, upward rook moves. Look for my example routines FillUpOccluded(),
>>>>FillRightOccluded(), etc in the CCC archives (when they get updated, eventually
>>>>:-< ) for a suggestion on how to calculate this type of bitboard quickly.
>>>>
>>>
>>>I already understood the concept with "one bitboard for each direction". Let's
>>>take a look at the example position I gave in a previous post (here again):
>>>
>>>[D]4r1k1/2q2pp1/p1p4p/Pp1b4/1P6/2N1PN2/4QPPP/3R2K1 w - - 0 1
>>>
>>>The bitboard for *all bishops right-down* is:
>>>
>>>::::::::
>>>::::::::
>>>::::::::
>>>::::::::
>>>::::#:::
>>>:::::#::
>>>::::::::
>>>::::::::
>>>
>>>As you said, each time a move is searched, its to-square is removed from the
>>>bitboard. We look at the bitboard above as a generic state in the generation
>>>process (part of the invariant). By knowing the direction "right-down" we start
>>>at the left-up most bit set to 1, right? Do you keep an additional invariant
>>>related to the from-square? Or do I like the from-square far too much?? *g*
>>
>>Alessandro,
>>
>>Given a bitboard with a single set bit for the move target square and a
>>(sliding) move direction, finding the source square of the moving piece is
>>simple. Just make an attack bitboard from the target square going in the
>>_reverse_ direction (using FillOccludedxxx), then bitwise AND (&) the result
>>with the 'AllPieces' bitboard. Put succintly, trace the attack back to its
>>source.
>>
>
>Ok, I was thinking of an idea without using attack detection again.
>
>This is done for each to-square. I am wondering if this isn't slowing things
>down too much. In the worst case the cost is for all moves....
>
>Alessandro

Now I took a look at my attack detection code. My method can only determine the
attack squares of a bishop for one diagonal at once:

#define attackDiagRightDown(from)
(attackFromRightDown[from][slideIndexRD[7-((from)>>3)+((from) & 7)]])

The direction "RightDown" here is related to the whole attack-ray.

So, with my method I need to do

to get the from-square.

This seems to be slower than with flood-fill, since flood-fill can be done in
one direction and therefore doesn't need the extra AND.

Conclusion: everthing put together with move ordering makes it difficult to
compare in mind (at least in mine). Since bitboarder using conventional move
generation already separate capture- from non-capture generation the best
performance comparison is done by testing.

I first have to finish rewriting my engine before I go back to move generation.
But since you are already writing an engine based on your ideas, we all
bitboarder can compare once.

Alessandro

```