Author: Gerd Isenberg
Date: 13:16:56 02/19/06
Go up one level in this thread
On February 19, 2006 at 15:12:49, Zach Wegner wrote:
>
>Very interesting. I have been looking for some way to get rid of bit-traversing
>for so long. First off, some questions, then some comments.
>
>I understand that there is one DeBruijn for each direction. How are these
>calculated, besides brute force? Would you mind explaining DeBruijn to me in
>more depth? I see how they work when multiplied by a power of two, but how on
>earth do you get the result to be unique for an arbitrary number of bits set?
Kind of brute force - a recursive de Bruijn generator already posted.
Takes about 67 seconds to traverse all 67108864 64-DeBruijns on my box.
>
>I notice that you mention non-empty. Could you change the DeBruijn to output
>something greater than 0 for all real attack maps, then you could also skip a
>conditional when there are no attacks in that direction (which is probably
>pretty often).
Yes, possible - good point.
>
>I used to use rotated bitboards. I don't like keeping all the tables and
>bitboards around, but it allowed for some neat things, and it was fast. One
>thing I liked was serialized attack tables. I wasn't able to serialize move
>generation effectively because of the capture squares, but with attack tables,
>you attack friendly pieces, so its a nice compact loop.
>I like using bitboards, but haven't been able to make them fast without
>rotation. One idea I tried is to find the last square attacked on a ray, compute
>the distance, and loop back towards the piece moving, just adding a step value.
>This however, is much slower than rotated, and not very practical.
>
>This technique is very intriguing though. It serializes bitboards after friendly
>pieces are removed, so it is practical for move generation. How do you compute
>the bitboards exactly? You can fill, but you have to do it in each direction,
>and if you do pieces together, then you have to somehow "demux" them. What if
>you combined them with rotated bitboards, do you think that could create an
>additional speedup?
I think rotated is quite fine and fast and the tables don't hurt the cache so
much with todays and future L1 sizes. You may also index pointers to movelists
with rotated occupied state and square index.
I use a c++ wrapper to hide SSE2-intrinsics, quad-bitboards and kogge stone
fill stuff based on that - T is either XMM or GPR, both derivered from a
BitBoard[2] base:
template <class T> __forceinline
void _east_Attacks(QBB& t, const QBB& s, const BB &empty)
{
T* pt = (T*)&t;
T r0((T&)s.bb[0]);
T r1((T&)s.bb[2]);
T o(empty);
o = ~o; // occupied
pt[0] = o ^ ((o - r0) - r0);
pt[1] = o ^ ((o - r1) - r1);
}
template <class T> __forceinline
void south_Attacks(QBB& t, const QBB& s, const BB &empty)
{
T* pt = (T*)&t;
T g0((T&)s.bb[0]);
T g1((T&)s.bb[2]);
T p(empty);
g0 |= p & (g0 >> 8);
g1 |= p & (g1 >> 8);
p = p & ( p >> 8);
g0 |= p & (g0 >> 16);
g1 |= p & (g1 >> 16);
p = p & ( p >> 16);
g0 |= p & (g0 >> 32);
g1 |= p & (g1 >> 32);
pt[0] = (g0 >> 8);
pt[1] = (g1 >> 8);
}
The quad-bitboard (0..3) - or one "verical" nibble - has the following semantic
different for diagonals or straight directions:
particular piece code for (king-meta) sliders
diagonals:
0 : black
1 : king
2 : queen
3 : slider (queen or bishop)
straight:
0 : black
1 : king or rook 1
2 : queen
3 : slider (queen or rook)
This allows efficient access of combined all sliding attacks (bitboard 3) as
well as disjoint attacks. With usual material i have disjoint piece - attack
relationship. Therefor rook1 which is the LS rook for both sides (r & -r).
Bishops are separated by square colors. More than 1 queen, 2 rooks or 1 bishop
per square color requires a conditional, (much) more expensive, but general
appraoch.
>
>Anyways, thanks very much for this and all of the other great ideas you post
>here. I love reading them.
Nice to hear ;-)
Gerd
>
>Zach
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.