Computer Chess Club Archives




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

Author: Gerd Isenberg

Date: 04:42:51 11/22/02

Go up one level in this thread

>>>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*
>>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
>Ok, I was thinking of an idea without using attack detection again.

Hi Alessandro,

same with me. I'm a bit torned by Steffans ideas with direction move/attack

>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....

I am thinking a lot about Steffan's great ideas, but this one seems a bit
counter productive to me, using attack detection again to determine the source
square, even if it is done only for one direction.

Another point is the number of statefull bitboards needed in Steffan's approach:
eg. for each knight direction. Thought about 8-direction move/attack bitboards
for all pieces except knights, but with pawn- and king moves, icluding castles
and ep, nice for determing the number of moves available.

For move generation, or if i really need disjoint attack sets, i currently favor
attack bitboards for a single sliding piece as well for a knight. That is what
my program does before with rotated bitboards and now with dumbfill and
Kogge-Stone mmx-routines.

It may be nice to suppress the bitscans and the further rebuiling of singular
bitboards by 1<<sq. Something like this:

 BitBoard rooksToTraverse = Rooks() & ownPieces();
 while (rooksToTraverse)
    BitBoard singleRook  = rooksToTraverse & -rooksToTraverse;
    BitBoard rookAttacks = getRookAttacks(singleRook);
    BitBoard captureTargets = rookAttacks & enemyPieces();
    while ( captureTargets )
       BitBoard captureTarget = captureTargets & -captureTargets;
       PushCapture(singleRook, captureTarget);
       captureTargets ^= captureTarget; // resets bit
    BitBoard moveTargets = attacks & ~Pieces();
    rooksToTraverse ^= singleRook; // reset bit

To get an index eg. for history table or to get really the native square
coordinates without bitscans, some hashkey-function may help, as Steffan already
mentioned, that maps the two from and to bitboards to an integer range.

I don't like div/mod, but had no better idea so far similar to Joel Veness
proposal to extract bits from a bitboard:

  (fromBB - toBB) mod 7961

gives unique numbers for each possible move. But the range is rather huge. There
should be something better...


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.