What is the point of magic hashing over simply using masked occupancy as index ?

[Earil]

Hello everyone,

I am new to chess programming, and have started developping my engine (in python) a month ago. My current goal is to have a working version by mid-july, and to use the rest of the summer to improve it.
So far, I'm able to efficiently generate moves using the bitboard approach and I implemented magic bitboards for sliding pieces.

Reading the documentation available on the chessprogramming wiki, and from my own experimentation, I have noticed that hashed blockers set (through the multiply then right shift method) are, in the best case, one power of two shorter than their corresponding blocker set (for example, for a bishop on a2, 2 ^ 5 possible blocker combinations exist, and the best magic found allows to compress this set to a 2 ^ 4 long hashmap). For many squares, however, no magic has been found that allows the creation of a significant amount of constructive collisions (at least from what I understood).

Considering that with modern computers, the size of the blocker set (4096 or 2 ^ 12 at worst for rooks on corners) is not at all a limiting factor when it comes to storing them in memory, and that with have efficient data-structures allowing O(1) access and lookup, I wonder what the point is in using magic hashing over simply mapping all blocker sets to their corresponding attack set and directly using this map instead of going through a hash.

I would be very grateful if someone with more understanding of the topic could clarify this to me, and I apologize if the question has a simple answer than I wasn't able to find by myself.

[hgm]

The problem is that the bits in the blocker sets are not contiguous. So you cannot use those to index a compact table, even if you would shift out all lowest non-members. So you somehow have to compactify the bits. The multiply with the magic does that.

[Earil]

Thank you for answering my question !

I did notice the compactness of the hash-table indeed. Why is it important to have a compact table though ? Does it improve access speed at all ?

[Sopel]

Thank you for answering my question !

I did notice the compactness of the hash-table indeed. Why is it important to have a compact table though ? Does it improve access speed at all ?

Without compaction you'd have 1 bits scattered all around the 64 bit number, requiring about 18,000,000,000 GB of memory

[j.t.]

If I understand correctly, the method that you are comparing to magic hashing is pretty similar to what kindergarten bitboards do. I believe (I am not sure) that the reason why many people prefer magic bitboards is that the generation of the hash is faster than the stuff you need to do to shift the relevant occupancy bits to the lowest bits. Though I personally think that it doesn't make a huge difference. The stuff that is most important for performance is mostly how your evaluation looks like, and there it doesn't matter much if you use kindergarten or magic bitboards, as long as you use bitboards (though all what I am saying is mostly just speculation/intuition).

[Earil]

Thank you for your answers, I think I understand where my confusion came from. The fact I'm using Python because I'm more familiar with the language, instead of a low-level language like C or C++, means that I'm able to use the dictionary built-in data structure for which the "uncompactness" of the blocker set is irrelevant (Python does its own hashing of dictionary keys, so their size in bits doesn't matter). Of course, this comes at a performance cost, and when I'll switch to a C++ implementation later on, the fact that I'm able to properly magic hash my blockers will be important.

Thanks again, I understand the concept properly now !

[hgm]

To use the language's dictionary for this just amounts to hiding the hash calculation from view; because of the non-compactness of keys it will have to apply some hash function to it to do the compactification, and you can only hope it is as simple as a multiply + shift. In addition it will probably assign a generous size to the table, and even then will have many collisions between entries that need to be different, requiring re-hashing, and lookups with multiple tries.

The idea of magic bitboards, and bitboard in general, is to make it fast. With the kind of overhead the dictionary lookup takes, you might as well use mailbox, and just loop over all destinations.

[Gerd Isenberg]

If I understand correctly, the method that you are comparing to magic hashing is pretty similar to what kindergarten bitboards do. I believe (I am not sure) that the reason why many people prefer magic bitboards is that the generation of the hash is faster than the stuff you need to do to shift the relevant occupancy bits to the lowest bits. Though I personally think that it doesn't make a huge difference. The stuff that is most important for performance is mostly how your evaluation looks like, and there it doesn't matter much if you use kindergarten or magic bitboards, as long as you use bitboards (though all what I am saying is mostly just speculation/intuition).

The main difference of kindergarten versus magic bitboards is that kindergarten bitboards only consider occupancy of one line to get the attacks on that line - instead of occupancy and attacks for both lines of a bishop or rook with magics simultaneously. So with kindergarten bbs one need to call two attack getters per bishop/rook to "or" them, instead of one call for magics, but with much larger tables. Instead of random trial and error magic factors, kindergarten factors may use file or diagonal pattern factors - but there is as well the option to apply magic compression using line-wise attacks, resulting only in 4 or 5 bit occupancy index per line.

The topic of the op was likely addressed by Hashing Dictionaries as proposed by Sam Tannous, using the built in hash arrays of Python:

• Sam Tannous (2007). Avoiding Rotated Bitboards with Direct Lookup. ICGA Journal, Vol. 30, No. 2, arXiv:0704.3773

[pedrojdm2021]

Thank you for your answers, I think I understand where my confusion came from. The fact I'm using Python because I'm more familiar with the language, instead of a low-level language like C or C++, means that I'm able to use the dictionary built-in data structure for which the "uncompactness" of the blocker set is irrelevant (Python does its own hashing of dictionary keys, so their size in bits doesn't matter). Of course, this comes at a performance cost, and when I'll switch to a C++ implementation later on, the fact that I'm able to properly magic hash my blockers will be important.

Thanks again, I understand the concept properly now !

I don't want to be that "guy" but please consider using C / C++. For chess programming you don't really need to dive very deep into the language used, we actually use some basic stuff from the language selected. Phyton is very slow compared even to C# if you switch to a compiled language you will thank me later

[j.t.]

Or use Nim, which is a very fast compiled language with similar syntax as Python and more syntactic sugar.