Magic Move generation

[cms271828]

No, I don't know what they are ?

[Gerd Isenberg]

No, I don't know what they are ?

Not sure what you don't know!?

Actually you mask five/six relevant occupied bits for a 5 bit 0..31 range (with the few exceptions of three rank squares, which take 6 bit 0..63). With the right magics, squares with only five relevant occupied bits (inner piece) may result in a 4 bit 0..15 range, taking only the upper four bits of the magic product. That is due to enough overflows and constructive collisions for squares with 6 or 10 distinct attack sets per line. {7, 6, 10, 12, 12, 10, 6, 7}. The shorter diagonals require even less bits - zero bits for diagonals of length one, two or even sometimes three.

[cms271828]

Ok, I had a quick thought,

Considering a file again, the attack set sizes are {7,6,10,12,12,10,6,7}

Suppose I choose a4, then there is a 5-bit occupancy with 12 attack sets.

Since we have 12 attack sets, the best we can do is 4 bits, and I've already got it working with 5.

so to find a magic that gives 4 bits, we could look at all the bits (0-63) which have an affect on the top 4 bits (60-63).
Since we have 5 occupancy bits, theres 5 bits that affect 63.
and 5 bits that can affect 62
and 5 bits that can affect 61
and 5 bits that can affect 60

So thats 20 possible bits (some of these may coincide, so could be less than 20)

and 2^20 is 1,048,576, so testing all those 1 million-ish magics should be sufficient to determine if 4 bits is possible.

This could be repeated all for squares, not just a4, so possibly even 6-bit occupancies (7 attacksets) could be done in 3 bits(but I doubt that very much!)

Is this thinking correct?
Thanks

[Gerd Isenberg]

Ok, I had a quick thought,

Considering a file again, the attack set sizes are {7,6,10,12,12,10,6,7}

Suppose I choose a4, then there is a 5-bit occupancy with 12 attack sets.

Since we have 12 attack sets, the best we can do is 4 bits, and I've already got it working with 5.

so to find a magic that gives 4 bits, we could look at all the bits (0-63) which have an affect on the top 4 bits (60-63).
Since we have 5 occupancy bits, theres 5 bits that affect 63.
and 5 bits that can affect 62
and 5 bits that can affect 61
and 5 bits that can affect 60

So thats 20 possible bits (some of these may coincide, so could be less than 20)

and 2^20 is 1,048,576, so testing all those 1 million-ish magics should be sufficient to determine if 4 bits is possible.

This could be repeated all for squares, not just a4, so possibly even 6-bit occupancies (7 attacksets) could be done in 3 bits(but I doubt that very much!)

Is this thinking correct?
Thanks

Seems correct to me, but you are the mathematician!

[wgarvin]

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

Let me brainstorm out loud for a few paragraphs. Lets ignore bishops for now, and just think about rooks.

The post-mask lets you combine the entire set of results for a square, with the entire set of results for another square. But there are limits on which squares you can combine it with, because if the result that goes in that slot for one square happens to have a bit set, then that bit *also* needs to be set in the result from the other square that goes in that slot.

You guys have worked out how to combine two diagonally-adjacent squares in the same bitboard. But since the squares which are "compatible" for merging in this way have different shift amounts, it seems like we might be able to do better?

I'm thinking that there are many result bitboards that will not have bits that reach all the way to the end of the ray (because that requires all of the bits along that ray to have been empty in the occupancy bits that are being hashed, which is not the case for most of the possible occupancies). Indeed, it seems that if you take two magics, then AND together the post-masks for their two squares, only the bits which are set in this result need to be "unambiguous". If the squares involved have these "need to be unambiguous" bits near the end of their rays, then most of the entries from both sets of bitboards will have zero for these bits. So it might be possible to fit them together in some fashion where there are no conflicts. So you could store more than two bitboards there as long as you can somehow enforce the requirement that for each pair of bitboards being stored, the "overlapping" bits from their post-masks are either both ones or both zeros.

If you are hashing N occupancy bits from the original bitboard, there should be lots of different magics that redistribute those keys over a range of 2^N entries, and indeed with the constructive collisions there are usually magics that can remap them to a range of 2^(N-1) entries. I'm guessing that there might be plenty of working magics that remap them into a 2^(N-1) range ? And we get to choose which one we use.

So maybe, through clever or lucky choosing of magics and shift amounts and starting offsets, it is possible to "fit together" more squares to optimize the space they take up.

It doesn't seem very important to me to optimize the space usage of the 5- and 6-bit magics because they are already using small, efficient tables. But the worst rook magics at 11 and 12 bits require a lot of table space (up to 32 KB for one square). So it would be interesting to see whether any savings are possible there, by somehow combining and interleaving the entries of their lookup tables. I.e. having chosen the best magic you can find for a "worst-case" square, try to pick random magics for another square such that you can lay them on top of each other and when the "post-mask" for the two squares crosses, they both have either a 1 or a zero.

I haven't tried this (or thought about the math much), so it might be more or less impossible.

Code: Select all

   A 1 a a a a * *    |    A 1 a a a a a *    A 1 a a a a * *
   1 B 1 b b b * *    |    1 B 1 b b b b *    1 - - - - - c d
   a 1 - - - - c d    |    a 1 - - - - - d    a - - - - - c d
   a b - - - - c d    |    a b - - - - - d    a - - - - - c d
   a b - - - - c d    |    a b - - - - - d    a - - - - - c d
   a b - - - - 1 d    |    a b - - - - - d    a - - - - - 1 d
   * * c c c 1 C 1    |    a b - - - - - 1    * c c c c 1 C 1
   * * d d d d 1 D    |    * * d d d d 1 D    * d d d d d 1 D

If it were possible to fit all four of these squares into the same array data... Only the bits marked with a * would have two obligations that have to be satisfied (and each bit would have only two). That still might be impossibly difficult, but what about the two diagrams on the right? Three bitboards each instead of two, and only 4 bits that need to do double duty, and those bits are right near the ends of the ray in all cases so *most* of the table entries for each square are going to want those bits to be zero.

[Pradu]

so to find a magic that gives 4 bits, we could look at all the bits (0-63) which have an affect on the top 4 bits (60-63).
Since we have 5 occupancy bits, theres 5 bits that affect 63.
and 5 bits that can affect 62
and 5 bits that can affect 61
and 5 bits that can affect 60

Is this thinking correct?
Thanks

You forgot about carry effects. Two bits that effect square 60 can carry and effect 61. Without carry effects, you would not be able to create better quality magics than the number of bits in the occupancy. Higher quality magics tend to be dense (cause more carry effects that interact in just the right way as to not have a collision).

It might help to come up with an algebraic mathematical baseline for discussion. I have on more than one occasion made a mistake by intuitively coming up with an algorithm without rigorous proof. My effort at this so far at this is here:

http://pradu.us/research/magics/uc.pdf

I haven't had the time to look into any of the implications of the proposition yet, but I hope some of the propositions made may help this discussion.

[Pradu]

Also take a look at this:

http://en.wikipedia.org/wiki/Backtracking

It might be interesting to guess bits in the magic one at a time and try to get "cutoffs" by having an algorithm that can foresee that no additional magics guessed will help create a feasible magic.

[cms271828]

Well I implemented it, and tried it down the a-file.

for square 0 [a8] (6 bit occ), I found 4 bits was impossible, but haven't tried 5 bits due to time required.

for square 8 [a7] (5 bit occ), best I found was 5 bits, so no change.
for square 16 [a6] (5 bit occ), best I found was 5 bits, so no change.
for square 24 [a5] (5 bit occ), best I found was 5 bits, so no change.
for square 32 [a4] (5 bit occ), best I found was 5 bits, so no change.
for square 40 [a3] (5 bit occ), best I found was 5 bits, so no change.
for square 48 [a2] (5 bit occ), best I found was 5 bits, so no change.

for square 56 [a1] (6 bit occ), I found 4 bits was impossible, but haven't tried 5 bits due to time required.

So I've got zero improvement so far.

On this page
http://chessprogramming.wikispaces.com/ ... +Bitboards
It mentions

Grant's proposal, so far with {5,4,4,5,5,4,4,5} bit ranges for the lookups per square for vertical rook attacks, results in a 1.5 KByte

Well if thats refering to the same thing I don't know how thats done.

Any thoughts?

[Gerd Isenberg]

Well I implemented it, and tried it down the a-file.

for square 0 [a8] (6 bit occ), I found 4 bits was impossible, but haven't tried 5 bits due to time required.

for square 8 [a7] (5 bit occ), best I found was 5 bits, so no change.
for square 16 [a6] (5 bit occ), best I found was 5 bits, so no change.
for square 24 [a5] (5 bit occ), best I found was 5 bits, so no change.
for square 32 [a4] (5 bit occ), best I found was 5 bits, so no change.
for square 40 [a3] (5 bit occ), best I found was 5 bits, so no change.
for square 48 [a2] (5 bit occ), best I found was 5 bits, so no change.

for square 56 [a1] (6 bit occ), I found 4 bits was impossible, but haven't tried 5 bits due to time required.

So I've got zero improvement so far.

On this page
http://chessprogramming.wikispaces.com/ ... +Bitboards
It mentions

Grant's proposal, so far with {5,4,4,5,5,4,4,5} bit ranges for the lookups per square for vertical rook attacks, results in a 1.5 KByte

Well if thats refering to the same thing I don't know how thats done.

Any thoughts?

Grant's file-attacks proposal for the A-File.

[Gerd Isenberg]

so to find a magic that gives 4 bits, we could look at all the bits (0-63) which have an affect on the top 4 bits (60-63).
Since we have 5 occupancy bits, theres 5 bits that affect 63.
and 5 bits that can affect 62
and 5 bits that can affect 61
and 5 bits that can affect 60

Is this thinking correct?
Thanks

You forgot about carry effects. Two bits that effect square 60 can carry and effect 61. Without carry effects, you would not be able to create better quality magics than the number of bits in the occupancy. Higher quality magics tend to be dense (cause more carry effects that interact in just the right way as to not have a collision).

It might help to come up with an algebraic mathematical baseline for discussion. I have on more than one occasion made a mistake by intuitively coming up with an algorithm without rigorous proof. My effort at this so far at this is here:

http://pradu.us/research/magics/uc.pdf

I haven't had the time to look into any of the implications of the proposition yet, but I hope some of the propositions made may help this discussion.

Hi Pradu,
is your other paper no longer available or renamed?
http://buzz.pradu.us/research/magic/Bitboards.pdf

Thanks,
Gerd