Author: Gerd Isenberg
Date: 02:16:47 02/20/06
Go up one level in this thread
>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?
See also
http://supertech.csail.mit.edu/papers/debruijn.pdf
Chapter 4 Indexing two 1's
Seems there is some empiric required even for the MIT guys ;-)
For bitscanning you usually isolate the LSB by (x & -x), where the de Bruijn
multiplication obviously leaves a unique index. If you try (x ^ -x) to get a
1...10...0 sequence, where the 1->0 changeover is determined by the LS1B, you
will get unique indices with De Bruijn multiplication as well.
I already used DeBruijn-indexing with multiple bits, eg. union of from- and
to-bits for a particular direction or even the difference of from-to-bits. It
was necessary to use the 9 upper bits of the De Bruijn-Product for the diagonals
(140/512) but 10 bits for straight directions (224/1024).
You may also try to map multiple but distinct directions to one index range, but
that requires greater tables. So far i found no way to map combined opposite
direction attacks this way as usually provided by rotated lookups.
This is the skeleton of the de Bruijn generator, is use to find De Bruijn
sequences with desired properties:
void findDeBruijn(BitBoard seq, int depth, int unique) {
if ( (m_Lock & pow2[unique]) == 0 && unique != 32) {
if ( depth == 0 ) {
deBruijnFound(seq); // make your tests here
}else{
m_Lock ^= pow2[unique];
if ( depth > 2 && unique == 31 ) {
findDeBruijn(seq | pow2[depth-1], depth-2, 62);
}else{
if ( depth > 1 )
findDeBruijn(seq, depth-1, (unique*2)&63);
findDeBruijn(seq | pow2[depth-1], depth-1, (unique*2+1)&63);
}
m_Lock ^= pow2[unique];
}
}
Gerd
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.