What constitutes a MAGIC multiplier?

[Steve Maughan]

It's Christmas so I have some time to play around with computer chess (yippee!). I've been trying to get my head around magic bitboards which seem, as the name says, quite simply magical. However, I'm having a little problem generating them. I've seen Tord's post where he suggests using sparse random numbers. This seems quite reasonable. However, when I set my routine spinning it certainly doesn't generate the magics in a reasonable time. I'm not sure I have the criteria right for when a magic is actually a magic.

So here's my question - does a magic (for a specific square) need to map each bit of the mask to one of the top 'n' bits? This is my understanding (but I could be wrong). In which case this code should test a mask and magic combination by cycling through the mask bits, multiplying each one by the magic and seeing if it adds one additional bit to the top n bits. Can anyone see a problem with my code or my logic?

Thanks,

Steve

Code: Select all

function TBoard.IsValidMagic(Mask, Magic: bitboard; bits: integer): boolean;
var
  a, c, d: bitboard;
  i: integer;
begin
  if BitCount((Mask * Magic) shr (64 - bits)) <> BitCount(Mask) then
  begin
    result := false;
  end
  else
  begin
    a := Mask;
    d := 0;
    i := 0;
    while a <> 0 do
    begin
      c := (a and (a - 1)) xor a;
      d := d or (c * Magic);

      if BitCount(d shr (64 - bits)) <> i + 1 then
      begin
        result := false;
        exit;
      end;

      inc(i);
      a := (a and (a - 1));
    end;
    result := true;
  end;
end;

[micron]

So here's my question - does a magic (for a specific square) need to map each bit of the mask to one of the top 'n' bits?

No. Consider a piece that is completely immobilised by its near neighbours. The only mask bits that matter are those for the neighbours. Other mask bits (further out on the four rays) are irrelevant.

Robert P.

[Steve Maughan]

Hi Robert,

Thanks for the reply.

I can see that the outer bits are irrelevant, however, if I'm going to do a simple lookup e.g.

Code: Select all

Lookup[(Mask * Magic) shr (64 - bits)]

the outer bits will still be part of the lookup. So for a rook on A1 there are 12 bits in the mask, so the lookup table must be 2^12 (i.e. 4096) even though the relevant bit are 6 on the column and 6 on the row, to give a mere 36 different relevant occupancy combinations.

I must be missing something.

Best regards,

Steve

[hgm]

So if people want to use smaller lookup tables for some squares, they use a smaller number of bits, and a magic multiplier that maps as litte of irrelevant bits to the used bits a as possible.

[Gerd Isenberg]

Hi Robert,

Thanks for the reply.

I can see that the outer bits are irrelevant, however, if I'm going to do a simple lookup e.g.

Code: Select all

Lookup[(Mask * Magic) shr (64 - bits)]

the outer bits will still be part of the lookup. So for a rook on A1 there are 12 bits in the mask, so the lookup table must be 2^12 (i.e. 4096) even though the relevant bit are 6 on the column and 6 on the row, to give a mere 36 different relevant occupancy combinations.

I must be missing something.

Best regards,

Steve

Sure, it would be fine if you perfectly hash all up to 12 occupied bits to distinct 12 bit values, which unfortunately is not always possible with one mul/shift for all squares. But it is about to perfectly hash attack sets and not necessarily occupancies. Therefor one can accept constructive collisions, where different redundant occupancies "behind" the first blocker map the same attack set entry. Those collisions make the mapping of N scattered occupied bits to N-bit indices always possible, for some squares even to N-1 bit indices, to half the table size for that square, see Best Magics so far.

Btw., it seems fixed shift fancy magics are quite successful nowadays ...

Cheers,
Gerd

[Steve Maughan]

Gerd & H.G.,

Many thanks. I see. I thought I must be doing something wrong. So the next question is - how do you test to ensure the collision don't matter? My first thought would be to cycle through all (in the case of a rook) 4096 possible combinations and test to ensure any collision are irrelevant. That sound possible but not trivial.

Thanks again,

Steve

[hgm]

That is indeed howI did it (but I involved myself with this only for a very short time, as none of my engines is bitboard, so I am far from an expert). Make a hash table of 4096 elements, cycle through all combinatons of occupation, derive the tabe index by multiplication with the tentative magic, and then store a number there derived from the 12 occupied bits with the insignificant bits masked off. And then complain if the entry was already occupied by another number.

[Steve Maughan]

Thanks H.G. - crystal!

[Gerd Isenberg]

Gerd & H.G.,

Many thanks. I see. I thought I must be doing something wrong. So the next question is - how do you test to ensure the collision don't matter? My first thought would be to cycle through all (in the case of a rook) 4096 possible combinations and test to ensure any collision are irrelevant. That sound possible but not trivial.

Thanks again,

Steve

Here is my proposal in Pascal pseudo code. Same as HG's, except I store the attack set to test for collisions.

Code: Select all

function TBoard.IsValidMagic(OccupancySuperSet, Magic: bitboard; square, bits: integer): boolean; 
var
  testAttacks : Array [0..4095] of bitboard; { init to zero }
  attacks, occupancy: bitboard;
  index: integer;
  isValid : boolean;
begin
  occupancy := 0;
  repeat begin
     attacks   := calculateAttacksInAClassicWay ( square, occupancy );
     index     := (occupancy * Magic) SHR (64-bits);
     if ( testAttacks[index] = 0 ) testAttacks[index] := attacks;
     isValid   := testAttacks[index] = attacks;
     occupancy := (occupancy - OccupancySuperSet) AND OccupancySuperSet; { next occupancy }
  end until (occupancy = 0 OR NOT isValid);
  IsValidMagic := isValid;
end;

[Volker Annuss]

I think H.G. and Gerd already answered your original question. Here some more tricks for getting good magic numbers.

I've seen Tord's post where he suggests using sparse random numbers.

Looking for sparse random numbers gives good magic numbers for all squares.

When you want to optimize hard and squeeze out some more entries out of your lookup table or you look for magics with some other interesting properties, some other types of magics may help:

For some squares it is better to look for magics that have most bits set. {NOT m is sparse}

For some squares it is better to look for magics where most bits have the same value as their neighbours. {m XOR (m SHR 1) is sparse}

When you have found two magics for the same square, that are different in only a few bits, take the bits they have in common and test all numbers you get by varying the different bits. But don't waste time on the highest and lowest bits, that don't contribute to the position in the lookup table.