Magic bitboards, Java

[Sargon]

[...]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.

A very good paper I think. Often those papers are a tad too mathematical for me, but this one is comprehendable. Thanks for pointing it out. :)

Sargon

PS. Is there a way to really have a tree view in this forum? After a certain depth, tree view is just like flat view, which makes it hard to follow threads, IMO.

[grant]

Hi Gerd

Is your magic number generator able to find 11-bit magics for rooks in any of the corners?

Strange that Lasse Hansen does not comment on the development of his own system.

Grant

[Gerd Isenberg]

Hi Gerd

Is your magic number generator able to find 11-bit magics for rooks in any of the corners?

Strange that Lasse Hansen does not comment on the development of his own system.

Grant

Hi Grant,

No - it is dedicated to find 64-bit de Bruijn numbers for bitscan purpose. At least I haven't tried it explicitly for rook-magigs. I tried it some time ago, to find factors for a masked single file or rank - and even then it was quite hard or even impossible iirc for some squares to find some matching pure De Bruijn numbers.

Here are some relevant links from the old CCC archives

http://www.stmintz.com/ccc/index.php?id=489664
http://www.stmintz.com/ccc/index.php?id=489834
http://www.stmintz.com/ccc/index.php?id=490977

What one may try - and I guess that is what Pradu was refering to - is to use a similar recursive or iterative graph traversing algorithm with some production rule and pruning conditions to look for magics.

Gerd

[grant]

I wondered whether I should take up the search again for better magics with my primitive random number routine. I remember it took a lot of cpu time.

Grant

[Pradu]

I wondered whether I should take up the search again for better magics with my primitive random number routine. I remember it took a lot of cpu time.

Grant

A distributed project may be a good idea:

Consider distributed.net's RC5-64 project. The challenge is to unscramble an encrypted message. To do this each possible key, from zero to 2^64.

In this type of search, we could be lucky and find the answer at the beginning. We could just as equally be unlucky and find the answer at the end. With average luck, the answer would be in the middle. This process would take a single Pentium III 200,000 years to complete. Beyond most lifespans.

Instead, we find ourselves 200,000 computers to divide up the task, so it will take just one year to complete. The key range is split up into blocks of 228 keys, one block making up a work package.

Of course we will have to search far less than 2^64 numbers so it might even work. 2^50 - 2^56 is a very conservative upperbound for most squares, infact it's far less than this but I don't know how much less. To give an idea, it can be proven that square A1 for rooks has no 6-bit magic in a couple hours. For bishops, many squares only take a few minutes or even seconds (search time depends greatly on the order of guessing). However some of the squares like H1 are very hard (I've had the generator running over night for over 2 days then quit). Also increasing the number of bits in the index makes it take too long to reasonably do it in single CPU.

[Jacob]

A distributed project may be a good idea

I have some experience with .NET remoting (in C#) and SQL, and looking at the source for the distributed perft project, it doesn't seem very difficult. As long as I had some help, I could write the client and server. Then it'd simply be a matter of finding someone to host the server and some chess engine enthusiasts to donate some of their testing time =).

Do you have a magic key generator that I could start porting to C#?

[Pradu]

A distributed project may be a good idea

I have some experience with .NET remoting (in C#) and SQL, and looking at the source for the distributed perft project, it doesn't seem very difficult. As long as I had some help, I could write the client and server. Then it'd simply be a matter of finding someone to host the server and some chess engine enthusiasts to donate some of their testing time =).

Do you have a magic key generator that I could start porting to C#?

Yes, but right now it's so hacked up and with zero documentation that even I hardly understand it. Also it's too poorly optimized to be any good for distributed computing. Reimplementing it from scratch would probably be the best way. Also we haven't figured out everything yet (like the best order to guess the bits in) so I guess we have to wait until we know exactly what to do before going distributed.

[jshriver]

I might be wrong, but are bitboards possible with JAva? Thought since JAva uses a VM, it wouldn't be able to make such low-level calls to utilize 64bit wide operations.

Thought bitboards and related optimizations benefited from working directly with the hardware.

-Josh

[Gerd Isenberg]

I might be wrong, but are bitboards possible with JAva? Thought since JAva uses a VM, it wouldn't be able to make such low-level calls to utilize 64bit wide operations.

Thought bitboards and related optimizations benefited from working directly with the hardware.

-Josh

Java long is 64 bit and offers all operations you need for bitboards.
For bitscanning see http://64.68.157.89/forum/viewtopic.php ... 72&t=14151

[Rein Halbersma]

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.

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?

Hi Gerd,

OK, it seems that I can't add an Excel-attachment on this forum?

Here's a 32-bit example where the LSB is bit 0 and the MSB is bit 31. I wish to index a bitmask with the following bits: 8,9,10,16,17,18,24,25 and 26. This means I AND my occupancy bitboard with the configuration 0x7070700 = 2^8 + ... + 2^26. I use the following magic: 0x82001 = 2^19 + 2^13 + 2^0, so the magic has only 3 active bits.

index = (occupancy & mask) & magic >> (32-9)

You can check that with mask = 0x7070700 and magic = 0x82001 this gives a 9-bit index. To check this with a multiplication table:

Code: Select all

       8   9  10  16 17 18 24 25 26
 0   -15 -14 -13  -7 -6 -5  1  2  3 
13    -2  -1   0   6  7  8 14 15 16
19     4   5   6  12 13 14 20 21 22

The above table shows the active bits in the mask (columns) and in the magic (rows). The entries in the table are the active bits in the index (entry_ij = i+j-(32-9)). Only bits 0...8 are used in the actual index.

Rowwise, notice that bit 0 in the magic fills bits 1,2,3 in the index, bit 13 in the magic fills bits 0,6,7,8 and bit 19 in the magic fills bits 4,5,6. Columnwise, notice that all bits in the mask almost uniquely fill a bit in the index.

There is only a single overlap: bit 6 in the index is filled by bits 0 and 13 in the magic when bits 16 and 10, respectively, are set in the mask. Fortunately, bit 10 in the mask is also uniquely filling bit 0 in the index. This means that the carry of bit 6 in the index can freely propagate to bits 7 and 8 since bit 0 in the index marks whether there has been a carry forward in the index.

It's reasoning like this that I would like to generalize when generating magics for arbitrary bitmasks.

Rein