Magic bitboards for position eval...?

[monk64]

I'm trying to grok magic bitboards.

I understand the fundamental goal, which is to take a sparsely-populated 64-bit number and, though multiplication by a magic factor, "compress it" so that it can be used as an index lookup to a precomputed array. In other words, if only a few bits of a 64-bit number are turned on, it should be possible to represent it using something less than 2^64.

Am I correct that magic bitboards really don't work unless the bits are "in a line"? i.e., they work for sliding piece attacks, but would not if you had a few squares in a bitboard lit but they were are scattered all over the board?

For example, let's say I want to add a penalty/bonus to a score based on the position of knights on the board (center = bonus, rim = penalty, etc.) One way would be to have a bonus_array[square_num], then take the bitboard that represents a side's knights, bit scan forward through it, and lookup each square in bonus_array[], etc.

I'm wondering if there is an alternative way of pre-generating all the possible positions, then taking the knight bitboard, applying magic, and looking it up in the array, etc.

This isn't practical for all theoretical cases, as it is possible there could be 10 knights on one side. Just considering 64 C 9 is already 110 billion+ combinations. However, the vast, vast majority of the time, there will be 0 - 2 knights. That's 64 C 2 + 64 C 1 + 64 C 0 = 3906 + 64 + 1 = 3970 (don't trust my math, though

Of course, those 3970 combinations will be spread all over the 64-bit space. So is it possible to magic-fy them down a reasonable number to lookup in an array?

The same thing could be done for the King's position, since there's only one, though I'm not sure if bitmap + magic, then array lookup is faster than one bitscan, then array lookup.

[Gerd Isenberg]

Yep, King- and knight target sets allow minimal perfect hashing e.g. with magic factors of four one-bits set.

[cms271828]

I don't see why you need magic numbers for non-sliding pieces.

For a king in middle of board, you can just have an array size 64, each element is the bitboard of squares it can move to. Similarly for knight.

Or am I missing something?

[monk64]

Yes, that certainly works. I guess in my mind, translating a bitboard to an integer via a bit scan forward is an "expensive" operation.

Which of these is typically more expensive?

(1) bit scan forward the bitmap, lookup the resultant integer in an array

(2) take the bitmap, apply magic, and lookup the index in an array

?

[kongsian]

I don't see why you need magic numbers for non-sliding pieces.

For a king in middle of board, you can just have an array size 64, each element is the bitboard of squares it can move to. Similarly for knight.

Or am I missing something?

For knights and king, what you get is not a bitmap of moves, but some sort of movelist which is stored in 64 bit. I use 6 bits to store the from & to squares.

E.g. for a king on A1 which can only move to B1,B2 my movelist would be

.......<a1><b2><b1>

which is total 18 bits.

So instead of doing bit scanning, you use bit shifting to extract the to squares.

Rgds.
Kong Sian