Fancy magic bitboards question

[Eric VanderHelm]

I'm trying to understand fancy magic bitboards by reading the wiki article here: http://chessprogramming.wikispaces.com/ ... ards#Fancy and the crafty source code.

Code: Select all

uint64_t *magic_bishop_indices[64] = {
  magic_bishop_table + 4992, magic_bishop_table + 2624,
  magic_bishop_table + 256, magic_bishop_table + 896,
  magic_bishop_table + 1280, magic_bishop_table + 1664.... etc

How were these offsets determined? Obviously certain squares require more space in the table because of the different index sizes, but couldn't the table entries be stored sequentially by the ordering of the squares? What's the motivation for this? My only guess would be to reduce cache misses somehow, but I really can't tell. Thanks in advance!

[bob]

I'm trying to understand fancy magic bitboards by reading the wiki article here: http://chessprogramming.wikispaces.com/ ... ards#Fancy and the crafty source code.

Code: Select all

uint64_t *magic_bishop_indices[64] = {
  magic_bishop_table + 4992, magic_bishop_table + 2624,
  magic_bishop_table + 256, magic_bishop_table + 896,
  magic_bishop_table + 1280, magic_bishop_table + 1664.... etc

How were these offsets determined? Obviously certain squares require more space in the table because of the different index sizes, but couldn't the table entries be stored sequentially by the ordering of the squares? What's the motivation for this? My only guess would be to reduce cache misses somehow, but I really can't tell. Thanks in advance!

You are thinking about it backward. The index is what it needs to be to index to the set of valid attack bitmaps for that particular square and occupancy.

[AlvaroBegue]

I don't understand that answer. In my own code, I store the attack bitmaps sequentially.

Code: Select all

  struct MagicInfo {
    u64 mask;
    u64 magic;
    u64 *table;
    int shift;
  };

  u64 attack_table[107648];

  MagicInfo bishop_attack_table[64] = {
    {0x0040201008040200ull, 0x0210f00081004204ull, attack_table + 0, 58},
    {0x0000402010080400ull, 0x00a0043102002608ull, attack_table + 64, 59},
    {0x0000004020100a00ull, 0xa850008081050588ull, attack_table + 96, 59},
    {0x0000000040221400ull, 0x0004040088344400ull, attack_table + 128, 59},
    {0x0000000002442800ull, 0x88020a1000071080ull, attack_table + 160, 59},
    {0x0000000204085000ull, 0x2802901008900400ull, attack_table + 192, 59},
    {0x0000020408102000ull, 0xf084011150900104ull, attack_table + 224, 59},
    {0x0002040810204000ull, 0x4412010381842004ull, attack_table + 256, 58},
    {0x0020100804020000ull, 0x0002692094042040ull, attack_table + 320, 59},
    // ...

[kbhearn]

one possible answer is that ends of some tables may constructively overlap with beginnings of other tables so an effort may have been made to place such convenient matches next to each other.

i.e. your lookup for one square that maps to a 7-bit attack table may not care about all 128 entries of said table, some might just not be reachable with any blocker configuration for that square. so you can try to start another table early in a way that as many 'don't care' squares as possible are actually given a meaningful value for another square's table. Since some squares matchup better than others, and since you're using a base index anyways there's no cost other than confusion to rearranging them in an order to maximise as much constructive overlap as possible.

For your first magic implementation using sequential storage makes perfect sense before adding more hardcoded constants to bugcheck by arranging the tables to overlap in a nonsequential order :)