Computer Chess Club Archives


Search

Terms

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

    attackDiagRightDown(toSquare) & leftUpMask[toSquare] & AllPieces

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



This page took 0.03 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.