Plain rook(resp. bishop) magics in 64 K each (and less)

[Roberto Mizzoni]

I know about the recent topic by crystal (http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=51996) witch the very beginning seems to start with the same approach as me (I found it when looking if there was something similar to my approach), but then it diverges so I decided to start this new topic.

I came up with the idea of dividing into two magic attack tables when I noticed the corner squares to be problematic regarding table size. So I divided the rook attack sets into two left/right and up/down cases respectively, and by using the standar magic techniques I could reduce the rook magics to two [64][64] magic tables, or just 64 K. The same goes for the bishops with little differences.

I'm using (n * magic) >> (64 - 6) as the hashing scheme, but it can be halved for the rook up/down case, that is, I can use (n * magic) >> (64 - 5) and reduce the table size by two for that case (I didn't test this for the bishop).

Of course all of this comes at the cost of some code duplication as compared with the standard plain magics, with the the simplicity of Plain magics and the total size advantage.

I can provide code for this if you think it's worth.

Has this approach been considered before?

[Gerd Isenberg]

I know about the recent topic by crystal (http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=51996) witch the very beginning seems to start with the same approach as me (I found it when looking if there was something similar to my approach), but then it diverges so I decided to start this new topic.

I came up with the idea of dividing into two magic attack tables when I noticed the corner squares to be problematic regarding table size. So I divided the rook attack sets into two left/right and up/down cases respectively, and by using the standar magic techniques I could reduce the rook magics to two [64][64] magic tables, or just 64 K. The same goes for the bishops with little differences.

I'm using (n * magic) >> (64 - 6) as the hashing scheme, but it can be halved for the rook up/down case, that is, I can use (n * magic) >> (64 - 5) and reduce the table size by two for that case (I didn't test this for the bishop).

Of course all of this comes at the cost of some code duplication as compared with the standard plain magics, with the the simplicity of Plain magics and the total size advantage.

I can provide code for this if you think it's worth.

Has this approach been considered before?

Yep.

Kindergarten Bitboards with multiple variants and space-time issues. Common is the 4 KByte shared lookup for lines with odd (1,7,9) increments (for Little-Endian Rank-File Mapping - ranks, diagonals, and antidiagonals) and 4 KByte for the lines with 8-increment. For the latter Grant Osborne proposed 8 magic like factors with an 1.5 KByte lookup table. The minimum memory requirements for those occupancy lookup techniques is 64*8 = 512 Bytes, but leading and trailing computations.

[Roberto Mizzoni]

Kindergarten Bitboards with multiple variants and space-time issues. Common is the 4 KByte shared lookup for lines with odd (1,7,9) increments (for Little-Endian Rank-File Mapping - ranks, diagonals, and antidiagonals) and 4 KByte for the lines with 8-increment. For the latter Grant Osborne proposed 8 magic like factors with an 1.5 KByte lookup table. The minimum memory requirements for those occupancy lookup techniques is 64*8 = 512 Bytes, but leading and trailing computations.

Wow, thanks!
I paid too much attention to the Magic Bitboards article and almost no attention to the kindergarten one.

[crystalclear]

Hi to Roberto Mizzoni.

So far my thoughts and conversation have concentrated on index generation, and your posting seems to be on storing the tables that are to be indexed.
I'm new to this and haven't got anything working yet, so I hope people go easy on me if I say something stupid, but here goes ....

https://chessprogramming.wikispaces.com ... +Bitboards

I believe the tables there are designed to be indexed by a six-bit occupancy-index in the 0..63 range.
If the data is compressed into tables, I assume that they are managing to achieve the compression for either or both of two reasons.

A. Unused bits in some data can be used to store something else.
B. Several distinct cases with the same result can be stored in the same place.

Before someone else can take advantage of the same compression, then, some preconditions will be imposed on them.
a. That the unused bits will be masked off and only the useful data extracted, ie the data must be used in a fairly similar way.
b. That the distinct cases can find the same memory location.

Let me discuss {B,b}, as I think that might be relevant to you.
It appears to me that the Kindergarten Bitboards are extracting an UNHASHED index for bit occupancy.
My current understanding is that some different lines on a chess board with the same scattering of pieces along them would generate the same occupancy index with Kindergarten Bitboards. These different lines will then result in the same memory locations in the table being accessed, via this same index.

Now with magic index generation, the line occupancy is HASHED into a fairly random sequence of bits.
So I think you CANNOT use the Kindergarten Bitboards with your magic index generation.

The trick is to share one 4KByte table by three line-directions by re-using the mask for a final intersection.

Unless you somehow have magic hashing that creates the same index for one diagonal and another, etc, I don't see how you can use Kindergrten Bitboards, because of (B). I think you can use (A), eg store 8 lines of data in a 64 bits.

People's thoughts are welcome, as I haven't got to grips with this yet.
One reason I am initially going with my approach is that I don't like magics and hashing for a couple of reasons.
1. It makes my data difficult to verify and code harder to debug.
2. Tables cannot be shared unless things hash to the same values.
3. I cannot populate the tables without first defining the hash function.
4. If I change the index generation method, I need to regenerate the tables.
5. Generating magic numbers seems complex too.

I could add that it seems ill defined quite what magic numbers are.
Sometimes they seem to be used for casting out zeros, and sometimes for performing a mathematical function.
Furthermore, sometimes a precise result is expected eg for bitscanning and sometimes a hashed result is satistactory.
Does "magic" really just mean any unintelligable muliply and shift that does something useful?

It is of course possible that a pair of magic numbers, each designed to operate with its own particular bit mask, manipulate the bits in essentially the same way, and thus produce indicies that can reference the same lookup table. If one of the bitmasks is a multiple of the other for example, then the magic numbers could be the same multiple of each other and do essentially the same operation and giving identical results.

I think I'd better ask if this is making sense before saying any more.

[Gerd Isenberg]

Hi to Roberto Mizzoni.

So far my thoughts and conversation have concentrated on index generation, and your posting seems to be on storing the tables that are to be indexed.
I'm new to this and haven't got anything working yet, so I hope people go easy on me if I say something stupid, but here goes ....

https://chessprogramming.wikispaces.com ... +Bitboards

I believe the tables there are designed to be indexed by a six-bit occupancy-index in the 0..63 range.
If the data is compressed into tables, I assume that they are managing to achieve the compression for either or both of two reasons.

A. Unused bits in some data can be used to store something else.
B. Several distinct cases with the same result can be stored in the same place.

Before someone else can take advantage of the same compression, then, some preconditions will be imposed on them.
a. That the unused bits will be masked off and only the useful data extracted, ie the data must be used in a fairly similar way.
b. That the distinct cases can find the same memory location.

Let me discuss {B,b}, as I think that might be relevant to you.
It appears to me that the Kindergarten Bitboards are extracting an UNHASHED index for bit occupancy.
My current understanding is that some different lines on a chess board with the same scattering of pieces along them would generate the same occupancy index with Kindergarten Bitboards. These different lines will then result in the same memory locations in the table being accessed, via this same index.

Now with magic index generation, the line occupancy is HASHED into a fairly random sequence of bits.
So I think you CANNOT use the Kindergarten Bitboards with your magic index generation.

The trick is to share one 4KByte table by three line-directions by re-using the mask for a final intersection.

Unless you somehow have magic hashing that creates the same index for one diagonal and another, etc, I don't see how you can use Kindergrten Bitboards, because of (B). I think you can use (A), eg store 8 lines of data in a 64 bits.

People's thoughts are welcome, as I haven't got to grips with this yet.
One reason I am initially going with my approach is that I don't like magics and hashing for a couple of reasons.
1. It makes my data difficult to verify and code harder to debug.
2. Tables cannot be shared unless things hash to the same values.
3. I cannot populate the tables without first defining the hash function.
4. If I change the index generation method, I need to regenerate the tables.
5. Generating magic numbers seems complex too.

I could add that it seems ill defined quite what magic numbers are.
Sometimes they seem to be used for casting out zeros, and sometimes for performing a mathematical function.
Furthermore, sometimes a precise result is expected eg for bitscanning and sometimes a hashed result is satistactory.
Does "magic" really just mean any unintelligable muliply and shift that does something useful?

It is of course possible that a pair of magic numbers, each designed to operate with its own particular bit mask, manipulate the bits in essentially the same way, and thus produce indicies that can reference the same lookup table. If one of the bitmasks is a multiple of the other for example, then the magic numbers could be the same multiple of each other and do essentially the same operation and giving identical results.

I think I'd better ask if this is making sense before saying any more.

The six-bit occupancy-index in the 0..63 range is still a bijective 1:1 mapping of the inner six bits of a line in default none magic kindergarten BBs. Only the redundant outer squares are not used since they have no more squares behind, and are attacked or not regardless from their own occupancy.

Code: Select all

index = maskedSixRelevantBitsonOddLine * 0x0202020202020202 >> 58;


I would consider this as minimal perfect hashing of inner six bit occupancy, but perfect hashing of the up to 12 different attack sets we lookup. Many slots indexed by this six bit occupancy index contain same line attacks.

If performing some magic compression by looking for "random" factors by trial and error for a reduced 0..31 (or even 0..15) range

Code: Select all

index = maskedSixRelevantBitsonLine * magic[sq] >> 59;

we have necessarily a surjective index mapping. Different occupancies with same attack-set due to same nearest blocker result in the same index. Those "constructive" collisions are very desired for 12 bit magics with two lines involved. You are right that this surjective mapping makes it harder or impossible to share tables i.e. for all "odd" increment lines.

[Roberto Mizzoni]

Hi to Roberto Mizzoni.

Hi crystalclear.

One reason I am initially going with my approach is that I don't like magics and hashing for a couple of reasons.
1. It makes my data difficult to verify and code harder to debug.
2. Tables cannot be shared unless things hash to the same values.
3. I cannot populate the tables without first defining the hash function.
4. If I change the index generation method, I need to regenerate the tables.
5. Generating magic numbers seems complex too.

1. I didn't have any problems with that (I didn't need debugging once I generated the magic numbers and filled the tables though).
2. You can make things hash to the same value by waiting longer when searching for the magic numbers, and save some bits; you can also share squares.
3. true.
4. true. btw, for plain rook magics(2048 K) I tested the scheme (((n + magic1) ^ magic2) * magic2 >> shift) (and with | instead of ^) with good results. If I remember correctly the best shift was 55, giving a table size of 512K.
5. Here's a good explanation: rivalchess.com/magic-bitboards.