Author: Gerd Isenberg
Date: 14:31:42 11/30/02
Go up one level in this thread
On November 30, 2002 at 13:37:04, Frank Schneider wrote:
>Hi Gerd,
>
>very interesting and good posting, thanks!
>
>(I have to admit I didn't understand everything, though ;-)
>Frank
Hi Frank,
Thanks :-)
In general, if you want to traverse bitboards in the "classical" way for move
generation, you need the square indicies. Some Capture Pattern sample like RxQ
1. the classical way eg. with rotated bitboards:
BitBoard rooks = OwnRooks();
while (rooks)
{
int rookSq = BitSearchAndReset(rooks);
BitBoard attackedQueens = getRookAttacksBySquare(rookSq) & EnemyQueens();
while (attackedQueens)
{
int queenSq = BitSearchAndReset(attackedQueens);
PushCapture (RookTakesQueen, rookSq, queenSq);
}
}
2. the bitboard metric (or what was the correct name Steffan?) way, i have in
mind, requires kogge-stone or flood fill, but saves the rather expensive
bitscans and possibly the recomputing of the bitboard metric for incremetal
update via (1<<sq).
BitBoard rooks = OwnRooks();
while (rooks)
{
BitBoard rook = rooks & -rooks; rooks ^= rook; // get and reset lsb
BitBoard attackedQueens = getRookAttacks(rook) & EnemyQueens();
while (attackedQueens)
{
BitBoard queen = attackedQueens & -attackedQueens;
attackedQueens ^= queen;
PushCapture (RookTakesQueen, rook|queen);
}
}
This loop don't takes advantage of the ability of Floodfill and Kogge-Stone, to
generate combined attack boards simultaniously for one kind of piece, like:
... = getRookAttacks(rooks) ...;
... because the remaining set are combined attack sets of possibly several
rooks, there is no unique target-source relationship. Therefore the loop over
all rooks with single bit bitboards.
Steffan Westcott has another approach, of keeping disjoint attacks sets in each
possible piece kind direction (up to eight for queens and knights!). But that
requires one additional direction fill from each target square, to find the
appropriate source square of a move (see appendix).
Anyway, even if your move-structure containes combined bitboard metric
coordinates (fromBB|toBB), at least for history index reasons or pushing packed
moves into the hashtables, it is necessary to convert bitboard metrics in board
coordinates, or something similar in this range with this mod5811 idea.
For this approach the double popCount-routine seems fine.
Using a single bitscan via mmx-popcount like
int BitSearch(BitBoard bb) {return PopCountMMX( (bb&(-bb))-1);
is not so effective than the bsf-routine (~21/15 slower) due to the (bb & -bb)
statement and more register dependencies. Comparing code size and execution
speed - amazing. But if you already have two singular from/to bitboards, the
second parallel bitscan is about for free.
With hammer (always in mind by this stuff) it will depend on how fast
the 64-bit bsf,bsr will be.
See you in Paderborn,
Gerd
-------------------------------------------------------------------------------
One example of the routines Steffan introduced here.
Kogge-Stone-Parallel-Prefix-Algorithm
BitBoard getRookAttacksRight(BitBoard rooks, BitBoard emptySquares)
{
return ShiftRight(FillRightOccluded(rooks, emptySquares));
}
BitBoard ShiftRight(BitBoard b) { return (b<<1) & 0xfefefefefefefefe; }
BitBoard FillRightOccluded(BitBoard g, BitBoard p)
{
p &= 0xfefefefefefefefe;
g |= p & (g << 1);
p &= (p << 1);
g |= p & (g << 2);
p &= (p << 2);
return g |= p & (g << 4);
}
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.