How many combinations to map all possible occupied?

[monk64]

I was thinking how efficient the code would be if, for each slider, lookup in a pregenerated hash the set of destination squares, given the current occupied squares. So if a bishop was on D4, I'd lookup the keys "Bishop", "D4", and the current occupied bitmap and retrieve a bitmap off all the possible destination squares.

However, 2^64 is waaaaay too big to store in memory (or even on disk ;-) But wouldn't it actually be smaller? There's a max of 32 pieces, not 64. I suppose you'd still need a 64-bit number, though...

I suppose this is infeasible for another few order of magnitudes of computer improvements.

Hmmm...is there a way to subdivide the board into 4x4 quadrants? 2^16 is quite doable...

[micron]

I was thinking how efficient the code would be if, for each slider, lookup in a pregenerated hash the set of destination squares, given the current occupied squares. So if a bishop was on D4, I'd lookup the keys "Bishop", "D4", and the current occupied bitmap and retrieve a bitmap off all the possible destination squares.

However, 2^64 is waaaaay too big to store in memory (or even on disk ;-) But wouldn't it actually be smaller?

The 'magic' method of attack generation
https://chessprogramming.wikispaces.com/Magic+Bitboards
does what you describe.
It first masks the occupancy to leave only bits that are relevant to attack-generation from the specified square. (The mask for bishop attacks is 4 diagonal rays with the edge bits off; the rook mask is similar but with orthogonal rays.) Masking reduces the number of bits from 64 to something like 10.

Unfortunately, those 10 (or whatever) relevant bits are scattered over a large fraction of the uint64 range.

That problem is solved by multiplying the masked occupancy by a 'magic' uint64, previously discovered by trial and error. The magic property is that multiplication 'compresses' or squashes the relevant bits to be consecutive. Then it is trivial to extract an int value as an index into your precomputed bishop (or rook) attacks db.

With the simplest implementation of magic attack generation, there's some redundancy in the precomputed dbs (especially the rook db). More complicated implementations allow the dbs to be smaller.

Robert P.