Computer Chess Club Archives




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

Author: Alessandro Damiani

Date: 08:53:54 11/22/02

Go up one level in this thread

On November 22, 2002 at 07:42:51, Gerd Isenberg wrote:

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

Hi Gerd,

Yes. I first will continue with my method until Steffan has a quite finished
engine. Then we all can compare.

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

I agree. We will see which combination of concepts is best.

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

That is a good idea. It works only in combination with flood-fill attack
detection, since for my method (Rotated Indices) and Rotated Bitboards the
from-square is needed.

Mmmh, currently I still will use my method (non flood-fill), so I can't use this
idea now.

These bitboards have a lot of potential! But I still prefer to eat a pizza than
a bitboard!! :)

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

I didn't think this far. Now that I see the implications of Steffans method I
continue my road until I have finished rewriting my engine. Then I come back.

We also don't have to overlook the implications on move ordering.


This page took 0.04 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.