Computer Chess Club Archives




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

Author: Sune Fischer

Date: 08:37:56 11/22/02

Go up one level in this thread

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

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

There is another thing which bothers we with disjoint attack boards, namely that
they are _disjoint_.

Some parallelism seem to be lost here, like how do you quickly detect a knight
attacking a certain square if your knight attack boards are split into 8?

If you knew the direction to look, you could of course build that attack
direction, but you don't as far as I can tell, unless there is some modulo trick
which works directly on bitboards and can give you the direction, as in 0x88.

So assuming you don't know this direction, how do you check if one of your rooks
attacks one of his queens, ie the RxQ pattern, without checking all 4

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

But then you don't have parallel attack computation of multiple rook instances,
might as well use rotated :(

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

You have to know this trick for it to work, you need to know directions here.


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