Magic bitboards, Java

[Pradu]

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

It's definately worth another shot. There seems to be quite a bit of theory on the Eulerian traversal of graphs. So for multiply with carrys, you must first do a search to generate only graphs that can be traversed by an Eulerian path. If you can find just one such graph, you can generate an optimal magic. If no such graphs exist, then you can effectively say that there doesn't exist a magic.

EDIT: I take that back, paths won't be Eulerian for graphs for move-bitboard generation because multiple input keys can collide to one index.

[Rein Halbersma]

Hi all, this is my first post here, my name is Rein Halbersma, and I'm a programmer on a 10x10 draughts program, where I think the magic can also be put to great use.

As far as I understand things, a De Bruijn constant does a somewhat different thing than a magic constant.

single_bit_anywhere * DeBruijn >> 64 - 6
configuration_of_n_specific_bits * magic >> 64 - n

So a De Bruijn constant maps any of the 64 = 2^6 single bits within a 64-bit board onto a 6-bit index.

A magic maps any of the 2^n configurations of n fixed bits onto a n-bit index. But e.g. for n adjacent bits, the magic is just a single-bit constant (i.e a power of 2).

My question: what do magics have to do with De Bruijn constants?

Rein

[Pradu]

My question: what do magics have to do with De Bruijn constants?

De Bruijn constants are magic constants for a very specific problem - the bitscan. They are used as an example to help visualize how the indices produced by the magic are related to the bits in the magic and it is easy. Methods used to produce De Bruijn constants with modification to handle carrys and allowed collisions can be applied to the generation and proof of optimal magics for any set of input keys.

A magic maps any of the 2^n configurations of n fixed bits onto a n-bit index. But e.g. for n adjacent bits, the magic is just a single-bit constant (i.e a power of 2).

Magics are not limited to 2^n configurations mapped to an index. That can be done very efficiently by just trying out random numbers. The idea is that you can compress to an index which is less than n bits with allowed collisions. For example, for the bitscan, all 64-bits are used in the index, however the index is only a few bits long. Likewise, for move-bitboard generation, these exist magic keys that produce indices whose "bit-size" is less than the number of bits in the key.

[Rein Halbersma]

My question: what do magics have to do with De Bruijn constants?

De Bruijn constants are magic constants for a very specific problem - the bitscan.

De Bruijn constants map a *random* set bit within a 2^n-bits string onto an n-bit index.

If you look at Section 4 of the paper http://supertech.csail.mit.edu/papers/debruijn.ps then they try to extend the bitscan to two random bits.

Magics map a configuration of a *fixed* n-bit pattern onto an 2^n-bit index. That seems quite different to me. In what way does a magic form a De Bruijn sequence?

They are used as an example to help visualize how the indices produced by the magic are related to the bits in the magic and it is easy. Methods used to produce De Bruijn constants with modification to handle carrys and allowed collisions can be applied to the generation and proof of optimal magics for any set of input keys.

This I don't understand yet. Can you elaborate on this?

[Gerd Isenberg]

Hello Rein,

welcome to CCC.

I agree with you. While de Bruijn multiplication with single bit sets applies perfect hashing of the bit-index, the magic multiplication of masked occupancies of all rook- and bishop rays suffers from quite huge index-ranges, specially for the rooks.

Due to my mathematicl naivity - inspired from the paper you mentioned - I tried De Bruijns (or De Bruijns xor other (shifted, rotated and what else) De Bruijn or constant) for the purpose to map masked single ray occupancies to a most dense index range into the precalculated attack-bitboards. While it took some cpu-time to get a match, Tony van Roon-Werten told me to use random-numbers to get faster matches. There is even the advantage to deal with redundant occupied bits behind the first blocker, which doesn't affect the resulting attack-set.

It took me some time to regocnize the waste of cpu-ressources and to understand the simple natur of Kindergarten-Bitboards, multiplying masked file- and diagonal/rank-pattern to map the relevant bits to the top rank.

I am very sceptical that De Bruijn constants may get denser ranges for magic lookups - they may helpfull to understand things better and to improve mathematical knowledge.

I was also very sceptical in the beginning about Lasse Hanssen's approach to map all rook- and bishop ray-occupancies with one and/mul/shift/lookup and Pradu's tries to improve it - a fixed sized two-dimensional array of [square][occupiedIndex] in mind. Then Pradu came up with a Java-like array, which really gave a huge reduction. It would be fine though to reduce further.

Cheers,
Gerd

[Pradu]

De Bruijn constants map a *random* set bit within a 2^n-bits string onto an n-bit index.

Or you can think of it as 64 possible input keys with 64 *fixed* n-bits.

If you look at Section 4 of the paper http://supertech.csail.mit.edu/papers/debruijn.ps then they try to extend the bitscan to two random bits.

Sure you can generate a magic to index 2,3,4 how many ever bits using the same generation technique. I do not believe the guys in that paper found a generalized way to generate a magic for a bitscan for arbitrary number of bits though.

Magics map a configuration of a *fixed* n-bit pattern onto an 2^n-bit index. That seems quite different to me. In what way does a magic form a De Bruijn sequence?

A magic for move-bitboard generation does not have any relation to a De-Bruijn sequence as far as I know. The method of generating De Bruijns can be generalized to work for arbitrary input keys, that is all.

They are used as an example to help visualize how the indices produced by the magic are related to the bits in the magic and it is easy. Methods used to produce De Bruijn constants with modification to handle carrys and allowed collisions can be applied to the generation and proof of optimal magics for any set of input keys.

This I don't understand yet. Can you elaborate on this?

The elaboration on how to modify my particular generation technique to handle carries and collisions is in the paper I posted earlier.

[Rein Halbersma]

It took me some time to regocnize the waste of cpu-ressources and to understand the simple natur of Kindergarten-Bitboards, multiplying masked file- and diagonal/rank-pattern to map the relevant bits to the top rank.

Hi Gerd,

It would be very helpful if some of you experts on magic could assemble a Wiki-page with all the nomenclature (Kindergarten, Kogge-fill). It's quite hard to learn everything by reading all the discussions.

I have been doing some very elementary exercises (mostly in Excel and by hand) with 16-bit integers in order to see what is going on.

1)If e.g. I have n scattered bits and want to form an n-bit index for the occupancy of those bits, I simply make an 16xn multiplication table. Every (i,j) entry has as value (i+j-(16-n)). This is just the fact that multiplication of powers of 2 is equal to addition of their exponents.

2)To find a magic, what I do is to look for a sequence of rows (out of the 16 available) in such a way that every number 0:n-1 occurs exactly once in the combined rows, and that every column has a unique number out of 0:n-1 on those selected row.

3) With carry effects, things are more subtle and I am trying to understand the patterns that happen then.

I am convinced that there are some simple (or at least simply to compute) conditions on the multiplication table that generate the magics. I think that parsing this very condensed table is all that is needed ("Sudoku-magic"). No random testing or looping over all 2^n possibilities. But perhaps I am too optimistic/naive

Rein

[Rein Halbersma]

The elaboration on how to modify my particular generation technique to handle carries and collisions is in the paper I posted earlier.

Yes, your paper is very interesting and helpful. It led me to believe that instead of trying all 2^n combinations there might be an algorithm that only considers combinations of the n exponents. So far only conjecture, but I am making progress.

[Pradu]

The elaboration on how to modify my particular generation technique to handle carries and collisions is in the paper I posted earlier.

Yes, your paper is very interesting and helpful. It led me to believe that instead of trying all 2^n combinations there might be an algorithm that only considers combinations of the n exponents. So far only conjecture, but I am making progress.

Yes my method is quite slow, it takes hours or days at best to prove an optimal magic for one square for rooks. Proving optimal magics for bishop is much faster however, but rooks are the one that take up the most memory. I think one way of improving it is to find more cuttoff/pruning conditions but I haven't come up with any so far. Also improving the guessing ordering would be another way.

[Gerd Isenberg]

Hi Gerd,

It would be very helpful if some of you experts on magic could assemble a Wiki-page with all the nomenclature (Kindergarten, Kogge-fill). It's quite hard to learn everything by reading all the discussions.

I have been doing some very elementary exercises (mostly in Excel and by hand) with 16-bit integers in order to see what is going on.

1)If e.g. I have n scattered bits and want to form an n-bit index for the occupancy of those bits, I simply make an 16xn multiplication table. Every (i,j) entry has as value (i+j-(16-n)). This is just the fact that multiplication of powers of 2 is equal to addition of their exponents.

2)To find a magic, what I do is to look for a sequence of rows (out of the 16 available) in such a way that every number 0:n-1 occurs exactly once in the combined rows, and that every column has a unique number out of 0:n-1 on those selected row.

3) With carry effects, things are more subtle and I am trying to understand the patterns that happen then.

I am convinced that there are some simple (or at least simply to compute) conditions on the multiplication table that generate the magics. I think that parsing this very condensed table is all that is needed ("Sudoku-magic"). No random testing or looping over all 2^n possibilities. But perhaps I am too optimistic/naive

Rein

Hi Rein,

I fear the real experts will outlaw my impertinence to call it kindergarten multiplication

Code: Select all

a..h is either 0 or 1

h . . . . . . .   1 . . . . . . .   a b c d e f g h
g . . . . . . .   . 1 . . . . . .   . a b c d e f g
f . . . . . . .   . . 1 . . . . .   . . a b c d e f
e . . . . . . .   . . . 1 . . . .   . . . a b c d e
d . . . . . . . * . . . . 1 . . . = . . . . a b c d
c . . . . . . .   . . . . . 1 . .   . . . . . a b c
b . . . . . . .   . . . . . . 1 .   . . . . . . a b
a . . . . . . .   . . . . . . . 1   . . . . . . . a

1 . . . . . . .   a . . . . . . .   a b c d e f g h
1 . . . . . . .   . b . . . . . .   . b c d e f g h
1 . . . . . . .   . . c . . . . .   . . c d e f g h
1 . . . . . . .   . . . d . . . .   . . . d e f g h
1 . . . . . . . * . . . . e . . . = . . . . e f g h
1 . . . . . . .   . . . . . f . .   . . . . . f g h
1 . . . . . . .   . . . . . . g .   . . . . . . g h
1 . . . . . . .   . . . . . . . h   . . . . . . . h 

On Kogge-Stone there seems something under construction.
http://en.wikipedia.org/wiki/Kogge-Stone_Adder
Propagating carries or sliding attacks have something in common. Unfortunately not always the direction

About your multiplication table, I don't get that. Can you elaborate a bit more on it, e.g. with some sample pattern and numbers for a mathematical patzer?

Thanks,
Gerd