Clarification on magic bitboards

[daz12]

Hi

I’m new to chess programming. I am struggling with some aspects of magic bitboards despite researching them and am hoping someone can give some quick answers.

I know the process:

OccupancyBB=AllpiecesBB & RookMaskBB[sq]

OccupancyBB*magic no[sq] >> 64 – bits = index

So does a square only ever 1 magic number associated with it? Does the magic number have to be different for every square? How do you know if it’s magic i.e. suitable?

What is bits – is it the number of squares, the Rook in this example, can potentially attack from square it is located at minus edge squares? Do you have to account for every permutation of this for each square or is one bitboard mask enough?

The OccupancyBB is an unsigned 64 bit and multiplying by magic increases its size. What is the shift to the right trying to achieve? A basic analogy would be helpful.

Can someone explain in a plain english what the formula does and idea behind it? From my basic knowledge of hash tables the aim seems to be to generate a unique index to relate to this input algorithm. Also I’ve read you have to account for RookMasks (or BishopMasks) permutations on each square and put it through this algorithm?

Thanks

Daz

[User923005]

Magic bitboards are nothing more than a perfect hash applied to chess boards.
A perfect hash is a hash where every item in the domain maps to a single element in the range.
There are programs that will search for excellent perfect hash functions for the chessmen that you want to map.
The computer chess club programmer's forum is where I would go to ask questions.
Have you seen the chess programming wiki?
https://chessprogramming.wikispaces.com/

[daz12]

Hi User923005 thanks for the clarification. I thought we could ask questions here too!

If possible could someone give me an example of 'occupancy variations' you have to store in your 'magic' database? Say using Rook on A1 as an example?

Thanks

[User923005]

Maybe something here can help you:
https://chessprogramming.wikispaces.com/Magic+Bitboards
http://www.rivalchess.com/magic-bitboards/
http://www.dcs.bbk.ac.uk/~mark/download ... _final.pdf

[hyatt]

Hi User923005 thanks for the clarification. I thought we could ask questions here too!

If possible could someone give me an example of 'occupancy variations' you have to store in your 'magic' database? Say using Rook on A1 as an example?

Thanks

Simple. With a rook on A1, you have 7 squares (bits) on the a-file, and 7 squares/bits on the first rank. A total of 2^14 possible combinations. For example, all 14 squares could be empty with just the rook on A1 (all 14 of those bits would be zero). Or all 14 squares could be occupied by friendly/enemy pieces and pawns, giving 14 1 bits. Or anything in between, giving the 2^14 choices I mentioned. Which means that a rook on a1 has 16384 possible sets of valid moves, depending on which bits are zero and which are one (for the all zero occupancy example, every square from a2-a8 and from a1-h1 would be set to 1 since the rook attacks all of those squares if everything is empty). For the all squares occupied example, the rook attacks from a1 would be 12 bits of zeros with the two adjacent squares set to one since a rook attacks those squares whether they are occupied or not.

Bishops are a bit smaller since a bishop attacks only 13 squares at best, and on some squares only attacks 7 (say a bishop at a1). So the bishop tables are smaller. The queen would be huge, but we do it by doing the same attack generation for a rook and then a bishop and ORing them together.

[daz12]

Thanks guys!