Magic bitboards, Java

[Gerd Isenberg]

There are way too many 64-bit magics to print out; however, there should be 2^27 magics for 64-bits

Please, show here the smallest one.

Here is my 64/6-bit De Bruijn bitScanForward-generator.
Considering only the 2^26 odd sequences with 6 leading binary zeros.

You can call it with 1...67108864 (0x4000000).
0x0218a392cd3d5dbf is the smallest one,
0x03f79d71b4cb0a89 the biggest (odd) one.

Code: Select all

C:\source\deBruijn\Release>debruijn 1

const u64 magic = 0x0218a392cd3d5dbf; // the 1.

const unsigned int magictable[64] =
{
    0,  1,  2,  7,  3, 13,  8, 19,
    4, 25, 14, 28,  9, 34, 20, 40,
    5, 17, 26, 38, 15, 46, 29, 48,
   10, 31, 35, 54, 21, 50, 41, 57,
   63,  6, 12, 18, 24, 27, 33, 39,
   16, 37, 45, 47, 30, 53, 49, 56,
   62, 11, 23, 32, 36, 44, 52, 55,
   61, 22, 43, 51, 60, 42, 59, 58,
};

unsigned int bitScanForward (u64 b) {
    return magictable[((b&-b)*magic) >> 58];
}

Code: Select all

C:\source\deBruijn\Release>debruijn 67108864

const u64 magic = 0x03f79d71b4cb0a89; // the 67108864.

const unsigned int magictable[64] =
{
    0,  1, 48,  2, 57, 49, 28,  3,
   61, 58, 50, 42, 38, 29, 17,  4,
   62, 55, 59, 36, 53, 51, 43, 22,
   45, 39, 33, 30, 24, 18, 12,  5,
   63, 47, 56, 27, 60, 41, 37, 16,
   54, 35, 52, 21, 44, 32, 23, 11,
   46, 26, 40, 15, 34, 20, 31, 10,
   25, 14, 19,  9, 13,  8,  7,  6,
};

unsigned int bitScanForward (u64 b) {
    return magictable[((b&-b)*magic) >> 58];
}

source code

Code: Select all

#include <stdio.h>
#include <stdlib.h>

typedef unsigned __int64 u64; // long long

class GenBitScan
{
public:
    GenBitScan(int match4nth)
    {
        m_Lock  = 0;
        m_dBCount = 0;
        m_Match4nth  = match4nth;
        initPow2();
        try {findDeBruijn(0, 64-6, 0);} catch(int){}
    }

private:
    u64 pow2[64];
    u64 m_Lock;
    int  m_dBCount;
    int  m_Match4nth;

    void initPow2()  {
        for (int i=0; i < 64; i++)
            pow2[i] = (u64)1 << i;
    }

    virtual void bitScanRoutineFound(u64 deBruijn)
    {
        int index[64], i;
        for (i=0; i<64; i++) // init magic array
            index[ (deBruijn<<i) >> (64-6) ] = i;
        printf("\nconst u64 magic = 0x%08x%08x; // the %d.\n\n",
                (int)(deBruijn>>32), (int)(deBruijn), m_dBCount);
        printf("const unsigned int magictable[64] =\n{");
        for (i=0; i<64; i++)
        {
            if ( (i & 7) == 0 ) printf("\n  ");
            printf(" %2d,", index[i]);
        }
        printf("\n};\n\nunsigned int bitScanForward (u64 b) {\n");
        printf("    return magictable[((b&-b)*magic) >> 58];\n}\n");
        throw 0; // unwind the stack until catched
    }


    void findDeBruijn(u64 seq, int depth, int unique)
    {
        if ( (m_Lock & pow2[unique]) == 0 && unique != 32)
        {
            if ( depth == 0 )
            {
                if ( ++m_dBCount == m_Match4nth )
                    bitScanRoutineFound(seq);
            }
            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];
            }
        }
    }
};

int main(int argc, char* argv[])
{
    if (argc < 2)
        printf("usage: genBitScan 1 .. %d\n", 1<<26);
    else
        GenBitScan(atoi(argv[1]));
    return 0;
} 

a folded De Bruijn Graf with chess board coordinates.
2^26 ways to traverse it...

Code: Select all

.->-a1-------------------------->--\../--<-----------------------------\
....^...............................b1.................................|
....|..............c1--------------/..\-------------d1.................|
....|......e1-----/..\-----f1...............g1-----/..\-----h1.........|
....|..a2-/..\-b2......c2-/..\-d2.......e2-/..\-f2......g2-/..\-h2.....|
....|a3..b3..c3..d3..e3.|f3|.g3..h3...a4..b4..c4..d4..e4..f4..g4..h4...|
....a5b5c5d5e5f5g5h5a6b6c6d6e6f6g6h6.a7b7c7d7e7f7g7h7a8b8c8d8e8f8..h8..|
....../\/\/\/\/\/\/\/\/\.\/\/\/\/\/\./\/\/\/\/\/\/\/\/\/\/\/\/\/\..|...|
...................................................................|...|
....................................../--<-------------------------/...^
....................................g8.................................|
...................f8--------------/..\-------------e8.................|
...........d8-----/..\-----c8...............b8-----/..\-----a8.........|
.......h7-/..\-g7......f7-/..\-e7.......d7-/..\-c7......b7-/..\-a7.....|
.....h6..g6..f6..e6..d6.|c6|.b6..a6...h5..g5..f5..e5..d5..c5..b5..a5...|
....h4g4f4e4d4c4b4a4h3g3f3e3d3c3b3a3.h2g2f2e2d2c2b2a2h1g1f1e1d1c1..a1..|
.....\/\/\/\/\/\/\/\/\/\.\/\/\/\/\/\./\/\/\/\/\/\/\/\/\/\/\/\/\/\...\--/ 

[Gerd Isenberg]

See also:
http://www.stefangeens.com/br13.pdf

2.1 De Bruijn sequences
..
In 1946, De Bruijn [1] (see [2]) proved his famous theorem:

Theorem 1. For s = 2 and each positive integer there are exactly 2^(2^(q-1)-q) complete cycles of
length 2^q.

Code: Select all

2^q   q   number of cycles                         hex
  4   2   2^((2^1)-2) = 2^ 0 =                  1  0x0000000000000001
  8   3   2^((2^2)-3) = 2^ 1 =                  2  0x0000000000000002
 16   4   2^((2^3)-4) = 2^ 4 =                 16  0x0000000000000010
 32   5   2^((2^4)-5) = 2^11 =               2048  0x0000000000000800
 64   6   2^((2^5)-6) = 2^26 =           67108864  0x0000000004000000
128   7   2^((2^6)-7) = 2^57 = 144115188075855872  0x0200000000000000

[Pradu]

There are way too many 64-bit magics to print out; however, there should be 2^27 magics for 64-bits

Please, show here the smallest one.

0x0218A392CD3D5DBF

However, I don't understand why choosing the lowest possible magic would make things faster. In a quick test they seem to be about the same speed.

EDIT: Oh Gerd replied already.

[Pradu]

You can call it with 1...67108864 (0x4000000).
0x0218a392cd3d5dbf is the smallest one,
0x03f79d71b4cb0a89 the biggest (odd) one.

So this would mean the biggest overall one would be (0x03f79d71b4cb0a89<<1).

[Gerd Isenberg]

You can call it with 1...67108864 (0x4000000).
0x0218a392cd3d5dbf is the smallest one,
0x03f79d71b4cb0a89 the biggest (odd) one.

So this would mean the biggest overall one would be (0x03f79d71b4cb0a89<<1).

yes, the "even" ones with five leading zeros define the same eulerian cycle in the de Bruijn graph.
http://en.wikipedia.org/wiki/De_Bruijn_sequence

[Pradu]

a folded De Bruijn Graf with chess board coordinates.
2^26 ways to traverse it...

Code: Select all

.->-a1-------------------------->--\../--<-----------------------------\
....^...............................b1.................................|
....|..............c1--------------/..\-------------d1.................|
....|......e1-----/..\-----f1...............g1-----/..\-----h1.........|
....|..a2-/..\-b2......c2-/..\-d2.......e2-/..\-f2......g2-/..\-h2.....|
....|a3..b3..c3..d3..e3.|f3|.g3..h3...a4..b4..c4..d4..e4..f4..g4..h4...|
....a5b5c5d5e5f5g5h5a6b6c6d6e6f6g6h6.a7b7c7d7e7f7g7h7a8b8c8d8e8f8..h8..|
....../\/\/\/\/\/\/\/\/\.\/\/\/\/\/\./\/\/\/\/\/\/\/\/\/\/\/\/\/\..|...|
...................................................................|...|
....................................../--<-------------------------/...^
....................................g8.................................|
...................f8--------------/..\-------------e8.................|
...........d8-----/..\-----c8...............b8-----/..\-----a8.........|
.......h7-/..\-g7......f7-/..\-e7.......d7-/..\-c7......b7-/..\-a7.....|
.....h6..g6..f6..e6..d6.|c6|.b6..a6...h5..g5..f5..e5..d5..c5..b5..a5...|
....h4g4f4e4d4c4b4a4h3g3f3e3d3c3b3a3.h2g2f2e2d2c2b2a2h1g1f1e1d1c1..a1..|
.....\/\/\/\/\/\/\/\/\/\.\/\/\/\/\/\./\/\/\/\/\/\/\/\/\/\/\/\/\/\...\--/ 

Could you explain what this graph means or perhaps point to a resource which explains it in layman terms? It looks like an interesting approach to generate magics although I don't understand it one bit at the moment and it is hard to read up on it because links like this assumes the reader already has knowledge of graph theory.

[Gerd Isenberg]

a folded De Bruijn Graf with chess board coordinates.
2^26 ways to traverse it...

Code: Select all

.->-a1-------------------------->--\../--<-----------------------------\
....^...............................b1.................................|
....|..............c1--------------/..\-------------d1.................|
....|......e1-----/..\-----f1...............g1-----/..\-----h1.........|
....|..a2-/..\-b2......c2-/..\-d2.......e2-/..\-f2......g2-/..\-h2.....|
....|a3..b3..c3..d3..e3.|f3|.g3..h3...a4..b4..c4..d4..e4..f4..g4..h4...|
....a5b5c5d5e5f5g5h5a6b6c6d6e6f6g6h6.a7b7c7d7e7f7g7h7a8b8c8d8e8f8..h8..|
....../\/\/\/\/\/\/\/\/\.\/\/\/\/\/\./\/\/\/\/\/\/\/\/\/\/\/\/\/\..|...|
...................................................................|...|
....................................../--<-------------------------/...^
....................................g8.................................|
...................f8--------------/..\-------------e8.................|
...........d8-----/..\-----c8...............b8-----/..\-----a8.........|
.......h7-/..\-g7......f7-/..\-e7.......d7-/..\-c7......b7-/..\-a7.....|
.....h6..g6..f6..e6..d6.|c6|.b6..a6...h5..g5..f5..e5..d5..c5..b5..a5...|
....h4g4f4e4d4c4b4a4h3g3f3e3d3c3b3a3.h2g2f2e2d2c2b2a2h1g1f1e1d1c1..a1..|
.....\/\/\/\/\/\/\/\/\/\.\/\/\/\/\/\./\/\/\/\/\/\/\/\/\/\/\/\/\/\...\--/ 

Could you explain what this graph means or perhaps point to a resource which explains it in layman terms? It looks like an interesting approach to generate magics although I don't understand it one bit at the moment and it is hard to read up on it because links like this assumes the reader already has knowledge of graph theory.

Each node is a six-bit number a1 = 0, b1 = 1, ..., h8 = 63.
There are max two possible successors of each node i,
(2i+0) mod 64 and
(2i+1) mod 64

The graph shows all possible successors of each square...

Code: Select all

         i
         /\
(2i+0)&63  (2i+1)&63

The condensed bottom line of each half ...

Code: Select all

.. b5c5
.. /\/\

wrap their successors somewhere to the "stretched" other half with almost same nodes for better presentation to make the edges clearly arranged.

a1 has only one successor b1
b1 has two possible successors c1 or d1
c1 has e1, f1
f1 has c2, d2
c2 has e3, f3
f3 has c6, d6
--- cut to the stretched lower half
c6 has f3 (oups a direct cycle) and e3
... and so on, until you reached each square on the board once.

Most squares have two possible successors, but h8 and a1 have only g8 and b1. The "wormhole" is the cycle f3<->c6, which is likely in the middle of the sequence.

The de Bruijn sequence 0x0218a392cd3d5dbf defines one eulerian cycle in this graph, starting with a1 and trying always the smaller (successor 2i+0)&63 first

Code: Select all

00000010000110001010001110010010110011010011110110111111(00000) 
000000             0=a1
 000001            1=b1
  000010           2=c1
   000100          4=e1
    001000         8=a2
     010000       16=a3
      100001      33=b5
       000011      3=d1
        000110 .........

[Gerd Isenberg]

I also vote for editing posts after 15 minutes!

Additionaly a0 has only one predecessor, namely a5=32.
This is of course due to the five traling hidden zeros and it is the last sub-sequence. h4 has the single successor h8.

[Pradu]

I also vote for editing posts after 15 minutes!

Hehe yes

Additionaly a0 has only one predecessor, namely a5=32.
This is of course due to the five traling hidden zeros and it is the last sub-sequence. h4 has the single successor h8.

Code: Select all

         i
         /\
(2i+0)&63  (2i+1)&63

Ok I think I get the gist of the method now. Basically every node represents an index and the connections show the interdependence (in this case a forward step) between the indices right?

Also the method of generation for your method I suppose is to traverse all nodes without going over a node twice (this becomes identical to my generation method). But I know for a fact that your magic generator is much faster than mine; is there some way you know for certain that you can prune out certain paths?

If you do have some way to prune out certain paths, maybe it can be applied to optimal magic generation with carry effects. Because the index computation will depend on carry effects and allowed collisions, you can perhaps create a map by adding say something similar to logic gates to choose the direction of the path and usability of nodes.

[Gerd Isenberg]

Ok I think I get the gist of the method now. Basically every node represents an index and the connections show the interdependence (in this case a forward step) between the indices right?

Exactly.

Also the method of generation for your method I suppose is to traverse all nodes without going over a node twice (this becomes identical to my generation method). But I know for a fact that your magic generator is much faster than mine; is there some way you know for certain that you can prune out certain paths?

Yes, if you have a closer look to this recursive routine which is part of the class i posted above, you'll see the extra conditions which speed up the search. Together with the lock condition, which ensures that no node is traversed twice, i prune 100000B = 32 forward in the outer if, since it is the very last sub-sequence with the five hidden zeros and therefor should not occur before. The fixed h4->h8->g8 (31->63->62) path is considered as well - and since the last bit is set, i forward prune even successors, if depth == 1. With the "unique != 32" condition, there is no need to prove the uniqueness of the five "last" sub-sequences containing the hidden zeros.

Code: Select all

void findDeBruijn(u64 seq, int depth, int unique)
    {
        if ( (m_Lock & pow2[unique]) == 0 && [b]unique != 32[/b])
        {
            if ( depth == 0 )
            {
                if ( ++m_dBCount == m_Match4nth )
                    bitScanRoutineFound(seq);
            }
            else
            {
                m_Lock ^= pow2[unique];
               [b]if ( depth > 2 && unique == 31 )[/b]
                {
                    findDeBruijn(seq | pow2[depth-1], [b]depth-2, 62[/b]);
                }
                else
                {
                    [b]if ( depth > 1 )[/b]
                        findDeBruijn(seq, depth-1, (unique*2)&63);
                    findDeBruijn(seq | pow2[depth-1], depth-1, (unique*2+1)&63);
                }
                m_Lock ^= pow2[unique];
            }
        }
    }

If you do have some way to prune out certain paths, maybe it can be applied to optimal magic generation with carry effects. Because the index computation will depend on carry effects and allowed collisions, you can perhaps create a map by adding say something similar to logic gates to choose the direction of the path and usability of nodes.

My experience so far using (combined) de Bruijn sequences to multiply masked occupancies with was rather disappointing.