Magic Move generation

[cms271828]

Hi,

I want to give magic move generation a try instead of rotated bitboards.
I'm just looking at rooks at the moment, I got all the data from crafty, for example (now in java code):

Code: Select all

private int[] rook_shifts =
{
	52, 53, 53, 53, 53, 53, 53, 52,
	53, 54, 54, 54, 54, 54, 54, 53,
	53, 54, 54, 54, 54, 54, 54, 53,
	53, 54, 54, 54, 54, 54, 54, 53,
	53, 54, 54, 54, 54, 54, 54, 53,
	53, 54, 54, 54, 54, 54, 54, 53,
	53, 54, 54, 54, 54, 54, 54, 53,
	53, 54, 54, 53, 53, 53, 53, 53
};

I've done a thorough test to show occupancies with distinct attack sets always map to a distinct N bits (top N bits of Magic[square] * occupancy).

But looking at the board above, all squares not on the edge (value 54) will require an array size 1024. But also, for each of those squares there is 2^5 x 2^5 = 1024 different attack sets.
So each element of the array has precisely 1 occupancy which maps to it.
I can see how this is useful, since you still get the bit-set you want in 1 array look up, but for those squares, it doesn't seem very efficient at all.

Are there any more upto date magics available?
I'm a little concerned these will turn out to be slower than the rotated bitboards due to the relatively large arrays I now have to use.

Eg, For Rook on d4

Rotated bitboards, requires HORIZ[64] and VERT[64], which is 2 look ups

Magic, requires ARRAY[1024], which is 1 look up, but into array 16 times larger.

Thanks for any input.

[Dann Corbit]

Did you read this:
http://chessprogramming.wikispaces.com/Magic+Bitboards

[cms271828]

Yep, I've pretty much read that.

On the best magics found so far, only a a few have been filled in.
But I think most of those there are 1 bit better than what I've got here.

But still going back to what I said before, I would have thought the arrays could be made even smaller considering that many occupancies have identical attack sets.

[wgarvin]

Yep, I've pretty much read that.

On the best magics found so far, only a a few have been filled in.
But I think most of those there are 1 bit better than what I've got here.

But still going back to what I said before, I would have thought the arrays could be made even smaller considering that many occupancies have identical attack sets.

Unfortunately, its hard to take advantage of the fact that many keys produce the same value. The only approach that seems to be popular so far is the "ad-hoc" method where you try and find a magic number that maps all 2^N keys of interest into a space of 2^(N-1) or even less, in such a way that all collisions that happen to occur, are "harmless" in the sense that all keys colliding at the same offset were supposed to have the same result anyway.

I think it was figured out that with one post-masking step, you can combine the table data from two or more squares into the same memory area. And some clever people have combined their shift amounts with some bits of the magic number. But these are only incremental improvements.

If you want to have significantly smaller tables, you probably need to hash fewer bits at a time (e.g. only hash one file/rank/diagonal at a time, instead of two), which would probably be slower than the standard magic way.

[Edit: If you were thinking of adding a layer of indirection, where the first lookup gives you some sort of "result index" and you then look that result up in a second array... that will be a lot slower].

[Gerd Isenberg]

Yep, I've pretty much read that.

On the best magics found so far, only a a few have been filled in.
But I think most of those there are 1 bit better than what I've got here.

But still going back to what I said before, I would have thought the arrays could be made even smaller considering that many occupancies have identical attack sets.

Magic keys of N-1 bits for N occupied bits seem hard to find for most squares, if they excist at all. Most annoying rook squares are 0 (a1) and 7 (h1), which both still have 12-bit keys and therefor 4K entries. I think the best one can do with respect to memory, is to use Lasse Hansen's post-mask trick of the attacks of the otherwise empty board with a union-attack of two rooks and up to two bishops per square ...

Code: Select all

R 1 1 1 1 1 1 1    1 R 1 1 1 1 1 1    1 1 R 1 1 1 1 1    1 1 1 R 1 1 1 1    
B R 1 1 1 1 1 1    R B 1 1 1 1 1 1    1 1 B R 1 1 1 1    1 1 R B 1 1 1 1    
1 1 1 . . . . .    1 1 1 . . . . .    . 1 1 1 1 . . .    . . 1 1 1 . . .    
1 1 1 1 . . . 1    1 1 . 1 . . . .    1 . 1 1 1 1 . .    . 1 1 1 . 1 . .    
1 1 . 1 1 . 1 .    1 1 . . 1 . . .    . . 1 1 . 1 1 .    1 . 1 1 . . 1 .    
1 1 . . 1 B . .    1 1 . . . 1 . .    . . 1 1 . . 1 B    . . 1 1 . . . 1    
1 1 . . 1 1 1 .    1 1 . . . . 1 .    . . 1 1 . . 1 1    . . 1 1 . . . .    
1 1 . 1 . . 1 1    1 1 . . . . . 1    . . 1 1 . 1 . .    . . 1 1 . . . .    

Even if the sets are not disjoint, their common bits only affect always attacked "one" squares, since they are direct neighbors of all Rooks or Bishops.

Gerd

[cms271828]

hi, thanks, I'll take a look at that shortly.

For my legal move testing, I sometimes need to see if king is in check by looking at rays from king, and see if they intersect revelant pieces of opposite colour.

So I'm trying to build magics for single file, rank, diagonals (in addition to magics for + and X directions).

For the ranks (I think this is hardest), I've made magics for all squares upto square 59 which is where it goes wrong.

So basically I have 5 relevant bits at squares 57,58,60,61,62.
And I'm trying to find a magic M, which takes these squares into top 5 bits (59,60,61,62,63).

I know the magic M = 2^5 | 2^(-1) will work, but thats obviously a fraction, so I can't do that, and any other combinations cause the bits to 'overlap' which is a complication (not sure if I can still get magic by overlapping bits).

Can anyone help me find magics here?

Thanks

[Gerd Isenberg]

hi, thanks, I'll take a look at that shortly.

For my legal move testing, I sometimes need to see if king is in check by looking at rays from king, and see if they intersect revelant pieces of opposite colour.

So I'm trying to build magics for single file, rank, diagonals (in addition to magics for + and X directions).

For the ranks (I think this is hardest), I've made magics for all squares upto square 59 which is where it goes wrong.

So basically I have 5 relevant bits at squares 57,58,60,61,62.
And I'm trying to find a magic M, which takes these squares into top 5 bits (59,60,61,62,63).

I know the magic M = 2^5 | 2^(-1) will work, but thats obviously a fraction, so I can't do that, and any other combinations cause the bits to 'overlap' which is a complication (not sure if I can still get magic by overlapping bits).

Can anyone help me find magics here?

Thanks

For disjoint lines like masked ranks and diagonals you can always go with six bits and a "Kindergarten" magic of "0x0202020202020202". See Kindergarten Bitboards. For the top rank, you need only a multiply py 2, before shifting the 6 most significant bits right by 58.

[Gerd Isenberg]

So basically I have 5 relevant bits at squares 57,58,60,61,62.
And I'm trying to find a magic M, which takes these squares into top 5 bits (59,60,61,62,63).

Can anyone help me find magics here?
Thanks

a magic range from 4 to 127 is appropriate to search for enough positive collisions of five of the inner six bits of the top rank. You should find at 5 bit range quite fast. If not, you'll have to stay with six bits and magic == 2

[cms271828]

I only had to use 6 bits instead of 5, for squares 59,60,61, so thats not too bad.

Regarding the file/diagonals, to get the magics I was simply gonna map least bit in occupancy to 63, next least to 62, and so on.

I figured the gap between bits in the occupancy would be 7,8,9 (or even 14,16,18), so there is no chance of 'overlapping' bits this way, at least in the top 6 bits anyway, which is what we need.

Does that sound correct?

Thanks

[Gerd Isenberg]

I only had to use 6 bits instead of 5, for squares 59,60,61, so thats not too bad.

Regarding the file/diagonals, to get the magics I was simply gonna map least bit in occupancy to 63, next least to 62, and so on.

I figured the gap between bits in the occupancy would be 7,8,9 (or even 14,16,18), so there is no chance of 'overlapping' bits this way, at least in the top 6 bits anyway, which is what we need.

Does that sound correct?

Thanks

Yes, the freedom to produce enough overflows for constructive collisions is a bit restricted at the top rank. For {7, 6, 10, 12, 12, 10, 6, 7} disjoint file attack-sets per square along the A-file, Grant Osborne found {5,4,4,5,5,4,4,5}-bit magics. Did you found about the half 4 bit keys as well for files and diagonals?